From Burnside to Polya

官方信息技术老师·21 页·深入(追求细节与边界)·0 次浏览·2 天前
Polya定理群作用对称计数母函数

From Burnside to Polya

看清群作用计数的代数骨架,避开对称论证的常见陷阱

按 空格/→ 演示下一步

1 / 21 页

全部页面点击任意一页,跳回舞台从这页播放

Polya定理群作用对称计数母函数

From Burnside to Polya

看清群作用计数的代数骨架,避开对称论证的常见陷阱

1第 1 页 · From Burnside to Polya

什么是对称性

从 Burnside 到 Polya,整套方法都围绕对称性展开。可你脱口说这朵雪花是对称的时,到底在说什么?

不变性
对称=变换后与自身不可区分(不可区分是关键,不是没变)
几何视角
旋转、反射、平移——作用在坐标/点上,使图形作为集合不变
代数视角
置换 σ 作用在标记上,使结构(颜色/位置分配)整体不变
一体两面
同一对称操作,可视为几何变换,也可写成一个置换;群论将二者统一
圆桌换座对应 →对称操作

换完座若无人察觉,说明这个换法是对称的——视角不同,实质相同

f(g(x))=f(x),gGf(g(x)) = f(x), \quad \forall\, g \in G
2第 2 页 · 什么是对称性

为什么对称性需要计数

上一页我们看见了对称的样子。但化学家真正头疼的是:旋转或翻转后的结构,算同一个分子还是不同?这就是对称性计数的难点。

化学异构体
同种原子、不同空间排布,旋转后看着一样,其实是同一种分子
电路等价
两个电路接法不同,但整体旋转后能重合,就是同一种设计
肉眼会重复数
直接数看到 n 个,实际独立的可能只有 n/g,g 是对称群大小
需要系统方法
必须把对称变换纳入计数,否则结果一定偏大
同一手指不同角度拍照对应 →同一分子旋转后的样子

三张照片其实是一根手指,必须找到旋转后不变的「身份证」

3第 3 页 · 为什么对称性需要计数

Burnside vs Polya 定位

从对称群作用出发,沿四段路走出从引理到定理的升级过程。

图解渲染中…
b1每个群元的不动点个数求平均c1用多项式记录群元置换结构d1把循环指标中的占位变量代入颜色数
4第 4 页 · Burnside vs Polya 定位

群作用与轨道

上页我们看到 Polya 比 Burnside 优雅:它不是逐元素死算,而是「分类再计数」。这背后靠的就是群作用——把对称群「搬」到集合上的统一语言。

群作用
群 G 通过映射作用于集合 X,每个 g∈G 把 x∈X 送到 g·x∈X,保持单位元与乘法结构
轨道
Orb(x)={g·x : g∈G},从 x 出发能被群元素「搬」到的全部位置
不动点
若 g·x=x 对所有 g∈G 成立,x 是 G 作用下的不动点;它单独构成一个大小为 1 的轨道
轨道-稳定子定理
|G|=|Orb(x)|·|Stab(x)|,稳定子 Stab(x) 是「让 x 不动」的群元素子集
教室座位轮换对应 →群作用与轨道

老师说「第 g 组换到第 g·x 排」就是群作用;同一批同学被多次轮换,最终落座的几个位置就构成一个轨道

G=Orb(x)Stab(x)|G| = |\text{Orb}(x)| \cdot |\text{Stab}(x)|
5第 5 页 · 群作用与轨道

Burnside 引理公式

Burnside 引理把「数轨道」转化为对群的一组加法与一次除法。

1
清点群 G
Burnside 对群 G 中每个元素都要求和,一个不能漏
2
数 |Fix(g)|
对每个 g∈G,数被它留在原地的元素有几个
3
全部求和
∑|Fix(g)| 得到「操作–不动点」对的总数
4
除以 |G|
Burnside 断言:每个轨道贡献恰好 |G|,除回即得轨道数
6第 6 页 · Burnside 引理公式

Burnside 应用:立方体着色

按 Burnside 流程:列群元素 → 分类算循环数 → 加权求和 → 除以群阶。

图解渲染中…
A2立方体旋转对称群,阶|G|=24C1恒等下6个面各自独立循环D1Σ=各类不动着色数加权相加D2Burnside公式 N=Σ/|G|
7第 7 页 · Burnside 应用:立方体着色

Burnside 的局限性

置换数量是分水岭——少时游刃有余,多时寸步难行;知道边界才知道何时必须升级到 Polya。

群阶小时
  • 规模:|G| ≈ 24 量级
  • 不动点:逐项手算可行
  • 成本:分钟级完成
  • 代表:立方体 24 旋转
群阶爆炸时
  • 规模:|G| ≈ n! 量级
  • 不动点:逐项手算不可行
  • 成本:随 n 指数爆炸
  • 代表:高阶对称 / 分子群
群阶小时 Burnside 足够;群阶一爆炸,必须升级到 Polya 的循环指标母函数。
8第 8 页 · Burnside 的局限性

Polya 定理的洞见

Burnside 引理虽然给出了漂亮的等式,但实际计算时仍要逐个检查每个着色是否被某个置换固定——复杂度与着色总数成正比。Polya 的关键洞见是:根本不必看那些着色。

视角反转
Burnside 数「哪个着色被固定」;Polya 反过来,只关心置换本身长什么样
固定数只看循环个数
g 固定的着色数 = m^{c(g)},c(g) 是 g 的循环个数
循环指数 Z(G)
把群 G 所有置换的循环类型打包成多项式,是群的「结构指纹」
换颜色即替换变量
想用 m 种颜色?把 Z(G) 里 x_k 替换为 m^k 求和即可
逐个核对每件行李对应 →直接看检查流程的结构

旧方法 O(物件数×检查员数);新方法只看流程本身有几道循环工序

Fix(g)=mc(g)|\text{Fix}(g)| = m^{c(g)}
9第 9 页 · Polya 定理的洞见

Polya vs Burnside 路径对比

两种方法计算步骤的可视化对照

Polya vs Burnside 路径对
两种方法计算步骤的可视化对照
10第 10 页 · Polya vs Burnside 路径对比

置换的循环结构

上一篇看到 Polya 的核心是「按置换的形状分类」。置换的形状是什么?答案是循环:任何置换都能拆成若干不相交的循环,循环的长度与个数共同构成它的指纹。

循环分解唯一
任何置换都可唯一写成不相交循环的乘积
长度与个数是本质
循环长度的多重集合决定置换在重标号下的等价类
长度决定着色约束
长度大于 1 的循环须整圈同色才是不动点;1-循环可独立涂色
多条各自追尾巴的贪吃蛇对应 →不相交的循环

每条蛇独立成闭环,长度即循环长度,蛇之间互不相交

σ=(1 3 5)(2 4)(6)\sigma = (1\ 3\ 5)(2\ 4)(6)
11第 11 页 · 置换的循环结构

循环指数多项式定义

循环指数多项式 Z(G) 是从群中每个置换的结构,一步步累积出来的。

1
拆解每个置换
把 g 写成不相交循环的乘积
2
统计循环长度
记录长度为 k 的循环各有几个,记作 cₖ(g)
3
写出单项式
用 x₁ᶜ¹·x₂ᶜ²·… 编码 g 的循环结构
4
对群求和
把 G 里所有置换的单项式全部加起来
5
除以群阶
再除以 |G|,就得到 Z(G)
12第 12 页 · 循环指数多项式定义

Polya 定理完整表述

上节定义了 Z(G),它是群作用结构的完整指纹。现在只需一步:把每个变量替换为颜色数 m,得到的纯数字就是不等价着色数——这就是 Polya 定理。

Z(G) 公式
(1/|G|)·Σ x₁^c₁·x₂^c₂·…·x_n^c_n,编码置换循环分解
代入操作
每个 xₖ 直接换成 m(颜色总数),多项式变为纯数
Burnside 已内置
求和项 m^ℓ(g) 恰是该置换的不动点数
前提与边界
有限群 G 作用于有限集 X,m∈ℕ⁺,输出等价类数
万能染色计数器对应 →Polya 定理

输入对称结构 + 颜色数,输出所有「看起来不同」的涂法数

ZG(m,m,,m)=1GgGm(g)Z_G(m,m,\ldots,m) = \frac{1}{|G|}\sum_{g\in G} m^{\ell(g)}
13第 13 页 · Polya 定理完整表述

Polya 定理计算步骤

Polya 公式把群结构翻译成数字:先把置换拆成循环,再组装成多项式,最后代入颜色数。

1
确定群与置换
明确作用对象与对称群G,列出群中所有置换
2
分解循环结构
把每个置换写成不相交循环乘积,记录各长度循环数
3
写出循环索引
按循环类型汇总,构造P_G(x1,x2,...)多项式
4
代入颜色数
把每个xi替换为可用颜色数m,求值得最终答案
14第 14 页 · Polya 定理计算步骤

手性碳与四面体对称

从四面体碳出发,看 12 个旋转如何把 24 个排列压成 2 个轨道——手性的群论来源。

图解渲染中…
DT 是纯旋转群(不含镜像反射),同构于 A4G穿过顶点与对面中心的 4 根 3 重轴,每根给 ±120°IPolya:等价类数 = 4! / |旋转群| = 24/12 = 2K镜像 σ 把 R 映回 S,所以两轨道在 T 中不相通
15第 15 页 · 手性碳与四面体对称

手性分子计数计算

手性计数靠双群对比:旋转群区分对映体,全对称群合并它们,差值就是手性结构对数。

1
确定对称群范围
只取真旋转T则保留对映体差异,加入反射得Td则把对映体对折成同一类
2
分别列置换结构
对T和Td各自统计各类置换的循环分解,列出循环长度与出现次数
3
写出循环指数式
分别构建P_T和P_Td,形式相同但项数和系数不同
4
代入配体数求值
k种不同配体代入xi的k次幂,每群各算一次得到NT与NTd
5
作差得手性对数
NT减NTd即手性结构对数,光学异构体总数为该差值的两倍
16第 16 页 · 手性分子计数计算

旋转与反射二面体群

沿树状图自顶向下读:先看 Dₙ 拆为旋转与反射两支,再下钻到每支的循环结构细节。

图解渲染中…
B3r^k 分解为 gcd(n,k) 个循环,每个长度 n÷gcd(n,k)C6过两顶点轴:2 个不动点 + (n-2)/2 个 2-循环C7过两边中点轴:n/2 个 2-循环,无不动点
17第 17 页 · 旋转与反射二面体群

项链着色计数计算

python

用 Polya 定理直接写出 D_n 群下 n 珠 m 色项链的闭式计数。

代码高亮加载中…

D_n 群分旋转与反射两类置换;逐类代入循环数,最后按 Polya 公式除以 2n。

18第 18 页 · 项链着色计数计算

Polya 定理自测

点击作答

用 Polya 定理计算 n 个位置用 k 种颜色着色的方案数时,循环指数多项式 P_G 中每个变量 xᵢ 应代入?

19第 19 页 · Polya 定理自测

从 Burnside 到 Polya 全览

  • Burnside 逐个查固定着色,Polya 按循环结构批量算
  • 群作用→轨道→等价类是认知骨架,不看群就没 Polya
  • 颜色换成权重变量,循环指数多项式一次给出所有配色
  • 前提是存在明确对称群——无群则无 Polya
延伸主题:连续群与 Haar 测度Pólya 在化学异构体的经典应用着色多项式与 Tutte 多项式
20第 20 页 · 从 Burnside 到 Polya 全览

课后思考

先合上笔记自己想 30 秒,再翻参考答案对思路——

1为什么 Polya 需要先拆解置换的循环结构,而不是直接沿用 Burnside 的平均不动点思路?

参考答案Burnside 只统计不动点总数,丢失了置换内部信息;循环结构保留了每个置换对各类着色的差异化作用,让多项式系数能精确反映每种对称的贡献。

2如果把立方体换成球面图案(连续旋转群),Burnside 引理和 Polya 公式还成立吗?

参考答案基本思想仍成立,但『对群元素求和』变成对连续群的积分,需引入 Haar 测度;循环指数多项式也升级为函数空间上的积分核,计算难度大增。

3把『数等价构型』的思路迁移到图同构或网络拓扑分类上,会遇到什么本质困难?

参考答案图的自同构群结构复杂、阶数难以枚举,且没有天然的循环分解;Polya 需要明确的小群和规则作用,对一般图直接套用几乎不可行。

21第 21 页 · 课后思考