当前课程知识点:组合数学 > 群 > Burnside引理 > 着色问题的等价类
我们刚才一直都在讲置换群
而置换群的对象无非就是一些文字
那么再回到我们本节课一开始
提出的问题
对应于这个正方形
我们顶点要用两种颜色
进行着色的话
会有多少种不同的方案
这时候其实我们仔细研究一下
如果这样一些图形摆在这里的话
它对应于不同的位置着不同的颜色
应该有多少个呢
实际上它看到的是一些图像
何为图像
就是像照片一样摆在这儿
我们看见的
它不能动
那么图像有多少个呢
我们每一个顶点都有两个选择
一共是4个顶点
所以是2的4次方种不同的图像
而我们要求什么
我们要求的是结构
结构对应的实际上叫做着色方案
也就是说如果我们经过外力
进行变换
比如说旋转翻转
原来这个图像能够通过变换
产生另外一个图像
那么这两个图像我们认为是等价的
我们要求什么
我们要求的就是一共有多少个
不同的等价类
那么这里面有几个概念
首先我们经过旋转以后
要求它的内部结构不发生变化
而所谓置换
什么叫做置换呢
我们说90度旋转
180度旋转
它就是一个置换
通过置换之后
它的图像就会变换成另外一个图像
那么我们现在研究的群
就应该是这些图像所构成的置换群
比如说我们给这所有的图像
16个图像都发生了一些标号
从1一直标到了16
这时候我们对应的一些外力的运作
比如说旋转90度
那么2号图像就变成了3号
3号就变成的4号
那么依次往下
这时候我们会发现
我们的图像作为一些元素
构成了置换群
而置换群又给我们作出了
很多的不同的等价类
那么我们要求的着色方案是什么呢
就应该是这些图像在
置换群中的作用下产生的等价类
有了这个概念之后我们来分析一下
实际上我们对应的这四个顶点的
着色问题
无非在求它一共有多少个等价类嘛
那么假如说我们现在考虑的置换
只考虑对应的是角度的旋转
而不考虑翻转
那这时候该怎么分析呢
首先我们要把置换拿出来
置换有多少个呢
我们可以考虑四种不同的旋转
构成的置换群包括它旋转0度
旋转0度
那么每一个图像还是
它的自己的样子
因此旋转0度的时候
它写出的置换就是单个单个的
一共是16个一阶循环
如果我说要旋转90度的话
旋转90度的时候
我们发现第一个图像旋转90度
还是它自己
而对应于2变成3
3变成4
4变成5
它们构成了一个四阶的循环
而6这个图像转的90度以后
就会变成7
因此6和7构成了一个2阶循环
同样8 9 10 11以及12 13 14 15
它们分别是4阶循环
接着16是个1阶循环
这就是对应的第二个置换
我们用P1来表示
那么接着旋转180度构成了
另外一个置换
对应于第一个元素
图像它是不变的
而对应于2
它转了180度
到了4
3转了180度
它到了5
而6转了180度还是它自己
7转了180度也还是它自己
依次类推
同样我们可以分析旋转270度的
270度的时候
我们用p3来表示的话
它就有这样一个对应的置换表示
我们来分析所有这样的置换
我们会发现
何为等价类
如果某一个置换能够把一个图像
转换成另外一个图像
那么这两个图像就属于同一个等价类
那么同时我们还会发现有一些
很有玄妙的地方
有一些置换
它虽然在这个图像上转了
但是没有发生任何的变化
比如说这里旋转180度
对于图像6来说
转了180度
还是它自己
没有发生任何的变化
因此我们会发现某些置换
它实际上对某一些图像
是不起作用的
我们给这种特别的置换取一个名字
叫做k不动置换类
英文呢 更形象
就叫stabilizer 把他stable住了
那什么意思呢
对应于G来说
它是1到n上的所有的置换
那么它有一个子群
这个子群也就是它对应于
k这个元素
有一部分的置换在k上
基本没有作用
那么我就称它为k不动置换类
用Zk来表示
举个简单的例子
有这样一个置换群
对应于G等于单位元e
以及1换2
3 4不动
3换4
1 2不动
以及1 2互换
3 4互换
这就是一个最基本的一个置换群
在这个置换群上我们来看
有哪些置换让1不动了
也就是z1等于什么
我们会发现当然单位元是不动的
对应于3和4互换
1和2不动
那么1在这里面也不会发生变化
因此对应于1的不动置换类呢
就包含两个元素
一个是e
一个是(3 4);对应于2它的
不动置换类同样也是e和(3 4)
而对应3呢
Z3也是e (1 2) z4和z3是相等的
这时候我们就分析了
什么叫做k不动置换类
那我们回头再来看对应于这样一个
四个顶点着色的问题
我们会发现它的不动置换类
会有什么样的规律呢
同样我们会看到对应于从p0 p1 p2 p3
这四个操作来说
对于1这样一个图像
谁会让它不动呢
其实我们发现1这个图像不论怎么转
还是它自己
因此它的不动置换类包含了p0 p1 p2 p3
四个元素都在内
而对于对应的下面的这个元素
比如说2来说
谁会让它不变呢
只有p0
对应于转90度
转180度和转270度
都会让它发生变化
因此对应的Z2就包含一个元素
也就是p0
而正好3 4 5它们对应的
不动置换类和2的不动置换类
是完全一样的
那么对应于6和7这样两个元素
我们也会发现Z6有谁呢
有转0度和转180度
因此就是p0和p2
对应于6和7
它的不动置换类也是完全一样的
那么这时候我们就会发现
是不是等价类和不动置换类之间
有一定的关系呢
那我们先看
我们要求的等价类
其实等价类是什么呢
回头还是这样一张图
我们会发现要求的等价类
好象是这个元素经过某些变换
就可以到达另外一个元素
依次它们好象构成了一个
围成的轨道一样
而每一个轨道就对应着一个等价类
因此其实等价类的英文更为形象
它就叫做Orbit
对应于一个等价类
就是一个经过置换的一个轨道
那么所谓等价类也就说对应于1 2 3
一直到n中的数k
如果存在某个置换使得k变成l的话
那么k和l属于同一个等价类
对应于作为的k对应的等价类
我们可以用Ek来表示
我们再看还是这道题
对应的4个顶点着色的话
我们会发现E1有谁呢
E1就是它自己
也就是一个元素
那么对应于E2有谁呢
我们会发现2 3 4 5这四个图像
位于一个轨道上
因此他们属于同一个等价类
那么接着6和7会发现
它们也是彼此可以通过置换达到的
所以6和7属于同一个等价类
那么E6等于E7
一共有两个元素
这时候我们发现
有一个很奇妙的地方
你会发现它的置换以后一共多少个
一共有4个
而对应于1这个元素
它自己的等价类只有一个
有就是E1的个数等于1
但是这时候它的不动置换类
有几个呢
正好4个
而对应于2 3 4 5
它在同一个轨道上一共有4个元素
也就是说E2它对应的个数等于4
而它的不动置换类有几个呢
有一个
再看
6和7
6和7属于同一个等价类
那么E6的个数等于2
而对应于不动置换类有几个呢
两个
2乘以2还等于4
这时冥冥之中是不是有一定的关系
我们会发现
有没有可能Ek的个数乘以Zk的个数
就直接等于置换的个数呢
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验