# Counting some Examples

• 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)!}$