当前课程知识点:组合数学 >  神奇的序列 >  指数型母函数 >  指数型母函数的应用

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

指数型母函数的应用在线视频

指数型母函数的应用

下一节:错排1

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

指数型母函数的应用课程教案、知识点、字幕

刚才我们分析了其实指数型母函数

主要它的来源就在于

可以处理多重排列

而我们曾经说过

多重全排列实际上是

所有的元素都必须用到

那么就应该是

n的阶乘除以n1阶乘 n2阶乘

依次累除下去

其中n就等于所有n1加n2

所有的总和

那么对于多重排列

实际上它少了一个字

也就意味着它

不是所有的元素都拿来

那个时候呢怎么来处理

我们就必须要用到指数型母函数

也就是Ge(x)

这里面我们每一个元素都要

找到它的通项是

x的k次方除以k的阶乘

因此对于第一个元素它的

指数型母函数可以写成

1加上x除以1阶乘

加上x2除以2阶乘

一直累加到xn1次方除以n1阶乘

对于第二个元素

第三个元素都是一样可以处理的

所以可以总结看到

实际上指数型母函数

具有一定的优越型

它可以非常直观地

去解决多重元素的排列

所以我们会发现实际上我们可以

来处理一些数字串的问题了

比如说我有4个数字

1 2 3 4

它呢构成了五位数(中?)

但是有一定的要求

它要求数字1出现的次数不超过2次

但是不能不出现 2出现的

次数不超过1次

3出现的次数可以达到3次

也可以一次都不出现

而4出现次数必须是偶数

大家看到这样的题觉得

这个太复杂了

这么多不可思议的条件

但是实际上用指数型母函数

就可以迎刃而解了

所以我们可以看一下

这道题目虽然条件非常复杂

但是用母函数来一次进行表示的话

其实也还不算太难

我们假设满足条件r的位数是ar

那么序列a0 a1

一直到a10的指数型母函数

就可以这样来表达

gex等于第一个数它对应的母函数

这里面它有个要求

它说不超过两次

那意味着最高项只能是

x平方项除以2阶乘

注意

因为是排列

所以我们要用的母函数

通项必须要除以k阶乘

还有一个要求它说不能不出现

也就是x0次幂不能有

它只能出现一次和两次

对于2来说

它说不超过一次

那意味着就出现0次或一次

对于3来说

它说可达3次

那意味着最大是3

但是可以是0

可以是1

可以是2

对应于4

它说出现次数是偶数

这个一般情况下我们会觉得

非常难以表达

但是在指数型母函数中非常方便

无非就是0次 2次和4次

这个式子如果求得它的系数的话

对应的不就是ar吗

那么我们依次累乘下去

会发现第一项和第二项一乘

然后依次第三项和第四项进行相乘

接着两项再分别相乘

乘出来以后

我们看出来对应的它

已经产生了一个对应的母函数

但是我们要求什么呢

我们要求的这个系数ar

实际上应该是x的r次方

除以r阶乘上面的分子个数

那么我们要整理一下

要把它每一项做成x的k次方

除以k阶乘的样子

比如说我们现在想要找五位数字

那就是要对应的去找

x5次方除以5的阶乘前面的系数了

所以答案就应该是215

刚才我们来看了

五位数字怎么用

指数型母函数

如果是n位数字呢

我们看这样一道题

一共有1 3 5 7 9这五个数字

它组成了一个n位串

那么请问有多少个这样的串呢

但是我们要求这里面3和7出现的

次数必须是偶数

对于其他数字1 5 9

我们不加限制

该如何做这道题呢

根据题意其实我们就可以直接地

列出它对应的指数型的母函数

我们说到一共有五个数字

是1 3 5 7 9

其中3和7是有约束的

它说3和7必须是偶数

那这时候偶数刚才我们就知道了

直接就是0项 x平方项

x4次方项

依次累加起来

所以对于3和7它们的母函数

都应该长这个样子

而对于其他的数字

是没有约束的

因此就是一个1加x加x平方

除2阶乘

加x3次方除以3阶乘

因此有三个数字

所以要进行一个三次方

这就是我们对于这道题目的

指数型母函数

有了这个以后

我们就可以进一步的展开了

由于我们知道对应于系数为1的

指数型母函数

它的通项就是e的x次方

所以这里面这一项

它就可以直接表达成e的x方

但是前面的这个该如何表示呢

我们怎么样才能去掉

它对应的奇数项呢

我们如果仔细想一下

会记得

对应于如果这个里面要

把x变成负x的话

相当于这里x添了一个符号

那对于奇数项它前面的符号就是负

而对于偶数项它前面符号就是正

那这两个如果进行相加减的话

就可以消掉奇数项或者是偶数项

这里我们直接就可以知道

把两个ex和e的负x相加以后

再除以2

自然而然就把对应的奇数项

全部都消掉了

只剩下偶数项

所以对于3和7的母函数

也直接可以用ex和e的

负x直接表达出来了

有了这个式子以后

我们再代入到原来的Ge(x)

前面这一项就相当于

1/2ex加上e的负x的平方

那么我们把1/2提出来

变成了1/4

里面就剩下了ex加e的负x平方

后来一项因为每一项

都等于e的x次方

它的三次方就等于e的3x次方

依次我们把这面e平方

ex次方加上e负x次方的

平方项展开之后

得这个式子

最终我们把e的3x累乘进

括号里面

就得到了一个新的答案

就是1/4乘以e的5x

加上2倍的e3x

加上e的x次方

对应于这个e的5x次方

它相当于就是序列是5的

那么我们可以直接累乘

这里面相当于每一个通项

是x的n次方

除以n阶乘

这里面前面的系数是5

对应于它里面的每一个x呢

都会变成了5x

因此对于xn次方

前面自然要带一个5的n次方

这里也是一样的

e的3x次方

相当于3的n次方

乘以xn次方

再除以n阶乘

依次类推过去

我们把所有的xn次方

除以n阶乘前面的系数提出来

就变成了系数是5的n次方

加上2乘以3的n次方

加上1

通项是xn次方除以n阶乘

当然不要忘了前面还有一个1/4

这时候答案就一目了然了

an意味着有这样约数的一个n位串

它的个数等于1/4乘以5的n次方

加上2乘以3的n次方加1

这也就是答案

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

指数型母函数的应用笔记与讨论

也许你还感兴趣的课程:

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