3
$\begingroup$

Suppose you want to distribute 15 identical candies to 5 different children.

a) In how many ways can this be done if every kid receives at least one piece of candy?

b) In how many ways can this be done if child A is to be given exactly 4 candies?

c) In how many ways can this be done if child C and child D receive exactly 7 candies together?

d) In how many ways can this be done if no kid receives more than 6 candies?

e) In how many ways can this be done if every kid ends up with a different number of candies? (i.e. A = 2, B = 3, C = 4, D = 1, E = 5)

\ \

My attempts:

a) First I gave each of the kids one piece of candy so I was left with 10 dots and 4 slashes (separating the distinct children). So I ended up with ${10+4\choose 4}$ = ${14\choose 4}$ ways.

b) Again I gave child A four candies and so I was left with 11 candies. In addition, I took child A way from consideration to ensure he received exactly four candies and thus I was left with 11 dots and 3 slashes, separating the 4 remaining distinct children. So I ended up with ${11+3\choose 3} = {14\choose 3}$ ways.

c) Again I gave both child C and D 7 candies collectively and took them away from consideration. I was left with 8 candies and 2 slashes, separating the 3 distinct remaining children. So I ended up with ${8+2\choose 2} = {10\choose 2}$ ways.

I am struggling with d and e quite a bit. For d I wanted to assign 7 candies to a child and them take them away from consideration, but if I were to do this another child could receive >6 candies since there would be 8 remaining candies with no restrictions to which of the four children would receive a specific amount of candies.

For e I would assume we would play around assigning different children different amounts of candies and then work with the remaining amount of candies to distribute among the children but I'm really not even sure where to start with this one...

Would someone mind checking my responses for a, b and c and then assisting with d and e?

$\endgroup$
0
$\begingroup$

Your answers to the first two questions are correct.

In how many ways can $15$ indistinguishable candies be distributed to five children if child $C$ and child $D$ receive $7$ candies together?

We must distribute seven candies among the children $C$ and $D$ and eight candies among the children $A$, $B$, and $E$. The number of ways we can distribute the candies to children $C$ and $D$ is eight since $C$ must receive between $0$ and $7$ candies inclusive, with $D$ receiving the rest. The number of ways the remaining eight candies can be distributed to the children $A$, $B$, and $D$ is $$\binom{8 + 3 - 1}{3 - 1} = \binom{10}{2}$$ as you correctly found. Hence, the number of ways of distributing to the five children if $C$ and $D$ receive exactly seven candies between them is $$\binom{7 + 2 - 1}{2 - 1}\binom{8 + 3 - 1}{3 - 1} = \binom{8}{1}\binom{10}{2}$$

In how many ways can $15$ indistinguishable candies be distributed to five children if no child receives more than six candies?

Let $x_i$, $1 \leq i \leq 5$, be the number of candies received by the $i$th child. Then we seek the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 15 \tag{1}$$ in the nonnegative integers subject to the restrictions that $x_i \leq 6$ for $1 \leq i \leq 5$.

A particular of equation 1 corresponds to the placement of four addition signs in a row of $15$ ones. For instance, $$1 1 1 + 1 1 1 1 + 1 1 + + 1 1 1 1 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 4$, $x_3 = 2$, $x_4 = 0$, and $x_5 = 6$. The number of such solutions is the number of ways we can place four addition signs in a row of fifteen ones, which is $$\binom{15 + 5 - 1}{5 - 1} = \binom{19}{4}$$ since we must choose which four of the nineteen positions required for fifteen ones and four addition signs will be filled with addition signs.

By similar reasoning, the number of solutions of the equation $$x_1 + x_2 + x_3 + \cdots + x_n = k$$ in the nonnegative integers is $$\binom{k + n - 1}{n - 1}$$ since we must choose which $n - 1$ of the $k + n - 1$ positions required for $k$ ones and $n - 1$ addition signs will be filled with addition signs.

From these, we must subtract those cases in which at least one child receives more than six candies. Observe that at most two children could receive more than six candies since $2 \cdot 7 = 14 < 15 < 21 = 3 \cdot 7$.

Suppose a child receives more than six candies. There are five ways to choose that child. We give that child seven candies. The remaining eight candies can be distributed among the five children in $$\binom{8 + 5 - 1}{5 - 1} = \binom{12}{4}$$ ways. Hence, there are $$\binom{5}{1}\binom{12}{4}$$ ways to distribute the candies in such a way that a child receives more than six candies.

However, if we subtract this amount from the total, we will have subtracted too much since we have counted each case in which two children receive more than six candies twice, once for each way of designating one of those children as the child who received more than six candies. We only want to subtract those cases once, so we must add those cases back.

Suppose two children each receive more than six candies. There are $\binom{5}{2}$ ways to select those two children. Give each of them seven candies. That leaves one candy to distribute among the five children, which can be done in five ways. Hence, the number of distributions in which two children receive more than six candies is $$\binom{5}{2}\binom{1 + 5 - 1}{5 - 1} = \binom{5}{2}\binom{5}{4}$$

By the Inclusion-Exclusion Principle, the number of ways of distributing $15$ indistinguishable candies to five children so that no child receives more than six candies is $$\binom{19}{4} - \binom{5}{1}\binom{12}{4} + \binom{5}{2}\binom{5}{4}$$

In how many ways can $15$ indistinguishable candies be distributed to five children if each child receives a different amount of candies.

List the ways $15$ can be expressed as a sum of five distinct nonnegative numbers, starting with $$0 + 1 + 2 + 3 + 9 = 15$$ and ending with $$1 + 2 + 3 + 4 + 5 = 15$$ For each of these ways (there are not many), there are $5!$ ways to distribute the candies to the children, depending on which child receives which number of candies.

$\endgroup$

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.