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

Question

I'm working through some combinatorics practice sets and found the following problem that I can't make heads or tails of.

It asks to prove the following:

$$128! = \binom{128}{64}\binom{64}{32}^2\binom{32}{16}^4\binom{16}8^8\binom 84^{16}\binom 42^{32}\binom{2}{1}^{64}$$

Weird, huh? The first thing I noticed is that the exponents mirror the $r$ variables. I would normally just re-express each statement in $\frac{n!}{(n-r)!r!}$ form, but the exponents throw me for a loop. Are there any intuitions about factorials or $_n C_r$ that I should be considering here?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

Divide $128$ items in half, and assign one half a $1$ bit in the first digit and the other a $0$ bit. Then divide each half in half again, and in each half assign one half a $1$ bit in the second digit and the other a $0$ bit. Continue until the halves consist of single elements. Now each element has been assigned a binary number from $0$ to $127$. The left-hand side counts the number of ways of assigning the numbers, and the right-hand side counts the number of ways of performing the subdivisions.