当前课程知识点:组合数学 >  组合之美 >  组合之美之线性常系数递推关系 >  组合之美之线性常系数递推关系

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

组合之美之线性常系数递推关系在线视频

组合之美之线性常系数递推关系

下一节:组合之美之多样的序列

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

组合之美之线性常系数递推关系课程教案、知识点、字幕

下面我们给大家回顾一下

线性常系数齐次递推关系

说到什么是线性常系数

齐次递推关系呢

无非它的定义就是这样的

它实际上就像一个多项式

那么它的右端项等于零

这时候我们实际上就说

它是满足一个线性的累加和

同时它的系数都是常数

而右端项都是零

对于这样一个递推关系只是表征了

它对应的有一个递推累加的关系

那么真正要把它求解出来

还需要有另外一个要素

也就是初始值

对应于这样一个值

比如说多项式来说它是有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算法

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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

组合之美之线性常系数递推关系笔记与讨论

也许你还感兴趣的课程:

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