《第7章 递推关系和生成函数》由会员分享，可在线阅读，更多相关《第7章 递推关系和生成函数（47页珍藏版）》请在金锄头文库上搜索。
1、第第7章章 递推关系和生成函数递推关系和生成函数7.1 一些数列一些数列算术序列（等差数列）算术序列（等差数列）几何序列（等比数列）几何序列（等比数列）例例1：确定平面一般位置上的：确定平面一般位置上的n个互相个互相交叠的圆所形成的区域数。交叠的圆所形成的区域数。例例2 (Fibonacci问题问题):lFibonacci数列是递推关系的又一典型数列是递推关系的又一典型问题问题, 数列的本身有着许多应用数列的本身有着许多应用. (1) 问题的提出问题的提出：假定初生的一对雌雄：假定初生的一对雌雄兔子兔子, 从出生的第从出生的第2个月之后每个月都个月之后每个月都可以生出另外一对雌雄兔可以生出另外
2、一对雌雄兔. 如果第如果第1个个月只有一对初生的雌雄兔子月只有一对初生的雌雄兔子, 问问n个月个月之后共有多少对兔子？之后共有多少对兔子？1月月2月月3月月4月月5月月6月月(2) 求递推关系求递推关系: 设满设满n个月时兔子对数个月时兔子对数为为Fn,则第则第n-1个月留下的兔子数目为个月留下的兔子数目为Fn-1对对;当月新生兔数目为当月新生兔数目为Fn-2对对, 即第即第n-2个月的所有兔子到第个月的所有兔子到第n个月都有繁个月都有繁殖能力殖能力 Fn= Fn-1+ Fn-2, F1 =F2=1 (7.1)由递推关系由递推关系(7.1)式可依次得到式可依次得到 F3= F1+F2=2, F
3、4= F2+F3=3, F5= F3+ F4=3+2=5, 前几项为：前几项为：0，1，1，2，3，5，8，13，21，34，55，89，144，233，(3) Fibonacci数列的性质数列的性质I.部分和部分和Sn n=f0 0+f1 1+f2 2+fn n=fn+2n+2-1II.Fibonacci数列是偶数当且仅当数列是偶数当且仅当n能被能被3整除整除III.Fibonacci数列满足公式数列满足公式例例3：令：令g0,g1,g2,gn,是满足下面是满足下面给出的给出的Fibonacci数列递推关系和初始数列递推关系和初始条件：条件：gn n=gn-1n-1+gn-2n-2 (n2)
4、 g0 0=2,g1 1=-1例例4：确定：确定2Xn棋棋盘用多米用多米诺骨牌完美骨牌完美覆盖的方法数覆盖的方法数hn n。例例5：确定用：确定用单牌和多米牌和多米诺骨牌骨牌对1Xn棋棋盘完美覆盖的方法数完美覆盖的方法数bn n。定理定理7.1.2 沿沿Pascal三角形左下到右上三角形左下到右上对角线上的二项式系数的和是对角线上的二项式系数的和是Fibonacci数数7.2 线性齐次递推关系线性齐次递推关系数列数列h0 0,h1 1,h2 2,hn n,hn=a1 1hn-1n-1+a2 2hn-2n-2+ak khn-kn-k+bn n (nk)错排数列排数列Dn n=(n-1)(Dn-2
5、n-2+Dn-1n-1) (n 2) Dn n=nDn-1n-1+(-1)n (n 1)Fibonacci数列数列 Fn= Fn-1+ Fn-2 (n 2)阶乘序列乘序列hn n=nhn-1n-1 (n 1)几何序列几何序列hn n=qhn-1n-1 (n 1)hn n=a1 1hn-1n-1+a2 2hn-2n-2+ak khn-kn-k (nk) 其中其中a1 1,a2 2,ak k 是常系数，称为常系数线性齐是常系数，称为常系数线性齐次递推关系。次递推关系。定理定理7.2.1 令令q为一非零数。则为一非零数。则hn n=qn是是hn n-a1 1hn-1n-1-a2 2hn-2n-2-a
6、k khn-kn-k =0(ak k0,nk) 的解，当的解，当且且仅当当q是多是多项式方程式方程xk-a1 1xk-1-a2 2xk-2-ak k=0的一个根。如果多项式方程有的一个根。如果多项式方程有k个不同个不同的根的根q1,q2,qk，则，则hn=c1q1n+c2q2n+ckqkn例例6：求满足初始值：求满足初始值h0=1,h1=2,h2=0的递推关的递推关系系hn=2hn-1+hn-2-2hn-3 (n3)的解的解例例7：只由三个字母：只由三个字母a,b,c组成的成的长度度为n的的一些一些单词将在通信信道上将在通信信道上传输，满足条件：足条件：传输中不得有两个中不得有两个a连续出出现
7、在任一在任一单词中。中。确定通信信道允确定通信信道允许传输的的单词个数。个数。例例8：递推关系推关系hn=4hn-1-4hn-2 (n2)的解的解定理定理7.2.2 令令q1 1,q2 2,qt t为为hn n=a1 1hn-1n-1+a2 2hn-n-2 2+ak khn-kn-k (ak k0,nk) 的特征方程的互异的的特征方程的互异的根。此根。此时，如果，如果qi i是是si i重根，重根，则对qi i部分一部分一般解般解为Hn n(i)=(c1 1+c2 2n+csi sinsi-1)qi in7.3 非齐次递推关系非齐次递推关系例例9 (Hanoi塔问题塔问题)：n个圆盘依其半径个
8、圆盘依其半径大小大小, 从下而上套在柱从下而上套在柱A上上, 如如图图3.1所所示示. 每次只允许取一个转移到柱每次只允许取一个转移到柱B或或C上上, 而且而且不允许大盘放在小盘上方不允许大盘放在小盘上方. 若若要求把要求把A上的上的n个盘转移到个盘转移到C柱上柱上. 请设请设计一种方法计一种方法, 并估计要移动几个盘次并估计要移动几个盘次. 现在只有现在只有A, B, C三根柱子可供使用三根柱子可供使用. 图图ABC4132lHanoi塔是个经典问题塔是个经典问题. 对于这个问题对于这个问题, 我们先要设计算法我们先要设计算法, 进而估计算法的计进而估计算法的计算复杂性算复杂性, 这里就是这
9、里就是移动的总次数移动的总次数. (1) 算法设计：算法设计：ln=2时时, 圆盘圆盘1从从A套在套在B上；把圆盘上；把圆盘2从从A转移到转移到C上；把圆盘上；把圆盘1从从B上转移到上转移到C上上. 完毕完毕. ln=3时时, 把圆盘把圆盘1从从A转移到转移到C上；把圆上；把圆盘盘2从从A转移到转移到B上；把圆盘上；把圆盘1从从C上转上转移到移到B上上; 把圆盘把圆盘3从从A套在套在C上上; 把圆把圆盘盘1从从B再转移到再转移到A上上; 把圆盘把圆盘2从从B转移转移到到C上上, 把圆盘把圆盘1从从A套在套在C上上. 完毕完毕.l看看看看n=3的演示过程的演示过程.ABCl假定假定n-1个盘子的
10、转移算法已经确定个盘子的转移算法已经确定. l对对n个圆盘问题个圆盘问题, 先把上面的圆盘先把上面的圆盘1,2, n-1转移到转移到B上上, 再把最后一个盘再把最后一个盘子转移到子转移到C上上, 然后把然后把B上的上的n-1个圆盘个圆盘转移到柱转移到柱C上上. 转移完毕转移完毕. l这运用的是递归算法这运用的是递归算法n=2时给出了算法时给出了算法; n=3时先利用时先利用n=2时的算法把圆盘时的算法把圆盘1, 2移移B上上; 再把圆盘再把圆盘3转移到柱转移到柱C上上;再利再利用用n=2时的算法把时的算法把B上两个圆盘转移到上两个圆盘转移到柱柱C上上. n=4,5,以此类推以此类推. (2)
11、算法分析算法分析：令：令hn表示表示n个圆盘所需要个圆盘所需要的转移次数的转移次数. 根据算法先把前面根据算法先把前面n-1个个盘子转移到盘子转移到B上上; 然后把第然后把第n个盘子转个盘子转移到移到C上上; 最后再一次将最后再一次将B上的上的n-1个盘个盘子转到子转到C上上. l算法算法可实现性可实现性可用归纳法得到可用归纳法得到. 因因n=2时对时对, 假定假定n-1对对, 那么那么n自然也对自然也对. l关于转移次数容易得到一个递归关系关于转移次数容易得到一个递归关系:hn=2hn-1+1 , h1=1. 例例10：解：解hn=3hn-1-4n (n1) h0=2步步骤总结I.求求求求齐
12、齐次关系的一般解次关系的一般解次关系的一般解次关系的一般解II.求非求非求非求非齐齐次关系的一个特解次关系的一个特解次关系的一个特解次关系的一个特解III.将一般解和特解将一般解和特解将一般解和特解将一般解和特解联联合，按初始条件求系数合，按初始条件求系数合，按初始条件求系数合，按初始条件求系数困困难在于特解的求解。在于特解的求解。例例11： hn=2hn-1+3n (n1) h0=2例例12：hn=3hn-1+3n (n1) h0=2 例例13： hn=hn-1+n3 (n1) h0=07.4 生成函数（母函数）生成函数（母函数）l母函数就象一根晒衣绳母函数就象一根晒衣绳, 我们把需要我们把
13、需要得到的一列数就挂在它上面得到的一列数就挂在它上面.l假定我们的问题的解是一列数假定我们的问题的解是一列数: a0,a1,a2,an, . 我们想知道这个我们想知道这个数列是什么数列是什么, 我们期望得到怎样的答我们期望得到怎样的答案案?l当然当然, 最好的答案就是关于最好的答案就是关于an的一个的一个简单的公式简单的公式. 比如诸如比如诸如an=n2+3之类的之类的表达式表达式. 即即, 通项公式通项公式.l但但是是, 如如果果一一个个未未知知数数列列没没有有简简单单公公式式, 或或者者即即便便存存在在, 但但是是很很复复杂杂, 很很不不容易得到容易得到, 我们也不知道我们也不知道, 该怎
14、么办该怎么办? l如如果果我我们们还还希希望望研研究究这这个个数数列列, 讨讨论论它的性质它的性质, 该如何下手该如何下手? l举举一一个个极极端端的的例例子子, 假假定定这这个个数数列列是是2, 3, 5, 7, 11, 13, 17, 19, 23, ., 此此处处an是是第第n个个素素数数. 这这样样的的情情况况, 期期望望任任何何简简单的公式都是不合理的单的公式都是不合理的. l母函数母函数把数列的所有成员用一种非常把数列的所有成员用一种非常巧妙的方法联系在一起巧妙的方法联系在一起, 虽然这样做并虽然这样做并不一定能得到数列的简单公式不一定能得到数列的简单公式, 可是也可是也许能够给出
15、一个许能够给出一个幂级数和幂级数和的简单公式的简单公式, 展开这个和函数展开这个和函数, 所得到的所得到的幂级数幂级数的的系系数数就是我们所要找的就是我们所要找的数列数列.l比如后面我们将会学习到的比如后面我们将会学习到的Fibonacci 数列数列, 它满足一个递归关系它满足一个递归关系l Fn+1=Fn+Fn-1 (n 2; F1=F2=1).1. 母函数概念母函数概念 l设有设有a, b, c三个不同的球三个不同的球, 从中选取一从中选取一个个, 或选或选a, 或选或选b, 或选或选c, 把这些可能把这些可能的选取形象地表示为的选取形象地表示为a+b+c. l类似地类似地, 从中选取二个
16、从中选取二个, 或选或选a和和b, 或或选选a和和c, 或选或选b和和c. 可形象地表示为可形象地表示为ab+ac+bc, 同样同样, 从中选取三个从中选取三个, 只有只有一种方法一种方法, 也可形象地表示为也可形象地表示为abc.l从多项式从多项式 (1+ax)(1+bx)(1+cx) (7.2) =1+(a+b+c)x+(ab+ac+bc)x2+(abc)x3 中发现中发现, 所有这些可能的选取方式正好所有这些可能的选取方式正好是是x幂的系数幂的系数. 其中其中xi的系数是从三个的系数是从三个球中选取球中选取i个的方法之形象表示个的方法之形象表示. l因子因子(1+ax)形象地指出形象地指
17、出, 对球对球a, 有两种有两种选取方法选取方法: 不选不选a, 或选或选a. 因子因子(1+ax)中中的的1表示不选表示不选a, 而而x的系数的系数a表示选表示选a.l既然在上述多项式中既然在上述多项式中, xi的系数表明选的系数表明选取取i个球的方法个球的方法, 那么那么 (1+ax)(1+bx)(1+cx) 所表明的是所表明的是: 对对a, b, c三球三球, 选取的方选取的方法是法是, “选选a或不选或不选a”和和“选选b或不选或不选b”以及以及“选选c或不选或不选c”. l多项式中多项式中x的幂次表示选取球的个数的幂次表示选取球的个数, 而其相应系数表示一切可能的选取方而其相应系数表
18、示一切可能的选取方法法. l如果我们只如果我们只关心关心不同组合方案的不同组合方案的数目数目, 不关心不关心各种各种方案方案的罗列的罗列. 可以在可以在(7.2)式中令式中令a=b=c=1, 则得到则得到l(1+x)3 = C(3,0)+C(3,1)x +C(3,2)x2+C(3,3)x3 =1+3x+3x2+x3. (7.3)l总方案数总方案数N=C(3,0)+C(3,1)+C(3,2)+C(3,3) =1+3+3+1=8. l(7.3)就是一个关于形式变量就是一个关于形式变量x的幂函的幂函数数, 这个幂函数中不同幂次的系数都是这个幂函数中不同幂次的系数都是一个组合数一个组合数.l这可以推广
19、到任意这可以推广到任意n个不同球所有可能个不同球所有可能组合的方案数情况组合的方案数情况. 这其实就是我们大这其实就是我们大家熟悉的二项式系数家熟悉的二项式系数. 不过现在我们是不过现在我们是用形式级数的观点来看问题用形式级数的观点来看问题.l利用这种形式级数不仅仅是一种不同利用这种形式级数不仅仅是一种不同的表达形式的表达形式, 还非常有用还非常有用. 2. 母函数定义母函数定义定义定义7.1 利用给定序列利用给定序列a0,a1,a2,所构造所构造的函数的函数 F(x)= a0+a1x+a2x2+ 称为序列称为序列a0, a1, a2,的的母函数母函数. l母函数定义中的级数是母函数定义中的级
20、数是形式幂级数形式幂级数, 不不必关心收敛性必关心收敛性, x只是一个形式变量只是一个形式变量.l有限序列有限序列 a0, a1, an也可以定义它的也可以定义它的母函数母函数. (后面添加后面添加0)3. 母函数的运算母函数的运算 设序列设序列ai的母函数的母函数A(x)= aixi, bi的的母函数为母函数为B(x)= bixi. 运算定义如下运算定义如下:(1) 相等相等:A(x)=B(x)ai=biai= bi, i=1,2,(2) 相加相加: A(x)+B(x)= (ai+bi) xi(3) 相减相减: A(x)-B(x)= (ai-bi) xi (4) 数乘数乘: cA(x)= (
21、cai) xi (5) 相乘相乘: A(x)B(x)= cixi, 其中其中 c0=a0b0, c1=a0b1+a1b0, c2=a0b2+a1b1+a2b0, ., cr=a0br+a1br-1+arb0, .(6) 逆逆: 如果如果A(x)B(x)=1, 则称则称B(x)为为A(x)的逆的逆, 记为记为B(x)=A-1(x) =1/A(x). (显然两者互为逆显然两者互为逆.)例例14 设设F(x)= 1+x+x2+, G(x)=1-x, 由定由定义可以得到义可以得到 F(x)G(x)=1, 因此因此1/G(x)= G-1(x)=F(x), 即即l这这同同微微积积分分中中函函数数1/(1-
22、x)的的幂幂级级数数展展开开式是完全一致的式是完全一致的.例例15 设设则则(F(x)-G(x)(1-3x+2x2)=x. 这说明这说明l这与把它们看成普通函数的运算是一致的这与把它们看成普通函数的运算是一致的.例例16：令：令k是一个整数，并令序列是一个整数，并令序列h0,h1,h2,hn,使使hn等于等于e1+e2+ek=n的非负整数解的个数。的非负整数解的个数。例例17：确定苹果、香蕉、橘子和梨的：确定苹果、香蕉、橘子和梨的n组合组合的个数，其中在每个的个数，其中在每个n组合中苹果的个数是组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在偶数，香蕉的个数是奇数，橘子的个数在0和和4之
23、间，而且至少要有一个梨。之间，而且至少要有一个梨。例例18：确定可以由苹果、香蕉、橘子和梨：确定可以由苹果、香蕉、橘子和梨袋装水果的袋数袋装水果的袋数hn，其中在每个袋子中苹果，其中在每个袋子中苹果数是偶数，香蕉数是数是偶数，香蕉数是5的倍数，橘子数最多的倍数，橘子数最多是是4个，梨的个数为个，梨的个数为0或或1。例例19：确定方程：确定方程e1+e2+ek=n的非负奇整的非负奇整数解数解e1,e2,ek的个数的个数hn的母函数。的母函数。例例20：令：令hn表示方程表示方程3e1+4e2+ 2e3+5e4 =n的的非负整数解的个数。求非负整数解的个数。求h0,h1,h2,hn,的的母函数母函
24、数g(x)。例例21：有无限多现成的一分、五分、一角、：有无限多现成的一分、五分、一角、两角五分和五角的硬币。确定用这些硬币两角五分和五角的硬币。确定用这些硬币凑成凑成n分钱方法数分钱方法数hn的母函数的母函数g(x)。7.5 母函数与递归母函数与递归例例例例2222 ( (HanoiHanoi塔问题塔问题塔问题塔问题) )：h hn n=2=2h hn n- -1 1+1 , +1 , h h1 1=1.=1. (7.4)(7.4)令令令令 H(H(x x)=)=h h1 1x x+ +h h2 2x x2 2+ +h h3 3x x3 3+ +lH(H(x x) )是序列是序列是序列是序列
25、h h1 1, , h h2 2, , h h3 3, , 的母函数的母函数的母函数的母函数. . l给出了序列给出了序列给出了序列给出了序列, ,就可确定对应的母函数就可确定对应的母函数就可确定对应的母函数就可确定对应的母函数. .反过来也一反过来也一反过来也一反过来也一样样样样, , 求得了母函数求得了母函数求得了母函数求得了母函数, , 对应得序列也就可得而知对应得序列也就可得而知对应得序列也就可得而知对应得序列也就可得而知. . l当然当然当然当然, , 利用递推关系利用递推关系利用递推关系利用递推关系(7.4)(7.4)也可迭代求得也可迭代求得也可迭代求得也可迭代求得h h2 2,
26、, h h3 3, , . .但现在我们一要寻找明确的公式但现在我们一要寻找明确的公式但现在我们一要寻找明确的公式但现在我们一要寻找明确的公式, , 二要显示母二要显示母二要显示母二要显示母函数的作用函数的作用函数的作用函数的作用. .令令H(x)=h1x+h2x2+h3x3 + + hnxn+为生成为生成函数，有以下方程：函数，有以下方程：H(x)=h1x+h2x2+h3x3 + + hnxn+-2xH(x)=-2h1x2-2h2x3-2h3x4 - -2hnxn+1-相加：相加：(1-2x)H(x)=h1x+(h2 -2h1)x2 +(h3 -2h2)x3 + +(hn -2hn-1)xn
27、 += x(1+x+x2+x3+) =x/(1-x) H(x)=x/(1-x)(1-2x) (7.5)l这就是转移次数数列的母函数这就是转移次数数列的母函数. l但是我们希望得到但是我们希望得到显式显式表达式表达式.l这不难做到这不难做到. 可以从母函数的幂级数展可以从母函数的幂级数展开式中求得数列开式中求得数列h1,h2,h3,. l我们下面所运用的方法是处理这种问我们下面所运用的方法是处理这种问题的一个题的一个常规常规的方法的方法, 初看起来可能感初看起来可能感觉不太适应觉不太适应, 用多了就习以为常了用多了就习以为常了. l这就是所谓的部分分数的算法这就是所谓的部分分数的算法. (A+B
28、)-(2A+B)x=x.l 解得解得A=-1,B=1.l 其实一眼就可看出结果其实一眼就可看出结果. 这里只是想这里只是想说说 明方法而已明方法而已.(3) 算法评价算法评价: hn是要移动圆盘数是要移动圆盘数n(规模规模)的指数函数的指数函数, 以以n=60为例子为例子. 可以计可以计算出算出260 1.15292 1018. 这个数是一个这个数是一个什么概念什么概念? 假如你每秒钟移动一个盘假如你每秒钟移动一个盘, 按照上述算法按照上述算法, 你移动你移动60个盘的时间是个盘的时间是:l真是不算不知道真是不算不知道, 一算吓一跳一算吓一跳. n=60, 数不过百数不过百, 2也是很小的整数
29、也是很小的整数, 可是可是260却是一个很大的数却是一个很大的数. l这就是所谓的这就是所谓的“指数爆炸指数爆炸”现象现象. 一般一般称复杂性为规模称复杂性为规模n的指数函数的算法为的指数函数的算法为“坏算法坏算法”. 好算法好算法是指多项式算法或是指多项式算法或者线性算法者线性算法.例例23：确定平方项序列：确定平方项序列0,1,4,n2,的母的母函数函数例例24：求解满足初始值：求解满足初始值h0=1和和h1=-2的递推的递推关系关系hn=5hn-1-6hn-2 (n2)例例25：令：令h0,h1,hn,是是满足足递推关系推关系hn+hn-1-16hn-2+20hn-3=0 (n3)的数列
30、，其的数列，其中中h0=0,h1=1,h2=-1。求。求hn的一般公式。的一般公式。定理定理7.5.1 令令h0,h1,hn,为满足为满足k阶常系数阶常系数线性齐次递推关系线性齐次递推关系hn n-c1 1hn-1n-1-c2 2hn-2n-2-ck khn-kn-k =0(ck k0,nk) 的数列。的数列。则它的生成函数它的生成函数g(x)形形如如g(x)=p(x)/q(x) 其中，其中，q(x)为具有非零常数具有非零常数项的的k次多次多项式，式，p(x)是小于是小于k次的多次的多项式。反之也成立。式。反之也成立。7.6 一个几何的例子一个几何的例子定理定理7.6.1 通过画出区域内部不相
31、交的对角通过画出区域内部不相交的对角线将具有线将具有n+1条边的凸多边形区域分割成三条边的凸多边形区域分割成三角形区域，令角形区域，令hn表示分成三角形区域的方法表示分成三角形区域的方法数。定义数。定义h1=1。则。则hn满足递推关系满足递推关系 该递推关系的解为该递推关系的解为7.7 指数生成函数指数生成函数1,x,x2,xk,1,x,x2/2!,xn/n!,指数生成函数指数生成函数例例26：令：令n为一正整数，确定数列为一正整数，确定数列P(n,0),P(n,1),P(n,n)的指数生成函数的指数生成函数例例27：序列：序列1,1,1,的指数生成函数的指数生成函数定理定理7.7.1 令令S
32、为多重集为多重集n1.a1,n2.a2,nk.ak,其中其中n1,n2,nk均均为非负整数。令为非负整数。令hn是是S的的n排列数，则序列排列数，则序列h1,h2,hn的指数生成函数由的指数生成函数由给定，其中，给定，其中，例例28：令令hn表示数字表示数字1，2或或3组成的组成的n位数位数字数的个数，其中字数的个数，其中1的个数为偶数，的个数为偶数，2的个的个数至少是数至少是3，3的个数最多是的个数最多是4。确定结果数。确定结果数列列h1,h2,hn的指数生成函数。的指数生成函数。例例29：确定每位数字都是奇数的确定每位数字都是奇数的n位数的个位数的个数数hn ，其中，其中1和和3出现偶数次。出现偶数次。例例30：确定用红色、白色和蓝色对确定用红色、白色和蓝色对1行行n列列棋盘的方格涂色的方法数棋盘的方格涂色的方法数hn ，其中红方格，其中红方格的个数是偶数并且至少有一个蓝方格。的个数是偶数并且至少有一个蓝方格。
