2
$\begingroup$

I need to prove the following: $$\sum_{k=0}^{n-1} {n\choose k}{m-1 \choose m-n+k} = {m+n-1 \choose m} $$

I have to prove it using combinatorics (not algebra). I understand the right side is the number of ways to divide m balls into n different boxes, but how can I think about left side?

Thanks.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

The right hand equals $$\binom {m+n-1}{m+n-1-m}=\binom {m+n-1}{n-1}$$

Thus, the right hand is the number of ways to choose $n-1$ objects out of $m+n-1$.

Similarly we can rewrite one of the left hand factors as $$\binom {m-1}{m-n+k}=\binom {m-1}{(n-1)-k}$$

To see that the left hand is the same as the right, say we single out $n$ objects from the total. Paint them blue and paint the others red. Note that there are $m+n-1-n=m-1$ red objects. Now $k$ denotes the number of blue objects in our list of $n-1$. Thus the $k^{th}$ term in your sum is the number of ways to choose $k$ blue and $(n-1)-k$ red objects out of $m+n-1$

$\endgroup$

You must log in to answer this question.

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