Polya计数原理与应用

可视化演示

Polya计数定理利用群作用解决对称计数问题，是Burnside引理的推广。本文详解群作用与轨道、Burnsi... 切换模式查看不同维度。

群作用与轨道：动作的数学化

小满发现，顾客看项链的方式无非几种：端详、顺时针转一格、翻个镜面。“端详、旋转、翻面”这些动作其实是一个个可以组合的对象——先转再翻也是其中一种。把这些动作收集起来，再规定“做完一个动作再做另一个”仍是动作，就得到一个“动作包”，数学上叫群。群作用就是让动作包里的每个动作去“作用”到物体上，把一条项链变成另一条项链。小满把墙上所有项链按“能互相转出来”分成一组，发现分组的结果和顾客的看法完全一致。

从数学上看，G 是一个群，X 是全体染色方案。动作 g 把方案 x 送到 g·x。两个关键概念由此诞生：轨道 O_x = {g·x : g∈G}，即 x 能变出的所有“看起来的样子”，一条项链的所有旋转版本属于同一轨道；稳定子 G_x = {g : g·x = x}，即让 x 纹丝不动的动作集合。轨道-稳定子定理把两者与群大小连起来：

小满恍然大悟：原来“几种样子”和“几种对称视角”互为镜像，数清一边就能算出另一边。但珠坊真正关心的是“总共几款”，也就是轨道的总数。这就要等 Burnside 引理登场。

Burnside引理：数不动点，不数款式

小满最初的做法是两两对比：把每条项链正反前后所有版本都拍成照片，查重后得到款数。项链一多，照片墙铺满整屋。老数学家提醒她：把视线从“款式”挪到“动作”上。对每个动作，数一数有多少款式在它手下“纹丝不动”——这些不动点可以直接算出；把所有动作的不动点数加起来求平均，就是轨道数。小满半信半疑地试：3 颗珠子 2 种颜色，只允许旋转。恒等动作不动点 8（所有方案都不变）；转 120° 后仍不变的只有 2 种纯色；转 240° 同理 2 种。平均 (8+2+2)/3=4，和实物对比果然 4 款。Burnside 引理正式写成：

引理的正确性来自“二重计数”：把“动作使方案不动”的对子（g, x）数两次——先按动作数，再按方案数——每个轨道恰好贡献 |G| 次，所以总数除以 |G| 就是类别数。小满烧掉照片墙，只保留一张“不动点统计表”。但她立刻发现新麻烦：6 颗珠 3 色时方案有 729 个，总不能逐个检查哪个方案在旋转后不变。Polya 定理正是来解决“不动点怎么快算”的。

Polya定理：把动作拆成轮换

老数学家教小满一个“偷懒”秘诀：看一个动作时，别盯着每条项链，只看“珠子的位置怎么被整体调动”。旋转两步时，第 0 颗到第 2、第 2 颗到第 4、第 4 颗到第 0，三颗珠子围成一个闭环；旋转 k 步就是把位置分成若干这样的环。每个环里的珠子在旋转后必须同色，整条项链才可能纹丝不动。这个闭环，数学上叫轮换。环的数量越多，颜色自由度越高。

旋转 k 步的轮换数等于 gcd(k, n)。每个轮换内部颜色可任选，且各轮换互不影响，于是该动作的不动点方案数 = c^{轮换数}。Polya 定理直接给出：

例如 6 颗珠 3 色、只考虑旋转：恒等动作 6 个轮换贡献 3^6=729；转 60° 和 300° 各 1 个轮换，共 6；转 120° 和 240° 各 2 个轮换，共 18；转 180° 有 3 个轮换，贡献 27。平均下来 (729+6+18+27)/6 = 130 款。小满终于敢接 8 颗珠的大订单了。

轮换指标多项式：给群做“指纹”

更精细的情况需要知道“每种长度的轮换各有几个”。比如正六边形的翻面里，对角翻是 1 个二轮换加 2 个不动点，而对边翻是 3 个二轮换，轮换结构完全不同。把动作 g 中长度为 k 的轮换个数记为 j_k(g)，则每个动作贡献一个单项式 x_1^{j_1} x_2^{j_2} … x_n^{j_n}。把群中所有动作的单项式取平均，就得到轮换指标多项式，也叫循环指数：

轮换指标多项式让“群”也能被存储、比较和运算。小满把六种常见群的轮换指标抄在小黑板上，遇到新订单先认领对应群，再套公式，又快又准。

项链染色实战：六珠三色订单

小满接到一笔大单：6 颗珠、3 种颜色，客人认为旋转或翻面后相同的都算同一款。她先认群：六边形的二面体群 D_6 有 12 个动作——6 个旋转、6 个翻面。接着写出 D_6 的轮换指标，再代入 c=3。D_6 的轮换指标是：

$$Z(D_6) = \frac{1}{12}\left(x_1^6 + 3x_1^2 x_2^2 + 4x_2^3 + 2x_3^2 + 2x_6\right)$$

代入 x_k = 3，得到：

代入 c=3 后分子为 729+243+108+18+6=1104，除以 12 恰好是 92。小满把 92 款手环照片贴在展示墙上，每一款对应一个“轨道代表”，再不用担心给客人报错库存。

应用与扩展：珠坊之外的对称世界

Polya 计数的威力来自它把“数物体”转化成“数动作”。只要实际问题能抽象成三件事——对象集 X、对称动作群 G、颜色集 C——就能套用四步流程：列出 G 的所有动作 → 各自做轮换分解 → 累加 c^{cyc(g)} → 除以 |G|。这个流程在化学、算法和密码学中反复出现，常被称为“Polya 计数三步走”。

化学里，苯环有 6 个等价取代位，二氯苯的异构体数正是“6 位 2 色”的 Polya 计数：代入 c=2 得 (64+48+32+8+4)/12=13，恰好对应 0 氯 1 种、1 氯 1 种、2 氯 3 种、3 氯 3 种、4 氯 3 种、5 氯 1 种、6 氯 1 种。算法领域，判断两张图是否同构时，把顶点标号看作位置、图着色看作方案，轨道就是非同构图类；Nauty 等算法利用群作用裁剪对称分支，正是 Polya 思想的工程化。密码学里，长度为 n 的二进制项链总数是 LFSR 序列与循环码的设计基础，de Bruijn 序列的构造也需要先枚举互不等价的项链类。

把以上流程收拢成一个通用公式，就是 Polya 计数的最终形态：

小满把小黑板挂在珠坊最显眼处。她终于明白：对称不是“看不清的重复”，而是一种可以被数清的结构。Polya 计数给所有“看起来一样”的问题，发了一把精确的尺子。

AI 应用场景

Python 演示

from math import gcd def rotation_classes(n, c):    total = 0    for k in range(n):        total += c ** gcd(k, n)    return total // n def dihedral_classes(n, c):    total = 0    for k in range(n):        total += c ** gcd(k, n)    if n % 2 == 0:        total += (n // 2) * c ** (n // 2)        total += (n // 2) * c ** (n // 2 + 1)    else:        total += n * c ** ((n + 1) // 2)    return total // (2 * n) def main():    print("Polya计数: 项链(仅旋转) vs 手环(旋转+翻面)")    for n in (4, 5, 6, 8, 10):        for c in (2, 3):            r = rotation_classes(n, c)            b = dihedral_classes(n, c)            print(f"n={n:2d}, c={c}: 旋转项链={r:4d}, 手环={b:4d}") if __name__ == "__main__":    main()

1. total += c ** gcd(k, n)对旋转 k 步，轮换数等于 gcd(k,n)，该动作的不动点方案数为 c 的轮换数次方。
2. return total // n除以旋转群大小 n，得到只考虑旋转的项链款数。
3. total += (n // 2) * c ** (n // 2)n 为偶数时，有 n/2 条“过对边”翻面轴，每条贡献 c 的 n/2 次方个不动点方案。
4. total += (n // 2) * c ** (n // 2 + 1)另外 n/2 条“过对角顶点”翻面轴，自由度为 n/2+1。
5. total += n * c ** ((n + 1) // 2)n 为奇数时，所有 n 条翻面轴都有 (n+1)/2 个轮换。
6. return total // (2 * n)二面体群大小为 2n，取平均得到最终手环款数。

常见误区

面试题