Counting Number of Groupings Using Group Actions 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.
 A: 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. 
