# 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 :) – user940 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
• @EmrePer: As Thomas Andrews comments, you can ignore the labels on the balls (and urns) if you want the probability of a given number of empties. – Ross Millikan Apr 4 '13 at 16:08
• 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
• @EmrePer: You’re not missing anything: the labels matter. – Brian M. Scott Apr 4 '13 at 19:14
• You are missing that the 3 ways are not equally likely. 3+ 0+0 has p=1/9, 2+1+0 has p=6/9 and 1+1+1 has p=2/9. The labels DO NOT matter. The logic is, for – Dale M Apr 4 '13 at 22:48