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.

I encountered this problem in my probability class, and we weren't able to solve it, so I would like to know the answer.

If you have $m$ balls and $n$ boxes, with $n < m$, and you insert the balls into the boxes randomly, what is the probability that all the boxes have at least one ball in it?

The problem doesn't specify if the balls are distinguishable or not, so you may assume either, so another question would be, if you assume they are distinguishable will you get the same answer as assuming they are not distinguishable? (This would be great because I think the non-distinguishable case is easier).

I appreciate any insight on the problem.

share|improve this question
    
Note that a distinction may also need to be made whether the boxes are distinguishable or not. In total, there are 4 possible interpretations of the question. –  Lie Ryan Mar 12 '11 at 15:32
1  
The distinguishable case is easier. This is actually a rephrasing of the "coupon collector problem"; if you've heard of that problem, great, and if it's not, you have another term to search for. –  Michael Lugo Mar 12 '11 at 15:53
    
As a probability question, I think you can only use counting methods if each possibility has equal probability. That will only happen if you use distinguishable balls (first, second, third etc.) and boxes (left, next to right, etc.). –  Henry Mar 12 '11 at 16:05

3 Answers 3

up vote 10 down vote accepted

This answer treats the balls and boxes as distinguishable so each pattern is of equal probability. I doubt there is a practical experiment to test this which does not also have them distinguishable.

The number of ways of putting $m$ balls in $n$ boxes is $n^m$ since each ball can go in any of the boxes.

The calculation for the number of ways of putting $m$ balls in $n$ boxes with each box having at least one ball is more complicated. Let's call it $A(m,n)$. If, when deciding what to do with the last ball, all the other boxes are full, then it can go in any of the $n$ boxes; if however one of the $n$ boxes is empty and the others full then it must go in the empty one. So $$A(m,n) = n A(m-1,n) + n A(m-1,n-1)$$ and clearly $A(m,1) = 1$ (there is only one way with one box) and $A(m,n) = 0$ for $m<n$. It turns out that $$A(m,n) = n! \, S_2 (m,n)$$ where $S_2$ means Stirling numbers of the second kind (OEIS A019538). $A(n,n)=n!$ as one would expect.

So the probability that all the boxes have at least one ball is $$ \frac{n! \, S_2 (m,n)}{n^m}.$$

For example, with 3 balls and 2 boxes, this gives $\frac{2 \times 3}{8} = 3/4$.

share|improve this answer
    
+1: Can you please make the last sentence the first, so the assumptions becomes clearer to people. –  Aryabhata Mar 14 '11 at 15:43
    
@Moron: So moved. I have also added an equal probability point to that paragraph. –  Henry Mar 14 '11 at 16:27

Let S be the number of ways to distribute m balls into n boxes with no restriction and T be number of ways to distribute m balls into n boxes with each boxes having at least one balls.

If we can calculate S and T, then the probability that all the boxes have at least one ball in it is simply $\frac T S$.

First, we count the number of ways to distribute m balls into n boxes with no restriction. In other words, the number of solutions to the equation:

$$x_1 + x_2 + x_3 + ... + x_n = m$$

We can calculate this with: $S = {m+n-1 \choose n-1}$

Second, we count the number of ways to distribute m balls into n boxes, with the restriction that all boxes have at least 1 balls. In other words, the number of solutions to the equation:

$$x_1 + x_2 + x_3 + ... + x_n = m \textrm{ where } x_i >= 1 \textrm { for all } i = 1..n$$

Let's reformulate this second question. Let's put a single ball into each boxes ($x_i = y_i + 1$) and then distribute the other $m-n$ balls:

$$(y_1 + 1) + (y_2 + 1) + (y_3 + 1) + ... + (y_n + 1) = m$$ $$y_1 + y_2 + y_3 + ... + y_n = m-n$$

So now, we can calculate $T = {(m-n)+n-1 \choose n-1} = {m-1 \choose n-1}$

Therefore, the probability of each box having at least one ball is

$$ \frac T S = \frac {m-1 \choose n-1} {m+n-1 \choose n-1} = \frac {(m-1)!m!} {(m-n)!(m+n-1)!} $$

share|improve this answer
    
I'm not sure, but shouldn't $S = {n+m-1 \choose m}$? Lets take simple case where $m=2$ and $n=1$. There is only one way to put two balls into one box, but according to your solution it is equal to $S = {1+2-1 \choose 1}= {2 \choose 1}=2$ –  Tomek Tarczynski Mar 12 '11 at 10:36
    
@Tomek Tarczynski: Well spotted, I've fixed it now. Thanks. Note that $S = \binom {m+n-1} {m} = \binom {m+n-1} {n-1}$, I've chosen the latter version for consistency with T. –  Lie Ryan Mar 12 '11 at 11:34
    
@Lie Ryan: You can also simplify a bit the final result $\frac{T}{S}=\frac{(m-1)!m!}{(m-n)!(m+n-1)!}$ –  Tomek Tarczynski Mar 12 '11 at 11:43
1  
@Henry: I suppose it depends on how you choose to insert the balls into the boxes (eg: see the question linked in Sivaram's answer). FWIW, I agree with your interpretation, the balls and boxes being distinguishable seems more natural to me and I interpret the process as: choose a random box for ball 1, then for ball 2 etc. The statement, "this is a probability question, not a counting question" is misleading, though. Your answer also uses a counting method to compute the probabilities :-) –  Aryabhata Mar 14 '11 at 15:55
1  
@Moron: I tried to suggest that if using counting methods to answer probability questions then you need to ensure each thing being counted is of equal probability, so you don't have the same freedom over distinuishable/indistinguishable issues. My apologies if this was not clear –  Henry Mar 16 '11 at 13:29

I have provided the solution to a similar problem here. The solution has the general case worked out as well.

share|improve this answer

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.