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

A classical example are –necklaces and –bracelets. These are words of length in a -letter alphabet, with beginnings and ends of the words glued together and made invisible (so one can visualise them as regular 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 and for the bracelet case it is the dihedral group of order

The set of labelled necklaces/bracelets is just the set of words of length in a -letter alphabet; so one has

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

Let a finite group act on a finite set Denote by for the set of elements of fixed by Then the number of orbits of on is the average, over of i.e.

The proof involves counting of edges in the bipartite graph, with one part being and the other being a pair for and is an edge iff Thus the total number of edges in this graph is

On the other hand, a pair is an edge iff the stabiliser of in Thus, for a -orbit one has the total number of edges leaving equal to Summing over all the -orbits, one obtains the total number of edges completing the proof.

Often it is easier to sum over distinctive representatives of the conjugacy classes as So one has

where denoting the *centraliser* of in

Let us see how this can be applied to **counting bracelets**. For simplicity, let us assume that is *prime*. We consider natural the action of the dihedral group on the set of words of a -letter alphabet.

We know that is generated by the cyclic permutation and an order two “flip” permutation The group can be decomposed into the union of cosets

The only words fixed by a nonidentity element of the subgroup are the “constant” ones, i.e. words consisting of a single letter, and so The coset equals (an unusual coincidence), and so it suffices to find

For a word to be in the latter set, it must have … so there are possibilites.

Thus we count

E.g. for one obtains

Tags: algebra, combinatorics, MAS313, maths

## Leave a Reply