I was reading about how group actions can be used to solve counting problems (i.e. Burnside's Lemma can count the number of arrangements of a roulette wheel).
Obviously this problem can be solved easily using counting methods, but can we use group actions to count say, the number of unordered pairs in $\{1,2,...,n\}$?
My first thought is to find a transitive action on the set of all pairs and then use the orbit stabilizer theorem to count the number of pairs in the orbit, but I'm having some difficulties.
Yes, and in fact let's generalize to unordered $k$-tuples. Write $[n]$ for the set $\{ 1, 2, \dots n \}$. The set of ordered $k$-tuples is the set $[n]^{[k]}$ of functions $[k] \to [n]$. This set has a natural action of the symmetric group $S_k = \text{Aut}([k])$, and the set of unordered $k$-tuples is the set of orbits under this action.
We can count the number of orbits using Burnside's lemma as follows. A permutation $\pi \in S_k$ fixes a function function $f : [k] \to [n]$ iff is constant on each of the cycles of $\pi$. It follows that the number of such functions fixed by $\pi$ is $|\text{Fix}(\pi)| = n^{c(\pi)}$ where $c(\pi)$ denotes the total number of cycles, and hence Burnside's lemma gives that the number of unordered $k$-tuples is
$$\frac{1}{k!} \sum_{\pi \in S_k} n^{c(\pi)}.$$
When $k = 2$ this gives
$$\frac{n^2 + n}{2} = {n+1 \choose 2}$$
since in this case there are just two permutations in $S_2$, with $1$ and $2$ cycles respectively. When $n = 3$ this gives
$$\frac{n^3 + 3n^2 + 2n}{6} = {n+2 \choose 2}$$
since in this case there are six permutations in $S_3$, the identity has $3$ cycles, the three transpositions have $2$ cycles, and the two $3$-cycles have $1$ cycle. In general this gives
$$\frac{1}{k!} \sum_{i=0}^k s(k, i) n^i$$
where $s(k, i)$ denotes the (unsigned) Stirling numbers of the first kind, which count the number of permutations in $S_k$ having $i$ cycles. It is not at all obvious at first glance that this sum should simplify to ${n+k-1 \choose k}$, but this can be proven in several different ways, e.g. by establishing an appropriate recursion for the Stirling numbers.