Burnside 引理与 Polya 定理

本节导读

Polya 定理单元是大纲组合数学的最后一个单元，列了四条：Burnside 引理、Polya 定理、母函数型的 Polya 定理、图的计数。它解决的是这样一类问题：用几种颜色给项链的珠子、正方形的顶点、立方体的面着色，旋转（或翻转）后能重合的算同一种，一共有多少种不同的方案。

这类题几乎都是计算题，步骤固定：找出对称操作组成的置换群，写出每个置换的轮换结构，代入公式。学完你应该能熟练写出正 n 边形的旋转群、二面体群和立方体旋转群的轮换结构，并用 Polya 定理一步算出答案。

等价类与 Burnside 引理

设 G 是作用在一组对象（比如全部着色方案）上的置换群。如果 G 中某个置换能把方案 a 变成方案 b，就说 a、b 等价；要数的就是等价类的个数。对 G 中每个置换 g，记 $c_1(g)$c1​(g) 为在 g 作用下保持不变的方案个数。Burnside 引理：

$L = \frac{1}{\lvert G \rvert} \sum_{g \in G} c_1(g)$L=∣G∣1​∑g∈G​c1​(g)

例如正方形的 4 个顶点用黑、白两色着色，只允许旋转，16 种方案里：不转时 16 种都不变；转 90° 或 270° 时，只有 4 个顶点同色的 2 种不变；转 180° 时，对角顶点同色的 $2^2 = 4$22=4 种不变。所以 $L = \frac{16 + 2 + 4 + 2}{4} = 6$L=416+2+4+2​=6。Burnside 引理的难处在于要逐个数「不变的方案」。

Polya 定理与轮换指标

如果 G 是作用在 n 个位置上的置换群，用 m 种颜色给位置着色：一个方案在置换 g 下不变，当且仅当 g 的每个轮换里的位置都同色。设 g 有 $c(g)$c(g) 个轮换（不动点也算长度为 1 的轮换），不变的方案就有 $m^{c(g)}$mc(g) 个。于是 Polya 定理：

$L = \frac{1}{\lvert G \rvert} \sum_{g \in G} m^{c(g)}$L=∣G∣1​∑g∈G​mc(g)

把置换 g 的轮换结构记成单项式：有 $b_k$bk​ 个长度为 k 的轮换，就记 $x_1^{b_1} x_2^{b_2} \cdots$x1b1​​x2b2​​⋯；对全群求平均，得到轮换指标 $P_G$PG​。把所有 $x_k$xk​ 都换成 m，就是上面的 L。常用的轮换结构如下：

群与置换	个数	轮换结构
正 n 边形绕中心转 k 格	每个 k 一个	$\gcd(n, k)$gcd(n,k) 个长为 $\frac{n}{\gcd(n, k)}$gcd(n,k)n​ 的轮换
正 n 边形翻转，n 为奇数	n 个	$x_1 x_2^{(n-1)/2}$x1​x2(n−1)/2​
正 n 边形翻转，n 为偶数，过两个对顶点	$\frac{n}{2}$2n​ 个	$x_1^2 x_2^{(n-2)/2}$x12​x2(n−2)/2​
正 n 边形翻转，n 为偶数，过两条对边中点	$\frac{n}{2}$2n​ 个	$x_2^{n/2}$x2n/2​

只许旋转时群是 n 个元素的循环群（项链问题）；允许翻转时群是 2n 个元素的二面体群（手镯问题）。审题时先看「能不能翻过来」。

立方体的旋转群有 24 个元素，作用在 6 个面上的轮换结构：

旋转	个数	面的轮换结构
不动	1	$x_1^6$x16​
绕对面中心轴转 ±90°	6	$x_1^2 x_4$x12​x4​
绕对面中心轴转 180°	3	$x_1^2 x_2^2$x12​x22​
绕对角顶点轴转 ±120°	8	$x_3^2$x32​
绕对棱中点轴转 180°	6	$x_2^3$x23​

所以 $P_G = \frac{1}{24}(x_1^6 + 6x_1^2 x_4 + 3x_1^2 x_2^2 + 8x_3^2 + 6x_2^3)$PG​=241​(x16​+6x12​x4​+3x12​x22​+8x32​+6x23​)。

母函数型的 Polya 定理

如果还要求每种颜色用几次，就把轮换指标里的 $x_k$xk​ 换成各颜色变量的 k 次方之和，比如两种颜色 r、b 时换成 $r^k + b^k$rk+bk，展开后 $r^i b^j$ribj 的系数就是恰用 i 个 r、j 个 b 的不等价方案数。例如 4 颗珠子的项链（只旋转），$P_G = \frac{1}{4}(x_1^4 + x_2^2 + 2x_4)$PG​=41​(x14​+x22​+2x4​)；求 2 红 2 蓝：$x_1^4$x14​ 贡献 $C(4, 2) = 6$C(4,2)=6，$x_2^2 = (r^2 + b^2)^2$x22​=(r2+b2)2 贡献 2，$x_4$x4​ 贡献 0，结果 $\frac{6 + 2}{4} = 2$46+2​=2，就是「红红蓝蓝」和「红蓝红蓝」两种。