I am trying to prove a formula (for ways of distributing $n$ identical balls among $r$ persons when each person may get any number of balls) ${n+r-1}\choose{r-1}$. But I am not able to prove it. I may be doing something wrong but I am not able to figure out what exactly?
This is what I am doing.
I put $n$ identical balls in a line. Now there are $(n+1)$ spaces/gaps between these $n$ identical things including (left to the leftmost ball and the next to the rightmost ball). So now basically I just need to select any $(r-1)$ gaps from these $(n+1)$ gaps and I will be able to create $r$ groups.
So, my answer is ${n+1}\choose{r-1}$.
But the actual answer to this is ${n+r-1}\choose{r-1}$ as per Number of ways of distributing n identical objects among r groups
I want to know what am I doing wrong? Thanks!
Best Answer
The fault lies in our inability to "choose" a bar twice (which we would need to do for empty inner bins).
Consider ten stars and four bars (corresponding to five bins):
There are five bins. The first starts on the left and goes until the first "|". The final bin begins with the final "|", and goes right from there.
Now the right-most bin is empty. This is all well and good, but what if we want an inner bin to be empty? We must choose the same "place" twice, which we can't do.
So instead of only counting the spaces between (and beside) the "*" characters above, we allow for fourteen characters - ten stars and four bars. We can choose adjacent characters to be bars to represent an (inner) empty bin.
$(2,3,0,4,1)$