Counting up to Symmetry: Burnside and Pólya

A colouring $f$ is fixed by $g$ exactly when it is constant on every cycle of the permutation of $X$ induced by $g$. Indeed, $g\cdot f=f$ means $f(x)=f(g^{-1}x)$ for every $x$, and iterating this equality around a cycle forces one common colour on that whole cycle. Conversely, a colouring constant on each cycle is unchanged by the action.

If $g$ has $j_d(g)$ cycles of length $d$, then each cycle may be assigned any one of the $m$ colours independently, so the number of fixed colourings is $m^{{\sum }_d{j}_d(g)}$.

In the weighted setting, a fixed colouring contributes on a $d$-cycle the factor $w(c{)}^d$ for the single colour $c$ chosen on that cycle. Summing over all colour choices on that cycle gives $p_d$. Independence across cycles from step 1.1 therefore yields the product ${\prod }_d{p}_d^{j_d(g)}$.

Apply [L1] to the induced action of $G$ on the colouring set $C^X$. The number of colouring orbits is therefore $\frac{1}{\mathrm{\mid }G\mathrm{\mid }}{\sum }_{g\in G}\mathrm{\mid }\{f:X\to C:g\cdot f=f\}\mathrm{\mid }$.

Replace each fixed-colouring count in step 1.1 by the formula from [L2]. This gives $\frac{1}{\mathrm{\mid }G\mathrm{\mid }}{\sum }_{g\in G}{m}^{{\sum }_d{j}_d(g)}$.

By the definition of the cycle index, substituting $s_d=m$ for every $d$ turns $\frac{1}{\mathrm{\mid }G\mathrm{\mid }}{\sum }_{g\in G}{\prod }_{d\ge 1}{s}_d^{j_d(g)}$ into the sum of step 2.1. Hence the orbit count is $Z_G(m,m,\dots ,m)$.

Because weights are preserved on orbits by [F1], the colouring set $C^X$ splits into finitely many $G$-stable blocks according to the value $u$ of $\mathrm{wt}(f)$. For one such value $u$, let ${\mathcal{C}}_u$ be the set of colourings of weight $u$. Applying [L2] to the induced action on the finite set ${\mathcal{C}}_u$ gives $\mathrm{\mid }G\mathrm{\mid }\mathrm{\mid }{\mathcal{C}}_u\mathrm{/}G\mathrm{\mid }={\sum }_{g\in G}\mathrm{\mid }{\mathcal{C}}_u^g\mathrm{\mid }$.

Multiply the identity of step 1.1 by $u$ and sum over all weight values $u$. The left-hand side becomes $\mathrm{\mid }G\mathrm{\mid }{\mathcal{I}}_G(X,C;w)$ by [F1], while the right-hand side becomes ${\sum }_{g\in G}{\sum }_{\begin{array}{c}f:X\to C\\ g\cdot f=f\end{array}}\mathrm{wt}(f)$.

Replace the inner weighted fixed-colouring sum in step 2.1 by [L1]. This gives $\mathrm{\mid }G\mathrm{\mid }{\mathcal{I}}_G(X,C;w)={\sum }_{g\in G}{\prod }_{d\ge 1}{p}_d^{j_d(g)}$. When $1\mathrm{/}\mathrm{\mid }G\mathrm{\mid }$ is defined in $R$, divide by $\mathrm{\mid }G\mathrm{\mid }$ to obtain ${\mathcal{I}}_G(X,C;w)=Z_G(p_1,p_2,\dots ,p_{\mathrm{\mid }X\mathrm{\mid }})$.

A rotation by $r$ steps decomposes the $n$ vertices into $\gcd (n,r)$ cycles, each of length $n\mathrm{/}\gcd (n,r)$. Therefore its cycle-index monomial is $s_{n\mathrm{/}\gcd (n,r)}^{\gcd (n,r)}$.

Fix a divisor $d$ of $n$. A rotation contributes the monomial $s_d^{n\mathrm{/}d}$ exactly when its cycles have length $d$, equivalently when its step size has the form $r=(n\mathrm{/}d)a$ with $a$ coprime to $d$. Indeed, the order of the rotation by $r$ is the least positive $m$ with $mr\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$, and for $r=(n\mathrm{/}d)a$ this least $m$ is exactly $d$ when $\gcd (a,d)=1$. Therefore the rotations of order $d$ are in bijection with the units $a\in (\mathbb{Z}\mathrm{/}d{)}^{\times }$, so there are $\phi (d)$ of them by [L1].

Average the monomials over all $n$ rotations. Grouping them by the divisor $d$ from step 2.1 yields $Z(C_n)=\frac{1}{n}{\sum }_{d\mid n}\phi (d)s_d^{n\mathrm{/}d}$.

The subgroup of rotations has $n$ elements. Since $D_{2n}$ has $2n$ elements, the total rotational contribution to $Z(D_{2n})$ is $(1\mathrm{/}2)Z(C_n)$ by [L1].

Suppose $n$ is odd. Every reflection fixes exactly one vertex and swaps the remaining $n-1$ vertices in $(n-1)\mathrm{/}2$ transpositions. Thus each reflection contributes the monomial $s_1{s}_2^{(n-1)\mathrm{/}2}$. There are $n$ reflections, so after division by $2n$ their total contribution is $(1\mathrm{/}2)s_1{s}_2^{(n-1)\mathrm{/}2}$.

Suppose $n$ is even. Then there are two reflection types. The $n\mathrm{/}2$ reflections through opposite vertices fix two vertices and swap the remaining $n-2$ vertices in $(n-2)\mathrm{/}2$ transpositions, so they contribute $s_1^2{s}_2^{(n-2)\mathrm{/}2}$. The $n\mathrm{/}2$ reflections through opposite edges fix no vertex and consist of $n\mathrm{/}2$ transpositions, so they contribute $s_2^{n\mathrm{/}2}$. Dividing the sum of these $n$ reflection monomials by $2n$ gives the contribution $\frac{1}{4}(s_1^2{s}_2^{(n-2)\mathrm{/}2}+s_2^{n\mathrm{/}2})$.

Combine step 1.1 with step 2.1 in the odd case and with step 2.2 in the even case. This yields the two displayed formulas.

Arrange the symbols $1,\dots ,n$ in a line. There are $n!$ such linearisations. Break the line into consecutive blocks: first the $m_1$ blocks of length $1$, then the $m_2$ blocks of length $2$, and so on, ending with the $m_n$ blocks of length $n$. Turn each block $(a_1,\dots ,a_d)$ into the cycle $(a_1{a}_2\dots a_d)$. This produces a permutation of the required cycle type.

Every permutation of that cycle type is produced many times by step 1.1. For each $d$-cycle, any of its $d$ cyclic rotations gives the same cycle, so each such cycle is counted $d$ times. Also, the $m_d$ cycles of the same length may be listed in any order, so they are counted a further factor of $m_d!$. Therefore each permutation is produced exactly ${\prod }_d{d}^{m_d}{m}_d!$ times.

Divide the total number $n!$ of linearisations from step 1.1 by the overcounting factor of step 2.1. This gives exactly $\frac{n!}{{\prod }_{d=1}^n{d}^{m_d}{m}_d!}$.

In the average from [F1], all permutations with the same cycle type contribute the same monomial ${\prod }_d{s}_d^{m_d}$. Thus the sum may be regrouped by cycle type.

For a fixed cycle type $(m_1,\dots ,m_n)$ with ${\sum }_{d}d{m}_d=n$, there are exactly the permutations counted by [L1]. Their total contribution to the unnormalized sum is therefore $\frac{n!}{{\prod }_d{d}^{m_d}{m}_d!}{\prod }_d{s}_d^{m_d}$.

Divide the regrouped sum of step 2.1 by $n!$, as required by [F1]. The factor $n!$ cancels, leaving exactly the displayed cycle-type expansion for $Z(S_n)$.

By [L1] and [L2], a permutation of cycle type $(m_1,\dots ,m_n)$ belongs to $A_n$ exactly when ${\sum }_d(d-1)m_d$ is even.

For such an even cycle type, the number of permutations in $A_n$ with that type is the same as the number in $S_n$, namely $n!\mathrm{/}{\prod }_d{d}^{m_d}{m}_d!$, because an entire cycle type is either even or odd. Therefore the unnormalized cycle-index sum over $A_n$ is ${\sum }_{\begin{array}{c}{m}_1,\dots ,m_n\ge 0\\ {\sum }_{d}d{m}_d=n\\ {\sum }_d(d-1)m_d\text{ even}\end{array}}\frac{n!}{{\prod }_d{d}^{m_d}{m}_d!}{\prod }_d{s}_d^{m_d}$.

Divide step 2.1 by $\mathrm{\mid }{A}_n\mathrm{\mid }=n!\mathrm{/}2$ from [L3]. This multiplies the cycle-type coefficients by $2\mathrm{/}n!$, leaving exactly $2{\sum }_{\begin{array}{c}{m}_1,\dots ,m_n\ge 0\\ {\sum }_{d}d{m}_d=n\\ {\sum }_d(d-1)m_d\text{ even}\end{array}}\frac{1}{{\prod }_d{d}^{m_d}{m}_d!}{\prod }_d{s}_d^{m_d}$. The equivalent filtered formula follows because $1+(-1{)}^e$ is $2$ when $e$ is even and $0$ when $e$ is odd.

A length-$n$ necklace over an $m$-letter alphabet is exactly a colouring of the vertices of a labelled $n$-gon by $m$ colours, up to the rotation action of $C_n$.

By [L1] and [L2], the number of such orbits is $Z(C_n)(m,m,\dots ,m)=\frac{1}{n}{\sum }_{d\mid n}\phi (d)m^{n\mathrm{/}d}$.

A bracelet is a colouring of a labelled $n$-gon up to all dihedral symmetries, so [L1] counts it by evaluating $Z(D_{2n})$ at $s_d=m$ for all $d$.

Substitute $s_d=m$ into the odd case of [L2]. Since $s_1{s}_2^{(n-1)\mathrm{/}2}$ becomes $m^{(n+1)\mathrm{/}2}$, the odd-$n$ bracelet count is $\frac{1}{2n}{\sum }_{d\mid n}\phi (d)m^{n\mathrm{/}d}+\frac{1}{2}{m}^{(n+1)\mathrm{/}2}$.

Substitute $s_d=m$ into the even case of [L2]. The two reflection monomials become $m^{n\mathrm{/}2+1}$ and $m^{n\mathrm{/}2}$, giving $\frac{1}{2n}{\sum }_{d\mid n}\phi (d)m^{n\mathrm{/}d}+\frac{1}{4}(m^{n\mathrm{/}2}+m^{n\mathrm{/}2+1})$.

Steps 2.1 and 2.2 are the two parity cases for $n$, so they prove the stated bracelet formulas.

By [F1], edge-sets on $[n]$ are exactly colourings of the finite set $E_n$ by the two colours white and black. The induced action of $S_n$ on those colourings is exactly the relabelling action on edge-sets.

Give white weight $1$ and black weight $x$. Then the weight of a colouring corresponding to $A\subseteq E_n$ is precisely $x^{\mathrm{\mid }A\mathrm{\mid }}$. The $d$-th power sum of the two colour weights is therefore $1^d+x^d=1+x^d$.

Apply [L2] to the action of $S_n$ on the colourings of $E_n$. By step 2.1, the resulting pattern inventory is exactly $Z_{S_n\curvearrowright E_n}(1+x,1+x^2,\dots ,1+x^{\mathrm{\mid }{E}_n\mathrm{\mid }})$, and by the definition of weight it is also exactly ${\sum }_O{x}^{\mathrm{\mid }A\mathrm{\mid }}=F_n(x)$, where for each orbit $O$ the symbol $A$ denotes any member of $O$.

Fix $n\ge 0$. Factors with $d>n$ cannot contribute to the coefficient of $t^n$, so that coefficient is already the coefficient of $t^n$ in the finite truncation $\exp \left({\sum }_{d=1}^n\frac{s_d{t}^d}{d}\right)$. By [L2], this truncation equals ${\prod }_{d=1}^n\exp \left(\frac{s_d{t}^d}{d}\right)={\prod }_{d=1}^n{\sum }_{m_d\ge 0}\frac{s_d^{m_d}{t}^{d{m}_d}}{d^{m_d}{m}_d!}$.

Expanding the finite product in step 1.1, the coefficient of $t^n$ is ${\sum }_{\begin{array}{c}{m}_1,\dots ,m_n\ge 0\\ {\sum }_{d=1}^{n}d{m}_d=n\end{array}}\frac{1}{{\prod }_{d=1}^n{d}^{m_d}{m}_d!}{\prod }_{d=1}^n{s}_d^{m_d}$. This depends only on $s_1,\dots ,s_n$.

The coefficient in step 2.1 is exactly the cycle-type formula for $Z(S_n)$ from [L1]. Since this holds for every $n$, the whole series satisfies ${\sum }_{n\ge 0}Z(S_n)t^n=\exp \left({\sum }_{d\ge 1}\frac{s_d{t}^d}{d}\right)$.

Let $C_4=⟨g⟩$ act on $X$ through the quotient map $g\mapsto \tau$. Then the two even powers of $g$ act as the identity and the two odd powers act as $\tau$, so $Z_{C_4}(X)=\frac{1}{4}(2s_1^4+2s_2^2)=\frac{1}{2}(s_1^4+s_2^2)$.

Let $V_4=\{1,a,b,ab\}$ act on $X$ through a quotient $V_4\twoheadrightarrow \{1,\tau \}$ with kernel of size $2$. Then again two group elements act as the identity and two act as $\tau$, so $Z_{V_4}(X)=\frac{1}{4}(2s_1^4+2s_2^2)=\frac{1}{2}(s_1^4+s_2^2)$.

The groups $C_4$ and $V_4$ are not isomorphic, but steps 1.1 and 1.2 give the same cycle index. Therefore the displayed claim is false.

Let $C_4=⟨g⟩$ act on $X$ through the quotient map $g\mapsto \tau$. Then two elements act as the identity and two act as $\tau$, so [F1] gives the cycle index $\frac{1}{4}(2s_1^4+2s_2^2)=\frac{1}{2}(s_1^4+s_2^2)$.

Let $V_4$ act on $X$ through a quotient onto $\{1,\tau \}$ with kernel of size $2$. Again two elements act as the identity and two act as $\tau$, so the same calculation gives the same cycle index $\frac{1}{2}(s_1^4+s_2^2)$.

The abstract groups $C_4$ and $V_4$ are not isomorphic, so equal cycle index does not determine the acting group. Therefore the displayed claim is false.

Give blue weight $1$ and red weight $u$. Because the action is trivial and $X$ has one point, there are exactly two colouring orbits, with weights $1$ and $u$. Hence the pattern inventory is $1+u$.

By [L1], the same conclusion is the cycle-index substitution for this one-point action. Unless $u=1$, the polynomial $1+u$ is not the plain orbit count $2$.

Therefore the displayed claim is false: a nonconstant weight assignment retains extra colour-profile information instead of collapsing to a single total.