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?
On
Hints/Guiding questions:
On
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).
On
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}\ .$$
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\;.$$