This is a simple question I came across in reviewing. I am wondering if I got the correct answer.
The question is simple. You have $n$ balls and $m$ bins. Each ball has an equal probability of landing in any bin. I want to know what the probability that exactly $1$ bin is empty.
My answer seems simple enough, but I don't think it's sufficient. It is $(\frac{m-1}{m})^n$ since for each ball, it can go in any of the other bins. I think, however, that this is just the probability that some arbitrary bin $A$ is empty, not exactly one bin. What else should I consider?
Best Answer
Let's count configurations, and then divide by $m^n$.
There are $m$ choices for the empty bin. Then the other bins are occupied. We can count the ways to place $n$ balls in $m-1$ bins so that no bin is empty by inclusion-exclusion: It is
$$\sum_{k ~\text {bins known to be empty}} (-1)^k {m-1 \choose k} (m-1-k)^n.$$
Another way to get this is to label the parts of a set partition of size $n$ with $m-1$ parts. The number of set partitions with a given number of parts is a Stirling number of the second kind, and we want $(m-1)! S(n,m-1)$.
Multiply this by $m$ and then divide by $m^n$ to get the probability exactly $1$ bin is empty.
We can use the same techniques to compute the probability exactly $e$ bins are empty for other values of $e$. For example, suppose there are $4$ bins and $6$ balls. Then there are $1560$ ways for there to be $0$ empty bins, $2160$ ways for there to be exactly $1$ empty bin, $372$ ways for there to be exactly $2$ empty bins, and $4$ ways for there to be exactly $3$ empty bins. The total is $4096 = 4^6$. Dividing by this gives a probability of $\frac{135}{256} = 0.52734375$ that exactly $1$ bin is empty.