I am having a difficulty with a well-known problem of balls and boxes.
1) In the first case we have a M distinguishable boxes with N distinguishable balls. Each box can contain more than one ball. So the total number of possible configurations is (permutations with repetition) $M^N$, right?
2) In the second case we have the same number of boxes, but the balls are indistinguishable. So now the number of possible configurations is equal to the number of combinations with repetition $(^{n+k-1}_k)$.
I am quite a bit confused if it is possible to derive the formula for the second case from the first one? Could, please, somebody explain me the reasoning behind such derivation or point me in the right direction for search?
Thanks a lot in advance!
Best Answer
So in 1) you are correct. As for 2), think about it the following way: take the $N$ balls and take $M-1$ indistinguishable sticks that will serve as separator walls between the balls. Now put the $N$ balls and $M-1$ sticks in a row in any order you want. So if '$*$' symbolises a ball and '$|$' a stick, you'll have something like: $$* * | * | * * * | * * * | * $$ or $$| * * * * * ||* | * * * *$$ if for the sake of an example you have 10 balls and 5 boxes (that is $5-1=4$ sticks). Now take all the balls before the first stick, and put them in the first box (if there aren't any, put all $0$ of them into the box). Similarly, take all the balls between the first and second stick, and put them in the second box, and so on. At least, the balls before the $m-1$th stick go into the $m-1$th box, and the rest of the balls go into the $m$th box. In the two examples, we would have the following number of balls in each box: $$2 | 1 | 3 | 3 | 1$$ and in the second example $$0 | 5 | 0 | 1 | 4$$So the order of the $m-1$ sticks and $n$ balls told you exactly how many balls go in which box (and you could reconstruct the order of the sticks and balls if you have them in the boxes). Also different orders of sticks and balls correspond to different ways of putting the balls in the boxes.
So it is sufficient to tell in how many different ways can you put $M-1$ indistinguishable sticks and $N$ indistinguishable balls in a row. Now, if you want to put these $N+M-1$ objects in a row, you could do it as follows: you first choose the $M-1$ places (out of the $N+M-1$) where you put the sticks in the row. You can do this in ${N+M-1 \choose M-1}$ different ways. After this, you don't really have much choice left, you have to put the $N$ balls in the remaining $N$ places - as the balls are indistinguishable, you can only do that in one way.
In the end, we see that you can put $N$ indistinguishable balls in $M$ boxes in ${N+M-1 \choose M-1}$ different ways, that is equal to the number of different ways you can place $N$ indistinguishable balls and $M-1$ indistinguishable separator sticks in a row.*
*You could just as well choose where the $N$ balls go first, and only then put the $M-1$ sticks in the remaining $M-1$ places. If we count this way, we get ${N+M-1 \choose N}$ different orders. But we counted the same thing, only in two different ways, hence the two results must be equal. So we get ${N+M-1 \choose M-1}={N+M-1 \choose N}$ as a corollary.
Your answer of ${n+k-1 \choose k}$ was correct, in case $n$ stands for $M$, the number of boxes and $k$ stands for $N$, the number of balls.