Combinatorics – Probability of k Empty Urns After Putting n Balls into n Urns

balls-in-binscombinatoricspermutations

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?

Best Answer

  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.

Related Question