当前课程知识点:组合数学 >  群 >  Burnside引理 >  Burnside引理

返回《组合数学》慕课在线视频课程列表

Burnside引理在线视频

Burnside引理

下一节: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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

Burnside引理笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。