1
$\begingroup$

I'm trying to make a combinatorial proof for the following identity:

${n \choose m}{m \choose k}={n-k \choose m-k}{n \choose k}$

From what I understand, the left side of the equation reduces to:

${n \choose k}$

However, I'm not entirely sure why it reduces to this. Can anyone explain why it reduces to n choose k? What's a good way to think about this identity so I can make my own combinatorial proof?

$\endgroup$

marked as duplicate by J.-E. Pin, Robert Z, Misha Lavrov, Xam, Servaes Oct 30 '17 at 23:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

These expressions don't equal $\binom{n}k$.

Let's solve this problem. We have $n$ numbered balls. We have to paint $n-m$ of them red, $k$ blue and the remaining $m-k$ green. We could choose the $m$ balls to be non-red, and then $k$ of them to be green. There are $\binom{n}m\binom{m}k$ ways to do this. Or we could pick the green balls, and then pick $n-m$ of the remaining balls to paint red, etc.

$\endgroup$

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