What is the probability that a random function has no collisions?

Question

Let $N = 2^{n}$ and $M= 2^{m}$.

Consider a random function picked uniformly at random from the set of functions given by

$$\{f: \{0, 1\}^{m} \rightarrow\{0,1\}^{n} \}.$$

What is the probability that the function, so picked, has no collisions? A collision is defined as two inputs $x_1$ and $x_2$, with $x_1 \neq x_2$, such that

$$f(x_1) = f(x_2).$$

---

I found a statement in this paper (page $3$) which says that

Note that if $M = o(N^{1/2})$, then there are no collisions with probability approaching $1$..

What might be a proof of this fact?

Answer 1

The proof is: for any particular pairs of $x_1, x_2$, we have $$\mathbb{P}(f(x_1) = f(x_2)) = \frac{1}{N}.$$ So by the union bound $$\mathbb{P}(\exists x_1\neq x_2, f(x_1) = f(x_2)) \leq \frac{M^2}{N} = o(1).$$