$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?

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\;.$$