1
$\begingroup$

I want to prove the combinatorical identity:

$$\binom{n+r-1}r=\sum_{k=1}^n\binom{n}k\binom{r-1}{k-1}$$

They both are ‘$r$ identical balls to $n$ different cells with repeats and without order’.

But for the left side I see it as ‘choosing $k$ not empty cells and put in them one ball in each, and then all the other $n-k$ balls put into the choosen $k$ cells with repeats and without order’.

But for the second part isn't it

$$\binom{k+r-k-1}{r-k}=\binom{r-1}{r-k}\;?$$

I don't see how it is:

$$\binom{r-1}{k-1}$$

$\endgroup$
  • $\begingroup$ You can get $\binom{n}k$ with \binom{n}{k}. $\endgroup$ – Brian M. Scott Mar 5 '16 at 19:55
1
$\begingroup$

You mean $r$ not $k$ in the first combinatorial interpretation. Yes: then choose $k$ cells to be non-empty, in $\binom{n}{k}$ ways, put one ball in each, then put the remaining $r-k$ balls in these $k$ cells in $\binom{(r-k)+k-1}{r-k} = \binom{r-1}{r-k} = \binom{r-1}{k-1}$ ways. The only thing you're missing is the identity $\binom{a}{b} = \binom{a}{a-b}$ used in the final step.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.