k(k-1)/2: Combinations and the Birthday bound Disclaimer: I'm new to cryptography. 

Background: I'm reading Cryptography Engineering by Ferguson, Schneier, and Kohno, where, in Chapter 2, the authors write this:



Question: What is $k(k-1)/2$ called? It seems related to an arithmetic sequence $a_n = a_1 + (n-1)d$ and some kind of combination (my notes below), but I can't place it.
$k(k-1)/2$ is usually called a binomial coefficient and written $k \choose 2$. It corresponds to the number of unordered pairs of distinct elements out of $k$ elements. It does indeed correspond to the sum ${k \choose 2} = \sum_{i=1}^{k-1} i$. This is quite intuitive: fixing one element, you have $k-1$ pairs containing this element. Now remove it, consider a second element: you have $k-2$ pairs with this second element, and so on. At the end, you get $(k-1) + (k-2) + \cdots +2 + 1 = k(k-1)/2$ pairs.

your bottom right formula is the general formula for ${k \choose r}$.