[Math] In how many ways can 5 different balls be packed in 5 different boxes such that 3 boxes are non-empty

combinatorics

Well, I have $5$ labeled balls and $5$ labeled boxes. I need to pack boxes with balls, such that $3$ boxes are non-empty ($2$ boxes are empty).
And how about if I need to pack $5$ unlabeled balls in $5$ unlabeled boxes, such that $3$ boxes are non-empty?

Best Answer

If the balls and boxes are labelled, there are $\binom53$ ways to choose the three non-empty boxes. Suppose that we’ve chosen the three boxes that are to be non-empty. There are $3^5$ ways to put the $5$ balls into those boxes, but some of those ways leave one or more of the three boxes empty. To correct for this we use an inclusion-exclusion argument.

Call the three chosen boxes Box 1, Box 2, and Box 3. There are $2^5$ ways to put the $5$ balls into Boxes 2 and 3, so that Box 1 remains empty. Similarly, there are $2^5$ ways to put the balls into Boxes 1 and 3, and $2^5$ ways to put the balls into Boxes 2 and 3. Thus, out of the $3^5$ arrangements of the balls in the three boxes, $3\cdot2^5$ leave a box empty and should be subtracted from the total to leave $3^5-3\cdot2^5$. But the arrangement that puts all $5$ balls into Box 3 got removed twice, since it leaves both Box 1 and Box 2 empty, and the same goes for the other two arrangements that put all $5$ balls into one of the three boxes. These should have been deducted only once from the original $3^5$, so we must add the $3$ back in, and the final count is

$$3^5-3\cdot2^5+3=243-96+3=150\;.$$

If the balls and boxes are both unlabelled, we simply want the number of partitions of $5$ into $3$ parts. This problem is small enough to be done by brute force: there are just two, $5=3+1+1$ and $5=2+2+1$.