Let's say I have $r$ identical balls to be put in $n$ boxes, without any restriction in the number of balls I can put in each box. For example, the following configuration would be one possibility for $10$ balls in $6$ boxes:
My question is: In how many distinct ways can we do this:
I've tried the following reasoning:
- If $r=0$, we have $1$ possibility.
- If $r=1$, then we have $n$ possibilites (one for each box).
- If $r=2$, then we will have $n$ possibilites for the first ball and $n$ possibilites again for the second, so that would be $n^2$. But we must notice that the balls are identical, and so we divide by $r!$ to avoid multiple counting. So: $n^2/2!$.
- If $r=3$, then we have $n$ possibilities for all the three balls, and hence $n^3$. However since the balls are identical, the total number of possibilities is $n^3/3!$.
In general we would conclude that the total number $N$ would be then $$N = \frac{n^r}{r!}$$ However, my professor used the generating function method (which is not clear to me WHY it works): Creating the polynomial: $$(1+x+x^2+ \cdots +x^r)^n$$ If $r \rightarrow \infty$ and $|x|<1$ this is just a geometric series, $(1-x)^{-n}$. Applying Taylor's expansion gives us: $$\sum_{k=0}^{\infty} {n+k-1\choose k} x^k$$ And hence the total number of possibilites would be $$n+k-1 \choose k$$ Question: What is wrong with my reasoning and why it gives incorrect results? Some explanation on why this polynomial method works would also be appreciated.
Thanks in advance.
Let's go back to the case with $r=2$. If you put one ball in the first box and the other in the last one, that is same of starting by putting a ball in the last box and the other in the first. In resume, since the balls are identical you are overcounting.
The best way that I know to solve these problems is following. Assume $r = 5$ balls and $n = 3$ boxes. Then, just like in your picture, one possibility is $$00|00|0$$ which corresponds to 2 balls (zeros) in the first box, 2 in the second and 1 ball in the third box. Basically, we are using | to separate the contents of the boxes. Thus, the number of possibilities comes from how many ways we can change the position of these objects. In this example $${5+2 \choose 2}$$ and in general $${n+r-1 \choose n-1} = {n+r-1 \choose r}.$$