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.

Suppose we want to prove $$ k \binom{n}{k} = n \binom{n-1}{k-1}$$

In the LHS we are choosing a team of $k$ players from $n$ players. Then we are choosing a captain. In the RHS we are choosing a captain from the $n$ players. Then we are choosing the remaining $k-1$ players from the $n-1$ players.

Is this a correct interpretation?

share|improve this question
2  
I don't see anything faulty. –  user21436 Dec 28 '11 at 16:38
6  
Yes, that interpretation is correct (and well-put). Algebraically, it's just $k{n\choose k} = kn!/(k!(n-k)!) = n!/((k-1)!(n-k)!) = n(n-1)!/((k-1)!(n-k)!)=n{{n-1}\choose{k-1}}$. –  mjqxxxx Dec 28 '11 at 16:41
    
if the captain is a player, then the LHS is OK, but the RHS is not because you are using $n-1$ in $ n \binom{n-1}{k-1}$ –  Emmad Kareem Dec 28 '11 at 16:43
    
I think this proof is correct. @EmmadKareem - It's $n-1$ because the choice of captain has already been made. –  Ben Blum-Smith Dec 28 '11 at 17:15
1  
@James : I think you've answered your own question. –  Michael Hardy Dec 28 '11 at 17:21

3 Answers 3

This question is Identity 130 on page 65 of "Proofs that Really Count" by Benjamin and Quinn.

Question: How many ways can we create a size $k$ committee of students from a class of $n$ students, where one of the committee members is designated as chair?

Answer 1: There are $\binom{n}{k}$ ways to choose the committee, then $k$ ways to select the chair. Hence there are $k\binom{n}{k}$ possible outcomes.

Answer 2: First select the chair from the class of $n$ students. Then from the remaining $n-1$ students, pick the remaining $k-1$ committee members. This can be done $n\binom{n-1}{k-1}$ ways.

share|improve this answer
    
Could you maybe summarize Art Benjamin's argument for the benefit of those who don't have the book? –  J. M. Apr 18 '12 at 6:27
    
@J.M.: Everyone should get this book. It's excellent! –  Fred Kline Apr 18 '12 at 16:04

Seems right. Interestingly by this method you can prove that the equality extends to the term \begin{equation} {n \choose k-1}\cdot (n-k+1) \end{equation}

by first picking the non-captains, then electing a captain among the rest. Similarly this equals

\begin{equation} {n \choose k}\cdot {k \choose 2} \; \big/ \; \frac{k-1}{2} \end{equation}

because you can first select the team, then pick two candidates to fight each other until K.O. for the captaincy, however you have to compensate for the fact that the winner could have been matched up against anyone, but would have lost half of the time ;)

share|improve this answer

I would say it is a correct interpretation (it could have another interpretation, just as meaningful). For full effect, I would write it as:

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

to better emphasize the start of the equational balancing (act).

share|improve this answer
    
You should use \$\$ \$\$ or \$ \$ for writing equations as in latex. –  Ustun Apr 18 '12 at 6:33

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.