当前课程知识点:组合数学 > 组合之美 > 组合之美之转动群与染色 > 组合之美之转动群与染色
我们刚才介绍的呢都是排列组合
但是实际上在组合数学中有一个
非常重要的概念
实际上是对形状进行染色的计数
而且不单单是平面上的形状
我们还要考虑立体空间里面
立方体的旋转进行染色
实际上这个概念呢我们实际上
用群论的思想进行的解释
因为它进行转动的时候对应的
就是转动群
我们要求的是在转动群的作用下的
等价类有多少个
我们一开始介绍了一个Burnside的东西
当然Burnside引理它实际上已经把
转动群转化成了固定的模式
来求解等价类
也就是它不再去看所有的对应的
结果是什么
它直接通过研究对应的循环的个数
也就是对应的不动点的个数
这里边它要求所有的循环中一阶
循环的个数累加起来再除以
对应的置换的个数
就得到了等价类的个数
当然Burnside引理并不实用
为什么这么说呢
因为Burnside引理处理的对象它是
要在所有的图像集合中
要知道对应的染色的图案的
集合是非常庞大的
我们要在这样一个庞大的集合
中去找谁和谁处于一个循环上
是非常困难的
因此波利亚定理解决了这个问题
波利亚定理不再拘泥于我要在
图像上进行研究了
而我看到的是对应的着色的
对象的结构
它对应的不再去研究对应的
图像转动群什么样子
而是研究我在没有转动之前
这样一个结构
我去研究它转动发生一个
什么样的转动群
同样呢我们不再找一阶循环的个数
而找的是对应的着色对应数的
循环次幂
同样结构完全类似
和Burnside的引理一样
它累加起来m的ci次方之后
再除以对应的置换个数
就是等价类的个数
当然波利亚定理给我们的结果呢
仅仅是说一共有多少个
真正影响到深入的内部
比如说多少个红色多少个蓝色
多少个绿色对应的方案的话
我们一定要用到母函数型的
波利亚定理
我们有了波利亚定理之后呢
其实如果已经有了转动群
那么我们直接套用公式就可以了
在其中呢非常要注意的就是一定
要研究它对应的每一个问题
一定要在求解它转了之后
是否能够保持一致
但是大家会觉得
其实做题套用这样公式很容易
但是它的转动群到底长什么样子
一个足球拿来我到底
怎么转才可以呢
实际上我们会发现对应于这么
若干个不同的正立方体来说
它的每个转动群都是不一样的
要怎么能够深入了解它呢
我们还是要从一些基本的概念出发
比如说对应一个正多边形
它的内角和就应该是顶点的
个数减二乘以一百八十度
这样的话我们就知道每一个
内角等于多少
同样为了帮助大家去计算
有多少个顶点多少条棱多少个面
便有了一个新的概念就是欠角
欠角就是说对于每一个顶点
它周围都有一些和它相关的顶角
那么这些顶角的和
对应于和360度的差
就是我们的欠角
而有这样一个公式
也就是说
对于所有的每一个顶点对应的
欠角累加起来它们的和应该是
七百二十度
有了这样的概念之后
其实经过大家练习
就可以熟练的掌握
各个不同的立方体啊
足球它们对应的转动群
下面让我们以一个例子进行讲解
下面我们来研究这样一道题
也就是我有十根儿红火柴
十根儿蓝火柴
十根儿绿火柴
我要搭一个正二十面体
请问有多少种不同方案
首先我们要想清楚正二十面体
它是由什么样的图形来构成的
我们可以分析一下
正二十面体实际上是由
三角形构成的
但有时候我们会说数不清
有多少个点多少个棱
我们利用欠角和的概念可以帮助
我们计算出来它一共有十二个顶点
三十条棱和二十个面
接下来我来研究它的转动群
研究它的置换群第一个
最简单的自然就是说不动
因为我们是要火柴搭正二十面体
因此我们研究对象应该是每一条棱
这时候它一共有三十条棱
那么对于不动它就相当于是
一阶循环有三十个
那么对应起来我们要求
十根儿红十根儿蓝
十根儿绿
在里面对应的也就是说
如果要产生不动意味着
每一个括号也就是每一个循环内
我应该采取同样的颜色
那这个时候就相当于意味着
我们对应一共有三十个括号
其中三十个括号里面有十个是
红色的
有十个是蓝色的
十个是绿色的
这里面那我就相当于对于
应该是一个多重全排列
也就是这三十条棱对应中有
十个红红十个蓝十个绿
它们的全排列就应该是三十的
阶乘除以十阶乘十阶乘十阶乘
而对应于每一个火柴
它又有两个方向
因此是二着色的三十次方
可以看到我们这里面并没有
用母函数的波利亚定理
而直接用这样循环的进行着色
来看它的多重排列
接着我们来看如果是顶点对顶点
也就意味着这个顶点与它对应的
对角的顶点如果对应起来
然后进行旋转
这时候每一个顶点它包含的
实际上是五个棱和它相关联
那么它在转动的时候就意味着
这五个棱应该处于同一个循环
意味着一共有三十条边
五个是一组
一共有六组
因此五阶循环有六个
有多少个这样的对应的
五届循环有六个的置换呢
因为它一共有十二个顶点
十二个顶点就意味着有六个轴
而每一个轴它的转动角度
可以是一二三四
因此它对应的十二个顶点
六个轴有四个转动角度
因此是六乘以四一共有
二十四个对应的顶点对顶点的置换
它既然是五阶循环有六个
我这时候有十根儿红火柴
十根儿蓝火柴 十根儿绿火柴
要把它分成六组
其中每一组有五根儿火柴
那就意味着实际上每两组
应该是同色
因此一共有六组每两组是同色
对应的多重全排列
就是六的阶乘
除以二阶乘二阶乘二阶乘
而同样它是二着色
因此一共有六组
每组有两种选择
依次是二的六次方
这时候我们会发现
顶点对顶点
它对应的考虑红蓝绿各有十根儿
同时每根儿火柴
有两个方向的着色方案
应该是这么多
同时对应于面心对面心
比如说这样的一个面对应的
它对面这个面
进行面心旋转的话
它对应的一共有三条边在
同样一个三角形中
因此每一组应该包含有三个边
一共有三十条边
因此把它分成了十组
这时候有多少个
面心对面心的置换呢
我们有二十个面
二十个面意味着有十个轴
而每个轴对应的角度呢
应该有两个转动
因此应该是十乘以二
二十个
接下来我们看一下
对于面心对面心
它要进行旋转的时候
有没有不动图像
我们这里要求是一共有
十根儿红十根儿蓝十根儿绿
而我要把它平均的分配到
十个小组中
每组有三根儿火柴同色
意味着我每组三根儿火柴一共十组
而每三根儿火柴颜色还必须相同
那这十根儿红的怎么整分到
这个三个三个一组中呢
因此必然会存在同一组中
有不同颜色的火柴
那如果是同一组中有
不同颜色的火柴
如果在这样一个三角形中
它同一组中
会发现它一转
颜色会发生变化
因此由于它颜色不能平分
这十根儿火柴的话
就会有动的图像
因此没有不动图像
也就不存在不动点
那面心对面心的这样置换中
是不存在不动图像的
我们不需要计算它
还有另外一个置换方法是
棱中对对面的棱中
棱中对棱中进行翻转相当于
这样一个头变成了这样一个头
对于火柴来说
它原来是头朝上的
如果一旋转
变成了头朝下
这时候是没有不动图像的
当然我们还是可以分析它
对应置换长什么样子
它对应的两条棱分别不动
另外的每一次转动会发现跟它
相关的棱会换到对面去
所以它应该是一阶循环有两个
二阶循环有十四个
对应于它一共有十五个这样的
棱中对棱中的置换
那么因此呢我们考虑了不动
顶点对顶点
面心对面心棱中对棱中
会发现
面心对面心
棱中对棱中是不用计算在内的
因为无不动图像
那么我们把上面的
两种方式累加起来
再除以它所有的置换个数
我们置换个数累加之后
发现是六十个
因此它的答案就应该是
这样一个数值
我们会发现这样一道题目呢
我们实际上并没有直接去套用
波利亚的母函数形式
而直接通过分析它循环内部
一定要着同色这样的规定的话
去分析十根儿红十根儿蓝十根儿绿
是否能够满足这样的循环结构
就可以更加简便的求解出来
对应的着色方案数了
我们今天呢有了这短短几节课
给大家回顾了一下
整整八周课的内容
当然其实呢我们只是想
带领大家去回顾一下在组合数学中
有那么多的精彩的东西
它给我们带来是一种抽象之美
这节课我们说是组合之美
实际上有这样一句话
数是美丽的
如果它们不是美丽的
那么世界上就没有什么事物是
美丽的了
这句话当然不是我说的
是谁说的呢
实际上是一位著名的
数学家保罗·埃尔德什说的
大家还记得吧我曾经说过
说欧拉一度是世界上发表
论文最多的数学家
这个记录后来被人打破了
是谁打破的呢
就是这位埃尔德什数学家
打破了欧拉的记录
足见埃尔德什发表了多少篇论文啊
而且呢埃尔德什实在是非常有名
他呢游历全世界
和众多的科学家合作论文
因此有一个数就以他命名
也就是埃数
埃数是什么数
并不是一二三四五六七这样定义的
他实际上定义了一个
数学界论文的一个关系网络
要知道埃尔德什游历全世界
他和不同的数学家合作发表论文
那么他的合作过的数学家又会和
其他的数学家合作发表论文
因此埃数就定义了这样一个概念
也就是说和
埃尔德什发表论文的人
他的埃数是零
和埃尔德什合作发表论文的
人再合作的人他的埃数定义为一
以此类推
所以同学们也可以去想一想
你查到的论文或者你自己发表的
论文之后你的埃数是多少呢
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验