If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what is $P(X=0)$?
I was able to calculate the $E(X)$ and thus bound with Markov's inequality $P(X \geq 1) \le E(X)$ but I don't how to work out an exact answer.
http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/588.596.pdf
On
Let $k$ equal the number of bins, and $n$ the number of balls thrown.
This answer is based on the accepted answer, but with more details.
Let $A_i$ represent the event that bin $i$ is empty.
$P(A_i) = (1-\frac{1}{k})^n$
$P(A_1\dots A_j) = (1-\frac{j}{k})^n$
By De Morgan's Law $P(A_1^c ... A_j^c) = P(~(A_1 \cup \dots \cup A_j)^c~)$
And $P((A_1 \cup \dots \cup A_j)^c) = 1 - P(A_1 \cup \dots \cup A_j)$
Now, by inclusion exclusion:
$1 - P(A_1 \cup \dots \cup A_k) = 1 - \sum_{j=1}^{k}~(-1)^{j+1}\binom{k}{j}(1-\frac{j}{k})^n$
Now to rearrange,
$1 - \sum_{j=1}^{k}~(-1)^{j+1}\binom{k}{j}(1-\frac{j}{k})^n =1 + \sum_{j=1}^{k}~(-1)^{j}\binom{k}{j}(1-\frac{j}{k})^n = (-1)^0 \binom{k}{0}(1-\frac{0}{k})+ \sum_{j=1}^{k}~(-1)^j\binom{k}{j}(1-\frac{j}{k})^n= \sum_{j=0}^{k}~(-1)^j\binom{k}{j}(1-\frac{j}{k})^n$
What is the chance that all $k$ bins are occupied?
For $1\leq i\leq k$, define $A_i$ to be the event that the $i$th bin stays empty. These are exchangeable events with $P(A_1\cdots A_j)=(1-{j\over k})^n$ and so by inclusion-exclusion, the probability that there are no empty bins is $$P(X=0)=\sum_{j=0}^k (-1)^j {k\choose j}\left(1-{j\over k}\right)^n.$$
Stirling numbers of the second kind can be used to give an alternative solution to the occupancy problem. We can fill all $k$ bins as follows: partition the balls $\{1,2,\dots, n\}$ into $k$ non-empty sets, then assign the bin values $1,2,\dots, k$ to these sets. There are ${n\brace k}$ partitions, and for each partition $k!$ ways to assign the bin values. Thus, $$P(X=0)={{n\brace k}\,k!\over k^n}.$$