Why does $(128)!$ equal the product of these binomial coefficients $128! = \binom{128}{64}\binom{64}{32}^2 \dots \binom21^{64}$?

For fun, we do it using a combinatorial argument. Take $128$ different objects. We show that the right-hand side counts the permutations of these objects.

Imagine doing the permutation as follows. First decide who will be in the first half (and therefore who will be in the second half). This can be done in $\binom{128}{64}$ ways. Now decide who among the first half will be in the first quarter, and who among the second half will be in the third quarter. This can be done in $\binom{64}{32}^2$ ways.

Now decide who among the first quarter will be in the first eighth, who among the second quarter will be in the third eighth, who among the third quarter will be in the fifth eighth, who among the fourth quarter will be in the seventh eighth. This can be done in $\binom{32}{16}^4$ ways.

Continue.


The question is straightforward. We have the right hand side equal to $$\frac{128!}{64!^2}\frac{64!^2}{32!^4}\frac{32!^4}{16!^8}\frac{16!^8}{8!^{16}}\frac{8!^{16}}{4!^{32}}\frac{4!^{32}}{2!^{64}}\frac{2!^{64}}{1}=128!$$


It is simple algebraicly. If we plug in the standard formula $\binom{n}{r} = \frac{n!}{r! (n-r)!}$, then we have \begin{align*} &\binom{128}{64} \binom{64}{32}^2 \binom{32}{16}^4 \binom{16}{8}^8 \binom{8}{4}^{16} \binom{4}{2}^{32} \binom{2}{1}^{64} \\[8pt] = {} & \left(\frac{128!}{64!^2}\right) \left(\frac{64!}{32!^2}\right)^2 \left(\frac{32!}{16!^2}\right)^4 \left(\frac{16!}{8!^2}\right)^8 \left(\frac{8!}{4!^2}\right)^{16} \left(\frac{4!}{2!^2}\right)^{32} \left(\frac{2!}{1!^2}\right)^{64} \\[8pt] = {} & \frac{128!}{64!^2} \frac{64!^2}{32!^4} \frac{32!^4}{16!^8} \frac{16!^8}{8!^{16}} \frac{8!^{16}}{4!^{32}} \frac{4!^{32}}{2!^{64}} \frac{2!^{64}}{1!^{128}} \\[8pt] = {} & 128! \text{ (everything else cancels.)} \end{align*}


Just for fun, here's a combinatorial proof as well. Let $A$ be a set of size 128, and let $S$ be the set of all binary strings of length $7$. Let's count the number of bijections from $A$ to $S$.

  • On the one hand, $|A| = |S| = 128$, so there are $128!$ bijections from $A$ to $S$.

  • On the other hand, to construct a bijection, first we choose which elements of $A$ go to a string begining in $0$, and then choose which elements of $A$ go to a string beginning in $1$. We can do this in $\binom{128}{64}$ ways. Then, among the elements that we assigned a string starting in $0$, we must split them into strings starting in $00$ and strings starting in $01$; we can do this in $\binom{32}{16}$ ways. Similarly for the elements assigned a string starting in $1$; they either start in $10$ or in $11$. And so on.