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

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

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

母函数型Polya定理(4)

下一节:图的计数

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

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

刚才我们看的都是立方体

一些旋转

现在我们看一个稍微有点

不太一样的例子

我们这回是拿字母

比如说我有四个标有字母的球

他们是可以重复的球的排列

比如说有两个球被叫做A

两个球被叫做B

AABB这四个球

要放到三个不相同的盒子里

方案数是多少

同样我如果再进一步

如果我们要求不允许有空盒的话

有多少种不同的方案

我们其实可以先放A再放B

如果先放A

无非就是两个元素要

放到三个盒子里面

两个相同元素放入三个不同的盒子

实际上我们用隔板法

就可以算出来

就是C2加3减1

答案就是6

这是A的方案

B的方案与它是一样的

所以根据分布的乘法法则

具体的答案就是

6乘以6等于36

这时候有可能有空盒

我们可以用容斥原理

把不允空盒子的情况

全部排除出去

也就是对应的C(4,2)的平方

36减去有一个空盒

一个空盒3种不同的选择

我可以有三种不同的选择

再乘以剩下的元素

放入两个盒子中

也就是C(3,2)的平方

对应于我可能还要补回来

有两个空盒子的情况

我再把它加回来

然后再减出去

最后的答案呢

我们利用容斥原理得出的答案是

要是允许它不能有空盒

它的答案是12种

这时候我们想这个问题是不是

也可以用波利亚定理来求解呢

我们来分析一下

刚才我们用传统容斥的方法

来把AABB放入三个

不同的盒子里面

而且不允许有空盒

现在我们用母函数型的

波利亚定理来求解

首先先把这四个球区分开

我们用A1 A2

B1 B2来表示

相当于把四个球放入三个盒子

就可以抽象成给

四个球进行三着色

这时候我们进行三着色的时候

因为A1和A2他们是一样的

因此它们可以看成

一种等价关系

所以我们建立这样群体的关系

G等于单位元

E以及A1 A2

A1 A2可以互换

B1 B2

B1 B2可以互换

以及

A1换A2

同时B1换B2

这样的约束条件下

我们实际上建立了

AABB的定量关系

这时候求对应的三着色

他们上面的三着色

首先对于E来说

它实际上一共有四个元素

每个元素都是一阶循环

而每个元素因为有

三个盒子可以去

可以抽象成三着色

因此是3的4次方

再加上第二个对应的

循环是2乘以3的3次方

因为第二个和第三个

他们长的样子是一模一样的

最后一项实际上对应的

是两个阶乘

每一个循环内部都是

有三种不同的颜色

因此是3的平方

再除以对应的置换个数4

答案是36

这时候我们也可以

利用母函数型把它依次打开

第一项中

每一个一阶循环就是

R加B加G三着色

一共有四个这样的情况

再加上第二项它可以有首先是

一个二阶循环

R平方加上B平方

加上G平方

剩下两个一阶循环

R加B加G的平方

一共有两个这样的东西

所以前面的系数乘以2

再加上后面的R平方

加上B平方加上

G平方的平方项除以4

对应我们想要求

要这展开中取

R的I次方

B的J次方和G的

K次方项的话

要求I J K必须大于零

我们就可以列出来

R1B1G2的系数和

R1B2G1的系数以及

R2B1G1的系数都相等

代入到上面的式子里面

就等于从四个里面挑一个

然后再乘以后面的C(3,1)

再乘以C(2,2)

再加上从这个里面的项

我们也可以找到一项

就是2的C(2,1)

同时再除以4

答案就是4

对于要求不允许空盒

上面这三种情况

已经完全枚举出来了

因此若不允许空盒

它的分配方案数就应该

每一个种类它有4种

在乘以三个种类

因为是4乘以3等于12种

我们用了相对比较另类的方法

把AA BB这样的

关系做成了群

利用置换上进行着色

得到方案数

和容斥原理得到的

答案是一模一样的

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

也许你还感兴趣的课程:

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