# Proving that $\binom{n}{k}\binom{\smash{k}}{m}\binom{m}{r} = \binom{n}{r}\binom{n-r}{n-m}\binom{n-m}{n-k}$

How would you show that $$\binom{n}{k}\binom{k}{m}\binom{m}{r} = \binom{n}{r}\binom{n-r}{n-m}\binom{n-m}{k-m}$$ for $n\geq k\geq m\geq r$ ?

-
Use the definition of the Binomial coefficient. – poirot Feb 9 at 11:52

You have $n$ blank sheets of paper. You pick $k$ of them and make a mark on each. Then you pick $m$ of the marked sheets and make a second mark on each. Finally, you pick $r$ of the doubly-marked sheets and put a third mark on each. Notice that you end up with $r$ triply-marked sheets, $m-r$ doubly-marked sheets, $k-m$ singly marked sheets, and $n-k$ blank sheets.

Alternatively, you could pick $r$ of the sheets, put three marks on each, and set them aside. Then you could pick $n-m$ of the remaining $n-r$ sheets and temporarily set them aside; that leaves $(n-r)-(n-m)=m-r$ sheets, which you mark twice and set aside. Now go back to the $n-m$ sheets that you set aside temporarily, and pick $k-m$ of them; mark those $k-m$ sheets once each, leaving $(n-m)-(k-m)=n-k$ sheets unmarked.

The lefthand side counts the number of ways of performing the first task, and the righthand side counts the number of ways of performing the second task, but the tasks are clearly the same: to divide the $n$ sheets into $r$ triply-marked sheets, $m-r$ doubly-marked sheets, $k-m$ singly marked sheets, and $n-k$ blank sheets.

-

Out of a group of $n$ citizens, you will choose $r$ Senatorial Officers; $m$ Senators (the $m$ include the Senatorial officers), and $k$ Parliamentarians (the $k$ includes the Senators).

The left hand side selects the Parliamentarians; then from among the Parliamentarians it selects the Senators; then from among the Senators it selects the Senatorial Officers.

The right hand side selcts the Senatorial Officers; then selects the remaining Senators (remember that $\binom{a}{b} = \binom{a}{a-b}$, so $$\binom{n-r}{n-m} = \binom{n-r}{(n-r)-(n-m)} = \binom{n-r}{m-r};$$ so the second binomial factor is the same as selecting $m-r$ from the remaining $n-r$ citizens). And finally, it selects the remaining Parliamentarians.

-
Whew, too much politics for me. I prefer Brian's sheets of paper =) politics these days.. – Patrick Da Silva Feb 28 '12 at 5:51

If we don't do combinatorics, there's always algebraic identities : we want to show that $$\frac {n!}{k! (n-m)!} \frac{k!}{m! (k-m)!} \frac{m!}{r!(m-r)!} = \frac{n!}{r!(n-r)!} \frac{(n-r)!}{(n-m)!(m-r)!} \frac{(n-m)!}{(k-m)!(n-k)!}$$ because $\begin{pmatrix} n \\ k \end{pmatrix} = \frac {n!}{k! (n-k)!}$. If we cancel out numerators that are the same as denominators ($k!$ and $m!$ on the left, $(n-r)!$ and $(n-m)!$ on the right), we deduce that the wanted equality is equivalent to $$\frac{n!}{r!(n-m)!(k-m)!(m-r)!} = \frac{n!}{r!(m-r)!(k-m)!(n-k)!}$$ Now this equality is clearly true, so that our result holds.

Hope that helps,

-

\begin{align*} \text{RHS} &=\frac{n!}{r!(n-r)!}\frac{(n-r)!}{(n-m)!(m-r)!}\frac{(n-m)!}{(n-k)!(k-m)!}\\ &= \frac{n!}{r!(m-r)!(n-k)!(k-m)!}\\ &=\frac{n!}{k!(n-k)!}\frac{k!}{m!(k-m)!}\frac{m!}{r!(m-r)!}\\ &= \text{LHS} \end{align*}

-
@Arturo - thanks for making it look nice! – user22805 Feb 28 '12 at 6:17

\begin{align} & \binom{n}{k}\binom{k}{m}\binom{m}{r} \\ = & \frac{n!}{(n-k)! \cdot k!} \cdot \frac{k!}{(k-m)! \cdot m!} \cdot \frac{m!}{(m-r)! \cdot r!} \\ = & \frac{n! \cdot k! \cdot m!}{(n-k)! \cdot k! \cdot (k-m)! \cdot m!\cdot (m-r)! \cdot r!} \\ = & \frac{n!}{(n-k)! \cdot (k-m)! \cdot (m-r)! \cdot r!} \cdot \frac{(n-r)!}{(n-r)!} \\ = & \frac{n!}{r! \cdot (n-r)!} \cdot \frac{(n-r)!}{(n-k)! \cdot (k-m)! \cdot (m-r)!} \\ = & \frac{n!}{r! \cdot (n-r)!} \cdot \frac{(n-r)!}{(n-k)! \cdot (k-m)! \cdot (m-r)!} \cdot \frac{(n-m)!}{(n-m)!} \\ = & \frac{n!}{r! \cdot (n-r)!} \cdot \frac{(n-r)!}{(n-m)! \cdot (m-r)!} \cdot \frac{(n-m)!}{(k-m)! \cdot (n-k)!} \\ = & \frac{n!}{r! \cdot (n-r)!} \cdot \frac{(n-r)!}{(n-m)! \cdot ((n-r)-(n-m))!} \cdot \frac{(n-m)!}{(k-m)! \cdot ((n-m)-(k-m))!} \\ = & \binom{n}{r}\binom{n-r}{n-m}\binom{n-m}{k-m} \end{align} Q.E.D.

-