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 the following question:

Throwing $k$ balls into $n$ bins. What is the probability that exactly $z$ bins are not empty?

I thought about something like: $$\Pr(z)=\frac{n! z^{k-z}}{n^k (n-z)!},$$ but this is not correct.

Another idea is: $\Pr(bin ~empty)=(1-1/n)^k$, $\Pr(bin ~Not ~empty)=1-(1-1/n)^k$, so:

$$\Pr(z)=(\Pr(bin ~empty))^{n-z}(\Pr(bin ~Not ~empty))^{z}\cdot A$$

So, how to obtain the $A$?

Thanks!

share|improve this question
    
Special case $z=n$: math.stackexchange.com/questions/174674/… –  Daan Michiels Jan 24 '13 at 13:02
    
But notice, $z\le k$. –  Michael Jan 24 '13 at 13:14
1  
I agree that $z\leq k$, but what's your point? The case $z=n$ is relevant if $n\leq k$. –  Daan Michiels Jan 24 '13 at 13:17
    
You are right. Thanks. But I need the general case, not the special one... –  Michael Jan 24 '13 at 13:19

2 Answers 2

up vote 2 down vote accepted

The probability that at most $r$ particular bins are not empty is $(r/n)^k$. Thus by inclusion–exclusion the probability that exactly $z$ particular bins are not empty is

$$ \sum_{j=0}^z(-1)^j\binom zj\left(\frac{z-j}n\right)^k=\frac{z!}{n^k}\left\{k\atop z\right\}\;, $$

where $\displaystyle\left\{k\atop z\right\}$ is a Stirling number of the second kind. Since there are $\displaystyle\binom nz$ ways of selecting $z$ particular bins, the desired probability is

$$ \binom nz\frac{z!}{n^k}\left\{k\atop z\right\}=\frac{n!}{(n-z)!n^k}\left\{k\atop z\right\}\;. $$

You can also derive this result by noting that there are $n^k$ outcomes in total, and the favourable outcomes are characterized by a partition of the set of $k$ balls into $z$ non-empty subsets (of which there are $\displaystyle\left\{k\atop z\right\}$ ) and then $n(n-1)\cdots(n-z+1)$ choices where to place each subset.

share|improve this answer
    
Thanks a lot Joriki! –  Michael Jan 24 '13 at 13:42

I wonder why it is not the simple answer shown below. Choose z bins(any), put 1 ball each in those bins, then randomly put balls in those z bins.

The required prob. is nCz*(z/n)^(k-z)

share|improve this answer
    
The events are dependent... You can't just multiply by nCz. I.e., you have many overlapping sets of bins. You can check it by summing your proposition over $z\in [1,...,k]$ and will see that it won't get 1, but a huge number... –  Michael Mar 4 '13 at 16:24

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.