Combinatorial proof (catching fishes and eating some from them)

Question

Combinatorial proof for :

$$ \binom{n}{m} \cdot \binom{n-m}{k-m} = \binom{n}{k} \cdot \binom{k}{m} $$

where $m\leq k\leq n$

I tried but I have no idea about how to do it. Any help will be appreciated.

Answer 1

You have $n$ distinct fish. You catch $k$ of them and eat $m$ of those $k$. There are $\binom{n}k$ ways to pick $k$ of the fish to catch, and once you’ve caught those fish, there are $\binom{k}m$ ways to choose which $m$ of them you’ll eat. Thus, there are

$$\binom{n}k\binom{k}m$$

possible outcomes, where an outcome is defined to be a certain set of $n-k$ uncaught fish, a certain set of $k-m$ caught-but-not-eaten fish, and the remaining set of $m$ fish that were caught and eaten. (Or perhaps I should call that the non-remaining set!)

To show that this is equal to

$$\binom{n}m\binom{n-m}{k-m}\;,$$

try to find a similar interpretation that involves choosing the three sets of fish in a different order. For instance, $\binom{n}m$ looks like the number of ways to choose $m$ fish to eat. Can you interpret $\binom{n-m}{k-m}$ to finish the argument?