Combinatorial proof that if $d$ is odd then $2^m$ divides $\binom{2^m}{d}$

Question

Unless I made a mistake, I could prove using the fomulas for $2$-adic valuations of factorials that $2^m$ divides $\binom{2^m}{d}$ when $d$ is odd, which is something that turns up in some article I'm writing about quadratic forms.

I assume there is a natural combinatorial explanation for that, and an interpretation of the integer $\frac{1}{2^m}\binom{2^m}{d}$, could anyone point me in the right direction?

When $d=3$, the sequence in terms of $m$ (which is just $\frac{(2^m-1)(2^{m-1}-1)}{3}$) is the OEIS sequence https://oeis.org/A006095, given by the gaussian binomial coefficient $\binom{m}{2}_q$ evaluated at $q=2$ . When $d=5$, this is no longer an OEIS sequence (the first non-zero terms are $7$, $273$, $6293$, $119133$).

Answer 1

This is not purely combinatorial but hopefully can give pointers

Set Up

Out of $2^{m}$ people, choose $d$. Out of these chosen people choose one representative.

First method

Select $d$ people out of $2^{m}$ then select $1$ out of $d$ people. The number of possibilities is given below

$$ d\binom{2^{m}}{d} $$

Second method

Select $1$ representative out of $2^{m}$ people then select the remaining $d-1$ out of remaining $2^{m}-1$. The number of possibilities is given below

$$ 2^{m}\binom{2^{m}-1}{d-1} $$

Put It Together

Counting the same objects, the two must be equal

$$ d\binom{2^{m}}{d} = 2^{m}\binom{2^{m}-1}{d-1} $$

RHS is divisible by $2^{m}$ and so LHS must be too. $d$ is odd, so …

Answer 2

I have found an answer that I find satisfying, but I'll wait to see if someone has a more "classically combinatorial" solution.

Let $G$ be a finite $2$-torsion group of order $2^m$. You can think of $G=(\mathbb{Z}/2\mathbb{Z})^m$, or $G=\mathcal{P}(X)$ endowed the symmetric difference, with $|X|=m$, for a more combinatorial flavour.

Let $Y\subset \mathcal{P}(G)$ be the set of subsets of cardinality $d$. Then there is a canonical action of $G$ on $Y$ by $g\cdot \{g_1,\dots,g_d\}=\{gg_1,\dots,gg_d\}$. This is valid for any group $G$ and any integer $d$.

Statement: when $G$ is as above and $d$ is odd, this is a free action. This means that if $g\cdot A=A$ for any $g\in G$ and $A\in Y$, then $g=1$ is the neutral element. In particular, all the orbits carry a simply transitive action, and therefore are all of cardinality $|G|$, so the set of orbits has cardinality $|Y/G|=\frac{1}{2^m}\binom{2^m}{d}$.

Therefore (taking $G=\mathcal{P}(X)$): $\frac{1}{2^m}\binom{2^m}{d}$ is the number of ways of choosing $d$ subsets of $X$ (with $|X|=m$), identifying two such choices if one can pass from one to the other by applying the symmetric difference with a single subset of $X$.

I feel like this is combinatorial enough for my taste, but feel free to come up with something better!

---

Proof of the statement: If $g\cdot A=A$, then $g$ acts as a permutation on $A$, but since $g^2=1$, this permutation has order $2$, and since $|A|=d$ is odd it must have a fixed point. This means that $gh=h$ for some $h\in A$, and thus $g=1$.

Answer 3

Alternative approach:

Every member of Pascal's Triangle is an integer.

So, $~\displaystyle A = \binom{2^m - 1}{d}~$ is an integer.

Comparing this with $~\displaystyle B = \binom{2^m}{d},~$ which must also be an integer, you see that

$$B = A \times C ~: C = \frac{2^m}{2^m - d}.$$

Since the denominator of $~C~$ is odd, and $~A \times C~$ is an integer, you must have that $~2^m~$ divides $~A \times C.$

Another way of saying the same thing is that $~A \times C~$ is an integer that must have $~2^\alpha~$ in its prime factorization, where $~\alpha~$ must be $~\geq m.$