# Number of orders of $k$-sums of $n$-numbers

Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$).

If the elements of $S$ are real numbers then to each $k$-element subset we can associate its sum. If these sums $\binom{n}{k}$ numbers are all distinct, they induce an order on $K$.

What is number of orders on $K$ we can obtain this way?

It is clear that this is not all $\binom{n}{k}!$ orders are possible. For example, because the smallest $k+1$ elements defined by the order of numbers of $S$ and $n! < \binom {\binom{n}{k}}{k}$ for sufficient large $k$. There are many other constrains on the orders of $K$.

For $n=4$, and $k=2$. $S=\{a, b, c, d\}$ and $K=\{(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)\}$. If $\{a, b, c, d\}=\{0.2, 0.4, 0.8, 0.3\}$, then the correspondent sums equals $\{0.6,1.0,0.5,1.2,0.7,1.1\}$, and we have the following order on $K$: $\{(a,d),(a,b),(b,d),(a,c),(c,d),(b,c)\}$.

Note that we can not get the order $\{(a,b),(a,c),(c,d),(b,d),(a,d),(b,c)\}$ because from the order of the first two elements we get that $b<c$, and from the second two element we get $b>c$.

You are asking for the number of regions of the real hyperplane arrangement with hyperplanes $x_{i_1}+\cdots+ x_{i_k}= x_{j_1}+\cdots+x_{j_k}$. For $n=4$ and $k=2$ the number of regions can be computed to be 48. The computation for $n=5$ and $k=2$ should be tractable, though beyond my computational skills. Based on what is known about counting the number of regions of a real arrangement, I would be very surprised if someone could give a nice answer to your question for any $n$ and $k$.
• Thank you! Can you estimate this number from below? Is it $O(|K|^{2(n-1)})$? – Arseniy Akopyan Nov 8 '14 at 11:14
• An arrangement in $\mathbb{R}^n$ with $m$ hyperplanes has at most $1+m+{m\choose 2}+\cdots+{m\choose n}$ regions. This gives a bound not far from what you want. More careful reasoning (for instance, using the fact that the arrangement is central) should give a better bound. For background on hyperplane arrangements, see math.mit.edu/~rstan/arrangements/arr.html. – Richard Stanley Nov 8 '14 at 18:12
• @MaxAlekseyev: Actually, the fourth term of A231085 is 2. This is because A231085 has the additional condition $x_1<x_2<\cdots<x_n$. To get from the $n$th term of A231085 to the sequence I am considering, multiply by $n!$. – Richard Stanley Nov 16 '14 at 1:10