Given N balls and M buckets(N > M), what is the probability that every bucket has at least one ball in it?

Question

In reality, I want to find the probability that at least one bucket is empty. But I'm not sure whether it is easier to calculate that or do 1 - P(every bucket has a ball in it).

Answer 1

This might work.

Each of N balls may be be placed into 1 of M buckets, that gives $M^N$ possibilities.

There are $\frac{(N-1)!}{(M-1)!(N-M)!}$ ways of adding up the contents of the M buckets, none of which are allowed to be empty.

So $P=1-\frac{(N-1)!}{(M-1)!(N-M)!M^N}$

Answer 2

I don't think this problem has an easy solution. Let $A$ be the event that there are no empty cells. Consider the following cases:

1. N = M: There are $M^M$ total ways to distribute the balls to the cells. There are $M!$ ways to distribute the balls such that there are no empty cells. Thus,

$\quad \quad P(A) = \frac{M!}{M^M}$.

2. N = M+1: There are $M^{M+1}$ total ways to distribute the balls to the cells. There are $\binom{M+1}{2}$ ways to pick the two balls that will occupy the same cell and $M!$ ways to rearrange a given arrangement with no empty cells. Thus,

$\quad \quad P(A) = \frac{\binom{M+1}{2} \; M!}{M^{M+1}}$.

3. N = M+2: There are $M^{M+2}$ total ways to distribute the balls to the cells. Here, there are two ways to get no empty cells; a) one cell has 3 balls or b) two cells each have two balls. For a) There are $\binom{M+2}{3}$ ways to pick the three balls that will occupy the same cell and $M!$ ways to rearrange a given arrangement with no empty cells. For b) there are $\binom{M+2}{2} \; \binom{M}{2} \; \frac{1}{2}$ ways to choose the two balls for the two cells without order ($\frac{1}{2}$ takes care of order) and $M!$ ways to rearrange a given arrangement with no empty cells. Thus,

$\quad \quad P(A) = \frac{M! \; [ \binom{M+2}{3} + \binom{M+2}{2} \; \binom{M}{2} \; \frac{1}{2} ]}{M^{M+2}}$.

etc.

Maybe there's a general formula for any $N (> M)$ to calculate $P(A)$, but i don't know what it is.