5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – almagest Sep 22 '19 at 20:29
  • 1
    $\begingroup$ 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}$. $\endgroup$ – almagest Sep 22 '19 at 20:50
2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ but my q is why is r 12 or 4, should it not be 5 because there are 5 children? $\endgroup$ – AlphaDJog Sep 22 '19 at 20:43
  • $\begingroup$ 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) $\endgroup$ – AlphaDJog Sep 22 '19 at 20:44
  • $\begingroup$ Check my edit @SkandanVecham $\endgroup$ – Moria Sep 22 '19 at 21:03
  • $\begingroup$ That helps, as to what evers left foes into the last container thank you. $\endgroup$ – AlphaDJog Sep 22 '19 at 21:32
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ (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). $\endgroup$ – AlphaDJog Sep 22 '19 at 20:59
  • $\begingroup$ @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. $\endgroup$ – Mike Sep 22 '19 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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