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.

I have $N>0$ coins that are thrown into $M>0$ boxes. Each box has the same chance to receive each coin. (i.e. the probability of a coin to land in one particular box is $1/M$)

How can I calculate the probability $p$, that each box contains at least one coin?

With $M > N$, $p = 0$
With $M = N$ $p$ would be $M!/M^N$
But with $N > M$ ?

Please give me some clues to solve this problem! Is it easier to just find $N = f(M)$ in order to have $p>90\%$?

share|improve this question
    
Why $\displaystyle p=\frac{N!}{3^n}$ if M=N and what is $n$ in this? –  Tengu Dec 4 '12 at 20:50
    
For $M = N$, I think it should be $M! / M^N$. –  StuartHa Dec 4 '12 at 21:00
    
@Stuart I think you are right. At least if $\displaystyle \frac{N!}{3^N}$, the probability could be greater than 1. –  Tengu Dec 4 '12 at 21:06
    
Oups. Of course it is M!/M^N for M=N. Thanks! –  Jenny Dec 4 '12 at 21:21
    
See duplicate: math.stackexchange.com/questions/26528/… –  StuartHa Dec 5 '12 at 7:12

1 Answer 1

up vote 0 down vote accepted

First we fix $N=n>0$ coins, and let $Q(m)$ be the probability that at least one of the $m$ boxes does not have any coins. Then $p=1-q$. $Q(1)=0$

If $m=2$, $Q(2)=\displaystyle \frac 2 {2^n}$.

If $m=3$, $Q(3)\displaystyle =\frac{\begin{pmatrix}3\\2\end{pmatrix}(1-Q(1))1^n+ \begin{pmatrix}3\\1\end{pmatrix} (1-Q(2))2^n}{3^n}$.

If $m=4$, $Q(4)=\displaystyle\frac {\begin{pmatrix}4\\3\end{pmatrix}(1-Q(1))1^n+\begin{pmatrix}4\\2\end{pmatrix}(1-Q(2))2^n+\begin{pmatrix}4\\1\end{pmatrix}(1-Q(3))3^n}{4^n}$

If $m=m_0$,$Q(m_0)=\displaystyle \frac{\sum_{k=1}^{k=m_0-1}\begin{pmatrix}m_0\\m_0-k\end{pmatrix}(1-Q(k))k^n}{m_0^n}$ for $m_0\geq 3$.

I considered the number of boxes that could be vacant.

share|improve this answer
    
Thanks. That helped. –  Jenny Dec 6 '12 at 11:55

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.