1
$\begingroup$

I'm looking for an intuitive explanation for this identity: ${n \choose k} = \frac{n}{k}{n-1 \choose k-1}$ for $0 < k \leq n$.

The math adds up, but I can't see why it's true. I'd expect that choosing $k$ elements from an $n$-set would be like choosing $k-1$ elements from an $(n-1)$-set, then add an $n$th element to the set, and choose another element from the $n - k + 1$ not-yet-chosen elements. But I guess I'm missing something.

Can anyone provide some intuition?

  • 0
    See also http://math.stackexchange.com/questions/94719/proving-k-binomnk-n-binomn-1k-12012-01-10

2 Answers 2

2

It's probably easiest to see as follows. Choose the "first" element; there are $n$ ways to do this. Now choose $k-1$ elements from the remaining $n-1$; there are ${n-1\choose k-1}$ ways to do this. That gives you $n{n-1\choose k-1}$, but you've overcounted: for example, $\lbrace 1,2,3\rbrace$ is counted separately from $\lbrace 2,1,3\rbrace$, since your first choice was $1$ in the former case and $2$ in the latter. So you divide out by the number of distinct ways of selecting a "first" element out of the $k$ that you've chosen; that gives you the additional factor of $1/k$.

  • 0
    Makes sense (though it took me a while :)). Thanks.2012-01-10
0

One can write it like this: $k{n \choose k} = n{n-1 \choose k-1}.$

First you choose $k$ out of $n$; then you choose one of the $k$ to be the leader. There are $\binom nk$ ways to make the first choice, and then $k$ ways to make the second choice. That's the left side of the identity.

Alternatively, first you choose one of the $n$ to be the leader; then you choose $k-1$ of the remaining $n-1$ to be the others in the group of $k$. That's the right side of the identity.