Help with a proof with combination: $\binom{n}{k}\binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m}$

Question

I have to prove that:

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

I'm not really sure how to approach this problem. I know the formula definition of combination but am unsure how to apply it to this question

Answer 1

$$\binom{n}{m}\binom{m}{k} = \frac{n!}{m!(n-m)!} \frac{m!}{k!(m-k)!}= \frac{n!}{(n-m)!} \frac{1}{k!(m-k)!}=\frac{n!}{k!} \frac{1}{(m-k)!(n-m)!}=\frac{n!}{k!(n-k)!} \frac{(n-k)!}{(m-k)!(n-m)!}=\binom{n}{k}\frac{(n-k)!}{(m-k)!((n-k)-(m-k))!}=\binom{n}{k} \binom{n-k}{m-k}$$

Answer 2

There are $n$ (healthy) doughnuts, all different-flavoured. We want to pick $m$ of them to eat today, and $k-m$ of them to eat tomorrow. We count the number of ways to do this, in two different ways.

Way 1: Pick the $k$ doughnuts we will eat today and tomorrow. From these, the ones for today can be chosen in $\binom{k}{m}$ ways, for a total of $\binom{n}{k}\binom{k}{m}$.

Way 2: Pick the ones to eat today. This can be done in $\binom{n}{m}$ ways. From the remaining $n-m$, pick the $k-m$ for tomorrow, total number of ways $\binom{n}{m}\binom{n-m}{k-m}$.

The two answers must be equal.

Answer 3

Here is a conceptual proof. Both sides we are choosing a $k$ element subset of an $n$ element set and then an $m$ element subset of the $k$ element set. There are two ways to do this. First choose the $k$ element set then choose the $m$ element subset, this is the left hand side. The other way is first to choose the $m$ element subset, and then choose the additional $k-m$ elements to form the $k$ element set. This is the right hand side.

Answer 4

Given $n$ people, we can form a committee of size $k$ in ${n\choose k}$ ways. Once the committee is formed we can form a sub-committee of size $m$ in ${k\choose m}$ ways. Thus we can form a committee of size $k$ with a sub-committee of size $m$ in ${n\choose k}{k\choose m}$ ways. We can count the same thing by forming the sub-committee first and then forming the committee that contains the sub-committee. Given $n$ people we can form a sub-committee of size $m$ in ${n\choose m}$ ways. Once the sub-committee is formed we must form the committee of size $k-m$ from the remaining $n-m$ people in ${n-m\choose k-m}$ ways. Thus we can form a sub-committee of size $m$ while forming the committee of size $k-m$ that contains the sub-committee in ${n\choose m}{n-m\choose k-m}$ ways. Hence ${n\choose k}{k\choose m}={n\choose m}{n-m\choose k-m}$.

This combinatorial identity is known as the Subset-of-a-Subset identity.

Answer 5

$\dbinom{n}{k}\dbinom{k}{m}$ counts the ways to divide $n$ items into three piles of size $n-k$, $k-m$, and $m$ by first removing $k$ items from and then dividing those items.

$\dbinom{n}{m}\dbinom{n-m}{k-m}$ counts the ways to divide $n$ items into three piles of size $m$, $n-m$, and $n-k$ by first selecting $m$ items and then dividing the rest.

---

$\begin{align}\dbinom{n}{k}\dbinom{k}{m}&=\dfrac{n!}{k!\, n-k!}\dfrac{k!}{m!\, (k-m)!}\\&=\dfrac{n!}{(n-k)!\,(k-m)!\,m!}\\&=\dfrac{n!}{m!\,(n-m)!}\dfrac{(n-m)!}{(n-k)!\,(k-m)!}\\&=\dbinom{n}{m}\dbinom{n-m}{k-m}\end{align}$