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

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

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

母函数型Polya定理(2)

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

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

母函数型Polya定理(2)课程教案、知识点、字幕

下面我们来拿

等边三角形的着色举例

比如说等边三角形的三个顶点

我们现在可以给它

进行红蓝绿的三着色

请问有多少种不同的方案

刚才我们已经计算过了

那么我们现在想更细致化

比如说我想问你

对应的三个珠子都是

红色都多少种方案

两个红一个绿多少种方案

一红一绿一蓝多少个方案呢

我们就利用母函数的方案来求解

对于它的置换群其实很简单

无非就是旋转正负120度

以及对它的对称轴进行翻转

以及不动

一共有6个不同的置换

依次列在这里

我们必须要找相应的

母函数的形式

我们看第一个

三阶循环有一个 这时候

它对应的母函数意味着

括号内的三个应该全部都取同色

那它的母函数就是R的3次方

加B的3次方

加G的3次方

而同样对于一阶循环一个

二阶循环一个

这样的形式它写出来就是

R加B加G乘以R平方

加B平方加G平方

一阶循环三个

这样实际上就是

R加B加G的3次方

我们如果把这样的

式子全部联立在一起

去求若干项前面的系数

就是对应的方案数

比如说我们想问全部都是

红色珠子有多少种

那就是求展开式中

R的3次方前面的系数

那么R的3次方大家看一下

在哪些项目中是可以的呢

比如说第一行中R加B加G

这个里面发现有一个

R的3次方

而前面因为有两个

所以2乘以对应的系数就可以了

下面这一项

R加B加G乘以R平方

加B平方加G平方

实际上它也会产生R的3次方

一共有多少个这样的置换

3个

对于下面的R加B加G的3

次方同样也有R的3次方

我们把这些所有累加在一起

发现正好是2个加3个加1个

同时不要忘记

对应的波利亚定理中

我们还要除以

置换的个数

置换的个数是6

所以刚好算出来是

2加3加1除以6等于1

意味着在三角形的

顶点上全部取红色

只有一种方案

同样还可以算别的

比如说要RGB它的系数有多少

当然我们不需要

把所有的式子展开

我们只要看每一项就可以

第一项里面

对应的应该是R的3次方

加B的3次方

加G的3次方

这里面根本就不可能

有RGB存在

我们再看第二项

第二项里面每一项至少是平方项

因为它前面是R加B加G

后面是R平方加B

平分加G平方

因此也不可能出现RGB

这样依次累乘

只有最后一项

R加B加G的三次方里面

有可能有RGB项

而它有多少项呢

实际上我们都知道

就应该是3的阶乘

除以R有多少阶乘

G一阶乘

这样一个可重排列

同样不要忘记除以阶乘个数6

答案仍然是我们

对应的RGB有多少种可能性

答案仍然是1

同样我还可以算两个红珠子

一个蓝色珠子

也是一样

对于第一项

所有项都是三次幂

因此不可能存在R平方B

只有在第二项中我们

可以第一项取B

第二项取R平方

产生了一个

而一共有三种不同的置换

因此对于在第二行中

有两个对应的R平方B出现

对于R加上B加上G的三次方

我们同样可以求R平方B的系数

实际上也就是

可重排列出来的结果

可以认为是用三阶乘除以

R平方对应的

两个R的可重排列

除以2的阶乘再除以1的阶乘

同样再除以6就得到

对应的答案

我们再看一下

如果是四颗珠子

要镶嵌在正六面体上

有多少种不同的方案呢

我们再仔细想一想

正六面体应该有多少个顶点

大家会想正六面体

应该有8个顶点

现在我的提议是说我

只有4颗珠子

4颗红色珠子要镶嵌

在8个顶点上

这就是说有些点是空的

虽然都是一种颜色

但是对应的是镶嵌

红珠子和不镶嵌红珠子

这两种对应的二着色问题

这时间我们直接对于正六面体中

顶点进行二着色

进行计算就可以了

但是它要求求什么

最后的方案中

红色的珠子必须是四个

如果我们用R来表示红色珠子

用B表示不存在珠子的话

实际上我们就去求R的四次方

B的四次方

前面的系数是多少

这时候我们还是同样应用

母函数型的波利亚定理

首先我们应该把正六面体对应的

所有置换全部列出来

分析一下在不动的情况下

顶点置换应该是8个顶点

每个顶点都是一阶循环

因此是一阶级循环的8次方

对于面心面心

上面四个顶点和下面四个顶点

进行交换

所以四阶循环有两个

依次往下

我们都可以把顶点的

置换群全部列出来

我们要求的是R的

四次方 B的四次方

我们看第一项里有没有

R的四次方

B的四次方

第一项如果要将它写成母函数型

应该是一阶循环有八个

意味着母函数是

B加R的8次方

B加R的8次方自然会

存在一个B四次方 R四次方

它对应前面系数就应该是

从八项目里面取四个

也就是C(8,4)

对于面心对面心旋转

它的格式是四阶循环有两个

那写成母函数就是B的四次方

加上R的四次方的平方项

这里仍然会有对应的B四次方

R四次方

同样依次往下

每一项每一项都去分析

它是否存在B四次方

R的四次方

我们写出对应的母函数形式

就可以分析出对应的展开式中

B的四次方

R的四次方的系数

就应该等于C(8,4)

加上12

再加上9乘以C(4,2)

再加上八乘以C(2,1)

乘以C(2,1)

同样不要忘记还要

再除以所有的置换个数

对于正六面体

它的置换个数正好是24

因此累加之后除以24

答案就得7

什么意思呢

意味着在这样的

正六面体中如果四个顶点有珠子

而其他四个顶点没有珠子

的情况下

不同的方案应该只有7种

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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定理(2)笔记与讨论

也许你还感兴趣的课程:

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