Monday, 9 March 2015

combinatorics - Combinatorial proof with binomial coefficients



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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...