Pólya Theory

Let $\Omega$ be the set of all colourings of a necklace. For example, with 3 colours and 6 beads we have $\mid \Omega \mid =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 )=\mathrm{BGRBGR}$. This defines a group action on the necklace. Group actions can be defined more formally.

Define the orbit of $\alpha$ as

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

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. Hence in our new terminology, the problem is now to find the number of orbits.

Define the stabilizer of $\alpha$ as

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

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

(compare with Lagrange’s Theorem).