当前课程知识点:组合数学 > 群 > 置换群 > 置换群的应用
刚才我们所说的置换群基本上
都是在做文字上置换
但现实中我们想要处理的
往往是物体的转动
那么最常见的 实际上
就是正多边形的转动
比如说刚才我们说到了
可以是正方形进行转动
可以是三角形进行转动
而为了让它转动以后
还能够重合到原来的样子
我们一定是在一个
正凸多边形里面进行转动
何为正凸多边形呢
实际上我们知道
三角形它的正三角形
每个内角 边都是一样的
而正方形对应的
内角以及边也都是一样的
因此叫正多边形实际上是
在凸多边形中
各个内角相等
而且边也相等的这样的
多边形才叫正多边形
对应于有多少条边
就可以是正多边形的多少个边
多少个角
我们有正三角形
正四边形 正五边形
一直到正多边形
七边形 八边形都有
那么只要是它的每一个内角把所有
的360度去整分就可以了
但是同样的我们会想到
我们怎么样来表示它对应的转动呢
就拿我们说到的正四边形来看
这里正四边形我们可以说它的转动
是根据顶角来进行转动的
也就是1 2 3 4转
变化成4 1 2 3等等
或者我们甚至可以拿边
来考虑它的转动
如果用abcd来表示四个边的话
可以看到转动之后
它的边也会发生变化
那我们先拿它的顶点为例
对于1 2 3 4这样4个顶点
它有什么样的一个转动群的表示呢
首先我们要看
先以转动为例
那么转动它有多少个角度
首先它转动0度的话
也就是不动
那么1还是1
2还是2
3还是3
4还是4
如果我转动90度呢
我们转动90度就会发现
如果是逆时针旋转
1变4
4变3
3变2
2变1
同样我们可以转动180度
以及转动270
所以对应的转动我们
一共有4个不同的置换
分别可以写成
ρ1 ρ2 ρ3 ρ4
那么同样的如果我们这样的
一个转动不仅仅是在一个平面上
我们还允许它翻转的话
那么这个群里面的置换会更多一些
比如说我们按照竖方向的
这样一个对称轴来看的话
会发现1 2点进行交换
而3 4点进行交换
同样我们还有横着一条对角线
另外我们斜也可以有一条对角线
这时候1 3点是固定的
2 4发生翻转
同样我们还有这样一个对应于
1 3和2 4两条斜对角线
因此根据它们对称轴
我们一共有4种不同的翻转
这时候我们就会发现
如果以顶点来考虑它的转动群的话
对应于这样一个正方形的话
我们的转动群可以包含有
4个不同的置换
当然我们有时候也会考虑说
如果我们不允许翻转的时候
只在旋转的角度下
那么它是包含4个置换的
刚才我们说的是平面上的正多边形
但是有时候我们是在
一个三维空间里进行转动
比如说我们可以说一个立方体
正立方体它也可以在
三维空间中进行旋转
要让它最后旋转以后
还能是原来位置的话
它必须要保证它对应的
顶角边面都是一样的
而对应于我们又知道
如果我们不是一个以方形为面
我们也许可以拿
三角形为面做一个正的多边形
这里我们看到正的
多面体可以有一个正四面体
那么它就像一个金字塔一样的形状
这时候我们就有一个定理来帮助
我们去求解所有的正多面体的形状
有一个欧拉定理
它表示的是说对应于
任何一个凸多面体
它的顶点个数加上它的面的个数
减去棱的个数
刚好等于2
这就是对应于一个凸多面体
它的顶点 棱和面之间的关系
而有了这样的关系
我们就能分析一下
全世界到底有多少个正凸多面体呢
大家想到这个问题就会觉得
应该不少吧
你想正多边形那么多个呢
但是现实中我们的
正多面体少的可怜
全世界所有的正多面体拿过来
一共只有五种
它们分别就是正四面体
正八面体 正六面体
正十二面体和正二十面体
其他情况都不可能构成
一个正的凸多面体了
就这五种正的多面体
它们之间其实还有一定的对应关系
我们会发现比如说我们把这样一个
正六面体它们的顶点 中心
对应的连接起来
每一个面上它们的
中心进行相连以后
我们实际上可以得到
它里面内嵌了一个正八面体
所以我们会发现实际上正六面体和
正八面体之间是一个对偶关系
同样的正十二面体和正二十面体
它们之间也是一个对偶关系
就只有这五种对应的凸正多面体
我们来定义它们的转动群
我们知道对于这样一个立方体
我们完全可以通过旋转
让它产生不同的变换
而对应于每一个旋转变换呢
我们都可以看作一个置换
因此把这样的置换集合在一起
它就构成了一个对应的
正多面体的一个转动群
也就被称为多面体群
这里我们举个例子
我们知道最简单的
正四面体来看一下
如果我们考虑的是顶点的转动的话
正四面体它们顶点分别是A B C D
这时候我们来看一下
它的正四面体群长什么样子
首先不动肯定是一个置换
也就是A点 B点 C点 D点
仍然保持自己
那么对应的它可以转动
它的转动是什么样子呢
我可以保持a点不动
下面的三个顶点发生
彼此之间的交换
那它们进行旋转的
时候角度有多少呢
它可以是正负120度
所以我们会发现
A点不动
可以是B D C产生一个循环
或者是B C D产生一个循环
同样A点可以作为不动顶点
B点C点D点都可以作为不动顶点
因此对应于我们用面心和
对面的顶点构成了轴进行旋转的话
它可以产生这样四种不同的置换
所以我们会发现实际上正四面体
它的转动群就是包含了
首先一个是不动置换
另外的呢就是顶点对面心
进行的旋转置换
其中一共有4个顶点
两个方向
因此是8个不同的循环表示
除了这个直观的对应的旋转之外
我们看还有没有其他的
对应的操作呢
我们会发现
实际上在这个正四面体中
我们完全可以做一个
穿过它其中的对称轴
比如说我们这里对应的
这样AB这条边
我们上面取它的中点
它对面的那条边也就是CD
它的中点如果将
两个中点进行相连的话
它可以沿着这样一个轴
进行一个翻转操作
那么它一共有多少个这样的
对称轴呢
因为它们两两可以进行对称
所以会发现实际上一共有
3个这样的对称轴
这个三个对称轴对应的
每一个它的置换长什么样子呢
我们会发现
这样一个对称轴实际上是
AB进行互换
CD进行互换
那么同样如果换了
另外一条对称轴的话
可以做到AC进行互换
而BD进行互换
另外一个是AD进行互换
BC进行互换
那么这就发现了除了
刚才的不动旋转
以及对应的面心和
顶点进行旋转之外
我们还有一个它的
内部对称轴进行的翻转
一共有多少个这样的转动和翻转呢
一共有12个
因此这12个置换就构成了
所谓的正四面体的转动群
分别可以写成e (BCD) (BDC)
依次类推
那我们会发现
这样一个置换中
一共有12个不同的置换元素
它对应的实际上就应该是
偶置换an构成了一个交错群
刚才我们看到了对于正四面体来说
它实际上是有12个置换
构成了它对应的置换群
也就是正四面体群
那么对应的我们会说
如果是立方体呢
正六边形呢
正六边形如果大家仔细研究一下
会发现它的对应的旋转和翻转
一共有24个不同的置换
而且这24个不同的置换实际上
对应的就是全排列的结果
它就和对应的四次对称群
s4是同构的
而且同时呢对于正八面体和
正六面体是对偶的关系
因为它们实际上对应的都是
s4这个对称群
那么同学可以作为练习
下面仔细思考一下正四面体和
正八面体的转动群长什么样子
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验