当前课程知识点:组合数学 > 线性常系数递推关系 > 线性常系数齐次递推关系 > 特征多项式
我们再看
汉诺塔里面有没有同样的现象发生
实际上在汉诺塔里面
它的递推公式一开始并不是一个齐次的
它的右端项为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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验