Upper bound on probability that a random function is injective I have two finite sets $A$ and $B$,such that  $|A|=m$ and $|B|=n$. and a random mapping $f : B \to A$. I know that probability that $f$ is injective is $$\binom{m}{n}*n!/m^n.$$
However I need a good upper bound for this that uses either $n$ or $m$ but not both.
I know that I can trivially bound this by $ne$ but this doesn't work well for me. Is there a way to do better? The $ne$ bound is achieved by $n!\le ne*(n/e)^n$ and $\binom{m}{n}\le (me/n)^n$.
Context: I want to find a constant $c$ such that $m \le n^2c \implies$ P($f$ is injective) $\le 0.01$.
 A: This is a very unhelpful way to write the injective probability; it's much more useful to write it as
$$\mathbb{P} = \prod_{i=1}^{n-1} \left( 1 - \frac{i}{m} \right).$$
An easy and useful upper bound can be obtained from here using the inequality $1 - x \le \exp(-x)$, which gives
$$\boxed{ \mathbb{P} \le \exp \left( - \sum_{i=1}^{n-1} \frac{i}{m} \right) = \exp \left( - \frac{ {n \choose 2} }{m} \right) }.$$
We immediately conclude that if $\frac{n^2}{2m} \ge \log 100$ then $\mathbb{P} \le 0.01$ which gives that we can take $\boxed{ c = \frac{1}{2 \log 100} \approx 0.108 \dots }$.
The expression $\frac{ {n \choose 2} }{m}$ itself can be interpreted as the expected number of collisions in a random function $f : B \to A$ which I find pleasantly intuitive. Note that by contrast the bound you're using on $n!$ loses a factor of $\sqrt{n}$ which is pretty bad as you are trying to bound a probability, and the bound you're using on ${m \choose n}$ loses at least an additional such factor, which is why you end up losing at least a factor of $n$. The even more trivial bound is that, since this is a probability, it is at most $1$.
