Problem 4

Prove that for every positive integer

t

there is a unique permutation

a_0,a_1,\ldots,a_{t-1}

0,1,\ldots,t-1

such that, for every

0\le i\le t-1

, the binomial coefficient

\binom{t+i}{2a_i}

is odd and

2a_i\neq t+i

Step 1 of 6: Kummer's theorem via bit-position sets

Previous step Next step

\binom{t+i}{2a_i}\text{ odd}\iff S(2a_i)\subseteq S(t+i)

Detailed analysis

For a non-negative integer $x$ , let $S(x)$ be the set of positions of the digit $1$ in the binary expansion of $x$ . Kummer's theorem says $\binom{n}{k}$ is odd exactly when adding $k$ and $n-k$ in binary produces no carries, equivalently $S(k)\subseteq S(n)$ . Since $2a_i<t+i$ , the condition $2a_i\neq t+i$ combined with oddness of $\binom{t+i}{2a_i}$ means $S(2a_i)$ is a proper subset of $S(t+i)$ .