2
$\begingroup$

$${n \choose k}{k \choose 1}{k-1 \choose 1} = n(n-1){n-2 \choose k-2}$$

$\endgroup$
8
$\begingroup$

We have group of $n$ people, and want to choose $k$ of them to go on a trip, and appoint one of them Leader, and another Vice-Leader.

We can choose the leader in $n$ ways. For each such way, we can choose the Vice-Leader in $n-1$ ways, and then choose the remaining $k-2$ people who will go on the trip in $\binom{n-2}{k-2}$ ways.

Or else we can choose the lucky $k$ from the $n$, choose one of the $k$ as Leader, and another as Vice-Leader. This can be done in $\binom{n}{k}\binom{k}{1}\binom{k-1}{1}$ ways.

We have counted the same thing in two different ways. The answers must be the same, and so we get our identity. Note that there are restrictions on $n$, it should be at least $2$, as should $k$.

Remark: Too bureaucratic! There are $n$ different-flavoured doughnuts. We want to choose $k$ of them, eat one, then another, and save the rest for dinner. Again, there are two ways to count the number of ways we can do this.

$\endgroup$
  • $\begingroup$ Nice interpretation of the equality! $\endgroup$ – mfl Jun 30 '14 at 20:39
  • $\begingroup$ Great one. One of the tournaments wanted a combinatorial proof just like yours. It went further to form 4 groups from it and each has to select a leader and a vice-leader. Thanks $\endgroup$ – Satish Ramanathan Jun 30 '14 at 20:50
  • $\begingroup$ You are welcome. But doughnuts sound OK too. Perhaps I should not answer MSE questions when I am hungry. $\endgroup$ – André Nicolas Jun 30 '14 at 20:53
  • $\begingroup$ Perfect interpretation. $\endgroup$ – hlapointe Jun 30 '14 at 21:02
3
$\begingroup$

$${n \choose k}{k \choose 1}{k-1 \choose 1} = \frac{n!}{(n-k)!k!}\cdot k\cdot (k-1)=\frac{n!}{(n-k)!(k-2)!}\\=n\cdot(n-1)\cdot \frac{(n-2)!}{(n-2-(k-2))!(k-2)!}=n(n-1){n-2 \choose k-2}$$

$\endgroup$
0
$\begingroup$

\begin{align*} {\color{Blue}{{n \choose k}{k \choose 1}{k-1 \choose 1}}} &=\frac{n!}{(n-k)!k!} \cdot k \cdot (k-1)\\ &=\frac{n!}{(n-k)!} \cdot \frac{k(k-1))}{k!}\\ &=\frac{n!}{(n-k)!} \cdot \frac{k(k-1)}{k(k-1)(k-2)!}\\ &=\frac{n!}{(n-k)!(k-2)!}\\ &=n(n-1)\frac{(n-2)!}{((n-2)-(k-2))!(k-2)!}\\ &={\color{Blue}{n(n-1){n-2 \choose k-2}}} \end{align*}

$\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.