Prove, using a combinatorial argument, that $\binom{m}{n}\cdot\binom{n}{r}= \binom{m}{r}\cdot \binom{m-r}{n-r}$

Question

Prove, using a combinatorial argument, that $$\binom{m}{n}\cdot\binom{n}{r}= \binom{m}{r}\cdot \binom{m-r}{n-r}$$

attempt: In $m$, suppose that $n$ went for a ride, and out of those $n$, $r$ were awarded. This can be done in $\binom{m}{n}\cdot\binom{n}{r}$ ways. Now suppose we choose $r$ people to be rewarded from these $m$, and then we choose the $n-r$ people who only went on the tour but were not rewarded: $\binom{m}{r}\cdot \binom{m-r}{n-r}$ . So $$\binom{m}{n}\cdot\binom{n}{r}= \binom{m}{r}\cdot \binom{m-r}{n-r}$$

I'm right?

Answer 1

Consider sets $M$, $N$, and $R$ of sizes $m$, $n$, and $r$, respectively. The left hand expression counts the number of ways to choose such an $N \subseteq M$ followed by $R \subseteq N$. The right hand expression counts the number of ways to choose $R \subseteq M$ directly followed by choosing $N' \subseteq M \setminus R$ from the remaining elements (after $R$ is removed).

Let's give these collections names: $$ \mathcal{A} = \bigl\{ (N, R) \bigm| R \subseteq N \subseteq M \bigr\} $$ so $$ \lvert\mathcal{A}\rvert = \binom{m}{n} \binom{n}{r}, $$ and $$ \mathcal{B} = \bigl\{ (R, N') \bigm| R \subseteq M \;\text{and}\; N' \subseteq M \setminus R \bigr\} $$ so $$ \lvert\mathcal{B}\rvert = \binom{m}{r} \binom{m-r}{n-r}. $$

We have to put these two sets in bijective correspondence. Try it yourself.

Consider the maps \begin{array}{ccc} \mathcal{A} &\longrightarrow &\mathcal{B} \\ (N, R) &\longmapsto &(R, N \setminus R) \end{array} and \begin{array}{ccc} \mathcal{B} &\longrightarrow &\mathcal{A} \\ (R, N') &\longmapsto &(N' \cup R, R) \end{array}

You can check that each is well-defined, maps into the stated set, and that they are mutually inverse. Thus, we have a bijective correspondence, i.e. a combinatorial argument that for all integers $0 \leq r \leq n \leq m$, $$ \binom{m}{n} \binom{n}{r} = \binom{m}{r} \binom{m-r}{n-r}. $$

---

By the way, it's easy to come up with "real world" examples of such sets. Say, for instance that you have $m$ math papers that you'd like to read, printed and sitting on your desk. You are going to take $n$ of them on your trip, and of those you are going to put $r$ of them in your carry-on backpack. How many distinct ways are there to do this?

The set $\mathcal{A}$ enumerates the possibilities, as stated. On the other hand, the set $\mathcal{B}$ enumerates the same set of choices, but via a different mechanism: select the $r$ carry-on papers, then from the rest of the $m$ papers on your desk, select papers to pack in your checked luggage so that you bring $n$ in total. This of course requires you to select $n-r$ papers from the remaining $m-r$ papers on your desk.

Answer 2

Solution:

For the left part, we have

$$ \left( \begin{array}{c} m\\ n\\ \end{array} \right) \cdot \left( \begin{array}{c} n\\ r\\ \end{array} \right) =\frac{m!}{n!\left( m-n \right) !}\cdot \frac{n!}{r!\left( n-r \right) !}=\frac{m!}{\left( m-n \right) !\left( n-r \right) !r!}, $$

and for the right part, we have

$$ \left( \begin{array}{c} m\\ r\\ \end{array} \right) \cdot \left( \begin{array}{c} m-r\\ n-r\\ \end{array} \right) =\frac{m!}{r!\left( m-r \right) !}\cdot \frac{\left( m-r \right) !}{\left( n-r \right) !\left( m-n \right) !}=\frac{m!}{\left( m-n \right) !\left( n-r \right) !r!}. $$

Therefore, we have

$$ \left( \begin{array}{c} m\\ n\\ \end{array} \right) \cdot \left( \begin{array}{c} n\\ r\\ \end{array} \right) =\left( \begin{array}{c} m\\ r\\ \end{array} \right) \cdot \left( \begin{array}{c} m-r\\ n-r\\ \end{array} \right). $$