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!
Best Answer
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.