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

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

对换在线视频

对换

下一节:置换群的应用

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

对换课程教案、知识点、字幕

我们刚才说到了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算法

--程序支持与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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

对换笔记与讨论

也许你还感兴趣的课程:

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