当前课程知识点:组合数学 > 群 > Burnside引理 > Burnside引理
刚才我们讲了有关置换群中
有非常多不同的概念
我们现在先回顾一下
比如说对应于一个有限群
我们用G来表示
那么它G中的元素就可以写ai
这里我举一个简单的例子
就是我们刚才看到的
对应于它里面一共有4个置换
第一个置换是单位元e
也就是1元素 2元素 3元素
4元素全部都不动
另外有一个置换是1 2互换
3 4不动
还有一个置换是1 2不动
3 4互换
最后一个置换是1 2互换
3 4互换
就是这样一个置换群
我们来分析一下相关的概念
首先对应于每一个置换
它可以用循环来表示
它有多少个
多大的循环
我们就把它记为一个共轭类的样子
那么这里面我们用ck(ai)表示
k阶循环有几个
比如说这里对应于第一个单位元
它里面就是1 2 3 4
一共有4个1阶循环
那我们写成样子
可以写成1阶循环有4个
对应于另外一个
比如说我们来看它最后一个置换
1 2互换
3 4互换
这时候2阶循环有两个
也就是c2(a4)等于2
那么也可以写成2阶循环有两个
那么还有一个概念是一个
非常新颖的概念
也叫k不动置换类
对应它的含义是什么
对应于这样几个置换
它作用在第一个元素中
能让第一个元素始终还是自己的
这一些置换统一在一起
就被为是1不动置换类
也就是Z1等于什么
这里单位元当然让1不动
另外3 4互换
1 2不动
这个置换也让1不动了
因此Z1就等于e (34)
还有一个等价类
等价类意思是说对于这样一个元素
它的等价类标志着是说
我如果通过某一个置换
能够到另外一个置换的话
我俩就应该是一个等价类
这时候我们会发现
1可以动作置换变成2
因此1和2属于同一个等价类
E1等于E2等于(1 2)
而对应于3可以变成4
因此E3等于E4等于(3 4)
而通过上一节的分析
我们有了这样的一个猜想
对应于等价类的个数
乘以对应的不动置换类的个数
它们的乘积之积是不是就等于
置换的个数呢
我们刚才是在对应的一个正方形的
四个顶点进行着色的这样一个
置换中去分析到的
可能存在这样的一个现象
其实这个现象就是所谓的
一个轨道定理
用英文来说就是Orbit-stabilizer定理
我们下面给它一个完整的证明
下面呢我们来证明一下这个定理
这个定理的描述是这样的
假设G是1到n上的一个置换群
那么Ek就表示1到n在G的作用下
包含k的等价类
Ek呢是k不动置换类
我们就有这样一个猜测
就是Ek的个数乘以Zk的个数
恰巧等于置换的个数
我们首先证明一下
我们假设Ek它里面有多少个元素呢
假设Ek里面就正好有l个元素
那么既然说是k元素的等价类
我们就可以设Ek中
第一个元素就是k
其他的元素呢分别是a2 a3
一直到al
那么这时候我们会发现
为什么它们属于同一个等价类呢
因为这个k元素a1经过某一个置换
就可以变到后面的任何一个元素
因此k作为a1它可以在pi的作用下
把它变成ai
有了这样一个思想以后
我们来证明一下是不是存在
Ek的个数乘以zk的个数等于g
首先我们把所有的pi都归纳出来
做成一个集合大P
其中包含了p1 p2一直到pl
那么我们就可以做出来一些
置换的子集
Gi也就是对应于原来置换中的
若干个子集
它表示的就是用k的不动置换类
乘以对应的pi
那这个时候我们发现
Zk既然是使k不变的
而pi是指的是将元素a1变成了ai
那么对应于元素k
在Zkpi的作用下
就将变成ai
那意味着实际上Gi就应该是
G的某一些子集分解
而对应于不同的i
比如说两个i和j是不相同的
那么它对应的这样的运算
置换运算也应该不同
因此gi交上gj应该是空集
这时候我们就发现
既然他们是属于G的
那么G1加G2一直加Gl
就应该仍然是G的一个子集
而另一个方面
我们会发现任何一个p
都应该是属于G这个置换类的
而k也就是a1经过了pj运算
变成了aj
同样可以经过pj的逆变回到k
那意味着k经过了pj乘以pj逆
又变回了k
意味着pj和pj逆它应该属于
k不动置换类
那么两边如果都在乘以一个pj
我们会发现左边就变成了
对应的某一个小的pj的运算
而这边呢就变成了Ek乘以pj
因此左边对应于p元素来说
这样的置换它应该属于
Ekpj的 而Ekpj对应的
我们刚才假设它应该等于Gj
那p对应的实际上是所有的置换
而这边又对应的是对应的子集
这时候我们发现G对应的是左边
而这边j从1一直取到l
因此G应该是属于G1加G2一直加到Gl
这两个式子我们会发现
两个式子一联立以后
就会发现G就等于G1加G2
一直加上Gl
而这个时候我们发现
每一个等于什么呢
G的个数划分成了G1的个数
加G2的个数
一直加到Gl的个数
而G1根据定义在这里
它就应该等于Zk乘以p1
对应于后面G2应该等于Zk乘以p2
一直累加到Zk乘以pl
而对应的每一项我们知道
它的个数就应该是一共有
l项不同的值
而每一项的个数应该是相等的
因此它的个数就应该等于
Zk的个数乘以l的个数
也就是在这里一共有多少个等价类
那么这里l的个数就相当于Ek的个数
因此G的个数就等于Zk的个数
乘以Ek的个数
我们就证明了对应的轨道定理
有了这个定理以后
我们看一个简单的例子
对于还是我们刚才一直提到的
对应于一个运算来说
置换
它有e (12) (34) (12)(34)
这时候它的不动类个数
也就是对应于a1来说
它的对应于1阶置换一共有4个
对应于2阶置换一共有1个
这时候我们想去发现一下
对应于1阶循环它的个数和
k不动置换类
有没有一定的联系呢
我们再依次看
对应于a3来说
它的1阶循环有两个
对应于4来说
它的一阶循环有0个
我们这时候就会发现
在这个例子里面
E1等于E2
就是包含1和2元素
3和4它们等价类也相同
就是3 4这样的集合
那么我们设计了一个新的表格
在这个表格中呢
我们每一行对应的都是一个置换
而对应的这里面每一个纵列
对应的就是一个元素
我们在每一个格子中间呢
取了一个这样的式子
我们用Sjk表示第j行第k列
它的运算可以通过
如果说对应于这个元素
在这个置换中它没有发生变化的话
那么我们就写1
如果这个元素在这个置换中发生了变化
我们就写0
依次类推
我们就可以列出这样一个表格
我们会发现
这个表格的每一行这么去数的话
实际上就在看对应于这样一个置换
有多少个元素是不变的
也就是1阶循环有几个
对应的就是c1aj
而竖着看呢
我们会发现如果竖着去处理看的话
就相当于1元素有多少个置换
让它不动
也就是k不动置换类的概念
那么如果把横加在一起
最终得到的结果和竖着列加在一起
最终得到的结果它们的结果
应该是相同的
这时候我们发现
对应这一行求列
它得到的是c1aj
对于第k列求和
它得到的是Zk
而所有元素之和就相当于要么是
Zk从1到n进行累加
要么就是对应于不同的置换c1aj
j从1到g
那么这时候它们的个数是相等的
有了这个概念以后
我们会发现
我们去求等价类也许不需要去找
k不动置换类了
我们是不是可以直接用
这样1阶循环有几个来直接计算呢
那么在这里我们就可以用到
Ek乘以Zk等于G这个概念
同样刚才只是拿一个特殊的例子来看了
我们对于更一般的情况下
我们都可以对应于置换a1一直到ag
来看它是否使某些元素发生了变化
而同样我们得到了一个和值的概念
是对应于所有k不动置换类的个数
的累加和
等于所有置换中1阶循环个数的累加和
有了这个概念之后
我们来计算对于等价类该如何求
假设1到n这么多元素
被分成了l个等价类的话
那么1到n就可以写成Ea1加Ea2 (发音错误)
一直加到Eal
这个时候我们有两个式子
一个是我们说的轨道定理
也就是Ek的个数乘以Zk的个数
等于整个置换的个数
另外一个通过表格的设计
我们知道了所有的k不动置换类的
k从1到n的累加和
等于所有置换的
对应的1阶循环之和
好
有了这个概念
我们来看一下
假如说i和j属于同一个等价类的话
它们在同一个轨道上
因为Ei是等于Ej的
Ei的个数自然等于Ej的个数
而这个时候我们又知道
Ei乘以Zi的个数
就应该等于置换的个数
因此对应于它们
因为等价类里面的个数是相同的
那么对应的不动置换类的个数
也肯定相同
因此Zi的个数等于Zj的个数
接着往下
又因为每个等价类中
我们知道所有的Zi的累加和
就应该等于对应于有多少个等价类
再乘以它们对应的里面的
k不动置换类的个数
而这个的个数我们一共有
l个等价类
把它提出来所有的
按照等价类把Zk进行分类的话
就相当于对应于从j
从1到l
而每一个i属于某一个等价类
来求它的Zi的个数之和
这里面每一个都是相等的
因此它们的个数就相当于
Eaj乘以Zaj
这个式子我们看
是不是刚好等于我们刚才说到的
轨道定理里面
它们的和累乘之和就等于一个常数
也就是置换的个数
那么这里面它就应该等于
所有置换的个数
而累加起来就是j从1到l
那么这就相当于是一共有
l个常数进行相加了
那我们自然可以求得l等于几了
那么l乘以G的个数
等于∑k从1到n所有的
k不动置换类的个数
那么l的个数自然就等所有的
k动置换类的个数
除以我们知道的置换的个数
当然我们还知道
k不动置换类不好找
但是k不动置换类在这里面
它的累加和就相当于所有的
1阶循环的个数
那么它自然就等于我们看到了
有置换之后
就去找所有置换对应的
1阶循环个数
然后再去除以它对应的
所有的置换
答案就是等价类的个数
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验