Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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 ;)
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).
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} $$
