当前课程知识点:组合数学 >  Polya定理 >  母函数型Polya定理 >  母函数型Polya定理(3)

返回《组合数学》慕课在线视频课程列表

母函数型Polya定理(3)在线视频

母函数型Polya定理(3)

下一节:母函数型Polya定理(4)

返回《组合数学》慕课在线视频列表

母函数型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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

母函数型Polya定理(3)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。