# Number of unique sortings of subset-sums

Take the set $A_n=\{a_1,...,a_n\}$. Let $S_n$ be the set of subset-sums of $A_n$. (The subset-sum of the empty set is assumed to be zero.) Assume that there are $2^n$ unique members of $S_n$. How many possible sortings are there of set $S_n$?

For instance, if $n=2$, we have $S_2=\{0,a_1,a_2,a_1+a_2\}$. The number of possible sortings of $S_2$ is 8: $$\left\{ \begin{matrix} 0<a_1<a_2<a_1+a_2,\\ 0<a_2<a_1<a_1+a_2,\\ a_2<0<a_1+a_2<a_1, \\ a_1<0<a_1+a_2<a_2, \\ a_2<a_1+a_2<0<a_1, \\ a_1<a_1+a_2<0<a_2, \\ a_1+a_2<a_1<a_2<0, \\ a_1+a_2<a_2<a_1<0 \end{matrix} \right\}.$$

-
I tried to put all 8 sortings of S_2, but it stopped me. Here they are: {0<a_1<a_2<a_1+a_2, 0<a_2<a_1<a_1+a_2, a_2<0<a_1+a_2<a_1, a_1<0<a_1+a_2<a_2, a_2<a_1+a_2<0<a_1, a_1<a_1+a_2<0<a_2, a_1+a_2<a_1<a_2<0, a_1+a_2<a_2<a_1<0. – Craig Feinstein Sep 20 '10 at 13:45
I fixed your LaTeX. You had two problems: Some of your backslashes were being eaten by the Markdown software (solution: enclose the whole expression in backticks) and you were trying to fit a lot of material in a one line environment. – David Speyer Sep 20 '10 at 13:48
Nice question. One way to phrase it is to ask how many regions $\mathbb{R}^n$ is divided into by the hyperplanes of the form $\sum_{i \in I} a_i = \sum_{j \not \in I} a_j$. I feel like this example should be in some survey on combinatorics of hyperplane arrangements, but I don't know which one. – David Speyer Sep 20 '10 at 13:53
One simplifying observation: If you make the additional assumption that the $a_i$ are all positive, it reduces the number of sortings by a factor of exactly $2^n$. (Replacing any one number by its negative gives the same ordering under complementation with respect to that one index.) – Tracy Hall Sep 20 '10 at 14:24
@David Speyer: Don't forget hyperplanes like $a_1=a_3$. (For uniqueness, either the sets or their complements can be taken to be disjoint, but not necessarily both.) – Tracy Hall Sep 20 '10 at 15:25

As David Speyer points out in a comment, this is equivalent to the number of regions resulting when $\mathbb{R}^n$ is divided by hyperplanes of the form $\sum_{i \in I}a_i = \sum_{i \in J}a_i$ for all disjoint pairs of subsets $I,J \subseteq [n]$. Dual to this description, it is the number of ways that the $3^n-1$ nonzero vectors in $\{-1,0,1\}^n$ can be divided into "positive" and "negative" by a hyperplane (in general position) passing through the origin, which makes it easy to see that the answer is indeed $8$ for $n=2$.

As I mentioned in a comment, the total is always $2^n$ times what you get when making the assumption $a_i > 0$ for all $i$. There is another symmetry that can also be exploited: making the assumption $a_1 < a_2 < \cdots < a_n$ reduces the total by a further factor of $n!$, which gives a known sequence:

http://www.oeis.org/A009997

http://arxiv.org/abs/math.CO/9809134

Various key words are "coherent boolean term order", "coherent generalized term order", and "additive antisymmetric comparative probability order". It doesn't look like anyone knows the values beyond $n=7$. You'll want to check Maclagan's reference to Fine and Gill 1976 to see if they give any asymptotics.

Including the $2^nn!$ symmetries gives these values:

1. $2$
2. $8$
3. $96$
4. $5$ $376$
5. $1$ $981$ $440$
6. $5$ $722$ $536$ $960$
7. $138$ $430$ $238$ $607$ $360$
-