7
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Craig Feinstein
    Commented Sep 20, 2010 at 13:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Sep 20, 2010 at 13:53
  • $\begingroup$ I am guessing that the answer is $2^{\Theta(n^2/2)}$, because of a theorem by Dobkin and Lipton. $\endgroup$
    – Craig Feinstein
    Commented Sep 20, 2010 at 14:24
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Tracy Hall
    Commented Sep 20, 2010 at 14:24
  • 3
    $\begingroup$ @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.) $\endgroup$
    – Tracy Hall
    Commented Sep 20, 2010 at 15:25

1 Answer 1

Reset to default
9
$\begingroup$

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$
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .