当前课程知识点:组合数学 > 神奇的序列 > 指数型母函数 > 指数型母函数
我们介绍了母函数的概念
下面我们再回头看看二项式定理
我们知道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算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验