Number of unique sortings of subset-sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:14:21Z http://mathoverflow.net/feeds/question/39386 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39386/number-of-unique-sortings-of-subset-sums Number of unique sortings of subset-sums Craig Feinstein 2010-09-20T13:39:56Z 2010-09-21T02:27:02Z <p>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$?</p> <p>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: <code>$$\left\{ \begin{matrix} 0&lt;a_1&lt;a_2&lt;a_1+a_2,\\ 0&lt;a_2&lt;a_1&lt;a_1+a_2,\\ a_2&lt;0&lt;a_1+a_2&lt;a_1, \\ a_1&lt;0&lt;a_1+a_2&lt;a_2, \\ a_2&lt;a_1+a_2&lt;0&lt;a_1, \\ a_1&lt;a_1+a_2&lt;0&lt;a_2, \\ a_1+a_2&lt;a_1&lt;a_2&lt;0, \\ a_1+a_2&lt;a_2&lt;a_1&lt;0 \end{matrix} \right\}.$$</code></p> http://mathoverflow.net/questions/39386/number-of-unique-sortings-of-subset-sums/39459#39459 Answer by Tracy Hall for Number of unique sortings of subset-sums Tracy Hall 2010-09-21T02:27:02Z 2010-09-21T02:27:02Z <p>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$.</p> <p>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 &lt; a_2 &lt; \cdots &lt; a_n$ reduces the total by a further factor of $n!$, which gives a known sequence:</p> <p><a href="http://www.research.att.com/~njas/sequences/A009997" rel="nofollow">http://www.research.att.com/~njas/sequences/A009997</a></p> <p><a href="http://arxiv.org/abs/math.CO/9809134" rel="nofollow">http://arxiv.org/abs/math.CO/9809134</a></p> <p>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.</p> <p>Including the $2^nn!$ symmetries gives these values:</p> <ol> <li> $2$ </li> <li> $8$ </li> <li> $96$ </li> <li> $5$ $376$ </li> <li> $1$ $981$ $440$ </li> <li> $5$ $722$ $536$ $960$ </li> <li> $138$ $430$ $238$ $607$ $360$ </li> </ol>