Find Divisible Sum Pairs in an array in O(n) time
Consider in your example the set $S_1=\{1, 4\}$ and the set $S_2=\{2,5\}$. Let $n_1 = 2$ and $n_2=2$, the sizes of sets $S_1$ and $S_2$. All of the elements $x\in S_1$ satisfy $x\equiv 1\pmod 3$ and so are of the form $x=3s+1$ for some $s$. Similarly all $y\in S_2$ are of the form $y=3t+2$ so $x+y=3s+1+3t+2=3(s+t+1)$, which is divisible by 3. The number of such pairs is $n_1\cdot n_2$: pick one element, $x$, from $S_1$ and one element, $y$, from $S_2$ to form the pair $(x, y)$, rearranging, if necessary so that the first element is less than the second. In sum, there will be $n_1\cdot n_2=2\cdot 2$ pairs: $(1, 2), (1, 5), (4, 2), (4, 5)$, which, after arranging the pairs in component orders, gives $(1, 2), (1, 5), (2, 4), (2, 5)$ (your highlighted quote didn't do that).

For a general $k$, then, you'll have sets $S_i$, for $i=1, \cdots k-1$ (ignoring $S_0$ for the moment), so if $n_i$ represents the size of $S_i$, you'll have pairs $(x,y)$ where $x\in S_i$ and $y\in S_{k-i}$. The number of such pairs is $n_1\cdot n_{k-1}+n_2\cdot n_{k-2}+\dotsc$.

[You have to be a bit careful, since, first, the sum only should include those products $n_i\cdot n_{k-i}$ for which $i&lt;k-i$, and second, you'll have to account for the cases where $i$ and $k-i$ are equal. You'll also have to deal with the pairs you get from $S_0$, which have to be counted differently.]

I'd suggest ignoring the sentence where $n(n-1)/2$ appears: it's true but irrelevant.