Consider randomly throwing $2 n$ balls into $k$ bins. I'm looking to upper bound the probability that at most $n$ bins are not empty.
How big does $k$ have to be for the probability of the event to be at most $n^{-n}$?
We can bound the probability of collisions between the first $n$ balls by ${n \choose 2}/ k$, and get that $k=O(n^{n+2})$ is enough, but this seems like a very weak bound as it ignores the remaining $n$ balls.
I suspect that a much smaller $k$ should be enough. Am I correct?
Since you only want an upper bound, we can select $n$ of the $k$ bins in $\binom kn$ ways, add the probabilities that all $2n$ balls are in these $n$ bins, and ignore the fact that these events aren't mutually exclusive, since taking that into account would only reduce the probability. This yields the upper bound
$$ \binom kn\frac{n^{2n}}{k^{2n}}\;. $$
Now let $k=n^\alpha$; then
$$ \binom{n^\alpha}n\frac{n^{2n}}{n^{2\alpha n}}\lt n^{\alpha n}\frac{n^{2n}}{n^{2\alpha n}}=n^{(2+\alpha-2\alpha)n}\;, $$
and setting $2+\alpha-2\alpha=-1$ yields $\alpha=3$. Thus $k=n^3$ is enough.
If you only need the probability to be less than $n^{-n}$ eventually for large $n$, you can use the stronger asymptotic result
$$ \binom{n^\alpha}n\frac{n^{2n}}{n^{2\alpha n}}\sim\frac{n^{\alpha n}}{\sqrt{2\pi n}\left(\frac n{\mathrm e}\right)^n}\frac{n^{2n}}{n^{2\alpha n}}\lt\mathrm e^nn^{(1-\alpha)n}\;, $$
which implies that the probability is eventually less than $n^{-n}$ for any $\alpha\gt2$.