组合数学之常系数递归关系

1、1,组合数学,第四讲,常系数递归关系,2,第四讲: 常系数递归关系,I. 路径问题选讲,II. 常系数齐次递归关系 (1) 特征值为不同的实数 (2) 特征值均为实数但是有重根 (3) 特征值有复根*,III. 常系数非齐次递归关系*,3,I. 与路径有关的问题,例1 设某地的街道把城市分割成矩形方格, 每个方格称为块. 某甲从家里出发上班, 向东要走m块, 向北要走n块. 问某甲上班的路径有多少种?,某甲上班路径数等于 从原点到 (m, n)点的 总路径数:,4,例2 从(0,0)点到达(m,n)点, 其中mn. 要求中间所经过的路径上的点(a,b)恒满足ab, 问有多少不同的路径？,解 与

2、例1不同, 现在要求路径不经过y=x上的点. 这样, 从(0,0)点第1步必须到(0,1)点, 而不允许到(1,0)点.,5,问题也可以提为: 求从(0,1)点到(m,n)点并且所经过的点(a,b)均满足条件ab的路径数. 由于mn, 显然从(1,0)点到(m,n)点的每一条路径, 必然穿过y=x上的点. 从(0,0)到(m,n)的路径可以分成两类: 第一类: 经过(1,0)点. 这类路径至少要穿过一次y=x上的点. 第二类: 经过(0,1)点. 这类路径可以分成两部分.,6,第一部分: 不经过y=x上任何的点. 这正是题目中要求的路径. 第二部分: 至少经过一次y=x上的点. 下面我们说明:

3、 第一类路径数目正好等于第二类中第二部分的路径数目. 这可以通过建立起从(1,0)到(m,n)点的路径与从(0,1)到(m,n)点但经过y=x线上点的路径间之间一一对应关系来加以证明.,7,设从(1,0)到(m,n)点的某一路径与y=x的交点从左到右依次为P1,P2, , Pk. 可以如下构造出(0,1)到(m,n)的一条路径, 而且经过y=x上的点同样的点P1,P2, ,Pk. 构造方法: 把该路径(0,0)到Pk点之间部分的路径对y=x取对称. 如图: 绿线是过(1,0)的一条路径, 红线是通过对y=x取对称所得的从(0,0) 经过(0,1)并经过y=x上的点同样的点P1,P2, ,Pk的

4、路径.,8,(0,0),(1,0),(0,1),(m,n),P1,P2,Pk,图4.2,9,这样建立了从(1,0)点到(m,n)点的一条路径与从(0,1)到(m,n)点且过y=x上点的路径之间的一一对应关系. 利用以上结论, 可以用两种方式得到题目中要求的路径数目N: N=从(0,0)点到(m,n)点的总路径数 - 2从(1,0)点到(m,n)点的路径数 N=C(m+n,m)-2C(m+n-1,m-1) =C(m+n-1, m)-C(m+n-1,m-1).,10,(2) N=从(0,1)点到(m,n)点的路径数 - 从(1,0)点到(m,n)点的路径数 N=C(m+n-1, m)-C(m+n-

5、1,m-1).,11,例3 音乐会票价为50元一张, 排队买票的顾客中有m位持50元的钞票, n位持100元的钞票. 售票处没有50元的零钱. 问有多少种排队的办法使购票能顺利进行, 不出现找不出钱的状态, 假定每位顾客只买一张票, 而且mn. 分析: 可以用m+n维0, 1向量来表示一种排队状态, 令该向量为: (a1,a2, am+n), 其中ai=0 或1, i=1,2,m+n. ai=0表示第i个顾客持50元的票款； ai=1表示第i个顾客持100元的票款.,12,这样的向量有m个0元素, n个1元素, 共有C(m+n, m)个. 可以建立(m+n)维0,1向量与从(0,0)点到达(m

6、,n)点路径间一一对应: 从(0,0)点出发, 第i步: 若ai=0沿x轴方向走一个单位, 若ai=1沿y轴方向走一个单位, i=1,m+n. 要保证顾客能顺利地买到票相当于要求路径上各点(x,y)必须满足xy.,13,我们的问题相当于求从(0,0)点到(m,n)点的路径中, 不穿越过y=x线上点的路径数(可以经过), 即需求出路径上各点(x,y)满足条件 xy的路径数. 这个问题与例2的问题不一样, 那里不允许经过y=x上点. 现在可以经过, 但不许穿过y=x这条直线是的点. 但是我们可以把这个问题转化为例2中的情况来加以解决. 实际上相当于进行一个坐标变换.,14,满足要求的路径一定不会经

7、过(0,1)点. 可以建立一个新坐标系: 原点在(-1,0), 这样我们原来(m,n)点在新坐标系里面的坐标就成了(m+1,n), 自然m+1n. 从新坐标系原点出发到达(m+1,n)点的路径, 如果所经过的点(a,b)满足ab, 则(1,0)点后的路径正好是满足条件的路径. (图4.3) 所以只需求出(0,0)到(m+1,n)不经过y=x上点的路径数.,15,(0,0),(1,0),(0,1),(m,n),图4.3,(-1,0),(m+1,n),16,这样变换之后, m+1相当于例2中的n, 而n则相当于其中的m. 由此我们知道所要求的路径数目N如下:,17,教材第3版p.53给出的结果是错

8、误的. 只要对于m=3, n=2的情况简单验证一下就可以发现书中的结果不对. 习题“由n个0和n个1构成的字符串中，在任意前k个字符串中，0的个数不少于1的个数的字符串有多少？”与买票问题相同. 路径问题很典型, 希望大家能掌握.,18,II. 常系数齐次线性递归关系,常系数线性递归关系有齐次和非齐次两种. 设Hn是一个递归数列. 常系数齐次递归关系:,其中,是实常数, f(n)非零.,常系数非齐次递归关系:,19,假定ar0, 则递归关系(4.1)称为是r阶的. 如果序列中r个相邻的H值Hk-r, Hk-r+1, ,Hk-1对某一k已知, 则可用(4.1)算出Hk的值, 于是Hk+1,Hk+

9、2,的值也可递归的算出. 所以(4.1)的解唯一的由r个相邻的H值(边界条件)所决定. 因此, (4.1)的解的一般形式包含有r个待定常数, 这些常数可由序列中相邻的r个H值来决定. 一般给定初值: H0, H1, , Hr-1.,20,对于(4.1)中的r阶齐次递归关系:,我们定义如下的一元 r 次方程:,称(4.2)为(4.1)的特征方程. 特征方程的根叫原递归关系的特征根(值).,21,定理 设q1, q2是二次齐次递推方程 Hn+2+a1Hn+1+a2Hn=0 的两个特征根，则Hn是递推方程的解的充 要条件是Hn可表成如下形式： 当q1q2时， Hn=b1q1n+b2q2n; (1)

10、当q1=q2=q时， Hn=(b1+b2n)qn (2) 其中b1, b2为常数。,22,证明：充分性. 当q1q2时,将(1)代人递推 方程的左边，因q1,q2是特征根，有,即 Hn=b1q1n+b2q2n 是递推方程的解。,23,当q1=q2=q时,将(2)代人递推方程的左边， 因q是重根，2q+a1=0,即 Hn=(b1+b2n)qn 是递推方程的解。,(必要性证明略),24,对于(4.1)中的r阶齐次递归关系:,我们定义如下的一元 r 次方程:,称(4.2)为(4.1)的特征方程. 特征方程的根叫原递归关系的特征根(值).,下面我们根据特征根的情况来给出相应的解法.,25,1. 有r个

11、不同的实特征根 定理4.1 设q1,q2,qr是递归关系(4.1) 的r个互不相同的实特征根, 则其一般解为:,证 (1) 先证(4.3)一定是原来的递归关系 的解. 在(4.3)式当中, 令n 取n-1, n-2,n-r, 得到r个等式:,26,27,把这r个等式相加并整理, 右边正好是(4.3)的右边, 即得到,这说明(4.3)中定义的数列满足定理4.1中的递归关系(4.1). 从而证明了对任意参数c1,c2,cr而言(4.3)都是定理中递归关系的一个解.,28,(2)下面证明任何一个解都可以表示成(4.3)的形式. 对任意一个解hn来说, 它由边界条件h0=b0, h1=b1, hr-1

12、=br-1完全确定. 由(1)我们知道(4.3)定义的数列都满足定理中的递归关系. 我们需要证明由这些边界条件可以完全决定一般解(4.3)中的参数c1,c2,cr.,29,我们使用待定系数法来证明c1,c2,cr存在性. 根据需要可以得到联立方程组,这个方程组的系数矩阵的行列式在著名的Vandermonde行列式.,30,因为所有的特征值q1,q2,qr都不相同, 所以这个行列式不为零. 于是原方程组关于c1,c2,cr有唯一解. 说明在这种条件下(4.1)的解是唯一确定的.,31,思考题: 通解公式(4.3)是如何得到的? (可以利用我们所学习的母函数的方式.) 例4.1 Fibonacci

13、数列的递归关系: Fn= Fn-1+ Fn-2, F0 =F1=1 (4.4) 可以利用特征值的方式来求解这个递归关系.,解 该递归关系的特征方程为x2-x-1=0, 其特征根为,32,可设该数列的解为:,由边界条件得到方程组,33,解这个方程组得到:,所以, 该递归数列的解为,例4.2 求解递归关系,34,解 该递归关系所对应的特征方程:,设递归关系:,特征根:,由边界条件确定常数c1,c2,c3. 需要解下列 线性方程组:,35,解之可得:,通解为:,例4.3 在信道上传输仅用3个字母a, b, c组成并且长度为n的词. 规定连续出现两个a的词不能传输. 试确定这个信道允许传输的词的个数.

14、 解 令h(n)为允许传输长度为n的词总数, n=1,2,. 直接计算知, h(1)=3, h(2)=8.,36,设n3, 第一个字母是b或c的词数均为h(n-1); 第一个字母是a的词, 第二个字母必须是b或c, 这种词的数目为2h(n-2).故有以下递归关系:,且h(1)=3, h(2)=8. 该递归关系的特征方程为,37,其特征根为：,故一般解为:,由边界条件h(1)=3, h(2)=8 解方程组：,38,2. 特征根有重根的情况 对于这种情况, 我们只通过例题说明求 解方法, 最后给出一般结论,不详细推导. 例4.4 求解递归关系:,解 特征方程:,可见 3是二重特征根. 此时, 除了

15、Hn=3n这 个解之外, 还有一个解: Hn=n3n.,39,一般解可设为:,利用边界条件得到线性方程组并求解:,40,定理4.2 设q1,q2,qt是递归关系,全部不同特根, qi的重数为ei(i=1,2,t), 则该递归关系对应于qi部分的一般解是:,41,3. 有复特征根* 当特征方程有复数根时, 因为复数根总是成对出现的, 而且任意复数a+bi都可以写成ei的形式, 故可设两个复根分别为,42,此时这两个根对应的一般解部分为:,因此这部分解也可以设为:,其中A, B为待定参数, 可利用边界条 件得到.,43,例4.5 给定边界条件a1=1,a2=0, 求解递归关系:,解 该递归关系对应

16、的特征方程为:,其特征根为:,44,所以,其中,该递归关系的一般解可设为:,45,由边界条件a1=1,a2=0, 便可决定A和B, 这只需要解下列方程组:,46,例 有n枚相同的棋子，甲、乙两人轮流取 子，每次可取1至2枚，取完为止。求首尾 两次都是甲取子的取法种数Hn.,解：递推方程为,其中,规定,其特征方程为,47,4个特征根为,所以，通解为,其中c1, c2, b1, b2为待定常数,48,把初始条件代人通解，得方程组,解得,49,III.常系数线性非齐次递归关系*,线性非齐次递归关系:,这里, a1, , ar全部是常数. 例如:,都是常系数线性非齐次递归关系.,50,常系数线性非齐次

17、递归关系的求解方法与非齐次线性方程组的求解思路类似. 非齐次通解=齐次通解+非齐次特解. 齐次通解求法已介绍. 问题归结为如何寻找递归关系的特解. 对于寻找递归关系的特解, 还没有一般方法. 通常根据f(n)的组成形式, 由观察法来决定特解. 当函数f(n)比较复杂时, 用观察法来决定特解是相当困难的.,51,当非齐次项是多项式时, 可通过增加递归关系的阶, 降低非齐次项的幂次, 从而化成齐次递归关系求解. 下面通过一个例题来说明这种升阶法. 例 4.5 平面上有n条直线, 任何两条直线不平行, 且任何三条直线不交于一点, 问共有多少个交点？,解 令hn为n条直线的交点个数. 第n条直线与前n

18、-1条有n-1个交点, 故有递归关系hn=hn-1+n-1, 且h1=0, h2=1, h3=3.,52,下面是通过增阶化为齐次的过程: hn=hn-1+n-1, (1) hn-1=hn-2+n-2, (2) (1)式-(2)式整理得: hn-2hn-1+hn-2=1 (3) hn-1-2hn-2+hn-3=1 (4) (3)式-(4)式整理得: hn-3hn-1+3hn-2-hn-3=0 (5),53,特征方程: x3-3x2+3x-1=(x-1)3=0 特征根: 1(三重) 齐次一般解: hn=(c1+c2n+c3n2)1n 由边界条件h1=0,h2=1,h3=3决定c1,c2,c3:,54,解之得到:,因此, 该递归关系的解为,