当前课程知识点:组合数学 > 初识母函数 > 母函数与递推关系 > 偶数个5怎样算
下面呢 我们来分析另外一道题
我们想要求在n位十进制数中
出现偶数个5的 数的个数
这道题目一看 大家似乎觉得毫无头绪
什么意思 n位的十进制数
也就是说一共有n个位置
它每个位置是0123456789
当然第一位它不能取0
在这样的数字中
它要出现偶数个5的数字才能算一个
比如说它出现35 25 几几几几几
其中两个5 那么它就算出现偶数个5
怎么来分析这道题呢
首先我们在想
是不是有可能从递推的思路来表示它呢
对应于一个数字它是否出现偶数个5
我们可以从一个n减1位的数字
往后再来区分
比如说假设我们现在有n减1位
p1 p2 一直到pn减1
那么我们想拼出一个n位数字
可以在后面再加一位
那加的这一位到底是不是5
就会有一定的影响了
假如说我想求的是偶数个5
那n减1位中如果已经包含了偶数个5的话
最后一位就不能再是5了
同样如果它的前面是奇数个5的话
那么它最后一位就必然应该是5
所以我们发现
我们可以把所有的分类考虑在内
也就是说前面n减1位到底包含了奇数个5
还是偶数个5
那我们可以分析它具体的递推方案
也就是说在这里我们分析到
可能是有奇数个5或者偶数个5
那我们用两个序列来进行表示
比如说an表示的是在n位串中
出现偶数个5对应的数目方式
bn表示在n位的串中
出现奇数个5对应的方式
那么利用这两个式子
我们来建立它的递推关系
首先我们分析一下
an可不可以用更小的n减1位串来得到呢
an表示的是偶数个5
如果说在n减1位当中
已经有偶数个5了
那么后面一位 它必然不能再取5
因此这样的表示下
它应该是9倍的an减1
剩下的如果它们前面n减1位
已经有奇数个5了
最后一位我只要在添一个5
它就是偶数个5
在这个情况下
它的个数应该是bn减1
因此an可以等于9倍的an减1加上bn减1
类似的对于bn 同样有这样的递推关系
bn也等于9倍的bn减1加上an减1
有了这样两个联立的式子
我们就可以利用递推的母函数方法进行求解
所以这时候
我们已经得到了一个递推的联立方程组
那么除了这个递推关系之外
我们还需要有一个初始值
实际上我们分析一下
对应于初始值
a1表示的是一位数中没有5的
也就是5出现偶数次的有多少个
那就意味着这一位数不能是0
也不能是5
所以有八种可能性
而对应于b1它表示的说是
一位数字中5出现奇数次的也就是说
出现了一次 那么b1也就是等于1
有了这样一个联立的递推方程组
和我们的初始值
我们就可以进一步的
去求解每一个递推关系了
首先我们还是按照原来的思路
我们利用这样的递推关系
给它对母函数进行一般的加法
这时候根据递推关系
这里ax对应的是x的n次方
而这里9倍的an减1
如果也要乘以x的n次方的话
它会差一个9x
因此我们用ax减去9x
来得到对应这一项和这一项 而bn减1
实际上如果我们两边都乘以x的n次方的话
这里会对于原来的母函数
多了一项x
所以这里我们再减掉x bx
通过ax减去9x ax 减去x bx
我们的右端可以配上这样一个递推关系
我们来分析一下
可以看到进行联加之后
左边实际上等于1减去9x乘以ax
还有一项是减去x bx
而右端项呢 右端项a1直接等于a1
而这边变成了a2减去9倍的a1减去b1
a2就等于9倍的a2加上b1
因此这一项x1次方的系数等于0
x2次方的系数呢
a3减去9倍a2 减去b2
实际上这一项也是满足递推关系的
也等于0
依此类推 因此右端项只剩下了第一项a1
而a1就是初始值 得8
因此我们就可以计算出来这样ax bx
母函数联立的一个方程式
而同样如果我们并不知道
直观的计算这样ax bx的时候
我们仍然可以利用母函数的定义 依此类推
比如说x对应的它的方程里面系数 a2
x平方对应的是a3
x3次方对应的是a4
依次呢累加起来
我们的左边同样也是
ax和这里面只是差了一个a1
所以变成了ax减8
而右端项呢 右端项这边我们看到了
它是9倍的a1x 原来我们对应的实际上
要从a1开始的话
我们这边是x0次方
所以这边多了一个9x出来
因此这一列对应的是9x乘以ax
而这边b1 b2 b3
对应的x x平方 x3次方
这里面我们实际上对应的是x乘以bx
因此这两个式子
实际上通过两种方法得到了同样的答案
也就是说综合第一个式子
我们就可以联立出来
对应于ax bx这样的母函数它们的形式
1减9x 乘以ax 减去x乘以bx等于8
同样我们针对第二个式子
bn的它的一个递推关系
联立原来的母函数
同样可以得到关于bx的一个方程
这两个式子实际上对应的就是
母函数的一个联立方程组
联立方程组可以进一步的求解
我们把大AX 和大BX
就变成变量来进行求解
通过提取它们对应的系数的行列式
就可以计算出来它们的相应的解
这里我们计算它的行列式
相当于是1减9x 负x 负x 1减9x
大家都知道行列式的计算
应该是这两点相乘减去这两点相乘
答案就是1减8x乘以1减10x的结果
而对应的ax的解
就应该是用行列式的作为分母
而对应的右端项作为替代它的系数8和1
这边x 负x 1减9x不变
因此这样联立
它的行列式除以它的系数行列式
就可以算出ax的取值是什么
ax我们计算出来
再去计算bx
bx也可以通过类似的方法得到
因此我们可以知道
ax是等于这样一个复杂的式子
这个式子我们需要进行化成部分分式的形式
具体的过程呢我就在此省略了
告诉大家答案是ax化成部分分式以后
等于1/2乘以7除以1减8x加上9
除以1减10x
那么这个式子
它实际上就等于
7乘以8的k次方xk次方的累加
这个式子
就等于9乘以10的k次方xk次方累加
因此我们就可以得到ax对应的系数
注意 这里面我们再次强调
大AX我们的设计呢 和前面稍有区别
并不是从a0开始的
我们是从a1开始
因此a1对应的是x0次方
a2对应的是x1次方
a3对应的是x2次方
这里面所有的ak呢
在这里的系数就应该要对应减1
ak就等于7/2 8的k减1次方
加上9/2 10的k减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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验