当前课程知识点:组合数学 >  Polya定理 >  Burnside引理的困境 >  Burnside引理的困境(1)

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

Burnside引理的困境(1)在线视频

Burnside引理的困境(1)

下一节:Burnside引理的困境(2)

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

Burnside引理的困境(1)课程教案、知识点、字幕

上节课

我们给大家介绍了一个新的概念

也就是群

什么是群

实际上群是包含一个集合

以及定义在集合上的二元运算

如果它满足封闭性 结合律

有单位元 有逆元的话

那么我就称它为群

说起来群的概念实在太抽象了

但是它又和我们的现实

有着密切的关系

比如说上节课

我们给大家介绍了转动群

我们就拿一个

正方形的顶点着色来看

如果只考虑它旋转多少角度的话

它的转动群应该是什么样子呢

我们首先来想

如果正方形顶点进行着色的时候

它要转动

它一共会有多少种不同的图象呢

在这里我们一下看到

如果全部都着蓝色

或者全部都着红色

或者中间有蓝 有红

这时候所有的图象

就必然是这16个

在这16个我们怎么来看转动以后

发生了什么样的变化呢

首先我们先看一个置换

第一个置换很简单

就是不动

意味着我转零度

转零度的时候

任何图象还是它自己

所以这时候我们写

置换群的话全部是一阶循环

一共有16个

接着往下我们会觉得

可以让它旋转90度

比如说顺时针旋转90度

我们会发现第一个图象

它四个顶点全部都是蓝的

这时候它转多少

仍然是它自己

所以1还是1

一阶循环是1

接着我们会发现第二个图象

第三个图象 第四个图象

第五个图象

它们转90度

就分别可以从二到三

从三到四 从四还可以到五

因为我们看到了四阶循环

依次往下

同样类似

如果我们转180度呢

转180度的时候我们会发现

当然第一个图象还是它自己

但是现在我们看到了

第6个图象可以转动

180度以后变成第6个图象

第7个图象转动180度

又回到第7个图象

因此我们可以写对应

180度旋转它的置换群是这样的

那么接着还有一个角度

旋转270度呢 旋转270度

和刚才是基本上一一对应的

这时候我们就写出了所有关于

正方形顶点着色对应的置换群

基于刚才的转动群

我们实际上介绍了

一个关于着色的计数法则

被称为 伯恩塞德引理

Burnside引理是说我有一个置换群

那么可以是a1

a2一直到ag

也就是说在这里面

特的置换个数是小g个

在这个情况下

我们就来定义

在转动置换作用下

我们等价类的个数是怎么计算的

其是在这里有用到一个因素

我们被称为是C1f

来表示对f这个置换

它里面有多少一阶循环

这个一阶循环有时候

也被称为是不动点

有这样的概念之后

我们就说定价类的计算

就直接可以套用公式

等价类个数为l的话

就直接等于所有对应

置换一阶循环之和

除以对应的置换个数

那么我们再来看刚才的那个问题

要去计算所有的对应

16个图象里面等价类有多少个

我们就可以依次地看它每个置换

每个置换中一共有多少

各对应的一阶循环呢

我们先看不动

不动a1这个置换中

它的所有的元素都是不动点

也就是全部都是一阶循环

一共有16个一阶循环

对应的下面转90度

只有1和16不动

对应于下面转180度

它有4个不动的一阶循环

270度有两个

这时候我们可以把

所有的C1(f)全部计算出来

另外还有一个我们要把

所有C1(f)之和

除以所有的置换个数

而置换个数一共多少个呢

这里面无非就是0度 90度

270度 180度

一共有4个

所以套用伯恩塞德引理直接就

可以算出我们对应l的个数

就等于16加2加

4加2除以4

答案就是6

这时候我们再回头看

我们一开始说到的

黑板上的排列组合

我如果用6种颜色

去给立方体图色的话

要求每个面的颜色都不一样

这时候有多少种不同的着色方案

当时我们是说可以用

排列组合的方案来计算

那么用伯恩塞德引理

可不可以直接做呢

我们这时候就看一下

对应于这样一个立方体

它实际上是可以发生转动的

那么它同样对应的有一个置换群

它一共应该在什么样的图象

集合里面做置换群呢

我们会发现每一个面上不同的

着色方案就对应一种图象

一共有多少个不同的图象呢

这里面每个面打开的话

就构成了这样的图案

实际上每个面对应的

就是一种排列

因此

所有的图象方案数就是6的阶乘

我们要找什么

我们要找在6个阶乘内

立方体进行旋转的话

会有多少个等价类

这时候回头看

在伯恩塞德引理中

我们如果想计算等价类

首先要知道我有多少

个对应的置换

同样我们还需要知道对应于

每一个置换

它一共有多少个不动点

何为不动点

当然如果你把置换都写的出来

我对应一看

只要是一阶循环就是不动点

那么另外它真正的意义是什么呢

其实在数学上

也有其他地方提到不动点

不动点的概念是说

经过了函数的运算

如果它的输入没有发生变化

它就被称为不动点

比如说我们来看这样一个函数

这个函数如果我把

X等于2代入的话

发现它的函数值仍然是2

那意味着这个2输入进去

经过处理它仍然还没有变

因此2就是这个函数的不动点

回头再看

在置换中如果一个图象

我把它转了180度

它仍然还是自己原来的样子

那就意味着这样的置换对它来说

没有产生变化

因此可以说经过置换或者

旋转等等操作之后

没有发生变化的图象

我们就叫做不动点

这个时候我们来看

对于这样一个立方体

只要能够找到它有多少个不动点的话

就可以直接套用伯恩塞德引理

而这样时候我们实际上是

在给正六面体的每个面进行着色

因此我们需要考虑对于

面的一种转动结构

对于面来说

我们看这样的一个立方体

我们能怎么去进行翻转和旋转呢

首先我们要把每个面

打上一定的标号

一共6个面

1 2 3 4 5 6

打上标号之后

我们要看

它是否有旋转的轴

我们可以在它的中心

面心对面心对应做一条轴

就可以发现沿着这个轴

我可以转90度 180度

接着我还可以说对应每一条棱

如果它们的中心点相连的话

也构成了翻转的对称轴

这时候上下一翻转

发现它仍然可以产生一定的置换

因此我们在这样基础下

就可以分析出来对应

正六面体关于面的置换方法

而在这里对于伯恩塞德引理

我们一方面要去找

它一共有多少个置换

另一方面我们要去找

有多少个让它不动的置换点

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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引理的困境(1)笔记与讨论

也许你还感兴趣的课程:

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