## Group Actions

We define mathematical objects for our puzzles to allow easy discussion of the ideas needed to solve them.

Let $$\Omega$$ be the set of all colourings of a necklace. For example, with 3 colours and 6 beads we have $$|\Omega| = 3^6$$. Let $$\alpha \in \Omega$$ be a colouring of a necklace, such as RGBRGB, and $$g$$ be an element of its symmetry group $$G$$, such as the reflection that takes 123456 to 654321, where we have numbered the beads from 1 to 6. Then write $$g(\alpha)$$ to mean the resulting colouring after applying $$g$$ to $$\alpha$$. In our example, $$g(\alpha) = BGRBGR$$. This defines a group action on the necklace. Group actions can be defined more formally.

Define the orbit of $$\alpha$$ as

$\mathrm{Orb}_G (\alpha) = \{ g(\alpha) : g \in G \},$

that is, the colourings you get when you rotate and reflect the necklace. For example:

$$\mathrm{Orb}_G(RGBRGB) = \begin{matrix} \{ & RGBRGB, & GBRGBR, & BRGBRG, & \\ & BGRBGR, & RBGRBG, & GRBGRB & \} \end{matrix}$$

Each orbit contains colourings that we consider to be the same: a suitable rotation or reflection moves from one colouring to another. Distinct orbits represent distinct patterns on our necklace, that is, given a colouring in one orbit, it is impossible to reach a colouring in another orbit via rotation or reflection.

Example: our 3-colour 10-bead necklace puzzle is asking for the number of orbits that partition the set of all possible 3-colourings of a 10-bead necklace, acted upon by the dihedral group of order 20.

We’ll need one basic fact about the the size of an orbit which we can derive with the same argument used to prove Lagrange’s Theorem.

Define the stabilizer of $$\alpha$$ as

$G_\alpha = \{ g \in G : g(\alpha) = \alpha \},$

that is, the rotations and reflections that preserve a given colouring. For example, if $$r$$ is the rotation that takes 123456 to 234561, then

$G_{RGBRGB} = \{ 1, r^3 \}$

where 1 is the identity element of $$G$$. Observe $$G_\alpha$$ is a group.

By considering its left (or right) cosets, for any $$\alpha$$, we have

$|G_\alpha| |\mathrm{Orb}_G(\alpha)| = |G| .$

Ben Lynn blynn@cs.stanford.edu