Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 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 assaign the properties.

share|improve this answer
1  
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
    
@AndreasCaranti Thank you! It's probably my favourite combinatorial proof! I'm never quite sure how generally to phrase a proof to be both understandable and to make sure it applies to all related situations, but the subset terminology is nice. –  Tom Oldfield May 11 '13 at 14:56
    
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
1  
@EricDong, look at my comment, it is the set of all pairs $(B, C)$ etc. –  Andreas Caranti May 11 '13 at 15:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.