Back to the on-screen lesson ·
How many configurations there are once symmetric ones are identified: average the number of things each group element leaves alone, and see why dividing the total by the order of the group is wrong.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state Burnside's lemma, count the configurations a given symmetry leaves unchanged by counting its cycles, carry out a full necklace, bracelet or cube-colouring count, say why dividing the number of configurations by the order of the group is wrong, and prove the lemma by counting one set of pairs in two directions.
Orbit-stabiliser measures a single orbit against the order of the group. A question such as how many different necklaces are there asks instead for the number of orbits, and the orbits have different sizes, so no single division answers it. Burnside's lemma is the correction, and the proof of it is orbit-stabiliser used once for every point.
For $g \in G$, the fixed set $\operatorname{Fix}(g) = \{x \in X : g \cdot x = x\}$ holds the points that element leaves alone — the opposite bookkeeping to a stabiliser, which fixes the point and varies the element. A configuration is a point of $X$ before any identification; two configurations are the same up to symmetry when they share an orbit, so the orbit count is the answer such a question wants.
Burnside's lemma. For a finite group $G$ acting on a finite set $X$,
$$\#\{\text{orbits}\} = \frac{1}{|G|}\sum_{g \in G} |\operatorname{Fix}(g)|.$$
The number of orbits is the average number of points left alone by an element of the group.
Why not just divide. The tempting formula $|X| / |G|$ is right only when every orbit has $|G|$ points, which happens only when no element but the identity fixes anything. Usually some configurations are more symmetric than others — the all-black necklace is fixed by every rotation — and they sit in short orbits that the division miscounts. Burnside is exactly the correction for that.
The proof in one line. Count the pairs $(g, x)$ with $g \cdot x = x$ by $g$ and by $x$:
$$\sum_{g} |\operatorname{Fix}(g)| = |P| = \sum_{x} |G_x| = \sum_{x} \frac{|G|}{|Gx|} = |G| \cdot \#\{\text{orbits}\},$$
because the $|Gx|$ points of one orbit each contribute $|G| / |Gx|$.
Why it is cheap. The sum runs over the group, which is usually far smaller than the set. Counting $10$ cube colourings by hand means sorting $64$ colourings into classes; Burnside instead asks $24$ easy questions of the form how many colourings survive this rotation, and most of them have a one-line answer.
The standard computation. For a rotation acting on beads, a colouring survives exactly when every cycle of the permutation is one colour. A rotation by $k$ places on $n$ beads has $\gcd(k, n)$ cycles, so it fixes $c^{\gcd(k, n)}$ colourings in $c$ colours — which turns the whole sum into a short piece of number theory.
Another way: picture
Draw a grid with one row per group element and one column per configuration, and tick the cell when that element leaves that configuration alone. The identity's row is entirely ticked. Reading the grid along the rows gives the fixed counts; reading it down the columns gives the stabilisers. The lemma is the observation that both readings count the same ticks, and that each orbit contributes exactly $|G|$ of them however wide or narrow it is.
Another way: steps
To count configurations up to symmetry: 1. Decide what counts as the same, and write down that group. 2. List the group elements, grouped by type — rotations by $k$ places, reflections through a bead, and so on. 3. For each, count the configurations it leaves unchanged; for a colouring that is $c$ to the power of the number of cycles. 4. Add, and divide by the order of the group. 5. Check the answer is a whole number, which it must be.
Almost every exercise in this family is a colouring problem, and almost all the work is counting cycles.
Rotations of $n$ beads. Rotation by $k$ places is a permutation with $\gcd(k, n)$ cycles, each of length $n / \gcd(k, n)$. So it fixes $c^{\gcd(k, n)}$ colourings in $c$ colours. Summing over $k = 0, \ldots, n-1$ and dividing by $n$ counts necklaces.
Reflections. A reflection of a regular $n$-gon has two shapes. When $n$ is odd, every reflection passes through one vertex and the midpoint of the opposite side: $1 + (n-1)/2$ cycles. When $n$ is even, half the reflections pass through two opposite vertices ($2 + (n-2)/2$ cycles) and half through two opposite edge midpoints ($n/2$ cycles). Getting these two cases right is most of what distinguishes a bracelet count from a necklace count.
Rotations of a cube. The $24$ rotations split into the identity, six quarter turns about face axes, three half turns about face axes, eight turns about long diagonals and six half turns about edge axes. For colouring the six faces with $c$ colours the cycle counts are $6, 3, 4, 2, 3$ respectively, giving
$$\frac{c^{6} + 6c^{3} + 3c^{4} + 8c^{2} + 6c^{3}}{24},$$
which is $10$ at $c = 2$ and $57$ at $c = 3$.
A check worth making every time. The total before dividing must be divisible by $|G|$. An arithmetic slip nearly always breaks that, so the lemma audits itself.
Dividing the total by the order of the group. The commonest error, and the reason the lemma exists. It is correct only when nothing is fixed by anything but the identity.
Confusing $\operatorname{Fix}(g)$ with $G_x$. One holds the group element still and varies the point; the other holds the point still and varies the element. They are counted in the same grid, along different directions.
Forgetting the identity. It contributes $|X|$, the largest term in the sum by far, and leaving it out gives an answer that is far too small.
Using the wrong group. Up to rotation and up to rotation and reflection are different questions with different answers. Deciding which is meant is part of the problem, not part of the arithmetic.
Counting cycles wrongly. A rotation by $k$ places on $n$ beads has $\gcd(k, n)$ cycles, not $k$ and not $n - k$. When $n$ is prime every non-identity rotation has exactly one.
The group is the five rotations. The identity fixes $3^{5} = 243$ colourings.
Start with the identity.
Five is prime, so each of the four other rotations has a single cycle and fixes $3^{1} = 3$ colourings: the constant ones.
Four rotations, three each.
The average is $(243 + 4 \times 3) / 5 = 255 / 5 = 51$ necklaces.
Add and divide.
Now the group has eight elements: four rotations and four reflections. The rotations contribute $16 + 2 + 4 + 2 = 24$, as for the necklace.
The rotations, as before.
Two reflections pass through opposite beads, each with three cycles: $2^{3} = 8$ apiece. Two pass through opposite gaps, each with two cycles: $2^{2} = 4$ apiece.
The two kinds of reflection.
The total is $24 + 16 + 8 = 48$, and $48 / 8 = 6$. The same as the necklace count here, because with four beads and two colours no two necklaces are mirror images without already being equal.
A count that happens to agree, for a reason worth checking.
The group is the three rotations. The identity fixes $3^{3} = 27$ colourings.
The identity.
Each of the two other rotations has a single cycle, so it fixes the $3$ constant colourings.
Two rotations, three each.
The average is $(27 + 3 + 3) / 3 = 33 / 3 = 11$. A whole number, as it has to be — and $27 / 3 = 9$ would have been the wrong answer, short by the two constant colourings that sit in orbits of size one.
Four beads sit in a ring, each black or white, and two necklaces count as the same when a rotation carries one to the other. The number of bead cycles of each rotation is given. Fill in how many colourings each rotation leaves unchanged, then the total and the number of different necklaces.
| Cycles of beads | Colourings it leaves unchanged | |
|---|---|---|
| The identity | 4 | |
| The quarter turn | 1 | |
| The half turn | 2 | |
| The three-quarter turn | 1 | |
| Total over the four rotations | — | |
| Different necklaces: the total divided by four | — |
How many are there: necklaces of $4$ beads in $3$ colours, counted up to rotation?
Answer:
Put the steps of a counting-up-to-symmetry argument into order.
Number the steps in order (write the number in the box):
Select every statement that is true of Burnside's lemma.
This task has no paper form; do it on a device.
Six beads sit in a ring, each black or white. Match each rotation to the number of colourings it leaves unchanged.
| $64$ colourings | $2$ colourings | $4$ colourings | $8$ colourings | $16$ colourings | |
|---|---|---|---|---|---|
| The identity | |||||
| Rotation by one place | |||||
| Rotation by two places | |||||
| Rotation by three places |
Build the proof of Burnside's lemma by counting one set of pairs in two directions.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Four beads sit in a ring, each black or white, and two necklaces count as the same when a rotation carries one to the other. The number of bead cycles of each rotation is given. Fill in how many colourings each rotation leaves unchanged, then the total and the number of different necklaces.
| Cycles of beads | Colourings it leaves unchanged | |
|---|---|---|
| The identity | 4 | |
| The quarter turn | 1 | |
| The half turn | 2 | |
| The three-quarter turn | 1 | |
| Total over the four rotations | — | |
| Different necklaces: the total divided by four | — |
You can count configurations up to symmetry by averaging fixed counts over the group. Say in your own words why the naive division is wrong and what Burnside corrects. Next: the group acting on itself by conjugation, where the fixed points become the centre.
9. Your turn: necklaces of three beads in three colours, step 3