13
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Lie Ryan
    Mar 12, 2011 at 15:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Lugo
    Mar 12, 2011 at 15:53
  • $\begingroup$ 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.). $\endgroup$
    – Henry
    Mar 12, 2011 at 16:05

3 Answers 3

Reset to default
14
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +1: Can you please make the last sentence the first, so the assumptions becomes clearer to people. $\endgroup$
    – Aryabhata
    Mar 14, 2011 at 15:43
  • $\begingroup$ @Moron: So moved. I have also added an equal probability point to that paragraph. $\endgroup$
    – Henry
    Mar 14, 2011 at 16:27
4
$\begingroup$

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)!} $$

$\endgroup$
8
  • $\begingroup$ 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$ $\endgroup$
    – Tomek Tarczynski
    Mar 12, 2011 at 10:36
  • $\begingroup$ @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. $\endgroup$
    – Lie Ryan
    Mar 12, 2011 at 11:34
  • $\begingroup$ @Lie Ryan: You can also simplify a bit the final result $\frac{T}{S}=\frac{(m-1)!m!}{(m-n)!(m+n-1)!}$ $\endgroup$
    – Tomek Tarczynski
    Mar 12, 2011 at 11:43
  • 1
    $\begingroup$ @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 :-) $\endgroup$
    – Aryabhata
    Mar 14, 2011 at 15:55
  • 1
    $\begingroup$ @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 $\endgroup$
    – Henry
    Mar 16, 2011 at 13:29
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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