The probability there is at least one bin with exactly 1 ball in it

Question

If you throw $m>0$ balls into $n>0$ bins independently and uniformly, what is the probability that there is at least one bin with exactly one ball in it?

Answer 1

First, since there are $n$ possible places to put any of the $m$ balls, we have $n^m$ equally likely distributions of the balls, and we need only to count how many of these have exactly one ball in at least one bin. Note that to get to $n^m$, we assumed that both the balls and the bins are distinguishable. We may assume that the former are numbered from $1$ to $m$ and the latter from $1$ to $n$. From now on, I'll call a bin with exactly one ball a "singleton".

We might try to count the number of distributions with $k$ singletons as follows. There are $\binom nk$ ways to choose the bins, and $\binom mk$ ways to choose the balls to go in them. They can be placed in the bins in $k!$ ways. The remaining $m-k$ balls can be placed in the remaining $n-k$ bins in $(n-k)^{m-k}$ ways, giving a total of $$ \binom nk\binom mk k!(n-k)^{m-k}$$

Unfortunately, this isn't correct, because one or more of the other $n-k$ bins may get exactly one ball. The principle of inclusion and exclusion proceeds by making the incorrect calculation above, and making successive corrections until it arrives at the correct answer.

Before developing the formula, we must deal with one other question. How large can $k$ be? If $n\geq m$ then each ball can go in its own bin, so $k\leq m$. If $m>n$ then at most $n-1$ bins can be singleton, and the remaining bin contains all the other balls. Then $$k\leq \phi(m,n):=\cases{ m,&$n\geq m$\\ m-1,&$n<m$ }$$ or more simply, $$\phi(m,n) = m-[n<m]$$ where $[\cdot]$ is the Iverson bracket

Now we start with $k=1$ to get $$ \binom n1\binom m1 1!(n-1)^{m-1}$$

We note however, that any distribution that has two singletons will have been counted twice in the above formula, once for each singleton, so we have to subtract the distributions with two singletons, giving $$\binom n1\binom m1 1!(n-1)^{m-1}- \binom n2\binom m2 2!(n-2)^{m-2}$$ Now a distribution with three singletons has been counted three times (once for each singleton) and subtracted three times (once for each pair of them) so we have to add these distributions back in, and so on.

By the inclusion-exclusion principle, the number of distributions containing at least one singleton is $$\sum_{k=1}^{\phi(m,n)}(-1)^{k+1}\binom nk\binom mk k!(n-k)^{m-k}\tag1$$

To compute the desired probability, just divide the value from $(1)$ by $n^m$.

Obviously, the expression in $(1)$ unattractive. I don't know if it can be simplified. At least you can compute for any value of $m$ and $n$, with a computer at any rate.