Combinatorics – Probability of n Balls in n Cells with One Remaining Empty

combinatorics

Counting problems have always intrigued me, and I'm working on some out of interest. The other thread on this topic had unsatisfactory answers, because they don't match the answer in my book.

My question is: If $n$ balls are placed at random into $n$ cells, find the probability that exactly one cell remains empty.

My book gives $\binom{n}{2} \frac{n!}{n^n}$.

But I'm not sure which answer is right?

Best Answer

There are $n^n$ equally likely ways to distribute the $n$ balls among the cells. We find the number of ways in which precisely one cell is empty.

The empty cell can be chosen in $n$ ways. For each such choice, the cell that will have two balls can be chosen in $n-1$ ways.

For each such choice, the two balls that go into the lucky cell can be chosen in $\binom{n}{2}$ ways. That leaves $n-2$ balls and $n-2$ cells. The balls can be permuted among these cells in $(n-2)!$ ways.

So with a denominator of $n^n$, the numerator is $$\binom{n}{1}\binom{n-1}{1}\binom{n}{2}(n-2)!.$$

This simplifies to $\binom{n}{2}n!$.

Remark: For fun, we obtain $\binom{n}{2}n!$ "directly." The balls that are to be glued together can be chosen in $\binom{n}{2}$ ways. Now we have $n$ "abstract" balls: the $n-2$ remaining ordinary balls, our glued pair, and the invisible ball. These $n$ objects are to be assigned, one object to a cell, to our $n$ cells. That can be done in $n!$ ways.