Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Have a look at math.stackexchange.com/questions/78444/… –  Jean-Sébastien Oct 23 '12 at 2:11

1 Answer 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}$.

share|improve this answer
    
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$ –  privacy policy Oct 23 '12 at 2:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.