[Math] Combinatorics question involving distributing 9 different candies to three different kids

combinationscombinatoricsinclusion-exclusion

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?

Best Answer

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.