The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I'm assuming that there is a (non-uniformly) random function $h\colon [n] \to [m]$, and $n_j$ is the number of preimages of $j$.

Notice that $\binom{n_j}{2} = \sum_{1 \leq a &lt; b \leq n} 1_{h(a) = h(b) = j}$. We have
$$
\mathbb{E}\left[\binom{n_j}{2}\right] = \frac{1}{2} \sum_{a \neq b} \Pr[h(a) = h(b) = j] = \frac{1}{2} \sum_{a=1}^n \sum_{b \neq a} \Pr[h(a) = h(b) = j] \leq \frac{n-1}{2m} \sum_{a=1}^n \Pr[h(a) = j].
$$
Summing this over $j$, we get
$$
\sum_{j=1}^m \mathbb{E}\left[\binom{n_j}{2}\right] \leq \frac{n-1}{2m} \sum_{a=1}^n \sum_{j=1}^m \Pr[h(a) = j] = \frac{n(n-1)}{2m} = \frac{1}{m} \binom{n}{2}.
$$