17
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I don't see anything faulty. $\endgroup$ – user21436 Dec 28 '11 at 16:38
  • 7
    $\begingroup$ 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}}$. $\endgroup$ – mjqxxxx Dec 28 '11 at 16:41
  • $\begingroup$ 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}$ $\endgroup$ – NoChance Dec 28 '11 at 16:43
  • $\begingroup$ I think this proof is correct. @EmmadKareem - It's $n-1$ because the choice of captain has already been made. $\endgroup$ – Ben Blum-Smith Dec 28 '11 at 17:15
  • 1
    $\begingroup$ @James : I think you've answered your own question. $\endgroup$ – Michael Hardy Dec 28 '11 at 17:21
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you maybe summarize Art Benjamin's argument for the benefit of those who don't have the book? $\endgroup$ – J. M. isn't a mathematician Apr 18 '12 at 6:27
  • $\begingroup$ @J.M.: Everyone should get this book. It's excellent! $\endgroup$ – Fred Kline Apr 18 '12 at 16:04
0
$\begingroup$

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 ;)

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ You should use \$\$ \$\$ or \$ \$ for writing equations as in latex. $\endgroup$ – user21965 Apr 18 '12 at 6:33
0
$\begingroup$

Generalizing it :

Let $n \in \mathbb{N}^*$ Let $E$ a set such as $\#E=n$

Let $k,p$ such as $0<k<p<n$.

We will choose a set $A$ of cardinal $k$ and a subset $B$ of cardinal $p$.

First count

I choose $k$ elements from $E$ :

$$ \binom{n}{k}$$

Then I choose $p$ elements in $A$ so the total:

$$ \binom{k}{p}\binom{n}{k}$$

Second count

I choose $B$ in $E$ so :

$$\binom{n}{p}$$

Then I choose $A$ i.e. $(k-p) $ remaining elements (because $A$ contains $B$) to choose in $E \backslash B$ whose cardinal is $n-p$ : so total:

$$ \binom{n}{p}\binom{n-p}{k-p} $$

Thus:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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