当前课程知识点:组合数学 >  初识母函数 >  母函数与递推关系 >  偶数个5怎样算

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

偶数个5怎样算在线视频

偶数个5怎样算

下一节:偶数个5怎样算(2)

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

偶数个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算法

--程序支持与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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

偶数个5怎样算笔记与讨论

也许你还感兴趣的课程:

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