Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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\}.$$

share|improve this question
    
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
1  
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
2  
@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
show 4 more comments

1 Answer

up vote 9 down vote accepted

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$
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.