当前课程知识点:组合数学 > 神奇的序列 > 指数型母函数 > 指数型母函数的应用
刚才我们分析了其实指数型母函数
主要它的来源就在于
可以处理多重排列
而我们曾经说过
多重全排列实际上是
所有的元素都必须用到
那么就应该是
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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验