# Prove this combinatorial identity

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

## 3 Answers

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.

• Nice interpretation of the equality! – mfl Jun 30 '14 at 20:39
• 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 – Satish Ramanathan Jun 30 '14 at 20:50
• You are welcome. But doughnuts sound OK too. Perhaps I should not answer MSE questions when I am hungry. – André Nicolas Jun 30 '14 at 20:53
• Perfect interpretation. – hlapointe Jun 30 '14 at 21:02

$${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}$$

\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*}