当前课程知识点:组合数学 > Polya定理 > 从Burnside到Polya > Polya定理的应用(1)
其实我们有了波利亚定理就可以
求解相应的对应的置换群着色
我们先拿一个简单的例子来看
我们看平面中的等边三角形
对于等边三角形它有三个顶点
这时候想问题
如果对于顶点可以进行
红 蓝 绿的三着色
请问
有多少种不同的方案
对于三着色我们知道如果把它的
所有的图象集画出来是非常庞大的
我们就考虑它对应的结构
其实对应于三维空间中我们要想
考虑三角形进行旋转翻转的话
对应的就是交换群S3
首先我们来考虑
对于中心就可以进行
正负120度的旋转
它应该长什么样子呢
这对应于么转可以变成1 3 2
反过来再转转成了1 2 3
这时候因为在波利亚定理中我们只需要考虑
它的循环长什么样子
对于细节上可以稍微忽略一下
这时候我就看
这样的循环它应该有多少个
实际上我们可以看到
因为1 2 3
换成了3 2 1
它是个三阶循环
有一个
因为角度是正负120度
因此这样的置换有两个
接着我们可以根据不同的
对称轴进行翻转
比如说固定住1点
3 2进行互换
这时候发现1阶循环有一个
2阶循环也有一个
符合这样一个结构对应的
置换有多少个呢
我有多少个对称轴就意味
有多少个不同的翻转
这时候正好有3个不同的对称轴
因此这样的置换有3个
另外还有一个比较简单的
就是根本不动
不动的情况下
1还是1 2还是2
3还是3
这时候1阶循环有3个
那么我们就会发现置换
一共有多少个呢
无非就是2加3加1
一共有6个
那么对应于我们要求
每一个置换中它有多少个循环
我们也已经依次列出来
对应于波利亚定理中
我们要求G的个数
就是刚才计算的6
对于后面的C(Pi)
加起来的话
我们可以看这里面对应于第一个正负
120度的时候
它只有一个循环
三着色就是3的1次方
有多少个呢
有2个
所以就是2乘以3的1次方
接着对应于翻转
翻转它有多少个呢
对应它有三个不同的轴
所以是三个
而它对应的应该是
三着色的多少次幂
我们来看
它一共有两个循环
就是三着色的二次幂
在不动的情况下
有4个不同的循环
因此是3的4次方
我们进行累加以后再除以
整个阶的个数6就得到了答案
下面我们来举一个
有关有机化学题目
实际上我们知道在有机化学中
有很多的立方体结构
比如说甲烷CH4
它有4个键
它的四个键可以有氢 氯
甲基 乙基等等进行连接
请问有多少种不同的构造方案呢
实际上它的结构就是
对应一个正四面体
而它对应的中心正好是
一个炭原子
这个四面体如何去考虑它的
顶点用不同的氯
氢来进行着色
这个问题就转化为正四面体
四个顶点进行着色的问题
首先我们应该分析它的转动群
对于这个正四面体来说
它的转动群是什么样呢
首先我们看到四个顶点它的不动
置换意味着A顶点
还是A B C D
它一共有一个一阶循环
对应的情况接着我们来看
如果从顶点向下对应的中心
可以构造一个对称轴
这时候按这个轴进行旋转的话
我们可以是正的120度
旋转或者是负的120度旋转
这时候产生的置换来说
我们拿AC这样的轴来转的话
它对应的是A不动
而BCD进行三阶循环
因此它的置换变换成A不动BCD
或者另外一个角度A不动BDC
同样我取另外一个不动点
比如说B不动
还产生置换
B不动ACD与
B不动ADC
以及置换C不动的时候
ABD和ADB
还有ABC ACB等等
因为我们对应角度一共有两个
而对应的不动的顶点有四种选择
因此总体来说这样的置换有8个
而每个置换长什么样子呢
都对应有一个一阶循环
有一个 三阶循环有一个
它的置换是这样的结构
除了刚才对应的顶点
不动下面进行旋转之外
我们还可以找到它的棱中
对应的棱中
棱中对应切分开之后
可以两两之间进行翻转
也就是A换B C换D
对于正四面形对边中心进行连线
旋转180度
我们可以把它写成AB互换
CD互换 AC互换
BD互换 AD互换
BC互换
一共有多少个呢
我们发现这两个对应的是一个
这两个对应的是一个
而正面和背面对应的是一个
在正四面体中一共有6条棱
每两个构成了棱中对棱中
因此它一共有三个对称的
这样的一个对称轴
每一个对称轴产生的
循环是二阶循环
有两个
这时候我们已经把
对应的置换列了出来
再代到对应的波利亚定理中
对于第一个不动循环
应该有一个
而它进行四着色
因此是4对应的k次方
而k代表着有多少个循环
在不动循环中刚好有4个循环
因此它对应的是4的4次方
再加上第二类置换一共有8个
8乘以4乘以多少个循环
这里刚好是两个循环
是4的平方
再加上3乘以4再乘以
对应多少个循环
这里也是4的平方
同样我们不要忘记还要除以
所有的置换个数1个加8个
加3个刚好是12个置换
根据波利亚定理我们就知道
这样的甲烷不同构造
就应该有36种
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验