# Thread: Combinatorics problem

1. ## Combinatorics problem

Hello Members,
If n balls are placed at random into n cells, How to find the probability that exact one cell remains empty?
n balls can be placed into n cells in $n^n$ ways.How to proceed further?

2. ## Re: Combinatorics problem

Originally Posted by Vinod
Hello Members,
If n balls are placed at random into n cells, How to find the probability that exact one cell remains empty?
n balls can be placed into n cells in $n^n$ ways.How to proceed further?
Are both the balls and the cells distinguishable? If they are, then you are correct that there are $n^n$ ways to place the $n$ balls into $n$ cells. Out of the $n$ cells, choose one to be empty. Of the remaining $n-1$ cells, choose one of them to have two balls. Then the probability is $\dfrac{n(n-1)}{n^n}$. Chances are, the balls are not distinguishable but the cells are. In that case, there are $\dbinom{2n-1}{n}$ ways to place $n$ indistinguishable balls into $n$ distinguishable cells. There are $\dbinom{n-1}{1}$ ways to place $n$ indistinguishable balls into $n-1$ distinguishable cells so that every cell has at least one ball. Therefore, the probability is $\dfrac{n-1}{\dbinom{2n-1}{n}}$. There are also the possibilities that the balls are distinguishable but the cells are not and that the neither the balls nor the cells are distinguishable.

3. ## Re: Combinatorics problem

Hello,
Answer provided by the author of the book is $\binom{n}{2}n!n^{-n}$.I think Your answer seems to be different.

4. ## Re: Combinatorics problem

My answer was incorrect. Let's try again. Suppose $n=1$. Then there is a zero percent chance that exactly one cell will be empty and a 100% chance that every cell will have one ball (one ball, one cell, there is only one way to place the balls). So, assume $n>1$. As I mentioned above, we choose an empty cell and we choose a cell to have two balls. There are $n(n-1)$ ways of choosing that. Then, we choose two of the balls to be the two balls in the cell that has two balls. There are $\dbinom{n}{2}$ ways of choosing that. This leaves $n-2$ cells and $n-2$ balls. So, basically, we order the remaining $n-2$ balls and place them into the remaining $n-2$ cells in order. That is $(n-2)!$. Since each step was independent of the previous, we apply the product rule. Thus, we have:

$n(n-1)\dbinom{n}{2}(n-2)!$ ways to place $n$ distinguishable balls in $n$ distinguishable cells with exactly one cell remaining empty. That is equal to $n!\dbinom{n}{2}$, just as the book has. My mistake. I went too quickly through the problem. Sorry about that.

5. ## Re: Combinatorics problem

Originally Posted by Vinod
Answer provided by the author of the book is $\binom{n}{2}n!n^{-n}$
Correct...confirmed by simulation...