我们刚才介绍了置换
可以用群来表示
那么对于每个置换我们
一般都会用两行这样的形式来表示
比如说对应于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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验