From Burnside to Polya
From Burnside to Polya
看清群作用计数的代数骨架,避开对称论证的常见陷阱
按 空格/→ 演示下一步
全部页面点击任意一页,跳回舞台从这页播放
From Burnside to Polya
看清群作用计数的代数骨架,避开对称论证的常见陷阱
什么是对称性
从 Burnside 到 Polya,整套方法都围绕对称性展开。可你脱口说这朵雪花是对称的时,到底在说什么?
换完座若无人察觉,说明这个换法是对称的——视角不同,实质相同
为什么对称性需要计数
上一页我们看见了对称的样子。但化学家真正头疼的是:旋转或翻转后的结构,算同一个分子还是不同?这就是对称性计数的难点。
三张照片其实是一根手指,必须找到旋转后不变的「身份证」
Burnside vs Polya 定位
从对称群作用出发,沿四段路走出从引理到定理的升级过程。
群作用与轨道
上页我们看到 Polya 比 Burnside 优雅:它不是逐元素死算,而是「分类再计数」。这背后靠的就是群作用——把对称群「搬」到集合上的统一语言。
老师说「第 g 组换到第 g·x 排」就是群作用;同一批同学被多次轮换,最终落座的几个位置就构成一个轨道
Burnside 引理公式
Burnside 引理把「数轨道」转化为对群的一组加法与一次除法。
Burnside 应用:立方体着色
按 Burnside 流程:列群元素 → 分类算循环数 → 加权求和 → 除以群阶。
Burnside 的局限性
置换数量是分水岭——少时游刃有余,多时寸步难行;知道边界才知道何时必须升级到 Polya。
- 规模:|G| ≈ 24 量级
- 不动点:逐项手算可行
- 成本:分钟级完成
- 代表:立方体 24 旋转
- 规模:|G| ≈ n! 量级
- 不动点:逐项手算不可行
- 成本:随 n 指数爆炸
- 代表:高阶对称 / 分子群
Polya 定理的洞见
Burnside 引理虽然给出了漂亮的等式,但实际计算时仍要逐个检查每个着色是否被某个置换固定——复杂度与着色总数成正比。Polya 的关键洞见是:根本不必看那些着色。
旧方法 O(物件数×检查员数);新方法只看流程本身有几道循环工序
Polya vs Burnside 路径对比
两种方法计算步骤的可视化对照
置换的循环结构
上一篇看到 Polya 的核心是「按置换的形状分类」。置换的形状是什么?答案是循环:任何置换都能拆成若干不相交的循环,循环的长度与个数共同构成它的指纹。
每条蛇独立成闭环,长度即循环长度,蛇之间互不相交
循环指数多项式定义
循环指数多项式 Z(G) 是从群中每个置换的结构,一步步累积出来的。
Polya 定理完整表述
上节定义了 Z(G),它是群作用结构的完整指纹。现在只需一步:把每个变量替换为颜色数 m,得到的纯数字就是不等价着色数——这就是 Polya 定理。
输入对称结构 + 颜色数,输出所有「看起来不同」的涂法数
Polya 定理计算步骤
Polya 公式把群结构翻译成数字:先把置换拆成循环,再组装成多项式,最后代入颜色数。
手性碳与四面体对称
从四面体碳出发,看 12 个旋转如何把 24 个排列压成 2 个轨道——手性的群论来源。
手性分子计数计算
手性计数靠双群对比:旋转群区分对映体,全对称群合并它们,差值就是手性结构对数。
旋转与反射二面体群
沿树状图自顶向下读:先看 Dₙ 拆为旋转与反射两支,再下钻到每支的循环结构细节。
项链着色计数计算
用 Polya 定理直接写出 D_n 群下 n 珠 m 色项链的闭式计数。
D_n 群分旋转与反射两类置换;逐类代入循环数,最后按 Polya 公式除以 2n。
Polya 定理自测
用 Polya 定理计算 n 个位置用 k 种颜色着色的方案数时,循环指数多项式 P_G 中每个变量 xᵢ 应代入?
从 Burnside 到 Polya 全览
- ✓Burnside 逐个查固定着色,Polya 按循环结构批量算
- ✓群作用→轨道→等价类是认知骨架,不看群就没 Polya
- ✓颜色换成权重变量,循环指数多项式一次给出所有配色
- ✓前提是存在明确对称群——无群则无 Polya
课后思考
先合上笔记自己想 30 秒,再翻参考答案对思路——
参考答案Burnside 只统计不动点总数,丢失了置换内部信息;循环结构保留了每个置换对各类着色的差异化作用,让多项式系数能精确反映每种对称的贡献。
参考答案基本思想仍成立,但『对群元素求和』变成对连续群的积分,需引入 Haar 测度;循环指数多项式也升级为函数空间上的积分核,计算难度大增。
参考答案图的自同构群结构复杂、阶数难以枚举,且没有天然的循环分解;Polya 需要明确的小群和规则作用,对一般图直接套用几乎不可行。