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

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

指数型母函数在线视频

指数型母函数

下一节:指数型母函数的应用

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

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

我们介绍了母函数的概念

下面我们再回头看看二项式定理

我们知道1加x的n次方它展开之后

每一项等于什么呢

其实每一项就正好是组合数C(n,k)

所以C(n,k)的母函数就是

1加x的n次方

那这时候大家就会觉得

母函数实际上对应的是在求组合的

那么有没有可能我们也去求排列呢

我们分析一下组合的概念

组合无非是说拿几个小球要放到

相同的盒子里

那怎么才能把它变成一个排列呢

只要我们给盒子打上标号就可以了

这就意味着其实排列和组合无非

就只差了一个标号方案数

所以C(n,k)乘以k的阶乘

就等于P(n,k)

那既然C(n,k)可以嵌入到

这样的1加x的n次方里面

我们是不是也可以把P(n,k)嵌进去呢

回头再看

其实在1加x的n次方里面

我们每一项每一项要么选1

要么选x

这时候如果我们再去回头想

能不能让这些x变成排列呢

我们只要给它打上个下标

就出来排列了

既然如果选择k的x的话

我们只差一个k阶乘的下标方案数

那么回头再看1加x的n次方

它原来是说数系数是C(n,k)

这时候我想把P(n,k)嵌进去

无非上下同乘k阶乘就可以了

上面的分子C(n,k)

乘以k阶乘就是P(n,k)

那下面的分母呢

多了一个k的阶乘

这时候我们把k阶乘留下

发现x的k次方除以k的阶乘就

变成了一个放位置的地方

那我们发现1加x的n次方

也可以去包含P(n,k)

所不同的是它后面不再是

x的k次方了

而是xk次方除以k阶乘

这时候我们实际上引入了

一种新的形式

如果想要计算排列的话

我们的通项不能再是x的k次方

而应该是x的k次方除以k的阶乘

那么我们来看一个下面的例子

其实这个例子我们以前就见过到了

对于乒乓ping pang来说

这些字母是可以重复的

有多少个不同的排列

当时我们说这个叫做多重全排列

因为我们所有的字母都要同时用上

回顾一下

我们怎么做的呢

那个时候就是分别把不同的字母

给它加上标号

就变成了p1 p2 n1 n2

因为你一共有8个字符

而且有两个相同

两个相同

因此我们只要算8阶乘除以2阶乘

2阶乘

2阶乘

就可以算出来多重全排列

但是如果我再仔细问一下

对于3个a1

2个a2

3个a3来说

要组成k个数字的组合有多少种呢

所以这个时候我们用母函数

来计算组合

对于a1来说

它要么是0个

要么是3个

所以我们可以用

1加x加x平方加x3次方来表示

对于a2来说呢

它有两个a2嘛

所以要么就是

1加x加x平方来表示a2的母函数

对于a3也是有三个

所以是1加x加x平方

加x3次方

那么我们把它进行累乘

第一项和第二项相乘以后

得到了一个这样的一个多项式

1加2x加3x平方

加3x3次方

加2x4次方

加x5次方

之后下一步再这样

两个多项式进行相乘

我们就得到了一个这样

复杂的一个多项式

当然对应于它的系数

就是组成k个数的组合数有多少种

通过刚才计算我们得到了

一个这样的复杂的式子

它代表的就是组合的方案数

但是同样大家却好奇了

那每一个组合到底长的什么样子呢

我们来分析一下

我们有了一个组合的母函数之后

我们就会想

到底那每一个组合里面它的

样子是什么样子呢

这里我们有3个a1

2个a2

3个a3

那么我们拿一个例子来看

比如说就是取4个进行组合

那么我们就看取4个其实

就蕴含在这10的x4次方里面

那意味着如果我要从这3个元素中来

取凑成4个元素的组合

它的组合方案数是10

那这10个方案都该长什么样子

我们实际上是原来的展开式

可以得到的

比如说我们不再用一样的x来表示

而用x1来表示a1

用x2来表示a2

x3来表示a3

这时候在进行多项式相乘的时候

每一个a1 a2 a3都可以有

不同的代表了

比如说在这里面我们

先还是第一项和第二项进行累乘

得到了一个这样比较长的式子

之后这个长式子再和

最后一项进行了累乘

累乘之后的结果有一点长(老师好萌啊)

但是我们仔细看

我们想要的实际上是x的4次方

所以这里x4次方就

一共有这么10项

当然每一项里面都告诉我们了

每一个组合长什么样子

比如x1 x3的3次方

表示a1有一个

而a3有三个

这里x2 x3的3次方

也同样类似表示a2有一个

a3有3个

刚才我们通过母函数已经知道了

组合会长什么样子

那自然我们会想一想我们

能不能知道排列有多少个呢

比如说3个a1

2个a2

3个a3

我们从中间选出4个

选出4个的这种多重排列

注意

已经是多重排列了

不再是多重全排列

不是所有的元素都拿来了

这时候我们只从8个元素中取了4个

请问这样的多重排列能有多少个呢

那我们回头再从

刚才看到的组合出发

比如说我们看到有一项

是x1平方乘以x3的平方项

是4个元素

两个a1

两个a3

这时候我再看这个问题的时候

它是4个元素两两、两两相同

进行多重的全排列

因此我们可以直接用4的阶乘

除以2阶乘2阶乘就表达出来了

同样对于其他的式子我们都可以

列出来所有对应的枚举

利用这样的一种思路

利用多重全排列对应到

组合中每一项

我们就可以计算出所有的多重排列

所以呢我们想要求所有的排列

实际上我们还是可以从

对应组合生成的母函数出发

比如说我们可以看

这里面我们不同的排列可以

分项来处理

我们看一下

对于这一项一共有1个a1

3个a3

那实际上如果想要做出

它的排列的话

无非就是一个可重的全排列

那一共是4个元素进行全排列

再除以分别的标号方案数

因此我们把4的阶乘全部都提出来

之后再除以它标号方案数

在第一项x1和x3次方

对应的标号方案数

就是1的阶乘乘以3的阶乘

与此类似

x2 x3对应的是这一项

x1平方x3的平方项

对应的是1除以2阶乘2阶乘

这时候我们就可以相应地

把所有的可重排列

全部列举出来了

这些整理之后就变成了

4的阶乘乘以4除以3阶乘

加上3除以2阶乘

2阶乘加上3除以2阶乘

之后我们进一步的整理

就会发现实际上它的答案就是

16加上18加上36

等于70

那这时候我们是不是

可以回到最原始的母函数呢

我们如果并不区分

所有的a1 a2或者是a3

我们就用x来代替

这时候有没有办法呢

我们回想一下

实际上在这里我们为了方便计算

可以像一开始分析的

我们直接把k的阶乘写到

这个通项位置上

那么在这里我可以用Ge(x)(请忽视口误)可以

表示成1加上x除以1阶乘

加上x平方除以2阶乘

加上x3次方除以3阶乘

这个里面就已经包含了对应的

a3它的方案数

如果我这里已经除以了3的阶乘

那自然这前面就已经是

它的排列数了

对应第二项a2它也有

这样一个表达式

对于a3也有类似的表达式

所以可以看到我们这里就用到了

一个新的通项

也就是用x的k次方除以k的阶乘

作为这一项

而它的系数呢

就作为它的对应的排列方案数了

我们把第一项和第二项进行累乘

再乘以第三项

我们就把这所有的式子

就可以列出来了

而真正在计算答案的时候

我们会发现

它的通项实际上还是应该包含有
这时候我们这样一个特殊的母函数

它的通项实际上还是应该包含有

xk次方除以k阶乘的

因此答案是xk次方除以

k阶乘前面的系数

因此回到我们最后一开始的问题

我们问到对于4个元素

它进行的一个多重排列有多少个呢

就应该答案是x4次方

除以4阶乘前面的系数

也就是70

这和我们刚才通过每一项

每一项分别打开计算

得到的结果是一模一样的

刚才我们进行一系列推演发现

其实母函数如果变换一下样子

把它的通项变一下

也许就会有新的结果

我们回头看

在原来的普通型的母函数的定义中

我们看到了它的通项就是x的k次方

但是刚才我们进行计算排列的时候

实际上用了一个新的东西

那这时候它就不再叫做母函数了

我们将它称之为是指数型的母函数

通常情况下

为了和普通的母函数G(x)相区别

我们用Ge来表示

那么具体它们样子上

有什么不一样呢

在普通型的母函数中

我们用的通项就是x的k次方

但是在指数型母函数Ge中

我们用的是xk次方除以k的阶乘

这两个母函数都是母函数

它们有不同的功能吗

确实是

实际上正如我们一开始

给大家分析到的

普通型的传统G(x)的母函数

它主要解决的是组合

里面是没有顺序的

但是对应于我把

标号方案数除掉了之后

下面处理的问题实际上是排列

而且我们知道

如果我们翻书看一下

对于e的x次方它有一个泰勒展开式

它的泰勒展开式实际上就正好是

∑i从0到无穷大

其中每一项通项就是

x的k次方除以k阶乘

但它的系数为1

所以我们可以说对于指数型母函数

我们照样能够找到一个

基准的泰勒展开式

也就是e的x次方

它的系数对应的是1

因此对应ex次方就是序列

全为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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

指数型母函数笔记与讨论

也许你还感兴趣的课程:

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