We've got $n$ urns, I have to show that for some $c>0$ there are $c \sqrt{n}$ balls, that after putting them inside urns, probability that all the urns have at most 1 ball is equal or lower than $\frac{1}{e}$.
I know that there are $\frac{n!}{(n-c\sqrt{n})!}$ different cases of putting $c\sqrt{n}$ balls following mentioned assumption (first ball can be thrown to $n$ different urns, second to $n-1$, $c \sqrt{n}$ ball to $n-c\sqrt{n}+1$ urns) and there are $n^{c\sqrt{n}}$ all cases of putting these balls inside $n$ urns.
Probability is the division of these two components, but how it can be compared to $e^{-1}$? I've got a hint to use inequality $e^{-x} \ge 1-x$, but after determining probabilities of these two events and dividing first by second, I don't know what to do next.
Edit So, using Stirling formula I've got $\frac{\frac{n!}{(n-c\sqrt{n})!}}{n^{c\sqrt{n}}}$ which is about $\sqrt{2\pi n} (\frac{n}{e})^n \cdot (\sqrt{2\pi (n-c\sqrt{n})} (\frac{n-c\sqrt{n}}{e})^{c\sqrt{n}})^{-1} \cdot (n^{c\sqrt{n}})^{-1}$
I simplified it into $\sqrt{\frac{n}{n-c\sqrt{n}}} \cdot (\frac{n}{n-c\sqrt{n}})^{n-c\sqrt{n}} \cdot e^{-c\sqrt{n}}$
But now I'm stuck again and I'm not certain if that Stirling approximation is greater or lower than previous fraction.
The number of possibilities of putting $c\sqrt n$ balls into $n$ urns s.t. each has his own urn is actually $n\choose c\sqrt n$.
The number of different ways of putting $c\sqrt n$ balls into $n$ urns is given by the probability of dividing $c\sqrt n$ objects to $n$ cells, which is known to be given by $n+c\sqrt n-1\choose n-1$.
From these two quantities we obtain: $$ {n\choose c\sqrt n} / {n+c\sqrt n-1\choose n-1}=\prod_{i=1}^{c\sqrt n - 1}\frac{n-c\sqrt n+i} {n+i}=\prod_{i=1}^{c\sqrt n - 1}1 -\frac{c\sqrt n} {n+i} \leq\prod_{i=1}^{c\sqrt n - 1}1 -\frac{c\sqrt n} {2n}\leq(1-c/2\sqrt n)^{c\sqrt n}\\ \leq e^{\frac{-c} {2\sqrt n}\cdot c\sqrt n}=e^{-c^2/2} $$