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

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

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

母函数型Polya定理(1)

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

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

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

刚才我们介绍了很多的例子

说明了波利亚定理可以有效的

帮助我们去进行着色方案的计数

但是大家会去想波利亚定理

告诉我们的结果是

一共有多少种着色方案

但是对于每一种着色方案

它会有多少个呢

比如说四个珠子去着色

每个珠子都有3种类颜色的话

我们有可能会问如果两红

一蓝 一绿有多少种不同的方案

这时候单纯的用波利亚定理

可能就不行了

我们会想其实我们有一个有利的

工具帮助大家进行枚举

大家还记得母函数吧

母函数实际上可以帮助我们

进行着色方案的枚举

就举个简单的例子

比如说我们要对三个

相同的小球进行着色

一共有四种不同颜色进行选择

它可能的颜色组合如果

用母函数的形式该怎么表达呢

我们会发现其实对于一个球它的

着色方案可以用

红色黄色绿色蓝色加在一起

这就是一个球的不同方案

一共有3个球就应该是

R加Y加B加G的三次方

如果我们把它依次展开之后

就会发现每一项前面的系数

就表示它有多少个方案

我们就会想如果波利亚定理

能够结合母函数

是不是就可以给我们找到特殊

情况下他们对应的

方案有多少个呢

我们举个简单的例子

比如说有三种不同颜色的珠子

我要拼成四颗珠子的项链

这道题我们刚才给大家进行了解答

这时候我们想来仔细分析一下

对应的如果把母函数引入进来

会有什么样奇妙的方案

首先我们还是要分析它的置换

比如说第一个置换就是

绕这种中心旋转90度

绕中心旋转90度

我们知道这实际上对应的

就是四阶的循环

四阶循环意味着在这个循环里

四个方案里面全部都要取同色

对应的母函数该怎么写呢

可以说我们这四个珠子

全部都是红色

那意味着

就是R的四次方

有可能它对应的

全部都是蓝色

就是B的四次方

它一共有四种不同颜色选择

因此对于这样四阶循环直接用

母函数的方式可以直接把它写成

R的四此放加上Y的四次方

加上B的四次方

加上G的四次方

那意味着

这样一个循环

用母函数是可以表达的

如果让它旋转180度

会产生两两的对换

那两两对换意味着在一个循环内部

两个珠子采取的颜色是同色的

两个珠子同色有多少种可能呢

就是R平方加上Y平方

加上G平方等等

我们就会发现这里我们同样利用

他们对应的循环大小不同

以及他们对应的每一个循环内部

应该采取同色这样的形势

就可以写出对应的母函数

我们如果考虑翻转的话

同样如果对于不穿过

珠子的对角线

它对应的置换就是两两互换

同样也可以写成对应的

母函数形式

就是R平方加B平方

加上G平方

因为它有两项

所以它有平方项

另外一个

另外一个穿过珠子的对角线

实际上一阶循环有两个

再加一个二阶循环

写出来意味着一阶循环里面

一个珠子颜色选择可以是红色

也可以是蓝 也可以是绿

那这时候R加B加G

它一共有两个

因此是R加B加G的平方项

对于二阶循环

可以直接写成R平方加

G平方加B平方依此类推

对于不动来说就是四个

都是一阶循环

就是R加B加G的四次方

这时候我们把所有对应不同情况

下的母函数都列出来的

这时候把所有的置换代入到

波利亚定理中

如果不考虑单个方案的话

直接就可以套用对应于C(Pi)

就可以找到所有的等价类方案数

但是现在我们把它用

母函数的方式引进来

会发现实际上PG bar

可以写成B的4次方

加上R的4次方

依此类推

我们把每一项展开

就可以得到对应的式子

而每一项都代表一些意义

比如说我这里面B的平方

R G意味着着它对应的

有两个是黑色的珠子

有一个红色的珠子

有一个绿色的珠子

而B平方 R G对应的

系数是多少呢

在这样一个多项式中

我们刚好发现

它的系数就是2

意味着有两种不同的方式

通过演示我们也确实发现

我们可以有这样

两个黑珠子的排列

另外我们也可以有

另外黑珠子的排列

通过这样的表达我们会发现

其实母函数和

波利亚定理如果结合

就可以更细致

去寻找对应的方案数

如果把原来的波利亚定理中

M的CPI次方进行改变

就会发现

每一个m的C(pi)次方里面对应的

项可以完全打开

这里面对应的m

实际上是着色方案

如果有可能是一个珠子

自己保持同样颜色的话

可以用B1加B2一直累加下去

他们对应的CP1次方

接着如果是两个

二阶循环

二阶循环意味着

循环括号内要取同色

那这时候我可以来写

就是B1的平方项加上B2的

平方项一直累加到BN的平方项

对应外面此幂就应该是

二阶循环的个数

依此类推

这时候我们已经把原来的

波利亚定理改成了

带有母函数形式的波利亚定理

利用这样的式子

就可以求解更多更多的问题

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

也许你还感兴趣的课程:

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