Lagmental Vicfred

Pólya Substitution Counts Colorings up to Symmetry by Vicfred

tags: mathematics, Polya enumeration, combinatorial species, symmetry

Replacing every cycle variable by a color inventory counts weighted coloring orbits. This is a compact note, but the quantifiers and hypotheses stay on the page.

Start locally

A group \(G\) acting on positions identifies colorings that differ by symmetry. Cycle indices record the cycle structure of each \(g\in G\) and support systematic substitution of color inventories.

$$ w(c_1,\ldots,c_m)=c_1+\cdots+c_m $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ \operatorname{Orb}_G(c_1,\ldots,c_m)=Z_G\!\left(w(c_i),w(c_i^2),w(c_i^3),\ldots\right) $$

Compute before generalising

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ Z_{C_4}=\frac14(s_1^4+s_2^2+2s_4)\quad\Longrightarrow\quad\#\text{binary necklaces of length }4=\frac14(2^4+2^2+2\cdot2)=6 $$

The global view

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad w(c_1,\ldots,c_m)=c_1+\cdots+c_m,\\[5pt] \mathsf{C}\;&:\quad \operatorname{Orb}_G(c_1,\ldots,c_m)=Z_G\!\left(w(c_i),w(c_i^2),w(c_i^3),\ldots\right). \end{aligned} $$

Edge conditions

Burnside counts orbits under the specified group only. Adding reflections changes necklaces into bracelets and requires a different cycle index.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \operatorname{Orb}_G(c_1,\ldots,c_m)=Z_G\!\left(w(c_i),w(c_i^2),w(c_i^3),\ldots\right) \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Fri 15 April 2016. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.