Combinatorics question involving distributing 9 different candies to three different kids

Question

Nine different chocolate bars are to be distributed to 3 different kids.

a) In how many ways can this be done if there are no restrictions?

b) In how many ways can this be done if the child A receives exactly four chocolate bars?

c) In how many ways can this be done if each kid gets at least one chocolate bar?

I'm pretty confident with the first two parts (a and b)

Here is my work:

a) Since there are no restrictions we can assign the kids to the chocolate bars in $3^9$ ways.

b) Since the first child must get four candies we can assign the candies to him in ${9\choose 4}$ ways. Then we can assign the rest of the candies using the same logic from part a in $2^5$ ways. So there are $2^5$${9\choose 4}$ ways.

c) I'm confused here because I did this problem in two distinct methods and did not obtain the same answer in the slightest...

$\textbf{Method 1:}$ Assign 3 candies to three kids: This can be done in 9×8×7 ways but we also have to consider that there are 3! arrangements of the kids. Then we need to assign the remaining candies to the kids, which can be done in $3^6$ ways. So in this first method I obtained $3^6$×3!×(9×8×7) ways = 2,204,496 ways.

$\textbf{Method 2:}$ I then tried using the inclusion exclusion principle. First I saw that there were $3^9$ ways to assign the kids to the candies in total. And then I took the cases in which one of the three kids received no candies. For each of the three kids this would be $2^9$ and thus would be $3×2^9$ for the kids collectively. However, we would have to add back the case in which none of the three kids received a candy, which would be 3. Thus the answer would be $3^9 - 3×2^9 + 3$ ways.

I'm really not sure which of part c or if either are correct at all...but could someone also check my answers for part a and part b?

Answer 1

Your method $1$ with restrictions far exceeds $3^9$ with no restrictions.

Your method $2$ is close. You didn't consider the case where $2$ children receive no candy and also, there isn't a case where all $3$ receive no candy (that wouldn't be a valid distribution of the candy).

Like you said, there are $3$ ways for one child to receive no candy and for each of those there are $2^9$ ways for the other $2$ children to receive the candy.

There are $3$ ways for $2$ children to have zero candy and for each of those there is only one way for the other child to have all $9$ candies.

c) $3^9 - 3\cdot 2^9 - 3 = 18144$

Answer 2

Your answers to the first two questions are correct, as is your second method for the third problem.

Your first method for the third problem over counts. To see this, suppose the candy bars the children receive are $A, B, C, D, E, F, G, H, I$. You count each distribution multiple times. For instance, if we give $A, B$ to the first child, $C, D, E$ to the second child, and $F, G, H, I$ to the third child, your method counts this case $2 \cdot 3 \cdot 4 = 24$ times, once for each of the two ways of designating one of the candy bars the first child receives as the candy bar reserved for that child, once for each of the three ways of designating one of the three candy bars received by the second child as the candy bar reserved for that child, and once for each of the four ways of designating one of the four candy bars the third child receives as the one reserved for that child. To illustrate a few ways you count this distribution, consider the following table.

\begin{array}{c | c |c | c | c | c} R_1 & R_2 & R_3 & A_1 & A_2 & A_3\\ \hline A & C & F & B & D, E & G, H, I\\ B & C & F & A & D, E & G, H, I\\ A & D & F & B & C, E & G, H, I\\ B & D & F & A & C, E & G, H, I\\ A & E & F & B & C, D & G, H, I\\ B & E & F & A & C, D & G, H, I \end{array} where $R_i$, $1 \leq i \leq 3$, denotes the candy bar reserved for the $i$th child, and $A_i$, $1 \leq i \leq 3$, represents the additional candy bars received by the $i$th child.

Answer 3

a) the species formula is $E(X).E(X).E(X)$; the $egf = exp(x)^3$ and the coefficient of $x^9 = 19683$

b) the species formula is $E_4(X).E(X).E(X)$; the $egf = {x^4 \over 4!}*exp(x)^2$ and the coefficient of $x^9 = 4032$

c) the species formula is $E^+(X).E^+(X).E^+(X)$; the $egf = (exp(x)-1)^3$ and the coefficient of $x^9 = 18150$

If we want to obtain the three numbers above in a more "terrestrial" way, we will have to consider the generating functions :

a) $GF = (1+x+x^2+...+x^9)^3$ and the coefficient of $x^9 = 55$

b) $GF = x^4(1+x+x^2+...+x^9)^2$ and the coefficient of $x^9 = 6$

c) $GF = (x+x^2+...+x^9)^3$ and the coefficient of $x^9 = 28$

The number shows types of distribution. For example, that there are $55$ ways to express $9$ as a sum of three terms $9=0+0+9, \ \ 9 = 0+1+8, \dots$, order matters.

For each of the 55 types we have to compute the distribution, eg. for 9 = 2+3+4 we have to take into account $\binom {2+3+4}{2,3,4}$

Then we sum all the 55 (or 6, or 28) numbers.