Counting up to Symmetry: Burnside and Pólya — Examples

The rotation action of $C_4$ on a square gives

$Z(C_4)=\frac{1}{4}(s_1^4+s_2^2+2s_4)\mathrm{.}$

Indeed, the identity has cycle type $1^4$, the half-turn has cycle type $2^2$, and the two quarter-turns each have cycle type $4$.

For the square,

$Z(D_8)=\frac{1}{8}(s_1^4+2s_1^2{s}_2+3s_2^2+2s_4)\mathrm{.}$

The four rotations contribute

$s_1^4,s_2^2,s_4,s_4,$

the two reflections through opposite vertices contribute $s_1^2{s}_2$, and the two reflections through opposite edges contribute $s_2^2$.

The three cycle types in $S_3$ are:

• one identity of type $1^3$;
• three transpositions of type $12$;
• two $3$-cycles of type $3$.

Therefore

$Z(S_3)=\frac{1}{6}(s_1^3+3s_1{s}_2+2s_3)\mathrm{.}$

Let the group $C_2=\{1,\tau \}$ act on

$X=\{1,2,3,4\}$

by the transposition $\tau =(12)$ and with $3,4$ fixed.

The orbits are

$\{1,2\},\{3\},\{4\},$

so there are $3$ orbits. This is a nonfree action, and the naive quotient $\mathrm{\mid }X\mathrm{\mid }\mathrm{/}\mathrm{\mid }{C}_2\mathrm{\mid }=4\mathrm{/}2=2$ is the wrong count.

Give blue weight $1$ and red weight $r$ in the dihedral action on the square. Substituting

$s_i=1+r^i$

into the cycle index of The cycle index of D_8 yields

$1+r+2r^2+r^3+r^4\mathrm{.}$

So, up to dihedral symmetry, there is:

• $1$ colouring with $0$ red vertices;
• $1$ colouring with $1$ red vertex;
• $2$ colourings with $2$ red vertices, namely adjacent and opposite pairs;
• $1$ colouring with $3$ red vertices;
• $1$ colouring with $4$ red vertices.

Evaluating the necklace formula at $n=6$ and $m=2$ gives

$\frac{1}{6}(\phi (1)2^6+\phi (2)2^3+\phi (3)2^2+\phi (6)2)=\frac{1}{6}(64+8+8+4)=14.$

So there are $14$ binary necklaces of length $6$.

The published symbolic-method necklace formula gives the same evaluation at $n=6$ and $m=2$:

$\frac{1}{6}(64+8+8+4)=14.$

So the cycle-construction route and the Pólya route both count $14$ binary necklaces of length $6$.

For $n=6$ and $m=2$, the bracelet formula gives

$\frac{1}{12}(64+8+8+4)+\frac{1}{4}(2^3+2^4)=7+6=13.$

So there are $13$ binary bracelets of length $6$.

The $24$ rotational symmetries of the cube act on its $6$ faces with cycle types:

• $1$ identity of type $1^6$;
• $6$ quarter-turns of type $1^{2}4$;
• $3$ half-turns through opposite faces of type $1^2{2}^2$;
• $8$ third-turns through opposite vertices of type $3^2$;
• $6$ half-turns through opposite edges of type $2^3$.

Therefore the number of face-colourings up to rotation with $m$ colours is

$\frac{m^6+3m^4+12m^3+8m^2}{24}\mathrm{.}$

For the action of $S_4$ on the $6$ unordered pairs of $[4]$, the induced cycle-index polynomial is

$\frac{1}{24}(s_1^6+9s_1^2{s}_2^2+8s_3^2+6s_2{s}_4)\mathrm{.}$

Substituting $s_i=1+x^i$ gives

$1+x+2x^2+3x^3+2x^4+x^5+x^6\mathrm{.}$

In particular, setting $x=1$ yields

$1+1+2+3+2+1+1=11,$

so there are $11$ edge-set orbits, equivalently $11$ simple graphs on $4$ vertices up to isomorphism.

Nonisomorphic groups cannot act on the same finite set with the same cycle index.

Replacing every cycle-index variable by the one-variable specialization

$x_i=x^i$

still retains the full colour-profile information of a weighted inventory.