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 :

OldTrout, Going Postal

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\)

OldTrout, Going Postal

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 :

OldTrout, Going Postal

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