I've got a balls and bins problem. Suppose I throw $n$ balls uniformly at random into $n$ bins. What is the probability that exactly $k$ bins end up with exactly $1$ ball?
I know this seems a classical problem and may look "simple" or "naive," but I've worked days on it and still can't get the answer.
However, I think I do have a good approximation for it. Namely, let $X$ denote the number of such bins. Then
$ Pr(X=k) \approx \binom{n}{k}\left(\frac{1}{e}\right)^{k}\left(1-\frac{1}{e}\right)^{n-k} $
where $1/e$ is an approximation for $(1-1/n)^{n-1}$.
This approximation works great when $n$ is big and poorly when $n$ is small (like $n<5$).
Anyway, I'm looking for an exact expression. Anyone have an idea?
PS: I've written a simple simulation in C++; you can check your answer with it first: Simulation Code Here.