Proving an identity with a combinatorial proof: $\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$

Solution 1:

Think of the problem of how to choose a sports team team consisting of $k$ people, and then to choose $r$ people from that team to play in a particular match (leaving $k-r$ people on the sidelines). How many ways are there to do this if you have $n$ total people from which to choose?

We can make these choices in two different ways. First of all, how many ways are there to pick the entire team first, and then pick the players for the match from the team? Secondly, how many ways are there to pick just the players for the match first, and then fill out the rest of the team from the people you didn't pick?

In more general terms, we you can think of this identity as saying that if we make a selection from a set of $n$ things so that $k$ of them have a property $1$ and $r$ of them have properties $1$ and $2$, it doesn't matter the order in which we assign the properties.

Solution 2:

You have $n$ children. Give $k$ of them plates, and on $r$ of those plates, put a cookie. That gives you the left hand side.

Now, with the same $n$ children, give $r$ of them a plate with a cookie. Of the $n-r$ children that don't have a plate with a cookie, give $k-r$ of them empty plates. This gives you the right hand side.