$n$ balls into $n+1$ urns (with one special urn)

Assume that there are $n$ balls numbered from $1,2,\ldots,n$ and $n+1$ urns, numbered as $0,1,\ldots,n$

Throw each ball randomly into one of $n$ urns: urn 1, urn 2, . . . , urn $n$. That is, any urn except urn $0$. (A ball goes to a certain urn with probability $1/n$) Check each urn and if there are more than one ball in an urn, choose one randomly and keep that in that urn and remove the other balls and put them into urn $0$.

What is the probability that there are $k$ balls in urn 0?

-
This is a great question that deserves an upvote. With that in mind...what have you tried? –  Jonathan Rich Apr 17 '13 at 14:34
Well, I tried first finding the probability of having $m$ empty urns- which is to do with Stirling numbers of the second kind. There is no ball to remove from those. The question then what is the probability of having $s$ urns that have more than 1 ball given that there are $n-m$ nonempty urns. That is the hard part and where I got stuck. –  Emre Per Apr 17 '13 at 14:39
But if you know the number of empty urns, don't you already know $k$? –  leonbloy Apr 17 '13 at 14:44
When you say "choose one randomly", do you mean one ball or one urn? (My guess is probably the former.) –  Michael Hardy Apr 17 '13 at 15:01

The number of balls in urn $0$ at the end is simply the number of urns numbered $1$ through $n$ that received no ball during the ball-tossing stage. Let $K$ be a set of $k$ of the urns numbered $1$ through $n$; a distribution of the balls that leaves exactly the urns in $K$ empty is a partition of the $n$ balls into $n-k$ parts. There are $n\brace{n-k}$ such unordered partitions, but the urns are numbered, so there are actually $(n-k)!{n\brace{n-k}}$ distributions leaving exactly the urns in $K$ empty. (Here $n\brace{n-k}$ is a Stirling number of the second kind.) Thus, there are

$$\binom{n}k(n-k)!{n\brace{n-k}}=\binom{n}k\sum_{i=0}^{n-k}(-1)^{n-k-i}\binom{n-k}ii^n$$

distributions that result in $k$ balls in urn $0$. Since there are $n^n$ equiprobable distributions, the probability $p_k$ of ending up with $k$ balls in urn $0$ is

$$p_k=\frac1{n^n}\binom{n}k(n-k)!{n\brace{n-k}}=\binom{n}k\sum_{i=0}^{n-k}(-1)^{n-k-i}\binom{n-k}i\left(\frac{i}n\right)^n\;.$$

-

Hints/Guiding questions:

• How many balls are not in urn $0$?
• How many of the urns $1$ up to $n$ had balls in them before moving balls to urn $0$?
• What is the probability of such a configuration occurring?
-

The problem you need to solve is not how many urns have more than one ball - if you have 12 urns, 11 balls, and 7 urns have balls in them, you're going to be putting 4 balls into urn 0 no matter what the count of the balls in each urn is.

You simply need to calculate sum of the probability that, for each thrown ball, whether it falls into an urn that already has a ball in it. The first ball is obviously probability $0$, and subsequent balls are $\frac{k}{n}$, where $k$ is the number of urns with balls in them. For the second ball, $k=1$ and for the third ball, $k=1+1-\frac{1}{n}$.

The wording of the question makes it seem much more complicated than it is. This is pretty much the birthday problem with an arbitrary number of months and people in the room - if two people share a birth month, one of them leaves the room (and gets put into an urn - yikes).

-

Denote by $q_r(j)$ the probability that after $r\geq0$ throws exactly $j\geq0$ urns are occupied. Then $p_0(j)=\delta_{0j}$ and $$q_r(j)={j\over n} q_{r-1}(j)+{n-(j-1)\over n}q_{r-1}(j-1)\qquad(r\geq1)\ .$$ Let $f_r(j):=n^r q_r(j)$; then $$f_r(j)=j f_{r-1}(j)+\bigl(n-(j-1)\bigr)f_{r-1}(j-1)\ .$$ Note that $r$ does not appear in the coefficients of this recursion. It is then easy to see that in fact $$f_r(j)=c_{r,j}\prod_{i=0}^{j-1} (n-i)$$ for constants $c_{r,j}$ that satisfy the recursion $$c_{r,j}=j c_{r-1,j} + c_{r-1,j-1}\ .$$ Now this is the recursion formula for the Stirling numbers of the second kind, denoted by $S(r,j)$ in Stanley's Enumerative combinatorics, vol. I. One easily checks that in fact $c_{r,j}=S(r,j)$. Therefore we obtain $$q_r(j)={1\over n^r} S(r,j)\prod_{i=0}^{j-1}(n-i)\ .$$ At the end the number of balls in ${\rm urn}_0$ is equal to the number of unoccupied urns among ${\rm urn}_1,\ldots,{\rm urn}_n$. The probability $p(k)$ that this number is $k$ is then given by $$p(k)=q_n(n-k)={n!\ S(n,n-k)\over k!\ n^n}\ .$$

-