# $k$ identical balls to $n$ different cells

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}$$

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

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.