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?

  • 1
    You didn't define $k$.2011-12-25
  • 0
    @DimitrijeKostic: Isn't it obvious? $k .2011-12-25
  • 0
    Since you say the total number of ways of distributing $n$ balls into $n$ cells [the denominator] is $n^n$, can I assume that balls and cells are distinct?2011-12-25
  • 3
    @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$.2011-12-25
  • 1
    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?2011-12-25
  • 2
    you can assume it2011-12-25
  • 0
    @Thomas +1 so it stays on top and others will agree with the answer2011-12-25
  • 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
    You have calculated # of favourable cases when the cells are identical: Look at the last table here http://www.math.dartmouth.edu/archive/m28w02/public_html/Chapter3.pdf .2011-12-25
  • 0
    You're referring to the table on page 61, right? I don't see which cell of that table applies here.2011-12-25
  • 0
    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.2011-12-25
  • 0
    Yes, we're doing the same thing. My answer just has a bit more detail.2011-12-25