当前课程知识点:组合数学 >  群 >  置换群 >  共轭类

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

共轭类在线视频

共轭类

下一节:对换

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

共轭类课程教案、知识点、字幕

我们刚才介绍了置换

可以用群来表示

那么对于每个置换我们

一般都会用两行这样的形式来表示

比如说对应于1 2 3 4

如果我们旋转90度的话

它变成了4 1 2 3

一般如果用置换来表示的话

我们会写

1 2 3 4 4 1 2 3

但是这时候我们会发现

其实对应于每一个数字

它似乎都可以连成串儿

比如说1换成了4

4又换成了3

接着依次往下

我们就可以把它写成一个循环

1 4 3 2再回到1

那么这时候我们就会想

置换也许不需要写成两行的形式了

只要循环就可以表示了

比如说对应于a1 a2一直到

an这样一个循环

它可以表示为a1换成a2

a2再换成a3

依次往复

接着等于an

最终an再换回a1

这就是置换的循环表示

我们举一个直接的例子

比如说1 2 3 4 5

要换成5 2 3 1 4

这时候怎么用循环来表示它呢

我们先从1开始

1到了5

5又到了4

这里面4又回到了1

这就是一个循环

1 5 4来表示

而剩下的两个元素呢

2还是2

3还是3

因此整个一个置换它由

三个循环来组成

这就意味着对应于一个置换

它可以有若干个循环表示进行相乘

那么每一个循环我们来

定义它的阶数

对于a1 a2一直到an

这个循环里面包含了n个元素

我们就定义它是个n阶循环

当然这个循环既然是个循环的话

那从哪儿开始算起头呢

无所谓

我可以认为是1变成了5

5又变成了4

4又变成了1

我也可以从5开始

5变4

4变1

1变5

因此对应于a1 a2一直到

an这样一个循环

它一共有n种不同的起始点

就对应着有n种不同的表示方法

那么两个循环没有共同的文字

也就是说它们相互之间

没有交的部分的话

它们之间的顺序也可以发生变化

比如说对应的一开始

我们把它划分成了

1 5 4一个循环

2一个循环

3一个循环

我们同样也可以让2在最前面

2单独地循环

再乘以1 5 4这个循环

再乘以3

同样都是一样的循环

那么对应于一个n阶循环

比如说a1 a2一直到an

它如果一直自己和自己运算的话

那么它经过n次的应算

也就是p的n次方

就会把它变成单位元

对应于比如说部分举个例子

循环1 2 3

1换2

2换3

3换回1

这时候如果我们

比它两次进行运算的话

比如说p的平方

它变出来就是3 2 1

而我再和它再运算一次

p的3次方就变成了1是自己

2是自己

3是自己

因此我们会发现

对应于一个循环

它的阶数就代表了它的多少次

直接自己和自己的运算

就可以得到单位元

既然有了这样的循环的表示

我们会发现

任何一个置换都可以表示成

若干个不相交循环的乘积

因为我们可以不停地从一个点出发

找它覆盖的所有循环

接着再从剩下的元素出发

再去找不同的循环

因此我们这时候就发现置换

不再需要两两这样行的对应形式了

我们可以通过循环的表示来进行

更为有效而直观的表示方法

在不同的循环表示中

有可能有一些循环长的样子非常像

因此我们给了一个新的概念

也就叫做共轭类

对应于我们任何一个置换

我们都可以用若干个不相交的

循环乘起来表示出来

那这些循环的长度是多少呢

我们举个例子

比如说对应于这样一个置换

它首先是a1 a2

一直循环到ak1

第一个循环中有k1个元素

第二个循环中

b1 b2一直到bk2

有k2个元素

依此类推

这时候每一个循环所有的个数之和

刚好就应该等于

所有元素的之和等于n

那这个时候我们就可以通过

循环的不同的长度

来表示每一个置换的结果

我们实际上就可以用k个元素

它一共有多少个这样的 k阶循环

用ck来表示

这样就表示出了一类的格式

我们称之为同样格式的

就叫做共轭类

那么对应的每一个置换我们都可以

写成1阶循环有c1个

2阶循环有c2个

一直到也许n阶循环有cn个

那么对应的我们会发现其实

所有元素的个数加到一起呢

就相当于它对应的每一个

循环乘以它的个数之和

这就是共轭类的概念

那么对应于我们举个例子S4来看

所有的4阶乘的全排列全部在这里

那么它们长的格式一样的有几个呢

比如说我们认为对应于

S4中取相应的

比如说2阶乘有两个的这样共轭类

那么长什么样子

我们可以看到

一共有3个

1 2一循环

3 4一循环

1 3一循环

2 4一循环

以及1 4一循环

2 3一循环

这就是对应的写成2阶循环

有2个的共轭类

同样呢

我们要找1阶循环有1个

而3阶循环有1个的共轭类

一共有这样8个

当然对于1阶循环

我们意味着它自己就变成自己

因此我们在这里面可以省略掉

也就是这里的

1 2 3代表的实际上

有一个3阶循环是1换2

2换3

3换1

另外还有一个1阶循环

也就是4换它自己

这时候我们就了解了

其实对应于每一个置换呢

它是具有一定的格式的

相同格式情况下

我们称之为是共轭类

我们刚才给大家介绍了

对应于一个置换

我们可以用循环来表示

那么循环怎么帮助

我们大家来洗牌呢

我们给大家举个例子

这里面我们有一副牌

我们把大王小王去掉了以后

剩下了52张

52张牌我们一分为二

我们的洗牌规则是很严格的

也就是说左边有26张牌

右边也有26张牌

它们按顺序排好了

这个时候我要求

每次洗牌从左边出一张牌

右边又落上另一张牌

依次往复左边右边

之后呢我们就洗出来了一副牌

那么按照这样的洗牌规则

请问我洗多少次之后

这副牌牌又恢复了原样呢

那么现在我们来形式化的

分析一下这个洗牌问题

它应该是52张牌嘛

我们先不考虑红桃黑桃了

我们就用1 2 3 4 5

一直到52来代表它

那它发生了一个什么样的变化呢

实际上对应于第一张牌

应该是1号牌

而第二张牌应该是谁呢

第二张牌应该是我右手边的牌

而它的序号是从27开始的

接着第三张牌应该是左边的2号牌

依次往上

最后呢我们的最后就把对应的

这里26号牌和

最后的一张52号牌放在上面

那如果我们把位置按照

1 2 3一直52排出来

会发现它对应于位置有一个变换

也就是我们有这样的一个公式

对应于你i这个位置

应该放几号牌呢

第一号位置它放的是1号牌

而第二号位置它放的是27号牌

第三号位置它放的是2号牌

我们发现实际上它是按照奇偶来的

对应于i等于1 3 5的时候

它应该等于i加1除以2

那么对应于它得

2 4 6 7 8的

偶数位置的时候

它应该等于i除以2加上26

这实际上构成了一种置换

而这个置换我们该如何来表示呢

我们会发现

我们照样可以把它写成循环的形式

而这个循环我们会发现

1还是1

但是呢对应的第二号位置

它应该变成了27

2换27

依次往后

再往后

我把它所有的置换

按照循环的形式写下来了

这时候我们看一下它的结构

我们知道对应于循环

如果几阶循环就意味着

我运算几次的话

它就可以变成单位元

那这里最大的是几阶循环呢

我们发现这里面最大的

实际上是8阶循环

那意味着什么

也就是说我按照这样的洗牌规则

只需要洗8次

最终它就可以恢复原样了

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

共轭类笔记与讨论

也许你还感兴趣的课程:

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