«
»

Orbit-counting Lemma

By Dima

Excercises in algebra

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.

Possibly related posts: (automatically generated)

Tags: , , ,

This entry was posted on 31 March, 2009 at 17:11 and is filed under undergrad maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply