5
$\begingroup$

We have n distinguishable balls (say they have different labels or colours). If these balls are dropped at random in n boxes, what is the probability that:

1- No box is empty? 2- Exactly one box is empty?

For 1, I figured that we have $n^n$ ways to put the n balls into the n boxes. And I figured there are $n!$ to sort the balls so there is one ball for each box.

So is the answer to question 1 $n!/(n^n)$?

For 2, there are $n-1$ ways for the boxes to be empty. This is because you can have box 1 be empty (and just that), box 2 be empty and just that, so ultimately you can have at most $n-1$ variations of empty boxes.

So I figured the solution to part 2 was $\frac{n-1}{n^n}$

Is any of this right?

$\endgroup$
2
  • $\begingroup$ I think your part two is incorrect, because for each box $n$ that is empty, there are $n-1$ boxes that could have the extra ball. $\endgroup$ Jan 26 '15 at 20:07
  • $\begingroup$ That sounds right...I'll edit my answer. $\endgroup$
    – vashts85
    Jan 26 '15 at 20:12
3
$\begingroup$

Your answer to part 1 is correct.

For part 2, you must place the balls so that there is one empty box, one box with two balls, and the remaining balls will have one ball each. There are $n$ ways to pick the empty box, and $n-1$ ways to then pick the box with two balls.

We can now fill the $n$ spaces for the balls with the $n$ balls in any order you wish. There are of course $n!$ ways to do this. However, there is a caveat. If the box with two spaces is filled with ball $a$ and then ball $b$, that is the same as if we put ball $b$ and then ball $a$. So we are double counting, and the number of ways to fill in the boxes is $\frac{n!}{2}$.

Thus the total number of ways to have one empty box is $\frac{n(n-1)(n!)}{2}$, so the probability of having one empty box is $\frac{\frac{n(n-1)(n!)}{2}}{n^n} = \frac{(n-1)(n!)}{2n^{n-1}}$.

$\endgroup$
4
  • $\begingroup$ It seems like order matters, so why would we divide by 1/2? $\endgroup$
    – vashts85
    Jan 26 '15 at 22:00
  • $\begingroup$ Of the $n^n$ possibilities, all that matters is which box each ball goes into. When we consider the $n!$ ways to put $n$ boxes into the $n$ spaces, we have two spaces in one box. So by that counting, if we put ball $a$ into space 1 of that box, and ball $b$ into space 2 of that box, that's counted separately from putting ball $b$ into space 1 and ball $a$ into space 2. But in the $n^n$ counting it's just counted once, since both balls go into the same box. So we have to divide by 2 to match up the counting. $\endgroup$
    – Deedlit
    Jan 27 '15 at 0:55
  • $\begingroup$ See the answer I posted above from the textbook. $\endgroup$
    – vashts85
    Jan 27 '15 at 17:56
  • $\begingroup$ Yes, the answer is the same: $\frac{n!}{2} = {n \choose 2} (n-2)!$. The book solution just picks the two balls in the one box first, then the remaining $n-2$ balls, whereas I picked all $n$ at once. $\endgroup$
    – Deedlit
    Jan 27 '15 at 19:10
1
$\begingroup$

Here is the answer to the question, based on the answer manual (it was worded slightly differently in my textbook, hence why I did not find it). My part 1 was correct.

The textbook question is as follows -- I'm not sure the cells versus boxes thing is supposed to make it be any different.

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

First, we have $n$ ways of picking the empty box. Then we have $n-1$ ways of picking the box with two balls.

Now which two balls will go into the one box that will have two balls? There are ${n \choose 2} $ ways to pick the two distinct balls to go into this cell.

Lastly we need to arrange the remaining $n-2$ cells, and there are $(n-2)!$ ways to permutate all of these.

So we have:

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

So the answer to part 2 is:

$\frac{n! {n \choose 2 }}{n^n}$

$\endgroup$
0
$\begingroup$

The argument in 1. is quite elegant. Another way to see this is that the probability to put the first ball in an empty box is $1$, for the second it is $(1 - 1/n)$, for the third it is $1 - 2/n$. The searched for probability is thus the product and this is exactly what you found in a different way that I actually like better.

For 2. you need to consider again all possibilities to place the balls. There are a lot more than you said. It is not just which box is empty (also there are $n$ ways for this) but also how the balls are distributed over the remaining ones.

$\endgroup$

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.