Number of ways of distributing $n$ identical objects among $r$ groups

I came across this formula in a list: The number of ways of distributing $n$ identical objects among $r$ groups such that each group can have $0$ or more $(\le n)$ objects

I know that standard way of doing this is to solve the problem of distributing n identical objects and $(r-1)$ partitions among themselves which can be done in $C(n+r-1,r-1)$ ways.

But I am unable to prove to myself why it is not $(r+1)^n$. Because each of the n objects has r+1 choices, either group1, group2,... group r or none at all.

Solution 1:

The post quotes the standard expression for the number of ways of distributing $n$ identical objects among $r$ groups. The wording used seems to indicate that you are aware of the counting argument that leads to this expression. In case I am wrong about that, please look at the Wikipedia Stars and Bars article.

What is meant by "prove to myself why it is not $(r+1)^n$?" I will write about this question for a while, and towards the end describe reasoning that might be connected with your $(r+1)^n$.

Let us first look at a simpler question, proving that it is not $(r+1)^n$. If you can find even a single pair $(r, n)$ of integers for which the expression $(r+1)^n$ gives the wrong answer, you will know that $(r+1)^n$ is not (always) correct.

To do this, just follow the excellent suggestion of Gerry Myerson. Look at a small example, like $r=2$, $n=2$. In how many ways can you distribute $2$ identical jelly beans between two people, $A$ and $B$? Maybe $A$ gets both of them. Maybe $B$ does. Maybe $A$ gets one and $B$ gets one. That's all, the total number of ways is $3$.

If the expression $(r+1)^n$ was correct for $r=2$, $n=2$, the number of ways would be $3^2$, which is clearly not equal to the correct answer $3$ that we are absolutely sure of. (We are absolutely sure because the count is so simple, so direct, that we could not possibly have made a mistake.) By the way, if you check, you will find that the expression $C(n+r-1,r-1)$ gives the right answer, for $C(3,1)=3$.

When you are trying to solve a combinatorial problem, it is important to experiment, to try to look at small cases where you can do the count "by hand." Unless the problem is very standard, that is the right way to start. And any concrete counting that you do can later serve as a check.

So we know that $(r+1)^n$, at least sometimes, gives the wrong answer. (Actually, it usually gives an answer that is much larger than the truth.)

Next let us try to deal with why $(r+1)^n$ gives the wrong answer. Is there any good reason to think that it should give the right answer? You think there might be. Let's look for a problem for which $(r+1)^n$ is the right answer.

I have $n$ distinct gifts to give out, to $r$ people, except that I may choose to not give out some of the gifts, and keep them for myself. For any gift, I have $r+1$ choices of what to do with it. Then there are $(r+1)^n$ ways to do the gift-giving. It is crucial here that the gifts be distinct.

I cannot see any direct connection between this gift giving and the problem of distributing $n$ identical objects among $r$ people.

If the gifts are distinct, and I cannot keep any of them, there are $r^n$ ways to do the distribution. One might think that then one could adjust this for the fact that the gifts are all identical. That kind of adjustment can be made when you count the number of $6$-letter "words" you can make using all the letters of CANADA. You first imagine the A's to be distinct, getting $6!$, and then divide by $3!$ to deal with the fact that the A's are not distinct. But such a strategy will not work for our distributing identical objects problem. It would grossly over count.

Any strategy for counting by thinking of giving out the objects one at a time quickly runs into trouble. It usually greatly overcounts the number of ways. For example, in how many ways can we distribute $n$ jelly beans among $2$ people, $A$ and $B$? Person $A$ can get $0$, or $1$, or $2$, and so on up to $n$, a total of $n+1$ possibilities. That's probably where your intuition about the $+{}1$ came from, though you applied it to $r$, not to $n$.

What about $n$ jelly beans and $3$ people? You might think there are $n+1$ ways to decide how many $A$ gets, and then $n+1$ ways to decide how many $B$ gets, with $C$ getting the rest. That argument would give a count of $(n+1)^2$. But that count would be incorrect. If you have $3$ people, and $8$ jelly beans, and have given $6$ to $A$, you can't then give $5$ to $B$. So although there are $n+1$ choices for how many to give to $A$, it is not true that for every one of these choices there are $n+1$ ways to decide how many to give to $B$.

Solution 2:

Lets consider there are $r-1$ blocks, so that, there will be $r$ spaces to be filled (including the left of the left most block and right of the right most block). Now, $n$ identical things should be filled in these spaces. There are $n+r-1$ things in that line now, which can be arranged in $(n+r-1)!$ ways.

But, we should avoid the arrangements between the $n$ things and $r-1$ blocks, since they are identical.

So, the final answer is $$\frac{(n+r-1)!}{n! (r-1)!} = C(n+r−1,r−1).$$