Exercise 11.5.1

$\star$ Suppose that we insert $n$ keys into a hash table of size $m$ using open addressing and uniform hashing. Let $p(n,m)$ be the probability that no collision occur. Show that $p(n,m) \le e^{-n(n-1)/2m}$. (Hint: See equation (3.12).) Argue that when $n$ exceeds $\sqrt{m}$, the probability of avoiding collisions goes rapidly to zero.