11
$\begingroup$

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?

$\endgroup$
4
  • 8
    $\begingroup$ Just calculate, there is less to this than meets the eye. Whole lot of cancellation goin' on. $\endgroup$ Jun 24, 2016 at 21:10
  • 1
    $\begingroup$ "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. $\endgroup$
    – JMoravitz
    Jun 24, 2016 at 21:10
  • 2
    $\begingroup$ I'd prove it by induction, using $(2^{k+1})!=\binom{2^{k+1}}{2^k}\cdot (2^{k}!)^2$. $\endgroup$ Jun 24, 2016 at 21:11
  • 1
    $\begingroup$ 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$ $\endgroup$ Jun 24, 2016 at 23:47

5 Answers 5

27
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ nice use of combinatorial arguments! Great answer $\endgroup$
    – vidyarthi
    Jun 24, 2016 at 21:23
  • 1
    $\begingroup$ Not going to lie, this was utterly mind-blowing. Very cool, and intuitive too! $\endgroup$
    – Chris T
    Jun 24, 2016 at 21:25
17
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for this, but I'm a little confused as to how you distributed the exponents - would you mind elaborating a little bit? $\endgroup$
    – Chris T
    Jun 24, 2016 at 21:24
  • $\begingroup$ somewhat similar to derangements and Stirling numbers. nice answer. $\endgroup$
    – vidyarthi
    Jun 24, 2016 at 21:28
  • $\begingroup$ @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. $\endgroup$ Jun 24, 2016 at 21:31
  • $\begingroup$ Thank you for clarifying, it was helpful to see it this way :) $\endgroup$
    – Chris T
    Jun 24, 2016 at 21:32
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ somewhat close to partitioning of integers. good answer $\endgroup$
    – vidyarthi
    Jun 24, 2016 at 21:25
0
$\begingroup$

Here is how to do this without figuring out any kind of clever combinatorial argument and without expanding all the factorials out. All you have to do is guess that there's nothing special about $128$ here and that the obvious generalization of this identity holds for any power of $2$. So, the first few cases of this general identity which we are guessing is true are

$$2! \stackrel{?}{=} {2 \choose 1}$$ $$4! \stackrel{?}{=} {4 \choose 2} {2 \choose 1}^2$$ $$8! \stackrel{?}{=} {8 \choose 4} {4 \choose 2}^2 {2 \choose 1}^4.$$

Both sides of these purported identities have an inductive structure: the LHS is given by taking the factorial of the next power of $2$, while the RHS is given by squaring the previous RHS, then multiplying by that big binomial coefficient. That is, if we define the LHS and RHS formally as two sequences

$$a_n = (2^n)!, b_n = {2^n \choose 2^{n-1}} {2^{n-1} \choose 2^{n-2}}^2 \dots {2 \choose 1}^{2^{n-1}}$$

then the inductive structure of $b_n$ is that

$$b_n = {2^n \choose 2^{n-1}} b_{n-1}^2$$

but the same is true of $a_n$, because of course

$${2^n \choose 2^{n-1}} = \frac{(2^n)!}{(2^{n-1})!^2} = \frac{a_n}{a_{n-1}^2}.$$

So once we check that $a_1 = b_1 = 2$ we have $a_n = b_n$ by a straightforward induction. Of course the combinatorial proof easily generalizes to give this result but the explicit expansion is somewhat annoying for general $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .