prove combinatorics theorem I am self-studying Combinatorics and come across this theorem. Can anyone show me how to prove the theorem. I like to understand why it is that way.


  n identical balls are put into $r$ labeled boxes and the number of balls in each box is not limited. The number of ways of doing this is $$\binom{n+r-1}{n}$$ or$$\binom{n+r-1}{r-1}$$
Regard the choice of the balls for each of the $r$ bins as determined by lining the balls up, and putting a hashmark in between the last ball to go in the $k$th bin and the first ball to go in the $k+1$th bin. That is, for example, let

$$ \cdot \cdot \cdot / \cdot \cdot / \cdot \cdot \cdot \cdot  $$

correspond to putting $3$ balls in bin $1$, $2$ balls in bin $2$, and $4$ balls in bin $3$, where $n = 9$ and $r = 3$.

Clearly, the number of ways to divide up the balls is the same as the number of ways you can choose where to put the hashmarks. But there are $n-1$ spaces in between two balls where you can put the $r-1$ hashmarks, so this gives ${n-1}\choose{r-1}$. However, this assumes that no bin gets $0$ balls. But each way you can put $n$ balls into $r$ bins, with bins possibly empty, corresponds one-to-one to the number of ways you can put $n+r$ balls into $r$ bins, giving each bin at least one ball - which we know by the above is ${n + r -1}\choose{r-1}$.
$\binom nk= \frac{n!}{k!(n-k)!}$  

$\binom n{n-k} =\frac{n!}{k!(n-k)!}$  

So, $\binom n{n-k} = \binom nk$