Whats the difference between the following? $n+k-1 \choose k$ ${{n+k-1}\choose{k-1}}$ ${{n+k-1}\choose{n}}$

Solution 1:

To make it clearer... I am going to avoid using either of $n$ or $k$.

If you have $\#Ball$ number of identical balls and $\#Bin$ number of distinct bins then the number of ways in which you can distribute these is:

$$\binom{\#Ball + \#Bin - 1}{\#Bin - 1}$$

This can be seen via a stars and bars argument, using barriers to break the ball into groups, those balls to the left of the first barrier go to the first bin, the next group going to the second bin, and so on... you will need $\#Bin-1$ number of barriers.

Recognize that since $\binom{n}{r} = \binom{n}{n-r}$ (seen easily by noting that to select $r$ people from $n$ to "keep" you could instead have selected $n-r$ people from $n$ to "remove" instead and had the same result) the above is also equal to:

$$\binom{\#Ball + \#Bin - 1}{\#Ball}$$

Now... some authors prefer to refer to the number of balls as $n$ and the number of bins as $k$. Other authors prefer to refer to the number of balls as $k$ and the number of bins as $n$. This is why you will sometimes see the formula written as $\binom{n+k-1}{k-1}$ and at other times as $\binom{n+k-1}{k}$, because the author of the first formula intends $k$ to be the number of bins while the author of the second formula intends $k$ to be the number of balls instead.