Probability of having $k$ empty urns after putting $n$ balls into $n$ urns

Question

Assume that there are $n$ balls (numbered from $1$ to $n$) and $n$ urns (numbered from $1$ to $n$). At the beginning no ball is placed in any urn. Balls are randomly thrown into urns: Each ball is thrown at each urn with probability $1/n$.

What is the probability that there are exactly $k$ empty urns?

Answer 1

1. Choose $n-k$ urns that won't be empty.
2. Group the $n$ balls into $n-k$ non-empty sets.
3. Distribute groups of balls into the designated urns.

These 3 steps explain the three factors in this expression: $$\mathbb{P}(\text{exactly } k \text{ urns are empty})={{n\choose n-k}{n \brace n-k}(n-k)!\over n^n}.$$

The notation ${n \brace n-k}$ refers to Stirling numbers of the second kind.

Answer 2

Hint: how many ways are there to choose the $k$ empty urns? How many ways to distribute the balls into the $n-k$ urns such that each urn gets at least one ball? For the second, think stars and bars.