## Orbit-counting Lemma

Excercises in algebra

One application of actions of finite groups is in combinatorics, more precisely, counting objects that possess particular symmetries.

A classical example are $n$necklaces and $n$bracelets. These are words of length $n$ in a $k$-letter alphabet, with beginnings and ends of the words glued together and made invisible (so one can visualise them as regular $n-gons$ with letters from the alphabet placed at the vertices). Two necklaces are identical when one is obtained from another by rotations; two bracelets are identical when one can be obtained from another by rotation and a “flip”. One can view counting of necklaces and bracelets as counting of orbits of certain groups on the sets of “labelled” necklaces (resp. bracelets). For the necklace case, the group is $\mathbb{Z}_n,$ and for the bracelet case it is the dihedral group of order $2n.$
The set $\Omega$ of labelled necklaces/bracelets is just the set of words of length $n$ in a $k$-letter alphabet; so one has $|\Omega|=k^n.$

Orbit counting is often simplified by the following result, often attrubuted to Burnside, although it was certainly known to Frobenius.

Let a finite group $G$ act on a finite set $\Omega.$ Denote by $\Omega^g,$ for $g\in G,$ the set of elements of $\Omega$ fixed by $g.$ Then the number $N$ of orbits of $G$ on $\Omega$ is the average, over $G,$ of $|\Omega^g|,$ i.e.
$\displaystyle N=\frac{1}{|G|}\sum_{g\in G} |\Omega^g|.$

The proof involves counting of edges in the bipartite graph, with one part being $\Omega,$ and the other being $G;$ a pair $(\omega,g),$ for $\omega\in\Omega$ and $g\in G$ is an edge iff $\omega\in\Omega^g.$ Thus the total number of edges in this graph is $\sum_{g\in G} |\Omega^g|.$
On the other hand, a pair $(\omega,g)$ is an edge iff $g\in G_{\omega},$ the stabiliser of $\omega$ in $G.$ Thus, for a $G$-orbit $\Omega_\omega,$ one has the total number of edges leaving $\Omega_\omega$ equal to $|\Omega_\omega||G_\omega|=|G|.$ Summing over all the $G$-orbits, one obtains the total number of edges $N|G|,$ completing the proof.

Often it is easier to sum over distinctive representatives $R=\{g_1,\dots,g_t\}$ of the conjugacy classes $g^G=\{xgx^{-1}\mid x\in G\},$ as $|\Omega^g|=|\Omega^{xgx^{-1}}|.$ So one has
$\displaystyle N=\frac{1}{|G|}\sum_{g\in R } |\Omega^g||g^G|=\sum_{g\in R } \frac{|\Omega^g|}{|C_G(g)|},$
where $C_G(g):=\{x\in G\mid xgx^{-1}\}$ denoting the centraliser of $g$ in $G.$

Let us see how this can be applied to counting bracelets. For simplicity, let us assume that $n$ is prime. We consider natural the action of the dihedral group $G=D_{2n}$ on the set of $k^n$ words of a $k$-letter alphabet.

We know that $G$ is generated by the cyclic permutation $c=(1,2,\dots,n)$ and an order two “flip” permutation $f=(2,n)(3,n-1)\dots (\lfloor n/2\rfloor,\lceil n/2\rceil).$ The group can be decomposed into the union of cosets $G=\langle c\rangle\cup f\langle c\rangle.$
The only words fixed by a nonidentity element $x=c^m$ of the subgroup $\langle c\rangle$ are the “constant” ones, i.e. words consisting of a single letter, and so $|\Omega^x|=k.$ The coset $f\langle c\rangle$ equals $f^G$ (an unusual coincidence), and so it suffices to find
$\Omega^f.$ For a word $w$ to be in the latter set, it must have $w_2=w_n,$ $w_3=w_{n-1},$$w_{\lfloor n/2\rfloor}=w_{\lceil n/2\rceil},$ so there are $k^{(n+1)/2}$ possibilites.
Thus we count $N|G|=2nN=|\Omega|+(n-1)|\Omega^c|+n|\Omega^f|=k^n+(n-1)k+n k^{(n+1)/2}.$
E.g. for $n=5,$ $k=3$ one obtains $N=39.$