6

Each of $n$ balls is independently placed into one of $n$ boxes, with all boxes equally likely. What is the probability that exactly one box is empty? (Introduction to Probability, Blitzstein and Nwang, p.36).

  • The number of possible permutations with replacement is $n^n$

  • In order to have one empty box, we need a different box having $2$ balls in it. We have $\dbinom{n}{1}$ choices for the empty box, $\dbinom{n-1}{1}$ choices left for the box with $2$ balls, and $(n-2)!$ permutations to assign the remaining balls to the remaining boxes.

  • Result: $$\frac{\dbinom{n}{1} \dbinom{n-1}{1} (n-2)!}{n^n}$$

Is this correct?

Jimmy R.
  • 35,868
NoBackingDown
  • 1,692
  • Looks good to me. I think you can simplify further to $n! / n^n$, if you don't want to cancel out n. – BCLC Dec 07 '14 at 18:24
  • Indeed, a duplicate. Actually, I searched for the question but couldn't find this one. – NoBackingDown Dec 07 '14 at 18:52
  • I think there is an even earlier question that this duplicates: http://math.stackexchange.com/q/685690/139123 – David K Dec 20 '14 at 17:35
  • Related: http://math.stackexchange.com/q/32444/139123 appears to be a generalization (therefore the answer is more complicated). – David K Dec 20 '14 at 17:45

2 Answers2

4

Your approach (although nice) has a flaw in the second bullet. The problem is that there you count two different things: on the one hand ways to choose a box and on the other hand ways to choose a ball and this results to a confusion. In detail

  1. Your denominator is correct,
  2. Your numerator is missing one term that should express the number of ways in which you can choose the $2$ balls out of $n$ that you will put in the choosen box with the $2$ balls. This can be done in $\dbinom{n}{2}$ ways.
  3. The other terms in your numerator are correct. Note that your numerator can be written more simple as $$\dbinom{n}{1}\dbinom{n-1}{1} (n-2)!=n\cdot(n-1)\cdot(n-2)!=n!$$

Adding the ommitted term, gives the correct result which differs from yours only in this term (the highlighted one) $$\frac{\dbinom{n}{1}\color{blue}{\dbinom{n}{2}} \dbinom{n-1}{1} (n-2)!}{n^n}=\frac{\dbinom{n}{2}n!}{n^n}$$

Jimmy R.
  • 35,868
  • Thank you for the clear explanation. In the duplicate, Ojas explained the last expression by first arranging the n balls in n boxes ($n!$), and then choosing the empty box ($n$), the box with 2 balls ($n-1$) and dividing by two because there are two arrangements for this. Are those arrangements in the expression $n!$ itself? – NoBackingDown Dec 07 '14 at 18:57
  • @Dominik No those arrangements are in the term $n\cdot (n-1)$ that he counts when he takes the one ball out. You know something, because it is the same result but with a different explanation let's delete the suggestion for duplicate and leave this question open too. What do you think? – Jimmy R. Dec 07 '14 at 19:15
  • I think that's a good idea. – NoBackingDown Dec 07 '14 at 19:18
3

You can think of the number of favorable arrangements in the following way: choose the empty box in $\binom{n}{1}$ ways. For each such choice, choose the box that will have at least $2$ balls (there has to be one such box) in $\binom{n - 1}{1}$ ways. And for this box, choose the balls that will go inside in $\binom{n}{2}$ ways. Now permute the remaning balls in $(n - 2)!$ ways.

Thus, the number of favorable arrangements is:

$$ \binom{n}{1} \binom{n - 1}{1} \binom{n}{2} (n - 2)! = \binom{n}{2} n! $$

d125q
  • 2,370
  • 17
  • 19