Rotating Polyhedron

官方信息技术老师·21 页·深入(追求细节与边界)·0 次浏览·2 天前
旋转群Polya定理等价类组合计数

Rotating Polyhedron

用Polya定理数清每一种旋转下的不等价染色方案

按 空格/→ 演示下一步

1 / 21 页

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

旋转群Polya定理等价类组合计数

Rotating Polyhedron

用Polya定理数清每一种旋转下的不等价染色方案

1第 1 页 · Rotating Polyhedron

旋转对称是什么

上一页我们看到正多面体能转着放回自身——这背后就是旋转对称。先从生活里找感觉:雪花转一下和原来一样,风车叶片每转 90° 看起来没变。数学上,这到底意味着什么?

旋转轴
穿过图形的一条直线,所有旋转都绕它发生
旋转角度
每次转过的弧度,完整一圈是 2π
不变性
旋转后与原图形严格重合,这才是「对称」的判据
阶数 n
绕一圈内有 n 个位置看上去相同,叫 n 阶旋转对称
风车叶片对应 →n 阶旋转对称

4 片叶每转 90° 看上去一样,对应 4 阶;叶数 = 阶数

2第 2 页 · 旋转对称是什么

旋转对称 vs 全对称

有无反射面的本质区别

旋转对称 vs 全对称
有无反射面的本质区别
3第 3 页 · 旋转对称 vs 全对称

正多面体的旋转群

从五种正多面体出发,按旋转对称群阶数归类,分三档展示。

图解渲染中…
R五种正多面体统称,古希腊称柏拉图立体G1交错群A4,12个旋转G2对称群S4,24个旋转G3交错群A5,60个旋转,三维最大有限旋转群
4第 4 页 · 正多面体的旋转群

旋转的循环表示

上一页讲到旋转会搬动多面体的面。但「搬动」具体怎么记?这就要用置换的轮换表示——给面编号,看它们怎么循环。

轮换记号
(a b c) 表示 a→b、b→c、c→a,括号内按序循环
轮换分解
任何置换都能唯一拆成若干不相交的轮换
长度即几何
长度为 k 的轮换对应一根轴,k 个面绕它转一圈
四面体实例
绕顶点轴:3 面成 (1 2 3);绕棱中点轴:2 面互换
旋转木马对应 →轮换表示

座位号随转动依次被不同孩子占据,正是一次轮换

ord(σ)=lcm(k1,k2,,km)\text{ord}(\sigma) = \operatorname{lcm}(k_1, k_2, \ldots, k_m)
5第 5 页 · 旋转的循环表示

Burnside引理回顾

上一页我们把旋转写成点的循环;现在让每个旋转作用在所有颜色方案上:有的方案被转回原样,有的会被改变。

颜色方案集合
把每种给多面体表面的着色看作一个对象,群作用会把彼此可通过旋转互换的方案归到同一轨道。
固定着色数
对每个旋转 g,统计在 g 作用下完全不变的着色数,记为 Fix(g)。
轨道—稳定数平均
Burnside 引理指出,轨道数等于所有旋转的固定着色数之和,再除以旋转数。
边界提醒
固定着色数是整个方案不变,不是每个面颜色都相同;它必须按每个群元素分别统计。
整理同一组人的座位表对应 →轨道数与固定着色数平均

每种座位重排对应一个旋转;重排后仍相同的表数记一次,最后把所有重排的固定数取平均。

轨道数=1GgGFix(g)\text{轨道数}=\frac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|
6第 6 页 · Burnside引理回顾

Burnside引理计算示例

三步走流程:左列三步主干,右列展开第二步对每个旋转的固定着色计数。

图解渲染中…
aG=C3作用于3颗珠子2色的项链b1恒等元固定所有着色,|Fix e|=颜色数^珠子数b2非平凡旋转只固定3颗全同色的着色d(8+2+2)/3=4,验证Burnside公式
7第 7 页 · Burnside引理计算示例

从引理到定理的跨越

Burnside 引理要逐元素算,元素一多就崩;用循环指标多项式把它压成一行式子。

1
逐一求固定着色
对群里每个旋转 g 数一遍 C(g),元素多时手算爆炸
2
按循环结构分组
同种循环类型对应同一个 C(g),不必逐个重算
3
写成循环指标多项式
每种循环类型一项 x₁^{c₁}x₂^{c₂}…,按元素个数加权求和得 Z(G)
4
代入颜色方案
把 xᵢ 换成「给长 i 循环染 k 种色的方案 k^i」,展开即得答案
8第 8 页 · 从引理到定理的跨越

循环指标多项式

用 Burnside 引理时,我们对每个旋转 g 只问:'涂完之后还认得出来吗?' Z(G) 把这个问题升级——它不只问认不认得,还把 g 内部'怎么循环的'完整记录下来。

Z(G) 形式
Z(G)=(1/|G|)Σ x₁^{c₁}x₂^{c₂}…,把整个群的循环结构打包成一个表达式
xₖ 含义
xₖ 是占位符,代表'长度为 k 的循环';指数 cₖ(g) 是元素 g 里这种循环的个数
构造步骤
遍历每个 g→写出循环分解→翻译成单项式→全部相加再除以 |G|
群母函数
把每个 xₖ 替换成颜色数 c,每项化简为 c^点数,可恢复 Burnside 计数
体检报告 vs 只量身高对应 →Z(G) vs Burnside

Burnside 只输出一个数(不变点数),Z(G) 给出更细的指纹(循环结构)

Z(G)=1GgGx1c1(g)x2c2(g)xncn(g)Z(G) = \frac{1}{|G|} \sum_{g \in G} x_1^{c_1(g)} x_2^{c_2(g)} \cdots x_n^{c_n(g)}
9第 9 页 · 循环指标多项式

循环类型计数方法

python

把正四面体的 12 个旋转拆成循环结构,统计每个指纹各有几个。

代码高亮加载中…

对每个旋转算循环指纹,再用 Counter 按指纹聚合,立刻看到 {(3,1):8, (2,2):3, (1,1,1,1):1}——几何上三类旋转在代数上就是三类循环类型。

10第 10 页 · 循环类型计数方法

立方体的24种旋转

立方体的所有旋转按旋转轴所在位置分为四大类,每类对应若干种旋转。

图解渲染中…
C1穿过两对面中心的轴,方向沿坐标轴D1穿过两条对边中点的轴,方向倾斜E1穿过两对顶点的轴,即立方体对角线
11第 11 页 · 立方体的24种旋转

立方体旋转群分析

立方体24种旋转不必逐一枚举,按轴类型分四类即可系统统计循环结构。

1
按轴类型分类
面中心轴3根、顶点对角线轴4根、棱中点轴6根,加上恒等共四种轴型。
2
确定类的大小
面轴可转90°/180°/270°,顶点轴120°/240°,棱轴只180°。每类大小=轴数×独立角度数。
3
追踪顶点循环
对每类旋转,标出8个顶点的轨道,分出固定点、2-轮换、3-轮换、4-轮换的个数。
4
追踪边与面循环
对12条棱和6个面同样追踪轨道,特别注意'棱整体不动但端点互换'的情况。
5
汇成循环类型表
把四类旋转的顶点、棱、面循环结构合并成一张表,为代入循环指标多项式做准备。
12第 12 页 · 立方体旋转群分析

立方体的循环指标

上一页把立方体24种旋转按共轭类分成了5组——这一页就给每组配上对应的循环结构项:次数乘以循环多项式,五项加和再除以24,Z(Cub)的完整多项式就落地了。

恒等旋转
1种,6个面都各是1-循环:贡献 x₁⁶
面心轴180°
3种,2面贴轴不动、4个侧面对换:贡献 3x₁²x₂²
面心轴90°
6种,2面贴轴不动、4个侧面绕一圈:贡献 6x₁²x₄
体对角线120°
8种,3+3个面各绕一圈:贡献 8x₃²
对棱中点180°
6种,3对对面两两互换:贡献 6x₂³
全班平均分对应 →Z(Cub)

5类旋转各贡献自己的循环结构,按出现频率加权求和再除以总人数——和算全班均分一个套路

Z(Cub)=124(x16+3x12x22+6x12x4+8x32+6x23)Z(\text{Cub}) = \tfrac{1}{24}\bigl(x_1^6 + 3x_1^2x_2^2 + 6x_1^2x_4 + 8x_3^2 + 6x_2^3\bigr)
13第 13 页 · 立方体的循环指标

应用Polya定理计算

循环指标已经写好,最后一步就是把颜色数代入,把染色方案总数算出来。

1
列出循环指标
把上一页得到的 Z(G) 完整写下来,cd 暂时保留
2
确定颜色数 k
明确有多少种颜色,比如 k=3 代表红蓝黄三色
3
代入 cd=k^d
把每个 cd 都换成 k 的 d 次方,多项式化为纯数字
4
算出最终方案数
计算多项式值再除以 |G|,得到本质不同的染色总数
14第 14 页 · 应用Polya定理计算

立方体染色自测

点击作答

立方体六个面用红、蓝两色染色,旋转后重合的视为同一种;按 Polya 计数,不同染色共有多少种?

15第 15 页 · 立方体染色自测

正四面体的旋转群

从 12 种旋转分三类型,逐层看每类对顶点的循环结构,最后合并为循环指标。

图解渲染中…
T24 个顶点任一与对面重心为轴, 转 120°/240°, 4×2=8 种T3对棱中点连线为轴, 转 180°, 四面体有 3 对对棱, 共 3 种P2顶点轴旋转时, 轴上顶点不动, 其余 3 个顶点循环移位P3棱中点轴不经过任何顶点, 4 个顶点恰好两两互换
16第 16 页 · 正四面体的旋转群

多面体对比表

对偶多面体群阶成对相等,但循环指标截然不同——这才是 Polya 染色差异的源头。

群阶 |G|
  • 四面体:12 ≅ A4
  • 立方 / 八面体:24 ≅ S4
  • 十二 / 二十面体:60 ≅ A5
  • 规律:对偶多面体群同构
循环指标特征
  • 四面体:含 3-轮换主导
  • 立方体:含 4-轮换主导
  • 十二面体:含 5-轮换主导
  • 规律:素数轮换长度对应面数
群阶告诉你「多少种旋转」,循环指标告诉你「每种旋转如何切染色点」——后者才是 Polya 计数核心。
17第 17 页 · 多面体对比表

着色约束条件

上页数出了立方体无约束染色方案。但现实常有附加条件——国旗对面同色、地图相邻异色。这些约束如何塞进 Polya 的统一框架?

Polya 的弹性
同一套循环指标,靠不同代入即可应对多种约束
邻面异色:色多项式代入
令 $x_k = c(c-1)\cdots(c-k+1)$,刻画相邻互斥
对面同色:合并复合面
把一对对面视为一个整体,问题从6面降到3面
多重约束叠加
分步处理再容斥,或用0/1矩阵的积和式
自助餐自由取餐对应 →约束染色计数

无约束每盘独立($x_i=c$),加了忌口/必选就换算法

PG(x1,x2,)约束代入N约束P_G(x_1,x_2,\ldots) \xrightarrow{\text{约束代入}} N_{\text{约束}}
18第 18 页 · 着色约束条件

权函数与颜色加权

上一节我们用循环指标算出了立方体三色染色的总数。但如果想精确知道「恰好2红1蓝」有多少种方案,就需要更细的工具——权函数。

颜色配变量
给每种颜色 c_i 配一个权重变量 w_i
染色的权重
一次染色的权重 = 各顶点颜色对应权重的乘积
变量替换
把循环指标里的 x_k 替换为 Σ w_i^k
提取分布
展开后 w₁ᵃw₂ᵇw₃ᶜ 的系数 = 用 a 个色1、b 个色2、c 个色3 的方案数
归一即总数
令所有 w_i = 1,权函数退化为普通染色总数
水果摊按品类称重对应 →颜色加权的染色计数

每个染色是一个果篮,权重对总斤数;提某斤数档位的系数 = 挑出该斤数的篮子数

ZG(w1,,wm)=1GgGk(iwik)ck(g)Z_G(w_1,\dots,w_m) = \frac{1}{|G|}\sum_{g\in G}\prod_k\Big(\sum_i w_i^k\Big)^{c_k(g)}
19第 19 页 · 权函数与颜色加权

Polya定理的边界

前面用Polya算自由着色数很顺——每个面独立选色、互不干涉。但真实问题常带约束:相邻面不能同色、某些配色被禁用。这时候直接套公式就会算错。

无限群不适用
SO(3)等连续旋转群元素无穷,求和前提被破坏
相邻约束要改写
地图染色要求相邻区域不同色,循环指标直接代入会高估
颜色禁配需处理
部分颜色组合不允许时,需用容斥原理修正
替代工具箱
邻接用色多项式,加权限制用Modified Polya枚举
万能量角器对应 →Polya定理

角度问题秒解,但拿去量面积就算错工具;Polya管自由着色,碰到约束得换方法

20第 20 页 · Polya定理的边界

课后思考

先合上笔记给自己五分钟,想不清楚再看下面。

1Burnside引理为何用「不动点平均」计数?「求和」与「求平均」差在哪?

参考答案求和会把每个等价类重复计入(重复次数=稳定它的群元素数);平均后每个等价类恰好记1次,这才是轨道数。

2正八面体与立方体在旋转对称性上有何关系?这让两者的Polya计算如何互相借鉴?

参考答案两者旋转群同构(都是S4,阶24)。顶点与面心互换后循环结构互换;只需把立方体循环指标中的变量含义切换,即得正八面体结果。

3若允许镜像反射(用全对称群O_h而非纯旋转群O),Polya定理的结论会如何变化?

参考答案群阶翻倍(24→48),新增反演相关循环类型,循环指标需重写。但Polya定理本身不变——换群就重算,思路完全通用。

21第 21 页 · 课后思考