0
$\begingroup$

Confusion about combinatorial identity $k {n\choose k} = n{ {n-1}\choose{k-1} }$

I saw this combinatorial proof in other posts about this identity. For the left hand side, we can say this is the number of ways to pick a team of $k$ people and then choose one of them to be the captain.

For the right hand side, we can say first pick the captain out of $n$ people, then there are ${n-1}\choose k-1$ ways to pick the rest of the team.

However, for the right hand side, what if we thought of the choice in the opposite direction: first pick $k-1$ regular teammates out of $n$ options, then choose the captain. Since we have already chosen $k-1$ people, there are only $n-(k-1)$ options remaining for the captain, so we would have ${n\choose {k-1}} (n-k+1)$, which is different from both sides of the identity.

What is wrong with the second interpretation of the right hand side? Choosing the non-captain teammates first then choosing the captain seems equivalent to choosing the captain first then choosing the non-captain teammates.

$\endgroup$
3
  • 4
    $\begingroup$ Looks good to me. Indeed, $k\binom nk=k\times \frac {n!}{k!(n-k)!}=\frac {n!}{(k-1)!(n-k)!}$ while $(n-k+1)\times \binom n{k-1}=(n-k+1)\times \frac {n!}{(k-1)!(n-k+1)!}=\frac {n!}{(k-1)!(n-k)!}$ $\endgroup$
    – lulu
    Commented Oct 28, 2022 at 1:04
  • 2
    $\begingroup$ "which is different from both sides of the identity" Yes. This identity could be expanded to have three, four, five... however many "sides" as you can come up with different expressions for. You happened to find a "third" side. That doesn't mean that the original two sides are invalid, but it does mean that your observation doesn't directly help prove the originally stated identity. $\endgroup$
    – JMoravitz
    Commented Oct 28, 2022 at 1:47
  • 2
    $\begingroup$ $1+1=2$. "But what if we subtracted $1$ from $3$?" Yes... $3-1=2$ as well. What is your point? $\endgroup$
    – JMoravitz
    Commented Oct 28, 2022 at 1:49

1 Answer 1

Reset to default
3
$\begingroup$

In your second interpretation, you wrote "pick $k-1$ regular teammates out of n options," but the RHS is actually ${n-1}\choose k-1$ not $n\choose{k-1}$. It's small things like that which make the difference.

Edit: I misread your question; see @lulu's comment, they are algebraically the same.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .