Count configurations up to symmetry using fixed points, distinguish rotation from reflection, and use a cycle index to track labelled-color composition.
Burnside lemma and Pólya enumeration
Burnside’s lemma counts objects up to a specified symmetry by averaging the number left unchanged by each symmetry. Pólya enumeration packages the same cycle structure into a polynomial, allowing counts by color composition. In a discrete model search, they can count genuinely distinct configurations when the model treats the permitted rearrangements as equivalent.
Which changes count as the same outcome?
Put one of three labelled colors, A, B or C, at each of four square vertices. Colors can repeat, and there are no adjacency restrictions. Number the vertices clockwise for bookkeeping. Before identifying any symmetries, the count is 34=81.
Now declare two colorings equivalent if a rotation of the square transforms one into the other. The permitted operations form C4: the identity and turns of 90∘, 180∘ and 270∘. An orbit is the set of colorings reachable from one coloring using these operations; we want one count per orbit.
The colors remain labelled: an all-A square and an all-B square are different. Rotating positions does not rename colors. If reflections also count as equivalences, the group changes to the eight symmetries of the square, denoted D4 here. Some texts call this group D8, indexing its order rather than the number of vertices.
These choices are part of the problem. A cyclic relabelling of four identical slots may be harmless in a model. Moving an observation to another date or assigning an exposure to another asset generally changes its meaning. A convenient geometric picture does not establish an economic symmetry.
Count what each operation fixes
Let a finite group G act on a finite set X. Write Fix(g)={x∈X:g⋅x=x}. Burnside’s lemma states
∣X/G∣=∣G∣1g∈G∑∣Fix(g)∣,
where X/G is the set of orbits. “Fixed” means the entire coloring is unchanged, even when some vertices move.
Each operation is a permutation of the vertices. Follow a vertex until it returns to its starting point: that gives a cycle. A fixed coloring must assign the same color to every vertex in a cycle. With q available labelled colors, each cycle has q choices, so an operation with c(g) cycles fixes qc(g) unrestricted colorings.
For our square:
Rotation
Cycles on the vertices
Fixed colorings
Identity
Four single vertices
34=81
90∘
One cycle of length four
3
180∘
Two cycles of length two
32=9
270∘
One cycle of length four
3
Hence
∣X/C4∣=481+3+9+3=24.
The four rotations fix 81, 3, 9 and 3 colorings, giving 24 rotation classes. Each of two vertex-axis reflections fixes 27 colorings; each of two edge-axis reflections fixes 9. Including all eight symmetries gives 21 classes.
Original square-vertex example. Letters on the vertices mark cycles forced to share a color; different cycle letters may choose the same color. Dashed lines show representative reflection axes.
Allow reflections and add two operations whose axes pass through opposite vertices. Each leaves two vertices fixed and swaps the other pair: three cycles, hence 33=27 fixed colorings. The two axes through opposite edge midpoints each swap two pairs: 32=9 fixed colorings. Therefore
∣X/D4∣=881+3+9+3+2(27)+2(9)=21.
Why dividing by four fails
An all-A square has only one distinct rotation. An alternating A–B–A–B coloring has two. A coloring with cyclic sequence A–A–B–C has four. There is no common orbit size by which to divide 81.
The lemma corrects for this through stabilizers. The stabilizer of x contains the operations that fix it, and its size times the orbit size equals ∣G∣. Counting pairs (g,x) with g⋅x=x, each orbit therefore contributes exactly ∣G∣ pairs. Dividing their total by ∣G∣ counts every orbit once, including the unusually symmetric ones. Uraltsev’s group-action notes develop the orbit–stabilizer argument.
For the underlying ordered-versus-unordered counting distinction, Counting and Combinatorics develops permutations, combinations and partitions. Its full lesson requires membership; the linked public preview gives the purpose and outline.
Pólya keeps track of composition
If cj(g) counts the length-j cycles of g, its cycle index is
ZG(a1,…,an)=∣G∣1g∈G∑j=1∏najcj(g).
For the four rotations,
ZC4=4a14+a22+2a4.
Substitute aj=q for every j to recover the total count (q4+q2+2q)/4. At q=3 this gives 24. Substitute q, notqj: a whole fixed cycle makes one color choice.
to produce a combinatorial generating function. The coefficient of urvswt counts rotation classes with r A vertices, s B vertices and t C vertices. For exactly two A vertices, one B and one C, the coefficient is
[u2vw]4(u+v+w)4+(u2+v2+w2)2+2(u4+v4+w4)=412=3.
Here [u2vw] means “take the coefficient of u2vw.” Only the identity term contributes: this composition cannot remain unchanged under a nontrivial rotation. The shortcut qc(g) assumes each cycle can choose any color independently. With constraints preserved by the group—such as forbidding equal colors at adjacent vertices—Burnside still applies, but the fixed-point counts must be recomputed.
A count is not a sampling rule
Uniformly drawing from the 81 vertex colorings does not draw uniformly from the 24 rotation classes. A particular monochrome orbit receives probability 1/81, while the four-member A–A–B–C orbit receives 4/81. Choosing a canonical representative removes duplicate representations but preserves this unequal probability mass. To sample classes uniformly, the sampling scheme must account for orbit sizes; knowing the sample space count alone is insufficient.
Keller and Trotter, Applied Combinatorics, §15.4: Pólya’s Theorem, §§15.4.1–15.4.2 and Theorem 15.11: cycle indices and color-inventory substitution. The square counts and coefficient above are independently enumerated for the conventions stated here.
