Probability of n balls in n cells, one remaining empty

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?

Solution 1:

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.

Solution 2:

There are $n^n$ ways of mapping balls to cells altogether, so as user84413 says the denominator $n^n$ is correct. The numerator $C^n_2\cdot n!$ is also correct: if there is exactly 1 empty cell, than all the other cells contain 1 ball except for 1 cell which contains 2. There are $C^n_2$ ways of choosing the 2 balls that occupy the same cell, $n$ cells to choose for the empty cell and $(n-1)!$ ways of assigning the non-empty cells. So the numerator is correctly given as $C^n_2\cdot n! = C^n_2 \cdot n \cdot (n-1)!$.

Solution 3:

Someone asked what about the case of indistinguishable balls. Well, they all have covered the distinguishable case so I'm answering about the case where the balls are indistinguishable.

Let $n$ indistinguishable balls are placed randomly in n cells. In this case, a configuration corresponds to a vector $(x_1, x_2, ...., x_n)$, where $x_i$ is the number of balls in the $i$-th cell. So we now determine all such configurations. Let us consider about the intermediate walls of the cells. There're $(n - 1)$ such walls.

Thus the total number of place taken by a ball or a wall is $n+(n-1)=(2n-1)$ . And we can place $n$ balls in $(2n-1)$ places in $\binom{2n-1}{n}$ ways. Therefore the total number of such configurations is $\binom{2n-1}{n}$.

Now we find out the number of ways that exactly one cell is empty. So we can choose the empty cell in n ways. And for each such choice there are $(n-1)$ choices of placing two balls in a cell. And there's only one way of placing $(n-2)$ indistinguishable balls in $(n-2)$ cells. So the total number of ways such that exactly one cell remains empty is $n(n-1)$. Therefore the probability of this event is $\frac{n(n-1)}{\binom{2n-1}{n}}$.