If we throw randomly $n+1$ balls into $n$ bins, what is the probability that exactly two bins are empty?
I tried to do this problem but I didn't get right solution, I would be very grateful if someone would point where am I making mistake, and how should I think about that. Also, if there are any simpler approaches, I would like to see them. I have seen that there have been similar questions but I would really like to find out where my intuition is making mistake.
First case:
$4$ balls inside one bin, and in other bins exactly one ball in each. We have $\binom{n+1}{4}$ ways of choosing $4$ balls from $n+1,$ and we can choose one from $n$ bins. Other balls we can place in $(n-3)!$ ways, so that is finally $n\cdot\binom{n+1}{4}\cdot(n-3)!$ ways. This way $2$ bins stay empty each time.
Second case:
$3$ balls inside one bin, $2$ balls in some other bin, and in left bins $n-4$ balls. I can choose $3$ balls in $\binom{n+1}{3}$ ways and place them into one of $n$ bins, after that I can choose two from $n-2$ left balls in $\binom{n-2}{2}$ ways and place them in one of $(n-1)$ left bins. Considering permutations of balls that I didn't pick, that is finally
$\binom{n+1}{3}\cdot n\cdot\binom{n-2}{2}\cdot(n-4)!$ ways.
In this case also two bins will be empty.
Third case:
Two bins with two balls in them and other bins with $1$ ball in them, that will also result in $2$ empty bins. Same as described in previous cases, this would be $\binom{n+1}{2}\cdot n\cdot\binom{n-1}{2}\cdot(n-1)\cdot(n-3)! $
Total number of cases is $n^{n+1}.$
Probability is sum of these three cases over total number of cases, but I am making some mistake in counting. Thank you.
Best Answer
Not sure what you did wrong, but I suspect that you ignored something in your casework. Also, the total number of cases should be $n^{n+1}$, not $n^{n+2}$. Here is an example of a much simpler approach.
First, calculate the number of ways there can be two empty bins. The number of ways for the two empty bins to be chosen is $$_{n}C_2=\frac{n(n-1)}{2}$$ then, since there must be exactly two empty bins, we must place one ball in each of the remaining $n-1$ bins so that none of them are empty. We then have one last ball with $n-1$ choices. Thus the number of ways to place the balls and have exactly two empty bins is $$\frac{n(n-1)}{2}*(n-1)$$ $$\frac{n(n-1)^2}{2}$$ And so the probability is $$\frac{\frac{n(n-1)^2}{2}}{n^{n+1}}$$ $$\frac{(n-1)^2}{2n^{n}}$$
EDIT: This is incorrect. By saying that the number of ways to distribute the balls is $n^{n+1}$, I imply that the balls are distinct objects; however, if they are distinct, then the number of ways to place one ball in each bin other than the two designated empty bins is $(n-1)!$, and so the number of ways to place the balls and have two empty bins is $$\frac{n(n-1)}{2}*(n-1)!*(n-1)=\frac{n(n-1)^2(n-1)!}{2}$$ and so the probability is $$\frac{\frac{n(n-1)^2(n-1)!}{2}}{n^{n+1}}$$ $$\frac{(n-1)^2(n-1)!}{2n^n}$$