形式陈述

设置换群 $G$$G$ 作用于 $n$$n$ 个位置，循环指标为

$$ Z_G(s_1,\ldots,s_n)=\frac1{|G|}\sum_{g\in G}\prod_{j=1}^n s_j^{c_j(g)}, $$$$Z_G(s_1,\dots ,s_n)=\frac{1}{|G|}\sum _{g\in G}\prod _{j=1}^n{s}_j^{c_j(g)},$$

其中 $c_j(g)$$c_j(g)$ 是 $g$$g$ 的 $j$$j$-循环数。把 $s_j$$s_j$ 代入颜色权生成函数 $a_1^j+\cdots+a_r^j$$a_1^j+\cdots +a_r^j$，所得多项式按颜色用量计数着色轨道。全设为颜色数 $r$$r$ 时退化为 Burnside 轨道计数。

直觉

一个置换固定某种着色，当且仅当每个循环内颜色相同；循环指标把所有对称的循环结构一次编码。

例子与边界

长度 $n$$n$ 项链用循环群，手镯还要加入反射形成二面体群。若颜色有不同权重，代入保留各颜色计数。Pólya 定理不是把颜色数简单代入普通生成函数；群必须明确作用在位置集合上。

推论与应用

Pólya 枚举用于带对称约束的着色、分子结构、图案设计和组合物种计数。

参考资料

• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，Chs. 1–4。
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009，Parts A–B。