6
$\begingroup$

If $p_n$ denote the probability that when $n$ balls are randomly put in $n$ bins then there is at least one bin with exactly one ball. Is there a simple (involving only little computation) reason for why $p_{n+1}>p_{n}$ if $n>3$ ? This simple looking problem turns out to be not too simple, perhaps because ${p_{n}}/{p_{n-1}}$ turns out to be approximately $e(1-{1}/{n})^{n-1}$ and hence whatever the difference is, it is extremely small.

Thanks

  • 0
    Have a loo$k$ at http://math.stackexchange.com/questions/78444/with-n-balls-and-n-bins-what-is-the-probability-that-exactly-k-bins-have?rq=12012-10-23

1 Answers 1

1

Is this even true? It seems to me that $p_3=\frac{24}{27} \approx 0.88889$ while $p_4=\frac{216}{256} =0.84375$ so $p_4 \lt p_3$.

With three balls and bins I can see $3$ ways of putting so no bins have exactly $1$ ball: put them all in the same one of three bins.

With four balls and bins I can see $40$ ways of putting so no bins have exactly $1$ ball: either put them all in the same one of four bins, or put them in two of the four bins and put two in one of those and two in the other, so $4+{4 \choose 2}{4 \choose 2}$.

  • 0
    Oops, you are right, it should have been n>3. In general $p_n=\sum _{i=1}^n \left((-1)^{i+1}\times \left( \begin{array}{c} n \\ i \\ \end{array} \right)^2\times i!\times \frac{(n-i)^{n-i}}{n^n}\right)$ where ${0}^{0}=1$2012-10-23