12 donuts split to 5 children

Suppose you buy 12 identical donuts and wish to give them to the 5 children you are babysitting. How many different ways can you distribute the donuts if: (a) there are no restrictions

My answer for this question is,

A) Combination with Repetition: (n+r-1,r) = (12+5-1,5) = (16,5)

B) But some people are getting different answers: (n+r-1,r) = (12+5-1,4) = (16,4) using the logic: 00|00|0000|000|0 there need to be 4 dividers to divide into 5 groups.

Please tell me which one is the right answer.

• You have slightly misstated (B). Correctly stated it is the right answer: ${n+r-1\choose r-1}$. Take a row of 16 zeros and pick 4. Child A gets the number of 0s to the left of the first picked 0. Child B gets the number strictly between the first and second picked 0s and so on. – almagest Sep 22 at 20:29
• Your problem on (A) is that you have muddled $n$ and $r$. It is often expressed as $k$ things between $n$ people or $x_1+\dots+x_n=k$ and the answer is ${n+k-1\choose k}$ but here $n$ is playing the role of $r$ and $k$ is playing the role of $n$. Note that ${n+k-1\choose k}={n+k-1\choose n-1}$. So combination with repetition actually gives the same answer ${16\choose4}={16\choose12}$. – almagest Sep 22 at 20:50

The correct formula is $$\binom{n+k-1}{k-1}=\binom{n+k-1}{n}.$$

To understand why this is, consider $$n$$ indistinguishable balls, and we need to put them into $$k$$ groups. Now, imagine for each group, we can separate them with dividers.

From here, we see we need $$k-1$$ dividers. Let's take a quick example:

How many ways are there to place $$5$$ indistinguishable balls into $$3$$ boxes?

Solution. We divide the groups by bars - for example, one possible way is $$**||***$$ As you can see, there are three groups:

• Group $$1$$: $$2$$ balls.
• Group $$2$$: $$0$$ balls.
• Group $$3$$: $$3$$ balls.

Another one would be like $$*|**|**$$ Experimenting with this a bit more, we see that we're just arranging $$5$$ balls and $$2$$ dividers, which can be done in $$\binom {5+2}2 = 21 \text{ ways}. \: \square$$

Now, for the general case:

We have to place $$n$$ balls in $$k$$ groups, which needs $$k-1$$ dividers. Then, using the example above, we conclude that there are $$\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$$ ways to do this.

Let $$x_1, x_2,...,x_5$$ be the kids, so we could model this problem as $$x_1+x_2+x_3+x_4+x_5=12$$ (because the donuts are identical).

This can be solved with a combination with repetition: $${5+12-1}\choose{12}$$ = $${16}\choose{12}$$.

Edit:

Another way of thinking this is suppose we have to place 12 balls in 5 containers. The balls are identical and the containers are not. Say those (°°°°°°°°°°°°) are the 12 balls.

1. First we take 2 balls and place it in a container. Now we have 12-2 balls left. We are going to represent this as (°°|°°°°°°°°°°).
2. Again we take 4 balls and we place them in the second container. Now we have °°|°°°°|°°°°°°.
3. Again we take another 3 balls and we place them in the 3rd container: °°|°°°°|°°°|°°°.
4. Again we take another ball and place it in the 4th container: °°|°°°°|°°°|°|°°.

5. Now we have 2 balls left, which we put them in the 5th container.

In how many ways can we place the four | in the 16 spaces we have?

• but my q is why is r 12 or 4, should it not be 5 because there are 5 children? – AlphaDJog Sep 22 at 20:43
• Tim Hortons sells 20 different kinds of donuts and always has at least a dozen of each type available. How many different ways can someone buy a dozen donuts? so in this case would this be (31,11) or (31,12) – AlphaDJog Sep 22 at 20:44
• Check my edit @SkandanVecham – Moria Sep 22 at 21:03
• That helps, as to what evers left foes into the last container thank you. – AlphaDJog Sep 22 at 21:32

Sounds like you are struggling with a formula. Maybe it will help to change the numbers so you can easily tell what the result will be. Assume there is $$1$$ kid rather than $$5$$. Is the correct number of ways to distribute $$12$$ donuts to $$1$$ child $$\binom{12}1$$ or $$\binom{12}0$$?

• (12,0), but for this q: Tim Hortons sells 20 different kinds of donuts and always has at least a dozen of each type available. How many different ways can someone buy a dozen donuts? Would the answer be (31, 20) or would it be (31,19). – AlphaDJog Sep 22 at 20:59
• @SkandanVecham Seems that the same stars and bars logic as in B. still applies. I couldn't refute the logic of it for the original question or for this one. – Mike Sep 22 at 21:10