Pólya 枚举定理 | Codeboy's Blog

形式陈述

设有限群 $G$ 作用在 $n$ 个位置组成的集合 $X$ 上，颜色集为 $\{1,\ldots,q\}$ 。着色是函数 $f:X\to\{1,\ldots,q\}$ ，群通过搬动位置作用于着色： $(g\cdot f)(x)=f(g^{-1}x)$ 。只相差这种位置变换的着色属于同一轨道；颜色名称本身保持不变。

每个 $g$ 在 $X$ 上诱导一个置换，令 $c_j(g)$ 为其中长度 $j$ 的循环个数，因而 $\sum_j j c_j(g)=n$ 。定义循环指标

Z_G(s_1,\ldots,s_n)=\frac1{|G|}\sum_{g\in G}\prod_{j=1}^n s_j^{c_j(g)}.

用变量 $a_i$ 记录第 $i$ 种颜色的用量。Pólya 枚举定理断言，库存多项式

F(a_1,\ldots,a_q) =Z_G\left(\sum_i a_i,\sum_i a_i^2,\ldots,\sum_i a_i^n\right)

中 $a_1^{m_1}\cdots a_q^{m_q}$ 的系数，等于各颜色分别出现 $m_1,\ldots,m_q$ 次的着色轨道数。只有 $\sum_i m_i=n$ 的项可能出现。令全部 $a_i=1$ ，即在循环指标中令每个 $s_j=q$ ，便得到轨道总数。

直觉

若着色被置换 $g$ 固定，同一循环上的位置必须同色：颜色沿循环移动一格后不变，反复移动便约束整个循环。长度 $j$ 的循环若选第 $i$ 色，就贡献 $j$ 个该色位置，权重为 $a_i^j$ ；该循环全部选项的权重和是 $\sum_i a_i^j$ 。

不同循环可以各自选色，所以把这些权重和相乘，得到被 $g$ 固定的全部着色的库存多项式。最后对 $g$ 求平均即可。其理由是：固定一种颜色用量后，这批着色在位置作用下仍封闭，可对它单独使用Burnside 引理。逐个用量比较系数，就证明了整个多项式公式。

例子与边界

四个位置围成一圈，只把旋转视为相同。旋转群 $C_4$ 有四个元素：恒等变换的循环型为 $1^4$ ，半转为 $2^2$ ，两个四分之一转各为 $4^1$ 。因此

Z_{C_4}=\frac{s_1^4+s_2^2+2s_4}{4}.

两色用变量 $r,b$ 表示，代入并展开为

\begin{aligned} F(r,b)&=\frac{(r+b)^4+(r^2+b^2)^2+2(r^4+b^4)}4\\ &=r^4+r^3b+2r^2b^2+rb^3+b^4. \end{aligned}

故总数为 $F(1,1)=6$ 。两红两蓝恰有两类：相邻同色的 $rrbb$ 与交替的 $rbrb$ 。前者轨道有四个带起点的串，后者只有两个，说明直接用六个带起点的双色等量串除以群阶四会失败；Burnside 平均正是处理这种不等大的轨道。

本例只允许旋转。若允许翻面，就要加入反射，使用二面体群的循环指标；不同长度或颜色数时，两种等价关系的计数可能不同。若还允许全体颜色互换，作用对象又变了，不能沿用“颜色名称固定”的公式。只知道群的阶也不够，同一个群作用在不同位置集合上可能具有不同循环型。

推论与应用

库存多项式保留每种颜色的数量，因此既能计总数，也能通过取系数处理固定库存。若各颜色具有非负整数重量 $w_i$ ，且只关心总重量，可再将 $a_i$ 代为 $t^{w_i}$ ，得到按总重量分类的普通生成函数；多元库存本身不依赖单变量级数的收敛性。

项链与手镯去重、固定骨架上的取代基分布，都可按这一机制处理。枚举无标号图时，“位置”应取可能的边，顶点置换诱导这些边位置上的作用，颜色表示边是否存在；若错把顶点循环型直接代入，计数的就不是图。对于还有邻接禁色等额外限制的着色，必须重新求每个变换固定的合法对象，不能直接使用所有着色的自由循环乘积。

参考资料

Mitchel T. Keller and William T. Trotter, Applied Combinatorics, 在线版，访问于 2026，§15.4 Pólya's Theorem，循环指标、库存多项式及 Theorem 15.11。
Kenneth P. Bogart, Combinatorics Through Guided Discovery, Mathematics LibreTexts 在线版，2021，§6.3 Pólya–Redfield Enumeration Theory，§6.3.1 的轨道权重与 §6.3.2 Exercises 320–323 的循环指标代入。

形式陈述 ​

反向链接

形式陈述