If n balls are thrown into k bins, what is the probability that every bin gets at least one ball? 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
 A: 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}.$$
A: To count the outcomes for this question, using inclusion-exclusion formula is correct, but $n$ choose $k$ and then multiplied by $k!$ is only correct if the question is asking that "each bin has only one ball". If n balls are thrown into $n$ bins, then, a simple answer is $n!$.
So the question asking at least one ball is complicated. We have to write down each possible way and sum up each combination, just like another question asking about each day per week has at least one call. If we have exact numbers, we can count the numbers of outcomes, but here, it is better to ask at least one ball with the setting of $n$ balls thrown into $n$ bins.
A: I propose to use combinatorics. Namely, stars and bars formulae.


*

*Number of outcomes with at least one ball in every bin is $\tbinom{n
    - 1}{k-1}.$

*Number of outcomes with any number of balls in every bin is $\tbinom{n + k - 1}{n}.$
Now just divide.
EDIT: As highlighted in the comment this gives wrong answer because it doesn't account for weights of every possible combination.
A: 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$
A: Set $X_i = 1$ if there is at least 1 ball in the $\textit{i}$th bin; and $0$ otherwise [$\textit{i}$ goes from 1 to k]. Then this question is asking what is $P[\sum\limits_{i=1}^k X_i = k]$. Given that each $X_i$s are independent of each other, $P[\sum\limits_{i=1}^k X_i=k]) = (P[X_i=1])^k =(1-P[X_i=0])^k =(1-(\frac{k-1}{k})^n)^k$
