当前课程知识点:组合数学 > Polya定理 > 立方体旋转 > 立方体旋转(1)
刚才我们举了很多不同的例子
包括呢甚至是立方体 项链
实际上我们发现对象的不同
对应的置换也会有所不同
有时候不处理的就是
平面上的一些旋转
有时候我们会处理立方体
我们就会想对于平面来说
其实有时候也可以是在
二维空间平铺下来的
这时候我们只考虑转动就好了
如果我们说的
如果它是在三维空间中
是可以进行翻转的
有一个特殊的例子
比如说棋盘
如果拿棋盘来看的话
它对面是一个平面上的东西
请问它翻过来还是
一个可以用的棋盘吗
所以我们一定要考虑
它是单面的还是双面的
一般情况下我们认为
它是不可以翻转的
对于立方体来说
它同样可以转动
可以有对称轴
另外一种比较奇特的
对于数字来说
我们同样可以有一些置换
甚至点的置换
我们在后面的课程中会
一一给大家进行介绍
这里我们还是拿立方体来看
对于正六面体来说
刚才说道
要想研究它的置换群
首先要知道它有多少个结构
也就是多少个面
多少个 棱 多少个点
对于正六面体
6个面 8个顶点 12条棱
我们可以考虑它是顶点的置换
还是面的置换还是棱的置换
我们先拿顶点的置换为例
对于8个顶点分别标号
1 2 3 4 5 6 7 8
我们看它不同转动情况下
有什么样的表现
第一个转动零度
因为它一共有八个不同的对象
因此它的描述就是
一阶循环有8个
这样的置换就只有一个
对于面心对面心
它可以旋转正负90度
这时候对于点来说
上面的4个点进行旋转
下面4个点进行旋转
因此四阶循环有两个
而有多少个这样的不同的置换呢
因为它有三对不同的面心
两个角度
因此它可以产生6个
这样的面心对面心置换
如果面心对面心
旋转180度的话
这时候我们会发现
上面的四个顶点两两进行互换
下面也是两两进行互换
因为两两互换一共有四个
而有三个这样的面心
根据这样的情况
我们可以看棱中对棱中的话
会发生什么样的情况
同样如果是点来看
点上下进行180度的翻转
自然是两个两个进行互换
因此一共八个顶点
两两一组一共四组
二阶循环有四个
同样有多少个棱中呢
有6个这样的棱中
对应于我们同样来考虑的
如果是顶角对顶角
我们看到的是
正负120度的旋转
对于顶点来说
对角线的两个顶点是
没有发生任何变化的
而剩下的正好三个一组
一共8个顶点有两个不动
剩下的正好是三个三个一组
有两组
有多少个这样的对称轴呢
一共有4个两个角度
因此这样的置换一共有8个
分析完之后
发现对于这样顶点置换和我们
刚才说的面的置换
还是有一定区别
当然一共有多少个
置换是确定好的
一共是24个
但是对于每个置换长的结构
样子是完全不同的
我就拿这样顶点
来给大家研究着色的问题
有两种颜色
对它的顶点进行着色
一共有多少种方案
刚才所有的置换群
我们已经一一写下来了
这时候很简单就是
要套用波利亚定理就行了
波利亚定理说了
二阶循环对应的有多少个
现在是二着色
我们整理之后代到所有的
二着色乘以对应的幂次
就可以得到所有的方案数
刚才我们是对顶点进行着色
其实还可以重新对面进行分析
对于正六面体
它的面的着色方案必须
考虑面的置换群
同样对于每个面打上编号
1 2 3 4 5 6
它同样有不动置换
一阶循环有6个
对应于面心对面心转
正负90度
实际上对于面来说
上下两个底面是不变的
中间作为高的
四个面产生了循环
因此它是1的平方
乘以4的1次方
就是一阶循环有两个
四阶循环有一个
一共有多少个这样的置换呢
有两个不同的角度
有3个面心对面心
转180度的时候
我们会发现所有
这四个都是两两进行互换
因为一阶循环有两个
二阶循环有两个
一共有三个不同的置换
同样对于棱中对棱中
进行翻转的话
我们会发现
棱中对棱中进行翻转实际上
上面和下面会发生变化
而它的对应的面也会
发生一定的变化
因此两两进行互换一共有三组
二阶循环有三个
对于对角线来说是
正负120度进行旋转
每次都是三个面和
三个面形成一个组
因此三阶循环有两个
有这样对应群的置换后
我们就可以具体来应用
比如说对于正六面体
六个面分别是二着色
我们先拿简单的二着色来看
对于二着色来看
我们已经有了所有的置换群
无非就是套用波利亚定理
对于一阶循环有6个
二着色嘛
表达出来就是2的6次方
对于下面1阶循环有两个
四阶循环有1个
一共三个循环
实际上对应的着色方案
就是2的3次方
它一共有6个这样的置换
因为第二项6乘以2的3次方
依此类推
3乘以2的4次方
加上6乘以2的3次方
依次累加
最后除以所有的置换个数24
答案是进行二着色
里面正六面体对应的
方案数一共是10种
当然回头我们再来看
原来我们曾经说到
伯恩塞德引理无法解决的问题
对于在黑板上的排列组合中
我们如果把题目变换成
不同的面是可以同色的
那意味着什么 意味着对于
正的六面体要进行六着色
六着色无非就是把刚才的
2换成6就行了
刚才是一阶循环有六个
这里面6着色
对应的是6的6次方
再加上6乘以6的3次方
再加上3乘以6的4次方
依次累加
再除以24
这时候再回头看伯恩塞
解决不了的问题
实际上用波利亚定理
是非常容易就可以求解的
我们再回头看骰子该怎么组织
大家都知道骰子无非
上面就是1 2 3 4 5 6
6个点
但是在上面的排列和组合
其实是有多样性的
那这时候我就问你
一个骰子6个面分别是1点
2点 3点 4点 5点 6点
那么它有不同的组织方式
如果允许它旋转 翻转
你看它最终真正不同的
方案有多少个
这个问题大家会想实际上
实际上这和我们说道的
每个面都是不同颜色
的六着色是不是一致的呢
这个问题我们仍然可以考虑
就是正六面体
它转动群中用六着色来做
同样我们发现其实
只要考虑不动点就可以了
对于正六面体
它的面的置换一共有24个
不同的置换
只有第一个不动置换
才会有不动点
其他都无所谓
所以我们就可以直接套用
伯恩塞德引理
伯恩塞德引理说到
它应该是所有不动点的个
数除以对应的置换个数
也就是6的阶乘
除以24是30个方案
对于其他的置换它的
不动点全部为零
到此就够了吗
我们想毕竟骰子上的
点和颜色是有区别的
为什么这么说呢
颜色摆到上面就是一种方案
但是点却不一样
比如说我们来看
2点 3点和6点它不是方的
它是用条形状的
那它就会有两种不同的方向取向
因此我们不要忽略
这样的小细节
除了要求它对应
伯恩塞德引理着色方案之外
我们还需要考虑
每一种方案内部着色的多样性
这里我们看两点 三点 六点
分别都有两种不同的取向
而一点 四点 五点它是对称的
只有一种取向
因此真正的答案应该是
30乘以2的3次方
等于240种不同的骰子构造
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验