1
$\begingroup$

If $n$ balls are randomly placed into $n$ cells, find the probability that exactly one cell remains empty.

So the denominator is $n^n$. I can pick the empty cell in $n$ ways. There are $n-1$ cells that can have $k$ balls. There are $\binom{n}{k}$ ways of picking the $k$ balls to go into this cell. Also there are $(n-k) \cdots (n-2)$ ways of placing the remaining $n-k$ balls into the $n-2$ cells. So the product of this is $n(n-1) \binom{n}{k} [(n-k) \cdots (n-2)]$

So the answer is $\frac{n(n-1) \binom{n}{k} [(n-k) \cdots (n-2)]}{n^n}$

Is this right?

  • 0
    @Thomas OK, suppose I say $n=5$. Can you compute your answer for me?2011-12-25

3 Answers 3

5

I'm not sure you're correct (what is k?).

If everything is distinct:

There are $n$ ways to choose the empty cell. There will be exactly one other cell with more than one ball in it; in fact, exactly two balls in it. There are $\underbrace{ (n-1)}_{\text{choose}\atop\text{urn}}\cdot \underbrace{( n (n-1)/2)}_{\text{choose the }\atop\text{two balls}}$ ways to chose and fill this cell. Since exactly one cell is empty, there are $(n-2)!$ ways to distribute the remaining $n-2$ balls (the cells are being thought of as distinct, and each of the remaining $n-2$ cells gets exactly one of the remaining $n-2$ balls; so the number of ways of distributing the remaining $n-2$ balls is just the number of ways to arrange $n-2$ objects).

So the probability is ${n\cdot( (n-1) n(n-1)/2)(n-2)!\over n^n}={(n-1)(n-1)!\over2\, n^{n-2}}.$

3

Hint: If no cell is empty, then each cell gets exactly one ball, hence the probability is $n!/n^n$. If exactly one cell is empty, then the distribution of balls in the cells (up to order) is $2,1,\ldots,1,0$. Hence the probability is ...?

2

Assuming the $n$ balls and $n$ containers are distinguishable, first we'll choose one container to leave empty. We can do this in one of $n$ ways. Then, the other $n-1$ containers have to get the $n$ balls leaving no other container empty. In other words, we need a surjective function from the set of $n$ balls to the set of $n-1$ nonempty containers. There are $(n-1)!S(n,n-1)$ such functions, where $S(n,k)$ is the Stirling number of the second kind, the number of ways to partition a set of $n$ elements into $k$ non-empty containers.

We can simplify $S(n,n-1)$ a bit; since such a partition will give one container two balls and the other containers one each, we can simply choose the two balls that will go in one container together. That is, $S(n,n-1)=\binom{n}{2}$.

There are obviously $n^n$ possible ways to distribute the balls among the bins. So the probability is $\frac{n(n-1)!S(n,n-1)}{n^n} = \frac{(n-1)!\binom{n}{2}}{n^{n-1}}$.

  • 0
    Yes, we're doing the same thing. My answer just has a bit more detail.2011-12-25