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?

  • 1
    $\begingroup$ You didn't define $k$. $\endgroup$ – Dimitrije Kostic Dec 25 '11 at 16:22
  • $\begingroup$ @DimitrijeKostic: Isn't it obvious? $k <n$. $\endgroup$ – Thomas Dec 25 '11 at 16:25
  • 3
    $\begingroup$ @Thomas Your answer is an expression in terms of $k$ and $n$. Your question is phrased just in terms of $n$, so your answer should be just in terms of $n$. $\endgroup$ – Dimitrije Kostic Dec 25 '11 at 16:28
  • 1
    $\begingroup$ I couldn't edit my comment as 5 minutes passed a minute ago, so this new one. Actually, I'd like to say that in writing that the denominator is $n^n$, you have assumed distinctness I am pointing out. So, Can I write an answer assuming this or you'll want to change your question? $\endgroup$ – user21436 Dec 25 '11 at 16:35
  • 2
    $\begingroup$ you can assume it $\endgroup$ – Thomas Dec 25 '11 at 16:38

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}}.$$


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 ...?


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}}$.

  • $\begingroup$ You have calculated # of favourable cases when the cells are identical: Look at the last table here math.dartmouth.edu/archive/m28w02/public_html/Chapter3.pdf . $\endgroup$ – user21436 Dec 25 '11 at 17:03
  • $\begingroup$ You're referring to the table on page 61, right? I don't see which cell of that table applies here. $\endgroup$ – Dimitrije Kostic Dec 25 '11 at 17:11
  • $\begingroup$ By the way, I think my answer agrees with @David Mitra's above. Our reasoning is similar as well, although he's a bit less wordy than I am. $\endgroup$ – Dimitrije Kostic Dec 25 '11 at 17:13
  • $\begingroup$ Yes, we're doing the same thing. My answer just has a bit more detail. $\endgroup$ – David Mitra Dec 25 '11 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.