Chapter 14: Group Actions and Symmetry

How many necklaces remain distinct after rotation?

Imagine designing a circular bead necklace with four equally spaced spots ($n=4$), where each bead can be colored either black or white. If the necklace has a fixed clasp marking position zero, there are $2^4 = 16$ distinct labeled binary strings. However, if we remove the clasp and allow the necklace to rotate freely in space, several different strings describe the exact same physical necklace!

What, Why, and Real-World Applications:

• What is Group Action Enumeration? It is the branch of combinatorics that counts distinct physical objects up to structural symmetry (such as rotations, reflections, or swaps).
• Why Naive Division Fails: Simply dividing total string count by the number of rotations ($16 / 4 = 4$) yields an incorrect answer. This naive calculation assumes that every necklace looks different under all four rotations. While asymmetric necklaces have $4$ distinct views, highly symmetric necklaces (like all-white 0000 or alternating 0101) look identical under some rotations. Group action techniques handle these varying symmetries seamlessly.
• Applications:
  • Chemistry & Drug Design: Counting distinct chemical isomers of cyclic molecules (e.g., benzene ring derivatives).
  • Computer Architecture & IC Design: Identifying unique rotational configurations of pinouts and printed circuit board layouts.
  • Cryptography & Coding Theory: Designing cyclic error-correcting codes and shift-register sequences.
  • Tile & Textile Patterns: Finding non-redundant decorative layouts under rotational and reflective symmetry.

We will keep the colors distinguishable and allow repeated colors. At first, turning the necklace over is not an allowed identification. That choice matters: rotation gives necklaces, while rotation together with reflection gives bracelets. Neither operation automatically exchanges black and white.

The prerequisites Permutations and Combinations and Permutation Structure supply permutation notation and disjoint cycles. The small amount of abstract algebra needed here is developed directly below; the course roadmap lists the broader abstract-algebra background.

14.1 Permutation and symmetry groups, orbits

A group is a set $G$ with a multiplication that is closed and associative, an identity $e$, and an inverse $g^{-1}$ for every $g\in G$. For permutations, multiplication means composition: throughout this chapter, $(gh)(i)=g(h(i))$, so the rightmost permutation acts first. A permutation group on a finite set $P$ is a collection of permutations of $P$ satisfying these conditions.

For $P=\{0,1,2,3\}$, let $\rho=(0\,1\,2\,3)$. The rotations form the cyclic group

$$ C_4=\{e,\rho,\rho^2,\rho^3\},\qquad \rho^4=e. $$

Products add exponents modulo $4$, so closure holds; the inverse of $\rho^j$ is $\rho^{4-j}$, with exponents interpreted modulo $4$. Associativity comes from composition of functions. The order of this group is $|C_4|=4$.

A group acts on a set $X$ when each $g\in G$ gives a transformation $x\mapsto g\cdot x$ satisfying

$$ e\cdot x=x,\qquad (gh)\cdot x=g\cdot(h\cdot x). $$

Here positions and configurations are different sets. The group permutes the four positions in $P$, and thereby acts on the $16$ colorings in $X=\{0,1\}^P$. For a coloring $f:P\to\{0,1\}$, define

$$ (g\cdot f)(i)=f(g^{-1}(i)). $$

This sends the color originally at $i$ to $g(i)$. The inverse ensures the action law: $(gh)^{-1}=h^{-1}g^{-1}$, so evaluating both sides gives the same original entry.

The orbit of $x$ is the set of all configurations reachable by allowed symmetries:

$$ G\cdot x=\{g\cdot x:g\in G\}. $$

Being in the same orbit is an equivalence relation. Identity gives reflexivity, inverses give symmetry, and multiplication gives transitivity. Thus the orbits partition $X$; write $X/G$ for the set of orbits.

Worked example. Under $C_4$, the orbit of 0011 is $\{0011,1001,1100,0110\}$. The orbit of 0101 is $\{0101,1010\}$. Both words have two black beads, but their orbits differ: in the first, the black beads are adjacent; in the second, they are opposite. The number of black beads is an invariant, a quantity unchanged by the action, but it does not completely identify an orbit.

We can enlarge the group. Let $\tau(i)=-i\pmod4$. This reflection fixes positions $0,2$ and exchanges $1,3$. Rotations and this reflection generate

$$ D_4=\{\rho^j,\rho^j\tau:0\le j\lt4\},\qquad \tau^2=e,\qquad \tau\rho\tau=\rho^{-1}. $$

Our convention is $|D_n|=2n$ for a regular $n$-gon, with $n\ge3$. Reflections reverse cyclic order, while rotations preserve it. If all position relabelings are allowed instead, the group is $S_4$, of order $4!=24$; it sends any two-black-bead placement to any other. Under $S_4$, black-bead count is a complete invariant and there are $5$ orbits.

Exercise. Find the $C_4$ orbit of 0111. Does adding reflections change this orbit? Hint: locate the unique white bead. Answer: $\{0111,1011,1101,1110\}$; reflection adds no new word because rotations already put that white bead at every position.

14.2 Burnside's lemma

A configuration $x$ is fixed by $g$ when $g\cdot x=x$. Write

$$ \operatorname{Fix}_X(g)=\{x\in X:g\cdot x=x\}. $$

For a finite group $G$ acting on a finite set $X$, Burnside's lemma (also known as the Cauchy–Frobenius Lemma) states:

$$ |X/G|=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}_X(g)|. $$

Thus we average fixed-configuration counts over group elements. We do not average orbit sizes. This finite-action formulation is also given in Klaus Sutner's Group Actions and Counting notes. cs.cmu.edu

Proof by double counting. Consider

$$ \mathcal F=\{(g,x)\in G\times X:g\cdot x=x\}. $$

Counting first by $g$ gives $|\mathcal F|=\sum_g|\operatorname{Fix}_X(g)|$. Counting first by $x$ gives $|\mathcal F|=\sum_x|G_x|$, where $G_x=\{g:g\cdot x=x\}$ is the stabilizer of $x$.

For a fixed $x$, the map $g\mapsto g\cdot x$ reaches every element of its orbit. Every fiber has $|G_x|$ elements: if $g_0\cdot x=y$, then exactly the elements $g_0h$, with $h\in G_x$, send $x$ to $y$. Hence $|G|=|G\cdot x|\,|G_x|$.

An orbit $O$ consequently contributes

$$ \sum_{x\in O}|G_x|=\sum_{x\in O}\frac{|G|}{|O|}=|G| $$

to the second count. Each orbit contributes the same amount, even though its size may differ. Therefore $|\mathcal F|=|G|\,|X/G|$, proving the lemma. Section 14.4 examines the fiber argument in more detail.

For colorings of positions, fixed points are easy to count from cycles. A coloring fixed by $g$ must be constant along each cycle of $g$ on $P$, because repeatedly applying $g$ moves a color around that cycle. Conversely, choosing one color independently for every cycle produces a fixed coloring. With $q$ distinguishable colors and $c(g)$ position cycles, including singleton cycles,

$$ |\operatorname{Fix}_{\{1,\ldots,q\}^P}(g)|=q^{c(g)}. $$

Here a position fixed by $g$ is only a cycle of length $1$; it is not the same thing as a whole configuration fixed by $g$.

Exercise. How many three-color necklaces have four beads? Hint: the four rotation cycle counts are $4,1,2,1$. Solution: $(3^4+3+3^2+3)/4=24$.

14.3 Pólya enumeration and pattern inventory

Burnside gives a total. Pólya enumeration also records how much of each color an orbit uses. Introduce formal variables $R$ and $B$ for the two distinguishable colors. A coloring with $r$ red beads and $b$ blue beads has weight $R^rB^b$. These variables are bookkeeping devices, not numerical probabilities.

The pattern inventory is

$$ I_G(R,B)=\sum_{O\in X/G}R^{r(O)}B^{b(O)}, $$

where the exponents are well-defined because position permutations preserve color counts. Thus the coefficient of $R^rB^b$ counts orbits of that composition, with each orbit contributing once.

If a position cycle has length $j$, coloring the entire cycle red contributes $R^j$ and coloring it blue contributes $B^j$. Its fixed-coloring factor is $R^j+B^j$. If $g$ has $c_j(g)$ cycles of length $j$, independence between cycles gives

$$ F_g(R,B)=\prod_{j=1}^n(R^j+B^j)^{c_j(g)}. $$

The finite-color form of Pólya's theorem is

$$ I_G(R,B)=\frac1{|G|}\sum_{g\in G}F_g(R,B). $$

Why averaging still works. Repeat the double count of Section 14.2, assigning weight $R^{r(x)}B^{b(x)}$ to each fixed pair $(g,x)$. All elements of one orbit have the same weight. That orbit contributes $|G|$ times its weight before division by $|G|$. The same proof works with any finite list of distinguishable colors: replace $R^j+B^j$ by the sum of the $j$th powers of their variables. Sutner's Pólya–Redfield notes present the pattern inventory in this form. cs.cmu.edu

Worked example. For the four rotations,

$$ I_{C_4}(R,B)=\frac14\left((R+B)^4+2(R^4+B^4)+(R^2+B^2)^2\right). $$

Expanding gives

$$ I_{C_4}(R,B)=R^4+R^3B+2R^2B^2+RB^3+B^4. $$

For example, the coefficient of $R^2B^2$ is $(6+0+2)/4=2$. Substituting $R=B=1$ gives $6$, while substituting $R=1,B=t$ gives $1+t+2t^2+t^3+t^4$, counting necklaces by blue-bead number.

The diagram isolates the half-turn contribution. Its two cycles receive colors independently, giving four fixed words. The two mixed choices have the same weight, so the coefficient $2$ in $(R^2+B^2)^2$ counts two fixed labeled words. After averaging over all rotations, the coefficient $2$ in the final inventory counts two orbits, illustrated below as adjacent and opposite blue beads. These are different counting stages.

Exercise. Introduce a third color variable $G$. How many four-bead rotation classes have composition $R^2BG$? Hint: only the identity can fix a coloring with exactly one blue and one green bead. Solution: the identity term contributes $4!/(2!1!1!)=12$ labeled colorings, so the coefficient after averaging is $12/4=3$.

14.4 Orbit–stabilizer theorem

For a finite group acting on a set, the orbit–stabilizer theorem states:

$$ |G\cdot x|=\frac{|G|}{|G_x|}. $$

The set $G_x$ is a subgroup: the identity fixes $x$; if $h,k$ fix $x$, then $hk$ fixes $x$; and $h^{-1}$ fixes $x$ whenever $h$ does. A left coset is a set $gG_x=\{gh:h\in G_x\}$. Each coset has $|G_x|$ elements because multiplication by $g$ is bijective.

Proof. Two elements $g,k\in G$ send $x$ to the same configuration exactly when

$$ g\cdot x=k\cdot x \quad\Longleftrightarrow\quad k^{-1}g\in G_x \quad\Longleftrightarrow\quad g\in kG_x. $$

Therefore the left cosets are precisely the fibers of $g\mapsto g\cdot x$. They partition $G$ and correspond bijectively to orbit elements. Counting elements proves the formula. No assumption that every group element produces a different configuration is needed.

Worked examples under $C_4$. The stabilizer of 0000 is all four rotations, giving orbit size $4/4=1$. The stabilizer of 0101 is $\{e,\rho^2\}$, giving size $4/2=2$. Only the identity fixes 0011, giving size $4/1=4$.

An action is free when every stabilizer is $\{e\}$. For a finite free action, all orbits have size $|G|$ and ordinary division is justified. The unrestricted necklace action is not free.

Under $D_4$, 0101 has the same two-element orbit, but now its stabilizer has four elements: $e,\rho^2,\tau,\rho^2\tau$. These preserve its white positions $\{0,2\}$ and black positions $\{1,3\}$. Enlarging a group can enlarge a stabilizer without enlarging that particular orbit.

For arbitrary position relabeling by $S_n$, a word with $r$ black and $n-r$ white entries has stabilizer size $r!(n-r)!$: permutations may rearrange black positions internally and white positions internally. The theorem gives

$$ |S_n\cdot x|=\frac{n!}{r!(n-r)!}=\binom nr, $$

recovering the number of labeled placements with that composition.

Exercise. Under $C_6$, what are the stabilizer and orbit size of 010101? Hint: an even shift preserves the word. Answer: $G_x=\{e,\rho^2,\rho^4\}$ and the orbit has size $6/3=2$. For 000111, no nonidentity rotation fixes the word, so its orbit has size $6$.

14.5 Cycle index polynomials

Optional extension. This section organizes fixed-point calculations into a reusable polynomial. It is not required to complete the chapter foundation; Section 14.6 can be read directly using Burnside's lemma.

For a finite group $G$ acting on a position set $P$ of size $n$, let $c_j(g)$ count the length-$j$ cycles of the induced position permutation. Introduce independent formal variables $a_1,\ldots,a_n$. The cycle index of this action is

$$ Z_{G,P}(a_1,\ldots,a_n) =\frac1{|G|}\sum_{g\in G}\prod_{j=1}^n a_j^{c_j(g)}. $$

Since cycles partition the positions, $\sum_j j\,c_j(g)=n$. Every monomial therefore has weighted degree $n$ when $a_j$ has weight $j$. Also $Z_{G,P}(1,\ldots,1)=1$, because its coefficients record proportions of group elements.

The action matters as much as the abstract group: rotating the vertices of a square and rotating those vertices together with a fixed center give different cycle indices. Every element acquires an extra singleton cycle in the second action, so its index is multiplied by $a_1$.

Worked example. Our $C_4$ cycle table gives

$$ Z_{C_4,P}=\frac14(a_1^4+a_2^2+2a_4). $$

Setting every $a_j=q$ gives the unrestricted $q$-color orbit count, $(q^4+q^2+2q)/4$. Substituting $a_j=R^j+B^j$ gives Section 14.3's inventory. By contrast, substituting $a_j=(R+B)^j$ would allow different colors inside one cycle and would not count fixed colorings correctly.

For rotations of $n$ positions,

$$ Z_{C_n,P}=\frac1n\sum_{d\mid n}\varphi(d)a_d^{n/d}, $$

where $\varphi(d)$ is Euler's totient: the number of integers $1\le u\le d$ relatively prime to $d$, including $\varphi(1)=1$. To prove the formula, a shift by $k$ has $\gcd(n,k)$ cycles, each of length $n/\gcd(n,k)$. A specified cycle length $d\mid n$ occurs for $k=(n/d)u$ with $u$ relatively prime to $d$, giving $\varphi(d)$ shifts. Interpret $k=0$ as the identity, with $d=1$.

For comparison, the action of $S_n$ on $n$ positions has

$$ Z_{S_n,P}=\sum_{\substack{c_1,\ldots,c_n\ge0\\\sum_j j c_j=n}} \frac{\prod_{j=1}^n a_j^{c_j}}{\prod_{j=1}^n j^{c_j}c_j!}. $$

Indeed, arranging labels into cycles gives $n!$ possibilities before dividing by $j$ for the cyclic starting point of each length-$j$ cycle and by $c_j!$ for the order of those cycles. Dividing again by $|S_n|=n!$ gives the displayed coefficient. For $n=3$, this is $(a_1^3+3a_1a_2+2a_3)/6$. Two-color substitution counts $4$ orbits, determined by the number of black entries.

Exercise. Compute the rotation cycle index for a hexagon. Hint: list the divisors $1,2,3,6$ and their totients $1,1,2,2$. Answer:

$$ Z_{C_6,P}=\frac16(a_1^6+a_2^3+2a_3^2+2a_6). $$

Check that its coefficients sum to $1$ and every monomial has weighted degree $6$.

14.6 Necklace and bracelet enumeration

A $q$-color necklace is an orbit of length-$n$ words under $C_n$. A $q$-color bracelet is an orbit under $D_n$, allowing rotations and reflections. Colors remain distinguishable, repetitions are allowed, and every position is colored. Assume $q\ge1$; necklace formulas hold for $n\ge1$, while our geometric bracelet discussion assumes $n\ge3$.

Let $N_n(q)$ denote the necklace count. A shift by $k$ has $\gcd(n,k)$ cycles: starting at one position and repeatedly adding $k$ returns after $n/\gcd(n,k)$ steps. Burnside gives

$$ N_n(q)=\frac1n\sum_{k=0}^{n-1}q^{\gcd(n,k)} =\frac1n\sum_{d\mid n}\varphi(d)q^{n/d}, $$

using $\gcd(n,0)=n$. The second equality groups shifts by their cycle lengths, as explained in Section 14.5.

Worked example. For six binary beads,

$$ N_6(2)=\frac{2^6+2^3+2\cdot2^2+2\cdot2}{6}=14. $$

To count bracelets, retain this rotation contribution and add reflections. With positions indexed modulo $n$, every reflection has the form $s_j(i)=j-i$. It is an involution, so its cycles have length $1$ or $2$. A fixed position satisfies $2i=j\pmod n$.

For odd $n$, each reflection fixes one position and exchanges $(n-1)/2$ pairs, giving $(n+1)/2$ cycles. For even $n$, the $n/2$ even values of $j$ give two fixed positions and $(n-2)/2$ pairs; the $n/2$ odd values give no fixed positions and $n/2$ pairs. Geometrically these are axes through opposite vertices and axes through opposite edges.

Consequently the bracelet count is

$$ B_n(q)=\begin{cases} \displaystyle\frac{nN_n(q)+nq^{(n+1)/2}}{2n},&n\text{ odd},\\[6pt] \displaystyle\frac{nN_n(q)+\frac n2 q^{n/2+1}+\frac n2 q^{n/2}}{2n},&n\text{ even}. \end{cases} $$

For $n=6,q=2$, the rotation contribution is $84$. Three reflections have four cycles and three have three cycles, so

$$ B_6(2)=\frac{84+3\cdot16+3\cdot8}{12}=13. $$

This is not $14/2$: many necklaces are equivalent to their own mirror images. The rotational representatives 001011 and 001101 are a distinct mirror pair that becomes one bracelet; their six rotations can be listed to verify that they are not rotationally equivalent. Among the $14$ binary six-bead necklaces, the other $12$ are each equivalent to their own mirror image.

For a specified number $r$ of black beads, use a variable $t$ for black and weight $1$ for white. A cycle of length $j$ contributes $1+t^j$. Grouping rotation cycles gives the refinement

$$ N_{n,r}=\frac1n\sum_{d\mid\gcd(n,r)}\varphi(d)\binom{n/d}{r/d},\qquad 0\le r\le n. $$

A length-$d$ cycle contributes either $0$ or $d$ black beads, so only $d\mid r$ contributes. The binomial coefficient chooses the $r/d$ black cycles from $n/d$ cycles. For $r=0$, use $\gcd(n,0)=n$.

Exercise. Count five-bead binary necklaces and bracelets, then restrict to exactly two black beads. Hint: a nonidentity rotation of five positions has one cycle. Solution: $N_5(2)=(32+4\cdot2)/5=8$, and $B_5(2)=(40+5\cdot8)/10=8$. With exactly two black beads, necklaces number $\binom52/5=2$, represented by adjacent black beads and black beads separated by one white bead. Each reflection fixes two such placements, giving $(10+5\cdot2)/10=2$ bracelets as well.

14.7 Primitive necklaces and Lyndon words

Optional extension. Here we distinguish genuinely length-$n$ patterns from repetitions of shorter patterns. This section is not required for the chapter foundation.

A nonempty word is primitive if it cannot be written $u^m$ with $m\ge2$ and $u$ shorter. For cyclic words, this is equivalent to having no nonidentity rotation fix the word. To see the nontrivial direction, if a shift by $k$ fixes a length-$n$ word, entries agree along its cycles. With $d=\gcd(n,k)$, positions with the same residue modulo $d$ agree, so the word repeats its first $d$ entries $n/d$ times.

Thus 010101 is not primitive: it is (01) repeated three times. The word 000111 is primitive. An ordinary linear string period need not divide the length, so “period” here always refers to cyclic repetition by a block whose length divides $n$.

Let $A_n(q)$ count primitive labeled words. Every length-$n$ word has a unique shortest repeated block, of some length $d\mid n$, and that block is primitive. Uniqueness follows by taking the smallest positive shift that fixes the word, allowing the full shift $n$. If this smallest shift is $d$, division with remainder shows that every fixing shift is a multiple of $d$: otherwise its remainder would be a smaller positive fixing shift. Since $n$ fixes every word, $d\mid n$, and the first $d$ entries form the unique shortest repeated block. Therefore

$$ q^n=\sum_{d\mid n}A_d(q). $$

Define the Möbius function by $\mu(1)=1$, by $\mu(d)=0$ when a prime square divides $d$, and by $\mu(d)=(-1)^s$ when $d$ is a product of $s$ distinct primes. Its divisor sums satisfy $\sum_{d\mid m}\mu(d)=0$ for $m\gt1$, and equal $1$ for $m=1$: only square-free divisors contribute, and their signs sum to $(1-1)^s$.

Substituting the preceding divisor identity gives

$$ \begin{aligned} \sum_{d\mid n}\mu(d)q^{n/d} &=\sum_{d\mid n}\mu(d)\sum_{e\mid n/d}A_e(q)\\ &=\sum_{e\mid n}A_e(q)\sum_{d\mid n/e}\mu(d) =A_n(q). \end{aligned} $$

Every primitive rotation orbit has exactly $n$ elements by orbit–stabilizer. Hence the primitive necklace count is

$$ L_n(q)=\frac{A_n(q)}n=\frac1n\sum_{d\mid n}\mu(d)q^{n/d}. $$

These formulas and their relation to primitive representatives are also developed in Sutner's Möbius Inversion notes. cs.cmu.edu

Order the alphabet, for example $0\lt1$, and compare equal-length words lexicographically: inspect the first position where they differ. A Lyndon word is a nonempty primitive word strictly smaller than each of its nontrivial rotations. Each primitive necklace has one such word, its unique smallest rotation; a repeated word cannot satisfy the strict inequality because some nontrivial rotation equals it.

Worked example. The binary Lyndon words of length $4$ are 0001, 0011, and 0111. The other three canonical necklace representatives, 0000, 0101, and 1111, are not primitive. The formula confirms

$$ L_4(2)=\frac{2^4-2^2}{4}=3. $$

For length $6$, the four divisors give $A_6(2)=64-8-4+2=54$, and therefore $L_6(2)=9$. The added $2$ restores constant words subtracted in both repetition cases.

Exercise. How many binary primitive necklaces have length $5$? Hint: the only proper repeated-block length dividing $5$ is $1$. Solution: $A_5(2)=32-2=30$ labeled words and $L_5(2)=30/5=6$ necklaces. Both constant words are excluded.

14.8 Symmetry-aware enumeration and canonical representatives

Optional extension. This section turns the orbit viewpoint into an explicit enumeration method. It is not required for the chapter foundation.

A canonical representative chooses one deterministic element from each orbit. For words over an ordered alphabet, define

$$ \operatorname{can}_{C_n}(w)=\min_{0\le k\lt n}\operatorname{rot}_k(w), $$

where $\operatorname{rot}_k$ is a cyclic shift by $k$. For bracelets, define

$$ \operatorname{can}_{D_n}(w) =\min\left(\{\operatorname{rot}_k(w):0\le k\lt n\} \cup\{\operatorname{rot}_k(w^{\mathrm{rev}}):0\le k\lt n\}\right), $$

where $w^{\mathrm{rev}}$ reverses the displayed word. Reversal followed by shifts gives exactly the reflections needed for a bracelet orbit. Left shifts or right shifts may be used consistently here; listing all shifts gives the same set.

Why this works. If $v=g\cdot w$, then $G\cdot v=G\cdot w$, because multiplication by $g$ permutes the group elements used to generate the orbit. Thus equivalent words have the same minimum. Conversely, equal minima belong to both orbits; orbits that intersect are equal. Therefore canonical equality is equivalent to orbit equality, not merely a necessary test.

A simple finite enumeration procedure is:

1. Generate all $q^n$ labeled words, or all words satisfying an invariant composition restriction.
2. For each word, generate its $n$ rotations, adding the $n$ shifted reversals when reflections are allowed.
3. Keep the minimum of these views and insert it into a set.
4. Sort the resulting set to list one representative per orbit.

This exhaustive method proves completeness for the given finite instance when all inputs and all allowed views are included. Its naive implementation uses $O(n^2)$ work per word to construct and compare the length-$n$ views, so $O(q^n n^2)$ total work. It is a useful validator for small instances; these bounds make no claim of an efficient large-instance generator.

Worked example. Rotating 110010 gives the same canonical necklace representative as rotating 001011, namely 001011. Reversing 001011 yields 110100, whose minimum rotation is 001101. Thus the two distinct necklace representatives 001011 and 001101 share the bracelet representative 001011. An inventory count by black-bead number alone cannot detect this mirror pairing.

If colors themselves are interchangeable, state a further action explicitly. A global color permutation $\sigma\in S_q$ can act together with a position symmetry $g$ by

$$ ((g,\sigma)\cdot f)(i)=\sigma\bigl(f(g^{-1}(i))\bigr). $$

The two transformations commute, so this is an action of $G\times S_q$. Canonicalization must now minimize over these additional global color permutations. For example, under rotations plus the global binary color swap, the six four-bead necklace representatives reduce to four classes: 0000 merges with 1111, 0001 with 0111, while 0011 and 0101 each remain their own color-swap class. This global swap is not permission to recolor individual beads independently. The ordinary $q^{c(g)}$ fixed-coloring formula does not cover transformations that also permute colors.

For uncolored graphs, vertex relabeling similarly changes adjacency data while preserving the abstract graph. A canonical graph label would minimize a chosen encoding over vertex permutations; the same orbit proof justifies its correctness, although enumerating all $n!$ relabelings is expensive. This connects symmetry counting with removing duplicate search states and storing equivalent objects under one key.

Exercise. Is a smallest necklace representative necessarily a Lyndon word? Hint: test 0101. Answer: no; 0101 is a smallest rotation but is periodic. The canonical representatives that are primitive are exactly the Lyndon words.

Compute a cycle index and count symmetry classes

Use a regular hexagon to bring together position permutations, fixed configurations, composition inventories, and canonical representatives. This is a finite investigation with a complete answer, not an unresolved research question.

An application is testing circular six-slot devices whose slots have two distinguishable states. If the device has no marked start, rotated configurations duplicate the same physical arrangement; if reversing orientation is also irrelevant, mirror views duplicate it as well. Counting chooses the number of test classes, while canonicalization supplies one concrete input for each class. A marked port or a direction-sensitive component changes the allowed symmetry group and therefore changes the test set.