One idea, slowly: count orbits by counting fixed points. Then the same proof with a weight attached, which is the whole theorem.
Schedule. Finn's board presentation moves to Wednesday, followed by transfer matrices. Problem set 5 is now due Monday, November 16, 10 p.m. (moved from Friday): Problem 3 is today's material and Problem 4 is Wednesday's and Friday's.
The demos (slides 6 and 12) are on the course page too, and everything computed today is checkable by brute force in the Lab 2 kernel.
Each box is one orbit of the rotation group $C_4$. Rotating a coloring never changes how many beads are black.
Four beads on a ring, each black or white: $2^4 = 16$ colorings. Rotate the ring and a coloring turns into another one. A necklace is what you cannot tell apart by rotating: an orbit.
There are six. We can see that here. The theorem is for when we can't: $8$ beads and $3$ colors is $6561$ colorings.
The setup. A finite group $G$ acts on a finite set $X$. The orbit of $x$ is $\mathrm{Orb}(x) = \{gx : g\in G\}$; the stabilizer is $\mathrm{Stab}(x) = \{g : gx = x\}$; the fixed set of $g$ is $\mathrm{Fix}(g) = \{x : gx = x\}$. The orbits form a set $X/G$, and we want $\#X/G$.
$|G| = |\mathrm{Orb}(x)|\cdot|\mathrm{Stab}(x)|$: the orbit is as big as the group divided by the stabilizer.
So $\dfrac{1}{|\mathrm{Orb}(x)|} = \dfrac{|\mathrm{Stab}(x)|}{|G|}$. Sum that over an orbit and you get exactly $1$. That one line is the proof of Burnside's lemma.
$\#X/G \;=\; \dfrac{1}{|G|}\displaystyle\sum_{g\in G}|\mathrm{Fix}(g)|$. The number of orbits is the average number of fixed points.
Proof. Count the pairs $(g,x)$ with $gx = x$, two ways.
By $g$ first: $\displaystyle\sum_{g}|\mathrm{Fix}(g)|$.
By $x$ first: $\displaystyle\sum_{x}|\mathrm{Stab}(x)| = \sum_x \frac{|G|}{|\mathrm{Orb}(x)|}$
$\displaystyle\qquad = |G|\sum_{O\in X/G}\;\sum_{x\in O}\frac{1}{|O|} = |G|\cdot\#X/G.$
Equate. $\blacksquare$
| rotation $g$ | what it does | $|\mathrm{Fix}(g)|$ |
|---|---|---|
| identity | fixes everything | 16 |
| quarter turn | all beads one color | 2 |
| half turn | opposite beads agree | 4 |
| three-quarter turn | all beads one color | 2 |
| sum $= 24$, divided by $|G| = 4$ | 6 | |
The four rotations of four beads, two colors.
Rotation by two steps on six beads: two 3-cycles, $\{1,3,5\}$ and $\{2,4,6\}$. A fixed coloring is constant on each.
A coloring $c$ is fixed by $g$ exactly when $c(gi) = c(i)$ for every bead $i$: the color is constant along each cycle of $g$.
So a fixed coloring is a free choice of one color per cycle:
$|\mathrm{Fix}(g)| = r^{\,z(g)}$, $z(g) = $ number of cycles of $g$ on the beads.
Which means Burnside only needs the cycle structure of each $g$. Record it in a monomial: $g \mapsto p_1^{z_1(g)}p_2^{z_2(g)}\cdots$, with $z_i(g)$ the number of $i$-cycles.
$Z_G(p_1,p_2,\dots) = \dfrac{1}{|G|}\displaystyle\sum_{g\in G} p_1^{z_1(g)}p_2^{z_2(g)}\cdots$ (a polynomial; $p_i$ stands for "an $i$-cycle").
$C_4$ on four beads. Identity $1^4$; quarter turns $4$ (two of them); half turn $2^2$.
$Z_{C_4} = \tfrac14\bigl(p_1^4 + p_2^2 + 2p_4\bigr)$
$C_6$ on six beads. Rotations by $0,1,2,3,4,5$ have types $1^6,\,6,\,3^2,\,2^3,\,3^2,\,6$.
$Z_{C_6} = \tfrac16\bigl(p_1^6 + p_2^3 + 2p_3^2 + 2p_6\bigr)$
$D_4$: add the four reflections. Through two opposite beads: $1^2\,2$ (two of them). Through two edge midpoints: $2^2$ (two of them).
$Z_{D_4} = \tfrac18\bigl(p_1^4 + 2p_1^2p_2 + 3p_2^2 + 2p_4\bigr)$
Burnside, restated. With $r$ colors, $|\mathrm{Fix}(g)| = r^{z(g)}$ is the monomial at $p_i = r$. So $\#X/G = Z_G(r,r,r,\dots)$. Four beads, two colors: $\tfrac14(16+4+4) = 6$. Six beads, two colors: $\tfrac16(64+8+8+4) = 14$.
Give color $j$ a variable $x_j$. For a coloring $c$ of the beads $1,\dots,n$ write
$x^{c} \;=\; \displaystyle\prod_{i=1}^{n} x_{c(i)} \;=\; x_1^{m_1}x_2^{m_2}\cdots x_r^{m_r},\quad m_j = \#c^{-1}(j).$
$m_j$ is the number of beads colored $j$; the vector $(m_1,\dots,m_r)$ is the content of $c$.
$x^c$ only depends on the orbit. Rotating the beads reorders the factors of the product: $x^{gc} = \prod_i x_{c(g^{-1}i)} = \prod_i x_{c(i)} = x^c$. So we may write $x^{O}$ for an orbit $O$.
The refined question: $\displaystyle\sum_{O\in X/G} x^{O}$, the generating function of necklaces by how many beads of each color.
Four beads: $x^4 + x^3y + 2x^2y^2 + xy^3 + y^4$. Setting $x=y=1$ gives back $6$.
$\displaystyle\sum_{O\in X/G}x^{O} \;=\; Z_G\bigl(\,p_i \mapsto x_1^i + x_2^i + \cdots + x_r^i\,\bigr).$ In particular $\#X/G = Z_G(r,\dots,r)$.
Four beads, two colors $x, y$. $Z_{C_4} = \tfrac14(p_1^4+p_2^2+2p_4)$, so
$\tfrac14\bigl((x+y)^4 + (x^2+y^2)^2 + 2(x^4+y^4)\bigr)$
$= \tfrac14\bigl(4x^4 + 4x^3y + 8x^2y^2 + 4xy^3 + 4y^4\bigr)$
$= x^4 + x^3y + \mathbf{2}x^2y^2 + xy^3 + y^4.$
The $2$ is the half turn's doing: $(x^2+y^2)^2$ contributes $2x^2y^2$ because a half-turn-fixed coloring can color its two $2$-cycles differently.
Reading the substitution. $p_i$ was "an $i$-cycle." Pólya says: replace each $i$-cycle by the generating function of its colorings, $x_1^i+\cdots+x_r^i$, one term per color, because all $i$ beads on the cycle share that color.
One variable is usually enough. Set $x_1 = q$ and the other colors to $1$: $Z_G\bigl(p_i \mapsto q^i + (r-1)\bigr)$ counts orbits by the number of beads of color $1$. Two colors: $p_i \mapsto 1 + q^i$.
orbits by number of black beads, with one representative of each
The rotation group has $24$ elements in five classes. On the six faces:
$Z = \tfrac1{24}\bigl(p_1^6 + 6p_1^2p_4 + 3p_1^2p_2^2 + 8p_3^2 + 6p_2^3\bigr)$ (check: $1+6+3+8+6 = 24$)
Two colors: $\tfrac1{24}(64 + 6\cdot 8 + 3\cdot 16 + 8\cdot 4 + 6\cdot 8) = \tfrac{240}{24} = \mathbf{10}$. Three colors: $\tfrac1{24}(729+162+243+72+162) = \tfrac{1368}{24} = \mathbf{57}$. (Careful: $p_3^2$ at two colors is $2^2$, not $2^3$.)
$B_4/C_4$, the necklace poset from the course page: rank sizes $1,1,2,1,1$.
A subset of $[n]$ is a $2$-coloring of $[n]$: in or out. So $B_n/G$ is the set of $2$-colorings up to $G$, graded by how many elements are in.
$\displaystyle\sum_{O\in B_n/G}q^{\operatorname{rank}O} = Z_G\bigl(1+q,\,1+q^2,\,1+q^3,\dots\bigr)$
$B_4/C_4$: $\tfrac14\bigl((1+q)^4+(1+q^2)^2+2(1+q^4)\bigr)$
$\quad= \tfrac14(4+4q+8q^2+4q^3+4q^4) = 1+q+2q^2+q^3+q^4.$
Drawn in September, computed today.
And $L(2,2) = B_4/(\mathfrak{S}_2\wr \mathfrak{S}_2)$ from October 26 has the same polynomial, $\genfrac{[}{]}{0pt}{}{4}{2}_q$: the $q$-binomial coefficient is a Pólya count too.
A multiset of $n$ objects from $\mathcal A$ is a sequence up to $\mathfrak{S}_n$: a coloring of $n$ positions by objects, with color $\alpha$ weighted $z^{|\alpha|}$. Pólya for $\mathfrak{S}_n$, with $p_i \mapsto \sum_\alpha z^{i|\alpha|} = A(z^i)$:
$\mathrm{MSET}(\mathcal A) \;\mapsto\; \displaystyle\sum_{n\ge0}Z_{\mathfrak{S}_n}\bigl(A(z),A(z^2),\dots\bigr) \;=\; \exp\Bigl(\sum_{k\ge1}\frac{A(z^k)}{k}\Bigr),$
Why an exponential? It is Wednesday's $\mathrm{SET}(\mathrm{CYC}(\mathcal Z))$ with each $k$-cycle marked by $p_k$. Since $Z_{\mathfrak{S}_n} = \frac1{n!}\sum_{\sigma\in\mathfrak{S}_n}\prod_k p_k^{z_k(\sigma)}$, the series $\sum_n Z_{\mathfrak{S}_n}t^n$ is the EGF of permutations with marked cycles, and a marked $k$-cycle contributes $(k-1)!\,p_k\,\frac{t^k}{k!} = \frac{p_k t^k}{k}$:
$\displaystyle\sum_{n\ge0}Z_{\mathfrak{S}_n}\,t^n \;=\; \exp\Bigl(\sum_{k\ge1}\frac{p_k\,t^k}{k}\Bigr).$
Check: every $p_k = 1$ gives $\exp\log\frac1{1-t} = \frac1{1-t}$. Then substitute $p_k = A(z^k)$ and set $t = 1$.
So the $A(z^k)/k$ of October 14 is what a $k$-cycle sees: a $k$-cycle fixes a sequence only if one object sits in all $k$ positions of the cycle, weight $z^{k|\alpha|}$, summed over $\alpha$. The $1/k$ is the cycle's share of $1/n!$.
Nothing on the problem set depends on this slide.
Pairs. Write the cycle index first, every time. Check each total against something: a listing, the demo, Lab 2's kernel.
Problems 1–3 now, 4–5 if you finish. Answers follow.
Check 5 by hand. Two red beads at distance $1$, $2$ or $3$; the other four beads then form a word in two colors read along the ring with the symmetry that remains: $16 + 16 + 10 = 42$.
Orbits are counted by averaging fixed points, and a fixed coloring is a free choice of one color per cycle. Everything else is bookkeeping, and the cycle index is the book.
Dictionary. Unlabelled sequence, multiset, powerset, cycle: all Pólya's theorem, with $\mathfrak{S}_n$ and $C_n$ as the groups. Labelled sequence, set, cycle: $\tfrac1{1-A}$, $\exp$, $\log$.
Wednesday. Finn's board presentation, then Act III: words, automata, and transfer matrices, where the growth rate of a counting sequence is an eigenvalue. Reading: FS I.4 and the first pages of V.5.
Problem set 5 is due Monday, November 16, 10 p.m., moved from Friday. Problem 3 is today; Problem 4 is Wednesday and Friday.
Lab 2 is open; Parts 0–2 need nothing beyond last week. Individual project meetings are the week of the 16th.