波利亚计数定理

波利亚计数定理用置换群的循环结构计算对称变换下不同的着色方式，并能记录每种颜色分别使用了多少次。它推广了只计算总轨道数的 Burnside 引理。

四颗珠子的旋转

把四个位置排成一圈，每个位置选黑或白。两个方案如果能通过旋转重合，就算同一种；此处不把翻转作为允许的对称操作。若暂时标记四个位置，原有 $2^4=16$ 种着色。

旋转群有四个元素。恒等旋转固定所有 16 种着色；转半圈把位置分成两对，固定着色要求每对同色，因而有 $2^2=4$ 种；转四分之一圈或四分之三圈时四个位置在同一个循环中，只能全黑或全白，各有 2 种。Burnside 引理把固定数取平均，得到 $$\frac{16+4+2+2}{4}=6.$$ 它们分别是全白、一黑、两黑相邻、两黑相对、三黑、全黑。两黑有两种情况：旋转保持“相邻或相对”，无法把一种变成另一种。

两黑两白在只允许旋转时有两类：黑珠相邻或相对。空心与实心区分颜色。

循环指标与公式

设有限群 $G$ 作用在有限位置集上，群元素 $g$ 的置换中长度为 $j$ 的循环有 $c_j(g)$ 个。定义循环指标多项式 $$Z_G(a_1,a_2,\dots )=\frac{1}{|G|}\sum _{g\in G}\prod _{j\ge 1}{a}_j^{c_j(g)}.$$ 只有不超过位置总数的循环长度会出现。若颜色有权重 $x_1,\dots ,x_r$，令 $p_j=\sum _{i=1}^r{x}_i^j$。波利亚定理给出不同着色轨道的权重生成函数 $$Z_G(p_1,p_2,\dots ).$$ 变量的指数记录各颜色使用次数，某个单项式的系数是相应配色数量下不同轨道的个数。

推导。 一个着色被 $g$ 固定，当且仅当同一个置换循环中的位置颜色相同。长度为 $j$ 的循环若选颜色 $i$，贡献权重 $x_i^j$；对该循环所有颜色求和得到 $p_j$。不同循环独立选择颜色，得到 $\prod _j{p}_j^{c_j(g)}$。对所有群元素平均，就是按颜色数量加权的 Burnside 计数。

记录黑白珠数

四个旋转的循环类型依次是 $1^4,2^2,4,4$，因此 $$Z_{C_4}=\frac{1}{4}(a_1^4+a_2^2+2a_4).$$ 用 $x$ 记录黑珠、$y$ 记录白珠，代入 $p_j=x^j+y^j$ 后展开： $$x^4+x^{3}y+2x^2{y}^2+x{y}^3+y^4.$$ 例如 $x^2{y}^2$ 的系数为 2，恰好对应相邻与相对两种排列；所有系数相加为 6。

对称群必须按实际问题指定。如果还允许将项链翻面，应把反射也计入群并重新计算固定数；这会改变某些问题的答案。颜色权重记录的是同一组位置上每色的使用次数，不应把颜色标签本身的交换误当成位置旋转。