12
$\begingroup$

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

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you! Can you estimate this number from below? Is it $O(|K|^{2(n-1)})$? $\endgroup$
    – Arseniy Akopyan
    Nov 8, 2014 at 11:14
  • 2
    $\begingroup$ 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. $\endgroup$
    – Richard Stanley
    Nov 8, 2014 at 18:12
  • $\begingroup$ 48 does not match the 4-th term (equal 12) of oeis.org/A231085 -- any thought on that? $\endgroup$
    – Max Alekseyev
    Nov 9, 2014 at 13:58
  • 1
    $\begingroup$ @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!$. $\endgroup$
    – Richard Stanley
    Nov 16, 2014 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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