It is well known that $$\sum_{k \textrm{ odd}} \binom{n}{k} = \sum_{k \textrm{ even}} \binom{n}{k} = 2^{n-1}.$$

One way of thinking about this is by "toggling" a specific element, e.g. $1.$ What I mean is that if you have an subset with an even number of elements and it contains $1,$ remove it. If it doesn't contain $1,$ add it in. This is a bijection between subsets of even and odd size.

I'm wondering for what (if any) $n$ is it possible to partition $\{0, 1, \ldots, n\}$ into four subsets $S_1\sqcup S_2 \sqcup S_3 \sqcup S_4$ such that $$\sum_{k\in S_1} \binom{n}{k} = \sum_{k\in S_2} \binom{n}{k} = \ldots = 2^{n-2}.$$

I would also be interested in the question for specific $n,$ e.g. $2^{m}$ or $2^{m}-1$ for some $m.$ Something to note is that you won't really be able to do this by hand since the middle terms themselves are close to $2^{n-2}$ for $n \le 16.$

When $n$ is large there is more room to play around since $\binom{2n}{n} \approx \frac{2^{2n}}{\sqrt{\pi n}}.$

  • $\begingroup$ This is an interesting question. It is a particular type of bisection of the binomial coefficients. The numerical evidence is not enough but, one may take a look at the last table in arxiv.org/pdf/1610.02063.pdf and get an idea that such an object is very unlikely to exist. $\endgroup$ – Eugen Ionascu Oct 5 '17 at 13:16

Your Answer

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

Browse other questions tagged or ask your own question.