Number of possible pairs from $\{1,\dots, n\}$ with $i < j$ I am not sure how to find the above number of possible pairs. For example, for $\Sigma = \{1,2,3,4\}$, the desired number would be $6$. I see that this is half of ${4 \choose 2}$ and I am wondering if this is in fact the way to go about this: take all possible two element selections from a set of $n$ elements, and then equate choosing $(i, j)$ with choosing $(j, i)$. 

${4\choose 2}$ is 6! ${n\choose 2}$ is the number of ways of choosing 2 elements from a set of n in any order. So it will just give you the number of pairs $(i, j)$ - but that is exactly what you want, as in any pair $(i,j)$ one of the elements must be greater than the other.
