I need to prove this with combinatorial arguments. I don't know how to start.
$$
\sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r}
=
{n \choose k}\,,
\qquad\qquad 1\ \leq\ r\ \leq\ k\ \leq\ n
$$
Answer
On the right hand side, I need to choose $k$ integers from the set $\{1,\ldots, n\}$. On the left hand side: for each possible $j$, $r\leq j\leq n+r-k$, I make sure that the $r$-th smallest number chosen is $j$, then choose $r-1$ numbers from the $j-1$ smaller ones and $k-r$ numbers from the $n-j$ larger ones.
No comments:
Post a Comment