Welcome to MathOverflow

Question

7

4

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

edited Sep 20 2010 at 13:47

David Speyer
55.1k●3●102●236

asked Sep 20 2010 at 13:39

Craig Feinstein
715●2●14

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 2010 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 2010 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 2010 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 2010 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 2010 at 15:25

show 4 more comments

Tracy Hall · Accepted Answer · 2010-09-21 02:27:02Z UTC

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.research.att.com/~njas/sequences/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:

$2$
$8$
$96$
$5$ $376$
$1$ $981$ $440$
$5$ $722$ $536$ $960$
$138$ $430$ $238$ $607$ $360$

Number of unique sortings of subset-sums

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.