I'm reading about combinatorics, specifically 'Cohen's Introduction to Combinatorial Theory', and am stuck on one of the problems.
I'm looking for a combinatorial proof for the following :
$\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$
If anyone can offer me any help, it would be much appreciated. I haven't been able to find a electronic or print version of the solutions to the problems in Cohen's book, so if anyone has any idea where I could find it, it will be truly of help.
In addition, if you are aware of any resources for constructing combinatorial proofs, please could you provide a link?
Thanks
Best Answer
From a group of $n$ people, we want to select $r$ people to go on a trip, including the trip leader. We count the number of ways of doing the choosing in two different ways.
(i) We can choose the leader in $n$ ways. For each of these ways, we can choose the rest of the people in $\binom{n-1}{r-1}$ ways, for a total of $n\binom{n-1}{r-1}$.
(ii) We can choose the $r$ people who go on the trip in $\binom{n}{r}$ ways, and for each of these ways we can choose the leader in $r$ ways, for a total of $r\binom{n}{r}$.
Thus $n\binom{n-1}{r-1}=r\binom{n}{r}$.