- It is true that

\[ \#\{ (i,j) : 1 \leq i < j \leq n\} = \frac 12 n(n-1)\]

and in general

\[ \#\{ (i_1,i_2,\cdots, i_k) : 1 \leq i_1 < i_2 < \cdots < i_k\leq n\} = \frac 1{k!} \frac{n!}{(n-k)!}\]

To see this, understand that each element of the set

\[ \{ (i_1,i_2,\cdots, i_k) : 1 \leq i_1 < i_2 < \cdots < i_k\leq n\} = \frac 1{k!} \frac{n!}{(n-k)!}\]

Corresponds the a different choice of a subset of \(k\) elements from the set

\[ \{1,2,\cdots,n\}\ .\]

We know that the number of such subsets of size \(k\) from a set of different element of size \(n\) is given by

\[\begin{pmatrix} n \\ k \end{pmatrix} = \frac{n !}{k ! (n-k)!} \]