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

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?

-
The labels for the balls and urns, incidentally, have no effect on this problem. –  Thomas Andrews Apr 4 '13 at 15:23
@Thomas: They do. For $n=3$, with urns and balls labelled, the probability of no empty urn is $\frac29$. With urns labelled and balls unlabelled, it’s $\frac1{10}$; with neither urns nor balls labelled, it’s $\frac13$. –  Brian M. Scott Apr 4 '13 at 19:14
That can't be true, @BrianM.Scott. That's only true if you ignore the conditions of the problem and treat results "2,1,0" and "1,1,1" as equal probability. –  Thomas Andrews Apr 4 '13 at 19:17
@Thomas: But if you ignore the labels, you are treating those as having equal probability. That’s precisely why you can’t ignore the labels, and why Ross’s solution doesn’t work. –  Brian M. Scott Apr 4 '13 at 19:18
@BrianM.Scott, which part of the condition: "Balls are randomly thrown into urns: Each ball is thrown at each urn with probability $1/n$" am I missing? The result set is smaller - there are not $n^n$ different results - but each result is not equally likely. –  Thomas Andrews Apr 4 '13 at 19:22

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.

-
Excellent! Thanks. –  Emre Per Apr 4 '13 at 22:17
@EmrePer No problem! I love throwing balls in urns :) –  Byron Schmuland Apr 4 '13 at 22:18
If you love balls and urns, can you have a look at the other question I posted (sequential allocation of balls into urns) :) I think it is a complicated one. I would appreciate your thoughts on that one. That is the original question that I am interested in. This question seems to be a small step in solving the other question. –  Emre Per Apr 4 '13 at 22:26
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.
My problem is that I can not compute How many ways to distribute the balls into the n−k urns such that each urn gets at least one ball since balls are also distinguishable? That is, (Ball 1, Ball 2 in urn 1, ball 3 in urn 2) is different than (Ball 1, Ball 3 in urn 1, ball 2 in urn 2). I see that answer will be: There are $n^{n}$ ways to put $n$ balls to $n$ urns. There are $\binom{n}{k}$ ways to choose $k$ empty urns. We want to place $n$ balls into $n-k$ urns which can be done in $x$ ways. Hence, the result is \ \frac{1}{n^{n}}\binom{n}{k}x \ –  Emre Per Apr 4 '13 at 16:03
Well, actually, I am confused now. Let's consider $n=3$. Assume there are no labels. Then, there are 3 ways to allocate balls: 3+0+0, 2+1+0, 1+1+1. Then, the probability of emptiness for each $k$ is $1/3$? But, this is not true in labeled version. What am I missing? –  Emre Per Apr 4 '13 at 16:39