Give a combinatorial proof for $\binom {n}{r}\binom {r}{k} = \binom {n}{k} \binom {n-k}{r-k}$

Question

What I have tried so far:

Combinatorial Proof: suppose there are $n$ people. first, we need to select a group of $r$ people. therefore, the number of ways to select $r$ people from $n$ people is $\binom {n}{r}$. Then, the number of ways to choose $k$ people from $r$ people is $\binom {r}{k}$. Therefore, the total number of ways to choose $k$ from $r$ from $n$ is $\binom {n}{r}\binom {r}{k}$.

RHS: To find the number of ways of choosing $k$ from $r$ from $n$, I can also pick $k$ people from $n$ people first, which the number of ways is $\binom {n}{k}$. But these $k$ people must be from a group of $r$ people. we need to consider the number of ways to choose the $r-k$ excluding $k$ from the rest of $n-k$, which the number of ways is $\binom {n-k}{r-k}$. therefore, the total number of ways to pick $k$ from $r$ from $n$ is $\binom {n}{k} \binom {n-k}{r-k}$.

Therefore, $\binom {n}{r}\binom {r}{k} = \binom {n}{k} \binom {n-k}{r-k}$

I'm not sure if I'm right. Can anyone correct me or improve my answer?

Answer 1

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

Story: We choose people to form a team of size $r$ and captains for that team, and size for the captains is $k$.

LHS: We choose $r$ people to be on a team from the pool of $n$, and we choose $k$ captains from $r$ (the size of the team).

RHS: We choose $k$ leaders from the pool of $n$ people, then we choose $r-k$ (the remaining people to form a team excluding the captains that are already chosen) from $n-k$ (the pool of people excluding the captains).

Answer 2

Yes, although rather than "select k from r from n", I'd say "form three teams of sizes $n-r$, $r-k$, and $k$".

---

We may take $n$ people, and form teams of sizes $n-r$, $r-k$, and $k$", by two methods.

• (1) First seperating them into teams of size $r$ and $n-r$. Then seperating those $r$ people into teams of sizes $k$ and $r-k$. We count the unique ways to do this by $\binom nr\binom rk$.

• (2) First...

Answer 3

There are $n$ people and $r$ shirts. Of the $r$ shirts, $k$ are black and $r-k$ are white. How many ways are there to assign these shirts to the people?

LHS: First choose the people that have shirts ($r$), from there, of the people that have shirts ($r$), choose the people that have black shirts ($k$).

RHS: First choose the people that have black shirts ($k$), then from the remaining pool, $n-k$, choose the people that have white shirts ($r-k$).