Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
What's your question? –  Patrick Li Jan 16 '13 at 20:50
add comment

2 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
    
$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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.