Combinatorics – Distributing 5 distinct candies to 3 different children making sure each child gets at least one candy

combinationscombinatorics

I've been preparing even more for the AMC8, and I've found a new type of question I'm not sure how to do:

There are $5$ distinct candies that are to be distributed to $3$ different children. However, to make sure no child gets upset, each child should receive at least one candy. How many ways are there to do this?

Now I know how we can do a similar problem, where the candies are all the same as each other, but I'm not sure how to approach this if they are distinct, especially with the condition that each child should receive one candy. But I do know that if there were only $4$ candies instead, then that would mean that one kid would have to get $2$ candies, while the rest only get $1$. And from there, I could simply computer that the kid who gets a second candy can be chosen in $3$ ways and the two candies they get would be chosen in $5$ choose $2$ ways. And then multiplying this by $2!$ for the rest of the children would get the answer. But my question is, is there an easy way to expand this logic to $5$ candies (like the question above asks), and is there perhaps a formula I could use for even larger cases under the same restrictions?

Best Answer

We can consider two cases: one child receives three candies and the others each receive one, or two children each receive two candies and the other child receives one.

One child receives three candies and the others each receive one: There are three ways to select the select who receives three candies, $\binom{5}{3}$ ways to select which three of the five candies that child receives, and $2!$ ways to distribute the remaining candies to the remaining children so each of them receives one candy. Hence, there are $$\binom{3}{1}\binom{5}{3}2! = 60$$ such distributions, as you found in the comments.

Two children each receive two candies and the other child receives one: There are $\binom{3}{2}$ ways to select the children who will receive two candies. There are $\binom{5}{2}$ ways to give two of the five candies to the younger of those two children and $\binom{3}{2}$ ways to give two of the remaining three candies to the older of those two children. The remaining child must receive the remaining candy. Hence, there are $$\binom{3}{2}\binom{5}{2}\binom{3}{2} = 90$$ such distributions.

Total: Since the above cases are mutually exclusive and exhaustive, there are $$\binom{3}{1}\binom{5}{3}2! + \binom{3}{2}\binom{5}{2}\binom{3}{2} = 150$$ ways to distribute five candies to three children so that each child receives at least one candy.


This problem can also be solved using the Inclusion-Exclusion Principle. There are three possible recipients for each candy, so there are $3^5$ possible distributions.

From these, we subtract those in which a child does not receive a candy. There are three ways to exclude one of the children from receiving a candy and $2^5$ ways to distribute the candies to the remaining children. There are $3 \cdot 2^5$ such cases.

However, if we subtract $3 \cdot 2^5$ from the total, we will have subtracted too much since we will have subtracted the three cases in which all the candies are given to one child twice, once for each way of designating one of the children who has not received a candy as the child who does not receive a candy.

Therefore, we must add those three cases to our running total, which yields $$3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5 = 150$$ ways to distribute five candies to three children so that each child receives at least one candy.