Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Hint: the objects are identical. –  Yuval Filmus Jun 24 '11 at 6:09
    
Additional hint: try it for some small case like $n=r=2$. –  Gerry Myerson Jun 24 '11 at 6:48
    
Actually, each of the $n$ objects has only $r$ choices ("none at all" is not an option). And because the objects are identical, $r^n$ definitely overcounts, since you are taking into account the order in which you distribute the elements. –  Arturo Magidin Jun 24 '11 at 18:48
    
The balls are not distinguishable. That's why it's not (r+1)^n –  user16967 Oct 1 '11 at 10:43

4 Answers 4

up vote 8 down vote accepted

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$.

share|improve this answer

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).$$

share|improve this answer

$C(n+r-1, r-1)$ is the answer for distribution of $n$ identical objects among $r$ persons. Not for the groups, because groups are considered as identical it do not have name. Example: two identical balls can to be distributed among two persons in three ways: $\left\{ (2,0), (0,2), (1,1)\right\}$. But when we go for groups, $(2,0)$ and $(0,2)$ are considered as the same, so now the answer will be only two.

share|improve this answer

let there be places to put the object numbered as 1,2,3,4,......,n. Let there be distinct r objects namely A,B,C,D,....... Now lets assume that the objects to be distributed are distinct. now that i have r+1 choices to put each object at a place lets say that on distributing, B and D were put at the place number 2 that is 2 gets two objects but 2 could also have gotten A C or E F or any other pair. when you think of putting a object at r+1 places u take into account which two object u placed now if all the object were to be identical say A,A,A,A,A,....(r) all the pairs BD AC EF would become AA AA AA ... hence repeating the cases when 2 got AA pair hence (r+1)^n would give you a greater value .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.