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

$\endgroup$
  • 8
    $\begingroup$ Just calculate, there is less to this than meets the eye. Whole lot of cancellation goin' on. $\endgroup$ – André Nicolas Jun 24 '16 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 '16 at 21:10
  • 1
    $\begingroup$ I'd prove it by induction, using $(2^{k+1})!=\binom{2^{k+1}}{2^k}\cdot (2^{k}!)^2$. $\endgroup$ – Thomas Andrews Jun 24 '16 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$ – Michael Hardy Jun 24 '16 at 23:47
21
$\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$
  • 1
    $\begingroup$ nice use of combinatorial arguments! Great answer $\endgroup$ – vidyarthi Jun 24 '16 at 21:23
  • 1
    $\begingroup$ Not going to lie, this was utterly mind-blowing. Very cool, and intuitive too! $\endgroup$ – Chris T Jun 24 '16 at 21:25
15
$\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$
9
$\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$
  • $\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 '16 at 21:24
  • $\begingroup$ somewhat similar to derangements and Stirling numbers. nice answer. $\endgroup$ – vidyarthi Jun 24 '16 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$ – 6005 Jun 24 '16 at 21:31
  • $\begingroup$ Thank you for clarifying, it was helpful to see it this way :) $\endgroup$ – Chris T Jun 24 '16 at 21:32
8
$\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$
  • $\begingroup$ somewhat close to partitioning of integers. good answer $\endgroup$ – vidyarthi Jun 24 '16 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.