◀ Burnside's LemmaInventory Theorem ▶
Contents

The Cycle Index Polynomial

When first attempting to solve the necklace problem, we noticed that certain patterns appear more than others amongst the \(3^6\) colourings. Roughly speaking, the easier it was to spot a pattern in a colouring, the rarer the colouring. For example, RRRRRR appears only once, RGRGRG appears twice, while something like RGBRRB appears 12 times in various guises. Pólya captured the reason behind this, and found an elegant way to describe it. Actually, J. H. Redfield published it first, but was somehow overlooked.

Again we shall number the beads from 1 to 6. Rotations and reflections are permutations of the beads. The key to solving the problem is to study the cycle structure of these permutations. For example, the reflection \(s\) taking 123456 to 654321 is the permutation \(s = (16)(25)(34)\) which consists of 3 2-cycles. We can represent this by writing \(x_2^3\).

Observe a permutation has no effect on a colouring if and only if each cycle consists of beads of the same colour. For example, if 1 and 6 are both red, 2 and 5 are both green and 3 and 4 are both blue, then \(s\) leaves the colouring unchanged. Conversely, if \(s\) leaves a given colouring unchanged, 1 and 6 must be the same colour, and similarly for 2 and 5, and 3 and 4.

Thus there are exactly \(3^3\) ways to colour 6 beads so that \(s\) has no effect, so \(|Fix_\Omega(s)| = 27\).

Another example: the rotation \(r^2\) is the permutation \((135)(246)\). This has 2 3-cycles, which we write as to \(x_3^2\), and there are \(3^2\) ways to colour 6 beads so that \(r^2\) has no effect, so \(|Fix_\Omega(r^2)| = 9\).

More generally, if \(G\) is a permutation group on a set \(X\) then the cycle index polynomial of \(G\) is:

\[ P_{(G,X)}(x_1, ..., x_n) = \frac{1}{G}\sum_{g\in G} x_1^{j_1(g)} ... x_n^{j_n(g)} \]

where \(j_k(g)\) is the number of cycles of length \(k\) in the permutation \(g\). We omit \(X\) when it is clear from context.

Thus, by Burnside’s Lemma, the number of necklaces with \(n\) beads of \(k\) colours is \(P_G(k,...,k)\) where \(G\) is the dihedral group of order \(2n\). More generally:

Theorem: (Pólya) Let \(G\) be a permutation group on a set \(X\). Let \(C\) be a set of size \(k\). Let \(\Omega\) be the set of all functions from \(X\) to \(C\), and define a group action of \(G\) on \(\Omega\) in the natural way. Then the number of orbits of \(G\) acting on \(\Omega\) is

\[ P_{(G,X)}(k, ..., k) . \]

The 6 bead case is small enough to compute \(P_G\) explicitly. We have the identity,

\[ 1 = (1)(2)(3)(4)(5)(6) \]

5 (nontrivial) rotations

\[ (123456), (135)(246), (14)(25)(36), (153)(264), (165432), \]

and 6 reflections

\[ (16)(25)(34), (15)(24), (14)(23)(56), (13)(46), (12)(36)(45), (26)(35), \]

giving

\[ P_G = \frac{1}{12} \left( x_1^6 + 3 x_1^2 x_2^2 + 4 x_2^3 + 2 x_3^2 + 2 x_6 \right) . \]

Then the number of different 6-bead necklaces where there are 3 kinds of beads is:

\[ (3^6 + 3\cdot 3^2 3^2 + 4 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3)/12 = 92. \]

Cyclic, dihedral and symmetric groups

Some exercises. Show that the cycle index polynomial for:

…the cyclic group of order \(n\) is:

\[ \frac{1}{n} \sum_{d|n} \phi(n/d)x^d_{n/d} = \frac{1}{n} \sum_{d|n} \phi(d)x^{n/d}_d \]

…the symmetry group of an \(n\)-gon for odd \(n\) is:

\[ \frac{1}{2n}\left( \sum_{d|n}\phi(d)x^{n/d}_d + n x_1 x^{(n-1)/2}_2 \right) \]

…the symmetry group of an \(n\)-gon for even \(n\) is:

\[ \frac{1}{2n}\left( \sum_{d|n}\phi(d)x^{n/d}_d + \frac{n}{2} x_1^2 x_2^{(n-2)/2} + \frac{n}{2} x_2^{n/2} \right) \]

…the group of all permutations on \(n\) objects is:

\[ \sum \frac{x_1^{\lambda_1} ... x_n^{\lambda_n}}{1^{\lambda_1} \lambda_1 ! 2^{\lambda_2}\lambda_2 ! ... n^{\lambda_n} \lambda_n !} \left[ \lambda_1 + 2\lambda_2 + ... + n\lambda_n = n \right] \]

In particular, for a 10-bead necklace with 3 kinds of beads, we have the cycle index polynomial

\[ P = 20^{-1} \left( x_1^{10} + x_2^5 + 4 x_5^2 + 4 x_{10} + 5 x_1^2 x_2^4 + 5 x_2^5 \right) \]

and \(P(3,...,3) = 3210\).

Ben Lynn blynn@cs.stanford.edu 💡