当前课程知识点:组合数学 > 组合之美 > 组合之美之线性常系数递推关系 > 组合之美之线性常系数递推关系
下面我们给大家回顾一下
线性常系数齐次递推关系
说到什么是线性常系数
齐次递推关系呢
无非它的定义就是这样的
它实际上就像一个多项式
那么它的右端项等于零
这时候我们实际上就说
它是满足一个线性的累加和
同时它的系数都是常数
而右端项都是零
对于这样一个递推关系只是表征了
它对应的有一个递推累加的关系
那么真正要把它求解出来
还需要有另外一个要素
也就是初始值
对应于这样一个值
比如说多项式来说它是有k阶的
那我们初始值也需要要有k个
有了这样一个定义之后
我们用什么方式来求解呢
实际上我们引入了一个叫做
特征多项式的概念
特征多项式和原来我们对于
递求关系是完全一一对应的
只是把对应的一个k阶的
一个多项式把它倒过来
变成了x的k次方加上系数乘以
x的k-1次方
依次向后等于零
这个特征多项式非常有用
因为我们实际上是根据
特征多项式的根来进一步求解的
对于我们特征多项式摆在这里之后
我们可以把它分成三种不同类型
比如说它的所有的根中对应的
全部都是不相同的实数根的话
那么我们直接可以套用公式
写出它对应的特解是什么
如果说它并不是全部都不相同
它里面有重根出现的话
我们就要看它的重根是多少重
对应于这样一个特征根前面
我们还需要用一个多项式
作为它的系数
如果对应的出现有虚数根呢
如果有虚数根的话我们同样用
对应的虚数可以表达出来
每一个特征值
在真正的回顾这些概念之前
我们还是去看一道作业题
这道题是我们的一道思考题目
它实际上说了一件事情
也就是多米诺骨牌的完美覆盖
在这里多米诺骨牌是1乘以2的
长方形
这样的一个长方形如果有
若干个的话
那么我就想把它摆在
一个3乘以m的这样一个路上
这时候我就问你
有多少种不同方案的
多米诺骨牌的排列方案呢
当然实际上在《编程之美》
这本书中也讲到了这个问题
它呢也是用的1乘以2的
多米诺骨牌
但是它又变化了形式
不是3乘m的
它问的是2乘m的这样一条路的话
如果用多米诺骨牌去摆
有多少种不同的方案
当然最后计算下来刚好就是
斐波那契数
所以其实在组合数学中
有一类问题被称为是铺砖问题
它就是去求解对应于
这样的多米诺骨牌啊
或者正方形 长方形甚至是
三角形形状的这样一些砖
怎么能够铺在一个长条形的路上
那么下面呢
我们来看这样一道题目
实际上这道题目就是最早
研究斐波那契数的
印度学家提出的一个装箱问题
也就是对应了我有
1乘以1的小方块砖
同时我还有1乘以2的多米诺
这时候我问你有多少种不同的
方案可以铺满这个1乘以n的
对应的道路呢
大家看到这里觉得挺容易的嘛
对应是什么呢
对应无非就是看最后一块砖
是不是一个多米诺砖呢
如果是多米诺砖的话
它对应的方案就应该是Fn-2
如果最后一块砖正好是小的
1乘以1的方砖的话
它对应的就是Fn-1
因此它的我们的方案数就应该
是Fn等于Fn-1加上Fn-2
然后我们再去计算它的初值
就可以了
这就是斐波那契数一部分
但是如果我把这道题变得
更复杂一点呢
我想问你所有的这么多的
铺满路的方案中
会用到多少块砖
也就是我要问所有方案的
总砖数是多少
我们来进一步的分析一下
这时候我们接着上一问
刚才那问我们已经知道它对应的
递求关系就应该是an等于
an-1加上an-2
那么通过初值的计算
我们计算出来对应的它的an的
方案数就应该等于对应的
斐波那契数中间的fn加1
也就是根号五分之一α n加1
减去β n+1
有了这个以后呢
我们来看第二问
也就是所有方案数中的
总砖数是多少
刚才我们已经用AN表示了方案数
接下来我们用BN来表示总砖数
同样我们还是拿最后一块砖
进行分类
我们会发现最后一块砖
如果是小方砖的话
我把所有的最后一块砖都是
小方砖的方案全部列在这里
会发现其实前面无非就是
所有的砖数就应该等于
长度为n-1的所有砖数
因此是b n-1
那么它一共会让再加上多少块砖呢
后面每一个砖都是多加一块
它一共有多少个方案意味着
我就会多加多少个小方砖
这时候一共的方案数就应该是
a n-1的方案数
那么另外如果最后一块砖刚好是
1乘以2的多米诺砖呢
那么前面对应的就应该是b n-2
而后面应该加多少块多米诺砖
就意味着应该加a n-2的多尼诺砖
那么把方案全部写出来
bn的方案数就应该等于B n-1
加上a n-1 b n-2
加上A n-2
这时候a n-1 a n-2 都是
符合刚才an的递推关系的
因此我们整理一下
BN就应该等于BN减1加上BN
减2加上AN了
那这个时候我们回头再一看会发现
这不是我们传统意义上的
线性常系数齐次递推关系了
只是它的递推关系后面除了
BN等于BN减1加BN减2之外
还有多了一个AN项
而AN又是符合一个递推关系
我们知道AN如果求解出来
因为等于FN加1的
那应该怎么去做呢
我们也可以去把AN全部消掉
这时候我们用另外一种方法
我们希望觉得an实际上它
也是满足递推关系的
而它的递推关系
和BN BN减1
BN减2完全一样
系数是一样的
只是它还需要多一个AN的
特征解而已
因此我们说对应于BN等于
BN减1加BN减2这一部分
它的对应的特征根可能也是
对应于α和β
那这时候我们用另外一种方法
假设α和β是特征根
对应于它的特解
因为它的右端已经有了AN对应的项
因此我们把它特解写成是AN乘以
αN次方加上CN乘以β的N次方
这是它我们拿出来的一种解的模式
那么BN的形式就应该等于
对应于这边是对应于
AN它要凑出来的解
应该是ANαN次方
加上CNβN次方
而对应它原来的这样一个通向
它的解应该是对应的
B乘以αN次方加上D乘以βN次方
α β就是对应的这样一个
BN等于BN减1间BN减2
对应的特征根
而对应于A B C D全部都是
它的待定系数
那么待定系数我们进行整理的话
会发现这时候实际上也可以
写成对应特征根跟αN次方
和βN次方前面带一个系数
它的系数是AN加上B
后面的系数是CN加上D
因此我们需要去求解
A B C D对应的值
要求值我们必须要知道初始值
这时候我们把所有的
初始值计算出来
B1等于1
B2等于3
推出B0等于零
同时可以求出B3等于7
B4等于15
B5等于30
那么我们以此类推的话
原来我们都会说我们
如果有初始值的话
那就挨个儿的带进去
算出来N等于零的时候它得零
N等于1的时候它得1
对应于要联立一个对应于
四个变量的一次方程组
这时候求解是非常复杂的
尤其我们还带了α和β这样的
无理数是非常难计算的
那么我们可不可以利用
递推关系来进一步的求解呢
我们会发现AN加上α的N次方
加上CN加上D乘以βN次方
是我们假设出来的对应的BN的方
对应的形式
那么它可以进一步的去展开之后
等于它对应的右端是BN减1
加上BN减2加上AN
那么BN减1代到它这样
一个式子里面就相当于
它等于A乘以N减1加上B的
α的N减1次方
加上CN减1加上D的β的N次方
这就是BN减1
BN减2等于AN减2加上
B乘以α的N减2次方加上
CN减2加上D乘以
β的N减2次方
对于还有一个AN
AN我们都知道
已经在第一步中就求了出来
它就应该等于根号五分之一
乘以αN减1减去βN加1
这时候我们实际上就按照递推关系
已经写出了ABCD的这样一个等式
对应的它们是分别作为
α前面的系数
或者是β前面的系数
那么这个式子是不是
能够帮助我们去求解ABCD呢
我们再看一下
这个式子我们联立出来会
发现这有一个AN
而这里面也有一个AN
而对应AN这边还有一个AN
它们对应的系数分别是α的N次方
αN减1和αN减2
我们知道αN等于αN减1
加上αN减2
这是它原来递推关系所满足的
因此我们会发现α和β不是
一般的数字
它是满足斐波那契数关系的
这时候我们就知道αN等于
αN减1加上αN减2
βN次方等于β的N减1次方
加上β的N减2次方
那么就可以带到这样的
一个式子里面去把一些式子约减开
比如说B乘以αN次方
就应该等于B成衣αN减1次方
加上B乘以αN减2次方
因此这一部分我们完全是
可以把它给消掉的
那么还有对应的D
我们也发现它是D乘以β的N次方
D乘以β的N减1次方
D乘以β乘以N减2次方
因此这边也是可以消掉
那么我们是不是可以说
对应这α的系数我们把它整理出来
对于αN次方前面的系数是AN
而右端项αN减1次方它前面的系数
应该是A乘以N减1
对应αN减2它前面的
系数刚好是A乘以N减2
后面还有对应的α的系数
就是这样一部分
我们把所有和α相关的
数字全部都拿出来
这时候我们进一步的整理会发现
我们整理成了ANαN次方减去
ANαN减1加上AαN减1减去
ANαN减2加上二倍的AαN减2
再减去根号五分之αN加1
我们发现这一项
这一项和这一项刚好是满足
α对应的递推关系的
那么这个式子就变得简单了
就变成了a乘以αN减1次方
加上二倍的AαN减2次方
等于这一部分我们移到右端项来
根号五分之根号αN加1
那这时候A的系数就完全
可以提出来
变成了A乘以α加上二倍的A
等于根号五分之一α的三次方
A自然求解出来就刚好等于
五分之一α平方
这时候我们并没有联立任何方程组
仅仅是利用了α对应的
递推关系以及α的K次方
对应的前面的系数相等
我们就求出了A的取值
同样我们也可以依次求C的取值
C的取值求出来之后
我们可以得到C等于负的
五分之一的β的平方
同样我们如果对于把B0等于0
B0等于0刚好把A对应的项和
C对应的项取走了
因此只剩下了B和D对应的项
带进来得B加D等于零
那么拿B1等于1带到原来
这个式子里面
我就可以算出来1等于
五分之一α三次方加上β的
三次方加上B乘以α减β
这时候B的取值自然就得出
那么综合起来A等于
五分之一的α平方
B等于根号五分之一
C等于负的五分之一倍的平方
D等于负的根号五分之一
因此
我们并没有联立任何一个方程组
就可以利用这样一个通项
进行消解的形式
求解出所有的四个对应的
待定系数的方案
因此BN等于什么
BN也就是所有的砖数就应该等于
五分之一α平方N加上
五倍的根号五分之一αN次方加上
负的五分之一β平方N减去
5乘以根号五分之一βN次方
这就是我们要求的答案
刚才我们用了一个非常规的方法
帮大家去求解了线性常系数
齐次递推关系中一个典型的例子
也就铺砖问题
那么铺砖问题往往困难在哪呢
就是怎么找到递推关系
实际上我们对应于线性常系数
齐次递推关系的很多个题目
可以分为很多很多类
比如说我们说到斐波那契
有汉诺塔
有铺砖问题
甚至还有一些字符排列
甚至是放球问题
那它的关键问题就在于
你怎么能够找到正确的递推关系
也就是能够分析出它
对应的不同的种类
而最后技巧上实际上无非就落到
你是不是能够熟练的掌握
线性常系数齐次递推关通过
特征多项式进行求解的步骤
当然
中间可能会有一些技巧
比如说你是否需要用
待定系数的方法来求解呢
或者还是对于面临复杂的问题
我们正好有一些
对应的虽然是非齐次
但是它有递推关系的重根形式
那这时候我们直接可以写它的特解
利用对应的它的重根有递推关系
可以对应它们的系数进行依次的求解
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验