$m$ balls $n$ boxes probability problem

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.

Solution 1:

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

Solution 2:

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

Solution 3:

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