It isn't hard to algebraically show that:
$${n \choose k} = \sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r}, 1 \leq r \leq k$$ I'm trying to find some sort of combinatorial "proof"/intuition as to why this is true. My thought is that it is similar to Pascal's Rule, but I'm not sure.
Thanks!
Answer
Clearly $\binom{n}k$ is the number of $k$-element subsets of $[n]=\{1,\ldots,n\}$. We can categorize these subsets according to their $r$-th smallest element. How many of them have $r$-th smallest element $j$? There are $j-1$ members of $[n]$ less than $j$, and we have to choose $r-1$ of them for our set; this can be done in $\binom{j-1}{r-1}$ ways. There are $n-j$ members of $[n]$ bigger than $j$, and we have to choose $k-r$ of them for our set; this can be done in $\binom{n-j}{k-r}$ ways. Thus, there are
$$\binom{j-1}{r-1}\binom{n-j}{k-r}$$
ways to choose a $k$-element subset of $[n]$ whose $r$-th smallest element is $j$. Summing over the possible values of $j$ yields the desired identity,
$$\sum_{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r}=\binom{n}k\;.$$
No comments:
Post a Comment