我们刚才说到了a已经不需要
用两排来表示一个置换了
我们可以把它写成一串的循环表示
但是这也许还不够
我们再想
是不是有可能有更加
不一样的表示方法呢
我们来看这个例子
比如说1 2 3要换成2 3 1
它实际上可以看成是1 2先互换
那这时候我可以看作是
它1 2 3换成了2 1 3
然后再运算1 2 3 3 2 1
这时候回头再看
这两个不同的置换
分别是什么
第一个置换就是1和2互换
3不动
而第二个置换实际上是2不动
1 3互换
那我可以把它写成两个循环相乘
这两个循环比较特别的是
每个循环中只有两个元素
意味着是两个元素进行对换
这时候我们就把一个1 2 3换成
2 3 1转换成了两个对换的乘积
也就是1 2互换乘以1 3互换
所以我们有这样一个想法
也许我们对应于任何一个循环
也可以把它写成若干个对换的乘积
那么在这里我们就可以
来给它一个证明
比如说我们已经证明了1 2
一直到n减1这样一个循环
是可以写成1换2
1换3
再依次类推的
那么如果又来了
想要把这个置换变得更长一点的
那么我想证明1换2
2换3
一直换到n
是不是可以写成1换2
1换3
一直累乘到1换n呢
我们把它分成两个部分
首先1换2换3
一直换到部n减1
最后再来一个置换
1换n
它们两个进行相乘的话
会有什么样的结果呢
我们知道第一个置换实际上就是
可以写成若干个对应的置换
表示成1 2 3
一直换到n减1
下面变成了2 3 4一直换到了1
后面是一个1换n的东西
那其他元素全部都保持
只是1换n
n换1
对应于两个要进行相乘
我们把它都要做成n阶的置换
第一个置换差了一个(n,n)
第二个置换中间这些元素
全部保留在一起
那这时候我们把
这样两个置换进行相乘以后
发现它变成了什么呢
它实际上就变成了1换2
2换3
依次往下
最后n减1换n
n换1
这个置换实际上不也就是
从1一直到换到了n嘛
所以我们可以看到
通过这样的地推方式
我们就可以证明了任何一个置换
都可以把它写成若干个对换的乘积
当然这些对换的起点是谁呢
是不定的
所以对应于每一个分解形式
大可以有不同的表示方法
我可以对应于1换2
2换3
一直换到n
从1开始
也可以把它们从2开始
写成2换3
2换4
依次类推2换n
2换1
对应于刚才我们看到了
对于不同的起点
它的循环可以有不同的表示
那么它们对应拆分的
个数是一样的吗
其实也不一定
比如说刚才我们看到了1 2 3
可以把它拆分成1 2乘以1 3
当然呢我还可以再长一点
它同样等于1 2乘以3 3
再乘以1 3 3 1
那意味着实际上对应于
不同的对换表示
它表示的可能是同一个置换
但是有一些东西是固定的
比如说任何一个置换
它要拆分成若干个对换的乘积
它的奇偶性是确定的
为什么呢
我们会想其实对换是什么
我们完全可以想对换也许
就是一种做出来的
带着符号的东西
比如说我要l和k进行互换
接着呢依次我们进行互换的时候
就可以认为l减k和k减l进行互换
这时候比如说我设计了一个函数
它把对应的取出l和k
它们对应的函数变成若干个
xl hk之间差值的累乘
那我们会发现
如果换一次的话
它的符号就会发生变化
对应于这样的换位
如果要产生同样的效果的话
那么这样换位的个数奇偶性
肯定是一致的
因此我们说对于对换
每次都要改变这个函数的符号
那我这样的对换要达到同样的效果
它的奇偶性是唯一的
这就把所有的置换分成了两类
一类叫做奇置换
一类叫做偶置换
也就是有的置换它就是
能够拆分成奇数个对换的乘积
比如说像这个
它对应的是
1 2 5 3 7 4 6
这里面有多少个对换呢
它一共有3个对换
因此它是个奇置换
而对应于这样一个置换
1还是1
2还是2
所有的元素
5个元素全部都自己换自己的话
这时候没有对换
它是一个偶置换
而奇置换和偶置换之间是
永远平行的关系
不能相互相等
这时候我们就用这样的
思想来解决一道问题
也就是数字华容道
我们可以看有这样一个格子
它是一个4乘4的格子
里面放置了从0一直到15
那么它可以通过对换
来表示来产生另外一个结果
比如说我们看到
这样一个对应的0到15的排列
可以通过一些对换
我们产生像这样一个新的图形
那么我们就问了一个问题了
它是可以通过两两对换来产生的
如果我规定它有一个
华容道的规则呢
也就是说每次它的变换都是0
和它相邻的位置进行交换的话
那么我们问在这个规则下
左边这张图可不可以
生成到右边这张图来
大家思考一下
我们来分析一下
左右两张图
首先我们不考虑这个0
和相邻位置进行交换这个约束
它是一个什么样的置换呢
我们会发现
它们的置换可以写成这样一般形式
其中包含了多少个两两对换
一共有7个
那这时候我们就知道了
要想从左图变换成右图的话
它需要经历一个奇置换
但是我们回头看
对应于我们有要求如果每次的
变换都是0和它的相应位置
进行变换的话
那么会发现什么事情
我们会发现
0其实它的位置没有发生变化
那么就可以想一下
它有可能就是和
上面两个两个进行交换
然后再回来两个两个
两个进行交换
那它必然是走了偶数步
才能够从原来的位置
又回到了原来的位置
因为我们会发现
加了这个0和它相邻位置
进行交换约束之后
我们这两张图实际上必须是
经过偶置换才可以得到的
但是对于其他的元素变换
我们知道它是一个奇置换
因此奇置换永远都不可能
变成一个偶置换
因此如果限制任何一个变动
都是0和相邻位置进行交换的话
这时候是不可能
从左边图生成右边这张图的
既然我们知道了所有的
置换可以进行分类
有奇置换和偶置换
那么我们就可以把所有的
偶置换拿出来
它实际上构成了所有的对称群
sn中间的一个子群
我们给它起了名字称为是交错群
一般就用an来表示
为什么说它构成了一个群呢
可以想象它仍然是具有封闭型的
因为偶置换和偶置换进行
相乘必然还是偶置换
结合律本来置换乘法就满足
而单位元正好对应于所有的
全部元素都不动的情况下
它的置换是0次
是个偶置换
而且它的逆元呢
对应于i换k
k换i
所以它们的逆元也仍然是
一个偶置换
这就说明了对应于所有的
偶置换构成的这样一个集合
可以产生一个新的群
我们用an来表示
那an元素有多少个呢
对应于我们知道
所有的sn中包括an
以及对应的其他的奇置换
an加上bn
也就是奇置换和偶置换之和的话
就应该等于n的阶乘
而我们知道一个奇置换
它再乘以一个兑换的话
就构成了偶置换
所以呢对应于奇置换的个数
肯定要小于等于偶置换的个数
而同时一个偶置换乘以
一个对换的话
又得到了奇置换
因此我们证明了奇置换和
偶置换之间是有一个一一对应关系
因此对应于an的个数和
pn的个数是相等的
那么在这样一个交错群中
它的元素个数就应该是
所有全排列个数除以2
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验