线性常系数非齐次递推关系.ppt

线性常系数非齐次递推关系.ppt

《线性常系数非齐次递推关系.ppt》由会员分享，可在线阅读，更多相关《线性常系数非齐次递推关系.ppt（52页珍藏版）》请在冰点文库上搜索。

2.9线性常系数非齐次递推关系,定义如果序列满足,及是常数，则称为的k阶齐次常系数线性递推关系，称为的初始条件，称为的特征多项式.,C（x）=x2-3x+2C（x）=0的解为1和2,相减得到,非齐次线性常系数递推关系,1,2.9线性常系数非齐次递推关系,例：

求n位2进制数中，从左到右逐步划去010，最后三位出现010图象的数的个数。

对于n位2进制数从左而右进行扫描，一出现010图象，便从这图象后面一位从头开始扫描，例如对11位2进制数00101001010从左而右的扫描结果应该是2-4，7-9位出现010图象，即而不是4-6，7-9位出现的010图象，即不是,2,2.8母函数和递推关系应用举例,为了找出关于数列an的递推关系，需对满足条件的数的结构进行分析。

由于n位中除了最后三位是010已确定，其余n-3位可取0或1：

故最后3位是010的n位2进制数的个数是2n-3最后3位出现010图象:

*010在n-4位到第n-2位出现010图象，而在最后3位并不出现010图象:

*01010,3,2.8母函数和递推关系应用举例,故有,利用推得,特征方程为,4,设,解方程组,5,2.9线性常系数非齐次递推关系,分析例题结果假定讨论的非齐次递推关系为对应的齐次递推关系为若和是非齐次递推关系的解，则序列是齐次递推关系的解；则要求的非齐次递推关系的解等于齐次递推关系的解和一个非齐次递推关系的特解的叠加,6,2.9线性常系数非齐次递推关系,例：

非齐次递推关系的特解代入原递推关系式满足齐次递推关系的解：

特征方程：

7,8,2.9线性常系数非齐次递推关系,例：

齐次递推关系特解非齐次递推关系的特解非齐次递推关系的特解代入原递推关系式,9,特征方程为,特解的形式,假定讨论的非齐次递推关系为1）其中b（n）是n的p次多项式，r是特征方程的m重根则特解的形式有k0,k1kp为待定系数，由非齐次递推关系确定2）若r不是C（x）=0的根，则令m=0；,2是特征根，m=1,特解的形式是,an的形式是,10,母函数和递推关系,例题：

铺砖题方砖1*1，长砖1*2，给1*n的路铺路面，求1）方案数2）总砖数（所有方案的总砖数）设方案数为an,以最后一块砖分类,an-1,an-2,11,2）总砖数设总砖数为bn,以最后一块砖分类,bn-1,。

an-1,bn-2,。

an-2,是特征根，m=1,特解是,bn的形式是,代入联立方程组太复杂,12,13,附加作业题：

某人要铺1*n长度的路，有三种砖可以使用：

1*1的方砖，或者两个直角边分别为1，1的直角三角砖（方砖从对角线切开得到两块这样的砖，称为小三角）以及斜边是2的等边直角三角砖（称为大三角）,求：

（1）铺1*n长度的路一共有多少方案数；

（2）铺1*n长度的路所有方案中一共可能出现的方砖总数；,bn,14,2.9线性常系数非齐次递推关系,例：

求n位的2进制数中，从左向右扫描，最后三位才第一次出现010图象的数的个数。

即求对n位2进制数从左而右扫描，第一次在最后三位出现010图象的数的个数。

自然，最后三位除外任取连续三个都不会是010的。

设表示满足条件的n位数个数，和前例类似，最后三位010的n位2进制数共个.,15,2.8母函数和递推关系应用举例,对这个数分析如下。

（a）包含了在最后三位第1次出现010图象的个数，其个数为，排除了在第到第位第1次出现010图象的可能。

（b）包含了在第到第位第1次出现010图象的数，其个数为,16,2.8母函数和递推关系应用举例,（c）包含了在第位到第位第1次出现010图象的数,其个数是,（d）包含了在第位到第位第1次出现010图象的数,其个数是，因在第位（打*号的格）可以取0或1两种状态。

17,2.8母函数和递推关系应用举例,一般可以归纳为对，从第位到第位第一次出现010图象的数，其数目为。

从第位到第位中间的位可以取0，1两种值,故有种状态。

18,2.8母函数和递推关系应用举例,故得递推关系如下：

时有下面几种状态：

排除了01010，因从左而右扫描时01010属于前三位出现010图象的。

19,请注意，递推关系式不是常系数递推关系。

故时有,时有,其它依此类推。

20,令,21,2.8母函数和递推关系应用举例,整理得,22,2.8母函数和递推关系应用举例,例11：

解图电路网络中的设其中,23,2.8母函数和递推关系应用举例,根据欧姆定律有,由于各点的电流代数和为零，,24,代入得递推关系,或,由点的电流代数和为零，可得,特征方程是,25,2.8母函数和递推关系应用举例,设解方程组,得,26,2.8母函数和递推关系应用举例,例：

求图2-8-6所示的n级网络的等效电阻。

所谓等效电路，相当于图2-8-6中虚线所包围的块用一电阻取代，使在两端点和之间的效果一样。

27,2.8母函数和递推关系应用举例,Rn可以作为由Rn-1等效电阻如图2-8-7所示的方式串并联构成的.,递推关系,28,令,因此,令,29,将代入得到,特征方程是,30,2.8母函数和递推关系应用举例,解方程组,31,2.8母函数和递推关系应用举例,例13：

设有地址从1到n的单元，用以纪录一组信息。

这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留下一个空单元无法存放其他信息，求这n个单元留下空单元的平均数。

设这个平均数为。

存储单元如上图，设某一信息占用了第i+1，i+2两个单元，把这组单元分割成两个部分，一是从1到i，另一从i+3到n。

32,（2-8-13）式是变系数递推关系，可改为,33,由于用相邻两个单元的几率相等，,设,34,35,2.10Stirling数,前面见到的递推关系都是一个参数的。

Stirling数导出的递推关系式是两个参数的。

（1）多项式系数n个有区别的球放到两个有区别的盒子里，若要求第1个盒子放k个球，第二个盒子放n-k个球方案数应是中项的系数依据加法法则有,2.10Stirling数,可把上面的讨论推广到n个有区别的球放到m个有区别的盒子里，要求m个盒子放的球数分别是的情况，其不同方案数用表示。

从n个有区别的球中取出个放到第1个盒子里去，其选取方案数为；当第1个盒子的个球选定后，第2个盒子里的个球则是从n-n1个中选取的，其方案数应为；第3个盒子的n3个球则是从n-n1-n2中选取，其方案数为；,2.10Stirling数,根据乘法法则有：

2.10Stirling数,n个有区别的球，放到m个有标志的盒子的问题，也可以考虑把n个有区别的球进行全排列。

对于每一个排列依次取n1个放到第1个盒子里，取n2个放到第2个盒子里，最后nm个放到第m个盒子里。

然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为,称为多项式系数。

2.10Stirling数,多项式的展开式是由式右端的n项中，每项各取一个元素相乘而得到的。

表达式中共有n个因子项，令第i个因子项对应于第i个有标志的球，从第i个因子项中取对应于把第i个有标志的球放到第i个盒子。

式展开的一般项表示第一个盒子有个球，第二个盒子有个球，等等。

因此式中项的系数应为,2.10Stirling数,定理：

展开式的项数等于C（n+m-1,n），而且这些系数之和等于,证明：

展开式中的项和从m个元素中取n个作允许重复的组合一一对应。

故得展开式的项数等于C（n+m-1,n）,2.10Stirling数,从m个中取n个作允许重复的组合的全体，对于每个球都有m个盒子可供选择，根据乘法法则有,2.10Stirling数,

（2）Stirling数只准备讨论其中的第二类Stirling数,至于第一类的Stirling数只准备给出它的定义和递推关系.,定义:

称为第一类Stirling数,或用S1表示,显然有,fallingfactorial,定义:

n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用或者表示,称为第二类Stirling数.例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种:

其中r表红球,y表黄球,b表蓝球,w表白球,2.10Stirling数,有序拆分的放球模型：

n的一个r-分拆相当于把n个无区别的球放到r个有标志的盒子，盒子不允许空着:

C（k-1,r-1）相当于把n个无区别的球放到r个有标志的盒子，盒子允许空着:

C（n+r-1,n）相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。

1.1,1.1,1.1,1.1,n个1,x1个1,n,n-1个空隙,r-1,的xn项系数。

r-1个门框,2.10Stirling数,定义:

n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数称为第二类Stirling数.定理:

第二类Stirling数S（n,m）有下列性质:

证明:

公式（a）,（b）,（e）是显然的,只证（c）,（d）.,（c）设有n个不相同的球从中取出球,其余的个球,每个都有与b1同盒,或不与同盒两种选择.但必须排除一种情况,即全体与同盒,因这时另一盒将是空盒.故实际上只有种方案,即,（d）n个球放到个盒子里,不允许有一空盒,故必有一盒有两个球,从n个有区别的球中取2个共有种组合方案.,2.10Stirling数,定理:

第二类Stirling数满足下面的递推关系,证明:

设有n个有区别的球从中取一个球设为.把n个球放到m个盒子无一空盒的方案的全体可分为两类。

（a）独占一盒，其方案数显然为（b）不独占一盒，这相当于先将剩下的个球放到m个盒子，不允许空盒，共有种不同方案，然后将球放进其中一盒，方案数为,根据加法法则有,2.10Stirling数,红、黄、蓝、白、绿五个球放到无区别的两个盒子里。

故共有15种不同的方案。

先把绿球取走，余下的四个球放到两个盒子的方案已见前面的例子。

和前面一样用r，y，b，w分别表示红，黄，蓝，白球，绿球用g表示，故得表,2.10Stirling数,表2-10-1,Stirling数,n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数:

S（n,m）n个有标志的球放进m个有区别的盒子，无空盒，其方案数是m!

S（n,m）相当于m个有标志的元素取n个做允许重复的排列,放球问题总结,n个球放到m个盒子里，依球和盒子是否有区别？

是否允许空盒？

共有种状态。

n个球有区别，m个盒子有区别，有空盒,n个球有区别，m个盒子有区别，无空盒,n个球有区别，m个盒子无区别，有空盒,n个球有区别，m个盒子无区别，无空盒,n个球无区别，m个盒子有区别，有空盒,n个球无区别，m个盒子有区别，无空盒,n个球无区别，m个盒子无区别，有空盒,的项系数。

n个球无区别，m个盒子无区别，无空盒,的项系数。