Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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.

share|improve this answer

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.

share|improve this answer
    
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,

share|improve this answer

$$\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*}$$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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