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

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 nCr I should be considering here?

• Just calculate, there is less to this than meets the eye. Whole lot of cancellation goin' on. Jun 24 '16 at 21:10
• "equals the product of these binomial theorems..." The word "theorems" should be replaced with coefficients. A theorem is a mathematical truth which has been proven via a chain of logic/reasoning, not a number to be multiplied. Jun 24 '16 at 21:10
• I'd prove it by induction, using $(2^{k+1})!=\binom{2^{k+1}}{2^k}\cdot (2^{k}!)^2$. Jun 24 '16 at 21:11
• My first thought was a combinatorial argument, then André's comment called to my attention that nearly everything cancels, then I thought just for fun I'd post an answer giving a combinatorial argument, then I saw that André had already done that. $\qquad$ Jun 24 '16 at 23:47

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.

• nice use of combinatorial arguments! Great answer Jun 24 '16 at 21:23
• Not going to lie, this was utterly mind-blowing. Very cool, and intuitive too! Jun 24 '16 at 21:25

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.

• Thank you for this, but I'm a little confused as to how you distributed the exponents - would you mind elaborating a little bit? Jun 24 '16 at 21:24
• somewhat similar to derangements and Stirling numbers. nice answer. Jun 24 '16 at 21:28
• @ChrisT I added a line, if that helps explain it! I also made a combinatorial proof, but I see Andre Nicolas and joriki have already done essentially the same.
– 6005
Jun 24 '16 at 21:31
• Thank you for clarifying, it was helpful to see it this way :) Jun 24 '16 at 21:32

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.

• somewhat close to partitioning of integers. good answer Jun 24 '16 at 21:25