当前课程知识点:组合数学 > Polya定理 > 母函数型Polya定理 > 母函数型Polya定理(3)
既然我们有了更有利的武器
也就是母函数型的波利亚定理
我们再来复习一下
黑板上的排列组合
在这面我们还是一样
要去求对于正六面体
如果用六种颜色着色
而每一面颜色都不一样的情况下
会有多少种不同的涂法
我们来仔细的分析一下
这时间我们想用
母函数形式来求解
黑板上的排列组合
首先第一步还是要把所有的
正六面体的转动群体找出来
这已经非常熟悉了
刚才我们已经列举了多次
包括不动 面心对面心
转正负90度
面心对面心转180度
棱中对棱中转180度
以及对角线为轴转正负120度
这个时候我们只需要考虑
它对应每个置换长什么样子
然后列出它的母函数我们来分析
我们来看它第一项对应的
母函数应该怎么写
这里它是一阶循环一个
因此如果我们分别用变量
来替代的话
用X1表示第一个颜色
X2第二个
一直到X6
那这个时候X1加
X2加X3一直加X6
代表括号内部的着色方案
它一共有6个
所以是6次方
因为面心对面心所有的置换
以及角度算下来一共是有6个
因此对应的是6乘以
后面展开的母函数
这里面一阶循环
X1加X2一直加X6次方
还有一个
有两个一阶循环
意思是平方项
有四阶循环的所以是X1的四次方
一直加到X2的四次方
一直加到X3四次方
一直累加到X6的四次方
这就是对应的这一项
而面心对面心转动180度
我们同样一共有三个
每一个对应的就是
一阶循环有两个
二阶循环有两个
接下来我们还有对于
有6个二阶循环
有三个这种情况
所以6乘以二阶循环有三个
加上8乘以三阶循环有两个
然后不要忘记
还有除以置换的个数
也就是除以24
这就构成了正六面体的
面着色母函数
我们要求什么呢
我们要求的是一面一色
且每面颜色不同
意味着X1 X2 X3
X4 X5 X6全部都要用上
因为有了这样的母函数之后
要求的X1乘以X2乘以
X3一直到X6的系数
我们依次来分析
对于每一项里面是否
存在这样的对应的单项
我们来分析一下
我们接着看
在第一项中
我们发现其实
确实这里面会存在
X1 X2一直到X6
那么它的相对应
6个多项式展开之后
进行不停的排列
因此它前面的系数就是6的阶乘
而后面我们会发现这里面
任何一项出来之后
都会有XK的4次幂
不符合这样多项式的展开
对于这一项也会有平方项
也不会产生X1 X2 X3
X4 X5 X6
这里不可能产生
这里也不可能产生
总结而言
我们会发现真正只有对应的
这一项会产生我们需要的
想要的
X1 X2 X3
X4 X5 X6
因此它的系数就是6的阶乘
而同时我们不要忘记
我们要再除以24
因此得到的方案数就是
6的阶乘除以24等于30
这又一次用不一样的方法
来求解了黑板上的排列组合
接下来我们来看另外一道题目
它是说正四面体
我们要在点上进行四着色
同时在面上要三着色
同时棱上要二着色
求方案数
这和刚才的有些区别
刚才只是对应某一些点
单独的给它镶珠子
染颜色
或者对面进行着色
或者我们也可以对棱进行着色
但是这到题目我们把
三个结合在一起
那应该怎么做呢
那么我们同样第一步
首先我们要分析
有多少个不同的置换
在这里我们总结而言
对于正四面体
无非就是顶点对面心
正负120度
以及棱中对棱中进行翻转
以及不动旋转
我们把点 面 棱分别列出来
在顶点对面心正负120度的时候
点是固定的一个
剩下的三阶循环
对于面来说
也是底面不动
三个面进行循环
对于棱来说
它实际上是上面三个棱进行循环
底面的三个棱也进行循环
因此三阶循环有两个
棱中对棱中进行兑换的话
对于点是两两进行交换
所以二阶循环有两个
对于面来说
实际上它也是前后进行的交换
二阶循环有两个
对于棱中
如果考虑它棱的对换会发现
AB这个棱因为
他俩的方向是一致的
所以我们仍然认为它是不动的
而对于ADBC这两个
会发生互换
因此一阶循环有两个
而二阶循环有两个
对于不动我们说四个点不动
四个面不动
而对于棱
有6条
所以是6个棱都不动
这时候我们可以把它综合在一起
根据分步的法则
这里面虽然有一阶循环
有三阶循环
我们可以都用X来表示
为了有所区别
我们用X1来表示
一阶循环
X3表示三阶循环
它的对应的都是一个
因此是X1的1次方
X3的1次方
对于面我们用Y来表示
Y1有一个
Y3有一个
对于棱我们用Z来表示
是Z的三阶循环
是Z3的平方项
棱中对棱中我们也可以写出来
那么对应于棱中对棱中
因为是二阶循环
所以是X2的平方项
乘以Y2的平方项
因为这里有两个
对应不同长度的循环
因此我们用Z1的平方
乘以Z2的平方
对于棱中对棱中
它一共有三个
而不动图象分别是
一阶循环有四个
一阶循环有四个
和一阶循环有六个
这时候只有一个
这时候我们再把它综合起来
首先它的转动群
它的置换个数一共是12个
而它的方案数我们代进来看一下
在这里X是几着色呢
X对应的是点
点是四着色
因为X1和X3都应该用4来替代
它就应该是等于8个这样的置换
乘以首先这一个项
产生的4的平方
我们可以看到
在这里这一项
正好是4的平方项
而这里呢
Y1和Y3对应的是面着色
它应该是3的平方项
这里对应的Z3是二着色
是2的平方项目
因此对于这一行实际上
我们就找到了
对应的元素
计数产生的就是这样一个结果
同样我们会发现棱中
对棱中来说
这里面是四着色
而Y2对应的是三着色
而Z对应的是二着色
所以是2的4次方
同样这时候
我们又可以找到
对应的它的
应该是4的平方
乘以3的平方
乘以2的4次方
它前面一共有三个
而同时我们回头看一下
会发现对应的一阶循环应该
就是4的4次方
乘以3的4次方
还有2的6次方
因此最后一项正好是
4的4次方 3的4次方
2的6次方
我们把所有的式子累加起来
再除以12个这样的置换
就可以得到答案
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验