当前课程知识点:组合数学 >  线性常系数递推关系 >  线性常系数齐次递推关系 >  特征多项式

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

特征多项式在线视频

特征多项式

下一节:母函数与特征多项式

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

特征多项式课程教案、知识点、字幕

我们再看

汉诺塔里面有没有同样的现象发生

实际上在汉诺塔里面

它的递推公式一开始并不是一个齐次的

它的右端项为1

我们通过相减

就把右端项减掉

所以产生了hn

等于3倍的hn减1加上2倍的hn减2等于0

那么通过刚才的分母进行变换的话

我们这样做出来是1减3x加上2x平方

等于1减x乘以1减2x

这个我们当然可以通过代入

x的负1次方求出来了

但是我们这时候仔细看

如果对应的Cm

在这里变成是m平方减去3m加2

同样和这个递推关系系数对应 阶数对应

那是不是有可能我们根本不需要

再拿x的负1次方代进去去求解了

直接从递推关系

就可以找到对应这样一个Cm的式子呢

所以根据我们线性常系数齐次递推关系的定义

我们有an加上C1

an减1加上C2

an减2一直累加到Ck

an减k等于0

那么还是套用原来的套路

我们是不是可以建立它的母函数呢

比如说我们假设gx是an序列的母函数

那么gx它就可以表达为

a0加a1x一直累加an的xn次方

a1作为它的系数存在在母函数里面

原来我们遇到这种情况

通常会通过一系列的累加得到母函数

对应的一个表达式

我们同样可以这样做

比如说对于xk次方

它可以利用刚才定义中的递推关系得到

xk次方乘以ak加上c1a减1

ak减1加上C2ak减2一直累加到CKa0等于0

同样对于xk加1次方

也可以写成这样的表达式

一直累加到x的n次方

这样我们可以两边分别相加

第一项我们看一下

实际上它是xk次方乘以ak

xk加1乘以ak加1

和原来的母函数对比看

实际上就是少了前面的k减1项

所以第一列它们的累加和

实际上就等于gx减去∑aixi

i从0到k减1

对应于第二项呢

我们会发现

它对于的是ak减1乘以x的k次方

和原来的母函数相比

它实际上多了一个x次方

那实际上我们通过可以把C1和x提出来之后

里面就变成了gx减去aixi

i从0到k减1

后面的若干项依次累加

我们就得到了右端项等于0

有了这样一个式子以后

我们就可以把gx整理出来

我们看一下

gx乘以1加C1x

加上C2x平方

一直累加到Ckxk次方

就会等于右端的所有的常数项

和gx无关的那些项累乘

有了这个式子

实际上gx就有了新的表达

对应于gx它就可以等于右端的这一项

如果我们统一用px来表示的话

我们分析就可以得到

其实px这样一个多项式

它次数肯定是小于等于k减1的

而右端gx这里

它乘以的系数

也就是gx等于px除以分母这样一个多项式

这个多项式实际上它的次数实际上是k次的

因此gx可以表达成px除以1加C1x加C2x平方

一直累加到Ckxk次方

这个式子我们看

是不是可以转换成刚才我们说到的

1减ax乘以1减bx类似的情况呢

这就依赖于我们

要把这样一个分母进行好好的分析

我们要产生1减x这样的样子

我们需要怎么做呢

我们为了这样一个性质的话

需要把x变成x的负1次方

在这里我们就把x的k次方提出来之后

用m来代替x的负1次方

因此分母中间和m相关的

就变成了Cm等于m的k次方

加上C1mk减1次方

一直累加Ck减1m加上Ck

这个系数我们可以把它进行因式分解

因式分解后

Cm有若干个根

包括a1、a2 一直到ai

甚至某些根呢不一定是一重根

有可能是多重根

所以Cm可以表达为m减a1的k1次方

乘以m减a2的k2次方

一直累乘m减ai的ki次方

其中k1加k2

也是它根的重数之和是等于k的

有了这个式子以后

我们继续代回来

实际上分子是不动的

而分母就已经可以写成1减a1x的k1次方

乘以1减a2x的k2次方

一直累乘 1减aix的ki次方

有了这样一个式子以后

我们实际上就可以把它

变成1减ax分之待定系数

再累加多少多少

所以我们可以看到

实际上通过这样的分析

母函数完全可以变成若干个泰勒展开的

1减ax分之若干的一个累加形式了

真正的关键在于中间它的分母进行了变换

用m等于x负1次方来代替了x

从而我们只需要把Cm进行因式分解的话

就可以找到1减a1x 1减a2x它们的系数为何

但是是不是我们每次做题

都需要走这样一个过程

来去把这个1减C1x来转换呢

我们回头看一下会发现

实际上最一开始的递推关系是an加上C1

an减1加上C2,an减2一直加到Ckan减k

和我们现在的这个Cm式子完全一一对应

对应的它的阶次和它对应的这个m的多少次幂

完全是一一对应的

比如说假设这个an减k

对应的是常数项Ck的话

那么它的前一项就应该是依次类推

直到最高项

它这里实际上就应该是k次

而这里C1an减1 这里就是C1mk减1

C2an减2 这里就应该是C2mk减2

依此类推

所以只要我们知道了它的递推关系

我们就可以直接地写出来这个Cm的表达式了

这就告诉我们

也许递推关系给我们一种直接的求解方法

所以到此为止我们会发现

线性常系数递推关系除了有它的递推关系

有它的初始值之外

还有一个非常重要的东西

只要我们知道了它有这样的一个线性递推关系

我们直接就可以写出一个表达式

这个表达式被称为是特征多项式

这个特征多项式和它的递推关系一一对应

对应于我们可以看到

有这样一个递推关系

只要我们把它阶次对应于相应的幂次

然后把它系数照抄过来

就可以产生它的特征项目式

也就是Cx

那么我们来拿例子直接看一下

比如说在斐波那契中

fn减去fn减1

减去fn减2等于0

它的特征多项式是什么呢

直接是它是一个二阶的

所以它对应的第一项fn就应该对应x平方

fn减1对应xfn减2等于1

所以这时候它的特征多项式直接写出来

就是x平方减x减1等于0

而汉诺塔呢

也是一样的

汉诺塔的关系是

hn减去3倍的hn减1加上2倍的hn减2等于0

同样 同学们也可以想

它对应的特征多项式就是

x平方减去3x加2等于0

有了这样一个特征多项式之后

所有的线性常系数递推关系

都可以非常容易的迎刃而解了

我们下节就会给大家介绍

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

特征多项式笔记与讨论

也许你还感兴趣的课程:

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