当前课程知识点:组合数学 > Polya定理 > Burnside引理的困境 > Burnside引理的困境(2)
首先我要研究对应的一个正立方体
我就要知道它有多少个顶点
有多少个面
有多少条棱
对于正立方体六个面我们很好分析
对于六个面来说
这个的正六面体它必然是有六个面
那么它有多少条棱呢
我们会发现它上面的平面和
下面的平面分别对应有四条棱
中间围成的高的有四条棱
因此它有12条
它有多少个顶点呢
它正好上面有4个下面有4个
8个顶点
在这样对它结构分析基础上
我们就可以去找到它所有的转动群
我们会发现首先不动置换是最简单的
一个那么不动置换对应的所有的
图象全部都应该保持不变
它有多少个不同的着色图象呢
刚才我们分析到了
每个面对应出来就是排列方案数
因此它一共有多少有
6的阶乘个图象
那对应于不动点里面
单位元对于我们来说
相当于6个阶乘所有的
这样全部是一阶循环
那它有多少个不动图象
自然是6的阶乘个不动图象
那另外其他方面呢
我们可以让它进行旋转
比如说上面的面心和下面的面心
连了一条轴
这时候让它进行旋转
正负90度的话
自然而然就会产生不同的置换
那么一共有多少个这样的置换呢
首先我们想有多少个
面心对面心这样的轴呢
我们刚才说了
一共有6个面
那么一共有多少个对立面呢
正好每两个面构成一个对面情况
因此它一共有三个
不同面对面的情况
面心对面心的轴一共有三个
而且我们说到了
有正90度和负90度
因此这样的置换一共有6种
在这样的置换下
请问会不会产生一些不动点呢
我们首先说到
在这到题目中要求
所有的面颜色都不一样
那意味着什么
转90度
原来红色的面可能就变成蓝色了
原来是蓝色的可能变成红色的
不管怎么样
因为它要求每个面的颜色都不一样
只要你转了就会发生变化
因此它是没有不动点的
那意味着实际上我们就不需要
把所有的着色图象都拿出来
只要分析它有没有不动点就够了
与此类似
除了正负90度之外
我们还可以转180度
转180度可是对应的面心对面心里
因此一共有三个不同的轴
同样分析
如果我们要求每个面颜色都不一样
那么它最后
转180度就会发生颜色的变化
因此也还不存在不动点
接着还没有其他置换呢
我们会想它是一个正的立方体
我们是不是在这样的棱
和它对面的棱
连接他们的中心点
构成了棱中对棱中的一条对角线
这时候我们只要沿着
这样对称轴进行翻转的话
它照样能够重合到原来的位置上
照样是一个置换
这样它一共有多少个
棱中对棱中呢
刚才我们分析到了
它有多少条棱呢
它上面4个下面4个
中间4个因此12条棱
是2条棱两两对应
两个棱中
这时候12除以2
应该有6个
对应的不同棱中
那同样也分析
翻转之后
上面和下面相互交换
本来上面是红色
一翻上面是蓝色
因此仍然不可能产生不动的图象
接着还有
比如说我们直接拿顶角
对着它的顶角做一条内部的对角线
这时候我们应该怎样让它翻转呢
我们不再转180度了
我们是沿着它的
顶角方案旋转120度
可以是正120度和负120度
它同样能够重合
应该有多少个这样的置换呢
首先我们想到有多少个
这样对应的内部对角线呢
我们一共有多少个顶点
一共有8个顶点
8个顶点中两两是一对对应的顶角
就会有4条不一样的对角线
有多少个角度呢
正120负120
有两个角度
因此我们对应的在这种旋转下
顶点对顶点应该有
2乘以4个不同的置换
走到这里
我们其实发现我们并没有把
六阶乘所有对应的图象
集全部列出来
我们分析了什么
我们分析了一共有
多少个不同的置换
我们同时还分析了
有没有不动点产生
很幸运的是因为在这里面我们的要求
每个面的颜色都不一样
只要发生转动
它就会产生图象的变化
因此不会有不动点产生
除了单位元
而单位元的个数我们很容易算
正好是6的阶乘个对应的一阶循环
那这时候再代入到伯恩塞德引理
我们发现所有的数字我们都有了
这时候对应的一阶循环的个数
就是6的阶层
而对应的置换
我们把刚才所有的数字加起来
正好是24的置换
因为它有多少个呢
就是6的阶乘除以24
答案就是30
刚才我们实际上用了
伯恩塞德引理解决了
黑板上的排列组合
但是大家还记得吗
我们曾经问到
但是稍微改一下这道题目呢
本来是要求每个面颜色都不一样
这样的话就很容易找到
对应旋转是不存在不动点的
但是如果我们要求各个面的
颜色是可以同色的
这时候问题的规模更大了
因为对于6个不同的格子
每个格子都有不同的可能
因此所有的图象集的个数
是6的6次方了
而且在旋转中存在不动点呢
我们会发现
比如说上底和下底颜色是一样的
周围高对应的四面颜色也都一样
这种情况对应于面心对面心旋转
90度和180度
或者是270度
都会发现这个图
没有发生任何的变化
那意味着在旋转的时候
会有各种情况的不动点的情况
如果分析对应的图象集以及对应的
不动点情况实在是太复杂了
我们回头再看
这似乎就遇到了
伯恩塞德对应的不能解决的问题
它针对的是什么
由于本身的缺陷
需要列出所有的着色图象集
着色图象集的规模是相当大的
而且如果你只是两种颜色的话
结果还相当少一些
如果是6种 8种 10种呢
这么多颜色对应所有的
方案结构就非常复杂了
理论上是可以用
伯恩塞德来求解的
但是
我们怎么去找对应的一阶循环
是非常非常困难的
因此就引导我们是不是
可以转化思路
不从着色图象集出发
我们是不是能够另辟蹊径呢
下面我们就给大家讲波利亚定理
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验