# In how many ways can 5 different balls be packed in 5 different boxes such that 3 boxes are non-empty?

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?

-
What's your question? –  Patrick Li Jan 16 '13 at 20:50

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$.

-

For the first question, first you choose the 3 boxes where you intend to put in the balls. This can be done in $\binom 53=10$ ways. Let the labels of the chosen boxes be $A,B$ and $C$. Now you want to associate to each one of the balls (i didn't say "your" balls ;-) ), say a,b,c,d,e, one of the boxes $A,B$ or $C$, in such manner that each one of the boxes is associated to at least one ball. In other words, you are looking for surjections from $\{a,b,c,d,e\}$ onto $\{A,B,C\}$. The number of such surjections is $3!St(5,3)$, where $St(5,3)$ is a Stirling number of the second kind (see here). Thus, the required number is $60\cdot St(5,3)$.

For the second question, since your boxes are unlabelled, then your problem amounts to fill 3 unlabelled boxes with 5 unlabelled balls, none of the boxes empty. Equivalently, you need to partition 5 into a sum of three positive numbers, which can be done only in two ways, namely, 1+1+3 and 1+2+2.

-
$S(n,k)$ is the number of partitions, not surjections, so the number $S(5,3)$ should be multiplied by $3!=6$ to get the number of surjections. –  David Moews Jan 17 '13 at 9:57
@DavidMoews You are right, thank you. Correcting now. –  Matemáticos Chibchas Jan 18 '13 at 19:15