- 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)!} \]
