# Throwing $k$ balls into $n$ bins.

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!

-
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
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

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.

-
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)

-
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