Number of ways to distribute 5 distinguishable balls between 3 kids such that each of them gets at least one ball

How many ways are there to distribute 5 distinguishable balls between 3 kids such that each of them gets at least one ball?

My approach is $ \binom{5}{3} 3! $ + $ \binom{2}{2} \binom{3}{2}2!$ which is equal to $66$?

Solution 1:

It’s not the quickest or most elegant approach, but this problem is straightforwardly done by considering cases. If each kid gets at least one ball, the balls must be distributed either $3$-$1$-$1$ or $2$-$2$-$1$.

• $3$-$1$-$1$: There are $\binom31=3$ ways to choose which kid gets $3$ balls, and $\binom53=10$ ways to choose $3$ balls for that kid. There are then $2$ ways to distribute the remaining $2$ balls to the other $2$ kids. This case therefore accounts for $3\cdot10\cdot2=60$ possible distributions.

• $2$-$2$-$1$: There are $3$ ways to choose which kid gets only $1$ ball, and $5$ ways to pick the ball for that kid. There are then $\binom42=6$ ways to choose which $2$ balls go to the next kid in line, and the remaining kid gets the remaining $2$ balls. This case accounts for another $3\cdot5\cdot6=90$ possible distributions.

The correct total, therefore, is $60+90=150$.

Added: It appears to me that you reasoned something like this: First we choose $3$ of the $5$ balls and distribute one of them to each kid; that can be done in $\binom533!$ ways. Then we take both of the remaining $2$ balls, pick $2$ of the $3$ kids, and distribute the last $2$ balls in one of the $2$ possible ways to the $2$ lucky kids. There are several problems with this approach.

1. You’ve considered only the second of my two cases.

2. You’re combining the results of successive choices, not the counts of disjoint cases, so you should be multiplying, not adding: $\binom533!\cdot\binom22\binom322!=60\cdot6=360$.

3. You’re overcounting. Suppose that the balls are labelled A, B, C, D, and E. Then you’ve counted the distribution AD | BE | C four times:

   • once as the result of distributing A, B, and C in the first step and then distributing D and E to the first and second kids in the second step;
   • once as the result of distributing D, B, and C in the first step and then distributing A and E to the first and second kids in the second step;
   • once as the result of distributing A, E, and C in the first step and then distributing D and B to the first and second kids in the second step; and
   • once as the result of distributing D, E, and C in the first step and then distributing A and B to the first and second kids in the second step.

Solution 2:

There is a reasonably nice Inclusion/Exclusion way of counting. Forget temporarily about the at least one ball restriction. For each ball, there are $3$ choices for who will get it, for a total of $3^5$.

Now let's count the bad distributions, where one or more kid is left out. We can choose who gets left out in $\binom{3}{1}$ ways. For each choice, there are $2^5$ ways to distribute the balls, for a total of $\binom{3}{1}2^5$.

However, we have double counted the distributions in which a kid gets all the balls, so we must subtract $3$.

It follows that there are $93$ bad distributions. Subtract this from the $3^5=243$.

Remark: The idea generalizes.