# Proving an identity with a combinatorial proof

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity:

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

The problem is that I can't come up with a good counting argument of what exactly the two sides are doing. The left hand side is quite mysterious, and the right hand side is apparently choosing $r$ items and then choosing $k-r$ items from the remaining, which should be equivalent to $\binom{n}{k}$ but somehow isn't. How should I approach this problem?

-
I think the reason the RHS is not $\binom{n}{k}$ is that in choosing $r$ items and then $k-r$ items, you can distinguish between the items chosen in the first batch and those chosen in the second. –  Alex Becker May 11 '13 at 14:46

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?
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.
Good way of explaining this. That is, let $A$ be a set with $n$ elements. You are counting the pairs $(B, C)$, where $B \subseteq C \subseteq A$, with $\lvert B \rvert = r$, and $\lvert C \rvert = k$, in two ways, either $C$ first (LHS), or $B$ first (RHS). –  Andreas Caranti May 11 '13 at 14:51
I'm not failing to get the identity. How can we formalize this? How can the left hand side be formulated into the size of a set $S$? –  user54609 May 11 '13 at 15:00
@EricDong, look at my comment, it is the set of all pairs $(B, C)$ etc. –  Andreas Caranti May 11 '13 at 15:01