Number of ways in which 4 distinct balls can be given to three children if each child gets at least one.

Question

Though the question is simple, I tried it solving with a different approach. So what I did was, first I selected 3 balls from in $ 4C3 $ ways so that the condition gets satisfied and after that I distributed the remaining ball in 3 ways such that the total ways com out to be $ 4C3 * 3 = 72 $ ways which is not the correct answer. So can anyone tell me what's wrong with this approach? Thanks in advance.

Answer 1

Note that $\binom{4}{3} \cdot 3 = 4 \cdot 3 = 12$. Perhaps, you meant $P(4, 3) \cdot 3 = 72$.

In any such distribution, one child receives two balls and the others each receive one. There are three possible recipients of two balls, $\binom{4}{2}$ ways to select the two balls that child receives, and $2!$ ways to distribute the remaining balls to the remaining children. Therefore, there are $$\binom{3}{1}\binom{4}{2}2! = 36$$ ways to distribute four distinct balls to three children so that each child receives at least one ball.

Say the balls are blue, green, red, and yellow. If we give both the blue and green balls to Alice, the red ball to Bruce, and the yellow ball to Claire, your method counts this distribution twice, once when you designate the blue ball as the ball you give to Alice and the green ball as the additional ball you give her and once when you designate the green ball as the ball you give to Alice and the blue ball as the additional ball you give her.

$$ \begin{array}{c c c c} \text{Alice} & \text{Bruce} & \text{Claire} & \text{additional ball given to Alice}\\ \hline \text{blue} & \text{red} & \text{yellow} & \text{green}\\ \text{green} & \text{red} & \text{yellow} & \text{blue} \end{array} $$

In fact, you count every case twice for this reason. Notice that $$\color{red}{\binom{2}{1}}\binom{3}{1}\binom{4}{2}2! = \color{red}{72}$$

Answer 2

In your method, you are including many extra cases as N. F. Taussig has shown.

The easiest approach would be to use inclusion-exclusion principle.

Each ball can go to any of the three kids. Hence total cases $=3^4=81$

Cases where all balls go to 2 kids $={3\choose 2}{\cdot}2^4=48$

Cases where all balls go to 1 kid $={3\choose 1}{\cdot}1^4=3$

Cases where each kid gets atleast one ball $=81-48+3=36$