Balls in bins, probability that exactly two bins are empty 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.
 A: 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}$$
A: This is a probability question, so you have a choice of considering ways to arrange indistinguishable balls or ways to arrange balls that are all different. You just have to be consistent in how you add up the probability of each arrangement.
The number of ways to arrange $n+1$ balls (all different) into the $n$ bins is $n^{n+1}.$  All these arrangements are equally likely.
The arrangements of indistinguishable balls are not all equally likely, so I will consider the balls all different.
When counting arrangements, you must consider the fact that different choices of which bins are empty will give you different arrangements.
I did not see any consideration of that in the question.
So for the first case, after choosing one of $n$ bins to put the four balls in, you must choose two of the remaining $n-1$ bins to be empty,
so instead of $n\binom{n+1}{4}(n-3)!$ arrangements
you have $n\binom{n-1}{2}\binom{n+1}{4}(n-3)!.$
Simplifying this a bit, it is  $\frac{1}{48}n(n-1)(n-2)(n+1)!.$
For the second case, you are missing a factor of $n-1$ to account for the number of ways to select the bin to put two balls in,
and a factor of $\binom{n-2}{2}$ for the choice of two empty bins,
so instead of 
$n\binom{n+1}{3}\binom{n-2}{2}(n-4)!$ ways
you should have $n\binom{n+1}{3}(n-1)\binom{n-2}{2}\binom{n-2}{2}(n-4)!.$
This simplifies to $\frac{1}{24}n(n-1)(n-2)(n-3)(n+1)!.$
For the third case, you actually need to put two balls into each of
three bins.
But you also need to avoid multiple counting of the same arrangement:
for example, choosing bin $1,$ putting balls $1$ and $2$ in that bin,
then choosing bin $2$ and putting balls $3$ and $4$ in it,
is the same result as choosing bin $2,$ putting $3$ and $4$ in it,
then choosing $1$ and putting $1$ and $2$ in it.
To avoid double-counting, rather than choosing one bin, then another, then another ($n(n-1)(n-2)$ ways), you can first choose the three bins that will each have two balls ($\binom{n}{3}$ ways) and then fill them left to right.
But also remember to choose two empty bins from the remaining $n-3$
before placing the remaining balls. So instead of
$\binom{n+1}{2}n\binom{n-1}{2}(n-1)(n-3)!$ you should have
$\binom{n}{3}\binom{n+1}{2}\binom{n-1}{2}\binom{n-3}{2}\binom{n-3}{2}(n-5)!.$
This simplifies to
$\frac{1}{96}n(n-1)(n-2)(n-3)(n-4)(n+1)!.$
Adding these up, we have $M$ arrangements with exactly two empty bins, where
\begin{align}
M &= \frac{1}{48}n(n-1)(n-2)(n+1)!
 + \frac{1}{24}n(n-1)(n-2)(n-3)(n+1)! \\
 &\qquad + \frac{1}{96}n(n-1)(n-2)(n-3)(n-4)(n+1)! \\
&= \frac{n(n-1)(n-2)(n+1)!}{96}\left(2 + 4(n-3) + (n-3)(n-4)\right) \\
&= \frac{n(n-1)(n-2)(n+1)!}{96}\left(n^2 - 3n + 2\right) \\
&= \frac{n(n-1)^2(n-2)^2(n+1)!}{96}.
\end{align}
And then the probability is just the number of arrangements with exactly
two empty bins divided by the total number of arrangements:
$$\frac{M}{n^{n+1}} = \frac{(n-1)^2(n-2)^2(n+1)!}{96n^n}.
$$
A: Randomly throw $n$ balls into $m$ bins
means that you consider as equiprobable and indipendent events the
launch the of the $k$-th ball into the $j$-th bin
i.e., a sequence of $n$ independent events, each having $m$ equiprobable results.
Thus the space of elementary events is the $n$D (hyper)cube of side $1\dots m$, containing $m^n$ points
(i.e. sequences).
For each launch sequence you are going to construct a histogram of the occupancy
level of the bins, as sketched below.
 
Different sequences will provide:
a different occupancy profile, and/or
a different labelling of balls among the bins.
But the order of the labels of the balls within each bin is not taken into consideration
(each successive ball can be taken to land over a precedent one, or over a void). 
That premised, the number of ways to throw $n$ balls into $m$ bins without restrictions is $m^n$.
It includes :
0) the configurations with $0$ empty bins = all bins with at least 1 ball;
1) the configurations with exactly $1$ empty bin, the empty bin being $\{1\},\{2\}, \cdots, \{m\}$;
 ...
q) the configurations with exactly $q$ empty bins, the empty bins being $\{1,2,\cdots,q-1,q\},\cdots,\{1,2,\cdots,q-1,m\}, \cdots, \{m-q+1,\cdots,m\}$, i.e.
all the q-subsets from  the set $\{1,\cdots,m\}$;
  ...
m) the configuration with all $m$ bins empty, which is possible only if $n=0$ (and $0<m$).  
Let's call $N(n,m,q)$ the number of configurations with exactly $q$ bins empty, and clearly with the other $m-q$ containing at least one ball.
The number of configurations is the same for each q-subset determined to be left empty, and it is N(n,m-q,0).
The number of q-subsets that can be drawn from the set $\{1,\cdots,m\}$ is ${m \choose q}$.
So we can write
$$ \bbox[lightyellow] {  
\left\{ \matrix{
  N(n,m,m) = \left[ {0 = n} \right] \hfill \cr 
  N(n,m,q) = \left( \matrix{
  m \cr 
  q \cr}  \right)N(n,m - q,0) \hfill \cr 
  m^{\,n}  = \sum\limits_{0\, \le \,k\, \le \,m} {N(n,m,k)}  = \sum\limits_{0\, \le \,k\, \le \,m} {\left( \matrix{
  m \cr 
  k \cr}  \right)N(n,m - k,0)}  \hfill \cr}  \right.
 } \tag{1}$$
where $[P]$ denotes the Iverson bracket
$$ \bbox[lightyellow] {  
\left[ P \right] = \left\{ {\begin{array}{*{20}c}
   1 & {P = TRUE}  \\
   0 & {P = FALSE}  \\
 \end{array} } \right.
 } $$
But it is well known that  powers, can be transformed into Falling Factorials and thus into
Binomial Coefficients, through the Stirling Numbers of 2nd kind, so
$$ \bbox[lightyellow] {  
m^{\,n}  = \sum\limits_{0\, \le \,k\, \le \,n} {\left\{ \matrix{
  n \cr 
  k \cr}  \right\}\,m^{\,\underline {\,k\,} } } \; = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \min \,\left( {n,m} \right)} \right)} {k!\left\{ \matrix{
  n \cr 
  k \cr}  \right\}\,\left( \matrix{
  m \cr 
  k \cr}  \right)}  = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \min \,\left( {n,m} \right)} \right)} {\left( {m - k} \right)!\left\{ \matrix{
  n \cr 
  m - k \cr}  \right\}\,\left( \matrix{
  m \cr 
  k \cr}  \right)} 
 } \tag{2}$$
Because of the symmetry of the Binomial we get the dual representation above, and there cannot be another one relating $m^n$ with ${m \choose k}$.
Therefore comparing identity (2) with (1), results in that we shall choose the second one, because we shall have
$$
N(n,0,0) = \left[ {0 = n} \right]\quad \quad N(n,n,0) = n!
$$
So we conclude that
$$ \bbox[lightyellow] {  
N(n,m - k,0) = \left( {m - k} \right)!\left\{ \matrix{
  n \cr 
  m - k \cr}  \right\}\quad  \Rightarrow \quad N(n,m,0) = m!\left\{ \matrix{
  n \cr 
  m \cr}  \right\}
 } $$
and
$$ \bbox[lightyellow] {  
N(n,m,q) = \left( \matrix{
  m \cr 
  q \cr}  \right)N(n,m - q,0) = \left( \matrix{
  m \cr 
  q \cr}  \right)\left( {m - q} \right)!\left\{ \matrix{
  n \cr 
  m - q \cr}  \right\} = {{m!} \over {q!}}\left\{ \matrix{
  n \cr 
  m - q \cr}  \right\}
 } \tag{3}$$
so that the answer to your question, in particular, is
$$ \bbox[lightyellow] {  
P(n) = {{N(n + 1,n,2)} \over {n^{\,n + 1} }} = {{n!} \over {n^{\,n + 1} \;2!}}\left\{ \matrix{
  n + 1 \cr 
  n - 2 \cr}  \right\}
 } \tag{4}$$
which fully agrees with the answer by David K.
A: Consider the probability that at least $k$ bins remain empty. Assume we chose some k bins, doesn't matter which ones, thus I won't consider the number of ways to choose $k$ bins. We don't want any balls to enter those k bins. The probability for it is $(\frac{n-k}{n})^{n+1}$, because we want $n-k$ bins (out of $n$ bins) to be hit for $n+1$ times. This ensures that those $k$ will remain empty; but maybe there are some other bins which were not hit by chance. So, this ratio, $(\frac{n-k}{n})^{n+1}$, gives you the probability that at least $k$ bins will remain empty. But you want "exactly $2$ bins" empty. So, I will subtract "the probability of at least 2 bins remain empty" from "the probability that at least 3 bins remain empty" which will result in "the probability that exactly 2 bins remain empty" as you desire. Here is the calculation:
$$(\frac{n-2}{n})^{n+1}-(\frac{n-3}{n})^{n+1}$$
$$\frac{(n-2)^{n+1}-(n-3)^{n+1}}{n^{n+1}}$$
$$\frac{(n-2)^n+(n-2)^{n-1}(n-3)+(n-2)^{n-2}(n-3)^2+...+(n-2)(n-3)^{n-1}+(n-3)^n}{n^{n+1}}$$
