# The Cyclic Group of a Necklace

A Cyclic group is a group $$G$$ that can be generated by a single element $$g$$.  The generator is denoted by $$\langle g \rangle$$ and satisfies :

$$g^n = e$$,

where $$e$$ is the identity element.

A Cyclic group, $$C_n$$, is the group of rotations of a regular $$n$$-gon.

A necklace is composed of $$n$$ beads.

We consider a necklace with six beads  and its rotational symmetries.

We number the set of beads from one to six clockwise :

$$X = \{1, 2, 3, 4, 5, 6\}$$

The Cayley graph :

We apply a group operation, $$\circ$$, of a rotation through $$\pi/3$$ anti-clockwise about the centre which acts on the set $$X$$.

The Cayley table :

$$\begin{array}{c|cccccc} \circ & e & r & r^2 & r^3 & r^4 & r^5\\ \hline e & e & r & r^2 & r^3 & r^4 & r^5\\ r & r & r^2 & r^3 & r^4 & r^5 & e\\ r^2 & r^2 & r^3 & r^4 & r^5 & e & r\\ r^3 & r^3 & r^4 & r^5 & e & r & r^2\\ r^4 & r^4 & r^5 & e & r & r^2 & r^3\\ r^5 & r^5 & e & r & r^2 & r^3 & r^4 \end{array}$$

where $$e$$ is the identity element (nothing changes) and $$r$$ is the rotation through $$\pi/3$$ and is the generator $$\langle r \rangle$$ of the group since

$$r^6 = r^0 = e$$

There are four subgroups: the trivial subgroup $$\{e\}$$, two proper subgroups $$\{ e, r^3\}$$ and $$\{e, r^2, r^4\}$$ and the whole group $$\{e, r, r^2, r^3, r^4, r^5\}$$.  Note that the order (size) of these subgroups are the divisors of six, namely, $$1, 2, 3$$ and $$6$$.

$$\begin{array}{c|cc} \circ & e & r^3\\ \hline e & e & r^3\\ r^3 & r^3 & e \end{array}$$

The rotation $$r^3$$ is $$\pi$$.

$$\begin{array}{c|ccc} \circ & e & r^2 & r^4\\ \hline e & e & r^2 & r^4\\ r^2 & r^2 & r^4 & e\\ r^4 & r^4 & e & r^2 \end{array}$$

The rotation $$r^2$$ is $$2\pi/3$$ and $$r^4$$ is $$4\pi/3$$ – the inverse.

We consider the permutations of the set $$X = \{1, 2, 3, 4, 5, 6 \}$$ under the action of  the group $$G =\{e, r, r^2, r^3, r^4, r^5\}$$.

For the identity element the permutation in two-line notation is

$$\biggl( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 3 & 4 & 5 &6 \end{matrix} \biggr )$$

It just says that every element in $$X$$ maps to itself under the null rotation of the group operation.  That is, every element is fixed.  Nothing happens.

This permutation in one-line notation is :

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

We have six cycles of length one.

The permutations of the other five rotations are given in the following sketch :

Using this information, the cycle index polynomial counts the number of different necklaces that can be made from $$n$$ number of beads using $$a$$ different colours.

$$\displaystyle Z(C_n) = \frac 1n \sum_{d|n} \varphi(d) a_d^{n/d}$$

where $$Z(C_n)$$ is the cycle index of the cyclic group of order $$n$$, $$\frac 1n$$ is the average over the following sum, $$\sum_{d|n}$$ is the sum over the divisors of the number, $$\varphi(d)$$ is the totient function of each divisor (the coefficient of the variable here) and $$a_d^{n/d}$$ is the variable with the cycle length of the divisor as the subscript and the number of these cycle lengths as the superscript.

For six beads, we have :

$$\displaystyle Z(C_6) = \frac 16 \sum_{d|6} \varphi(d) a_d^{6/d}$$

which simplifies to :

$$\displaystyle Z(C_6) = \frac16 (a_1^6 + a_2^3 + 2a_3^2 + 2a_6)$$

When $$a = 1$$, we have a trivial sum and the number of different necklaces is one.

$$\frac 16 (1 + 1 + 2 + 2) = 1$$

When $$a = 2$$, we have :

$$\frac 16 (2^6 + 2^3 + 2\cdot2^2 + 2\cdot2) = 14$$

These are : the seven easy ones first –

R R R R R R
R R R R R B
R R R R B B
R R R B B B
R R B B B B
R B B B B B
B B B B B B

where R is red and B is blue.

Where do we find the other seven?  The first and last two will yield nothing more.

From the third and fifth we find :

R R R B R B
R R B R R B
R B R B B B
R B B R B B

The fourth yields :

R B R B R B
R R B B R B
R R B R B B

For a total of fourteen.

When $$a = 3$$, the number of different necklaces is $$130$$.

Notes :

Every cyclic group is Abelian.  That is, the group operation is commutative.

$$rr^3 = r^4 = r^3r$$

© OldTrout $$2018$$

No Audio file – does not translate well