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