当前课程知识点:组合数学 > Polya定理 > Burnside引理的困境 > 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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验