递推关系和生成函数.ppt

第第7 7章章 递推关系和生成函数递推关系和生成函数 7.17.1 一些数列一些数列 算术序列（等差数列）算术序列（等差数列） 几何序列（等比数列）几何序列（等比数列） 例例1 1：确定平面一般位置上的：确定平面一般位置上的n n个互相个互相 交叠的圆所形成的区域数。交叠的圆所形成的区域数。 例例2 2 (Fibonacci(Fibonacci问题问题): ): l lFibonacciFibonacci数列是递推关系的又一典型数列是递推关系的又一典型 问题问题, , 数列的本身有着许多应用数列的本身有着许多应用. . (1)(1) 问题的提出问题的提出：假定初生的一对雌雄：假定初生的一对雌雄 兔子兔子, , 从出生的第从出生的第2 2个月之后每个月都个月之后每个月都 可以生出另外一对雌雄兔可以生出另外一对雌雄兔. . 如果第如果第1 1个个 月只有一对初生的雌雄兔子月只有一对初生的雌雄兔子, , 问问n n个月个月 之后共有多少对兔子？之后共有多少对兔子？ 1月 2月 3月 4月 5月 6月 (2)(2) 求递推关系求递推关系: : 设满设满n n个月时兔子对数个月时兔子对数 为为F F n n , ,则第则第n n-1-1个月留下的兔子数目为个月留下的兔子数目为 F F n-1n-1对 对; ;当月新生兔数目为当月新生兔数目为F Fn-2 n-2对 对, , 即第即第 n n-2-2个月的所有兔子到第个月的所有兔子到第n n个月都有繁个月都有繁 殖能力殖能力 F F n n = F= Fn n-1 -1+ F + Fn n-2 -2, F , F 1 1 =F =F 2 2 =1 =1 (7.1)(7.1) 由递推关系由递推关系(7.1)(7.1)式可依次得到式可依次得到 F F 3 3 = F= F 1 1 +F+F 2 2 =2, F=2, F 4 4 = F= F 2 2 +F+F 3 3 =3, =3, F F 5 5 = F= F 3 3 + F+ F 4 4 =3+2=5, =3+2=5, 前几项为：前几项为：0 0，1 1，1 1，2 2，3 3，5 5，8 8，1313 ，2121，3434，5555，8989，144144，233233， (3)(3) FibonacciFibonacci数列的性质数列的性质 部分和部分和S S n n =f=f 0 0 +f+f 1 1 +f+f 2 2 +f+f n n =f=fn+2n+2-1-1 FibonacciFibonacci数列是偶数当且仅当数列是偶数当且仅当n n能被能被3 3 整除整除 FibonacciFibonacci数列满足公式数列满足公式 例3：令g0,g1,g2,gn,是满足下面 给出的FibonacciFibonacci数列递推关系和初始数列递推关系和初始 条件：条件：g g n n =g=gn-1n-1+g+gn-2n-2 (n (n2) g2) g 0 0 =2,g=2,g 1 1 =-1=-1 例例4 4：确定：确定2Xn2Xn棋棋盘盘盘盘用多米用多米诺诺诺诺骨牌完骨牌完 美覆盖的方法数美覆盖的方法数h h n n 。 例例5 5：确定用：确定用单单单单牌和多米牌和多米诺诺诺诺骨牌骨牌对对对对 1Xn1Xn棋棋盘盘盘盘完美覆盖的方法数完美覆盖的方法数b b n n 。 定理定理7.1.27.1.2 沿沿PascalPascal三角形左下到右三角形左下到右 上对角线上的二项式系数的和是上对角线上的二项式系数的和是 FibonacciFibonacci数数 7.27.2 线性齐次递推关系线性齐次递推关系 数列数列h h 0 0 ,h,h 1 1 ,h,h 2 2 ,h h n n , h h n n =a=a 1 1h h n-1n-1+a+a 2 2h h n-2n-2+a a k kh h n-kn-k+b+b n n ( (n nkk) ) 错错错错排数列排数列D D n n =(n-1)(D=(n-1)(Dn-2n-2+D+Dn-1n-1) ) (n (n 2)2) D D n n =nD=nDn-1n-1+(-1)+(-1) n n (n (n 1)1) FibonacciFibonacci数列数列 F F n n = F= Fn n-1 -1+ F + Fn n-2 -2 (n (n 2)2) 阶阶阶阶乘序列乘序列h h n n =nh=nhn-1n-1 (n (n 1)1) 几何序列几何序列h h n n =qh=qhn-1n-1 (n (n 1)1) h h n n =a=a 1 1h h n-1n-1+a+a 2 2h h n-2n-2+a a k kh h n-kn-k ( (n nkk) ) 其中其中 a a1 1,a ,a2 2 ,a a k k 是常系数，称为常系数线性齐是常系数，称为常系数线性齐 次递推关系。次递推关系。 定理定理7.2.17.2.1 令令q q为一非零数。则为一非零数。则h h n n = =q q n n 是是h h n n - - a a1 1h h n-1n-1-a-a 2 2h h n-2n-2-a a k kh h n-kn-k =0(a =0(a k k 0,0,n nk)k) 的解，当的解，当 且且仅仅仅仅当当q q是多是多项项项项式方程式方程x x k k -a-a 1 1x x k-1k-1-a -a 2 2x x k-2k-2- - a ak k =0=0的一个根。如果多项式方程有的一个根。如果多项式方程有k k个不个不 同的根同的根q q 1 1,q ,q2 2 ,q q k k ，则，则 h hn n =c=c 1 1q q1 1 n n +c+c 2 2q q2 2 n n +c c k kq qk k n n 例例6 6：求满足初始值：求满足初始值h h 0 0 =1,h=1,h 1 1 =2,h=2,h 2 2 =0=0的递推的递推 关系关系h h n n =2h=2hn-1 n-1+h +hn-2 n-2-2h -2hn-3 n-3 (n (n3)3)的解的解 例例7 7：只由三个字母：只由三个字母a,b,ca,b,c组组组组成的成的长长长长度度为为为为n n 的一些的一些单词单词单词单词 将在通信信道上将在通信信道上传输传输传输传输 ，满满满满足足 条件：条件：传输传输传输传输 中不得有两个中不得有两个a a连续连续连续连续 出出现现现现在任在任 一一单词单词单词单词 中。确定通信信道允中。确定通信信道允许传输许传输许传输许传输 的的单单单单 词词词词个数。个数。 例例8 8：递递递递推关系推关系h h n n =4h=4hn-1 n-1-4h -4hn-2 n-2 (n (n2)2)的解的解 定理定理7.2.2 7.2.2 令令q q 1 1,q ,q2 2 ,q,q t t 为为h h n n =a=a 1 1h h n-1n-1+a+a 2 2h h n-n- 2 2 +a a k kh h n-kn-k (a (a k k 0,0,n nk)k) 的特征方程的互异的特征方程的互异 的根。此的根。此时时时时，如果，如果q q i i 是是s s i i 重根，重根，则对则对则对则对 q q i i 部部 分一般解分一般解为为为为HH n n (i (i) ) =(c=(c 1 1 +c+c 2 2 n+cn+c si sin n si-1si-1)q )q i i n n 7.3 非齐次递推关系 例例9 9 ( (HanoiHanoi塔问题塔问题) )：n n个圆盘依其半径个圆盘依其半径 大小大小, , 从下而上套在柱从下而上套在柱A A上上, , 如如图图3.13.1所所 示示. . 每次只允许取一个转移到柱每次只允许取一个转移到柱B B或或C C 上上, , 而且而且不允许大盘放在小盘上方不允许大盘放在小盘上方. . 若若 要求把要求把A A上的上的n n个盘转移到个盘转移到C C柱上柱上. . 请请 设计一种方法设计一种方法, , 并估计要移动几个盘并估计要移动几个盘 次次. . 现在只有现在只有A, B, CA, B, C三根柱子可供使三根柱子可供使 用用. . 图 AB C 4 1 3 2 l lHanoiHanoi塔是个经典问题塔是个经典问题. . 对于这个问题对于这个问题 , , 我们先要设计算法我们先要设计算法, , 进而估计算法的进而估计算法的 计算复杂性计算复杂性, , 这里就是这里就是移动的总次数移动的总次数. . (1)(1) 算法设计：算法设计： l l n n=2=2时时, , 圆盘圆盘1 1从从A A套在套在B B上；把圆盘上；把圆盘2 2 从从A A转移到转移到C C上；把圆盘上；把圆盘1 1从从B B上转移上转移 到到C C上上. . 完毕完毕. . l l n n=3=3时时, , 把圆盘把圆盘1 1从从A A转移到转移到C C上；把圆上；把圆 盘盘2 2从从A A转移到转移到B B上；把圆盘上；把圆盘1 1从从C C上转上转 移到移到B B上上; ; 把圆盘把圆盘3 3从从A A套在套在C C上上; ; 把圆把圆 盘盘1 1从从B B再转移到再转移到A A上上; ; 把圆盘把圆盘2 2从从B B转转 移到移到C C上上, , 把圆盘把圆盘1 1从从A A套在套在C C上上. . 完毕完毕. . l l看看看看n n=3=3的演示过程的演示过程. . A A B B C C l l假定假定n n-1-1个盘子的转移算法已经确定个盘子的转移算法已经确定. . l l对对n n个圆盘问题个圆盘问题, , 先把上面的圆盘先把上面的圆盘 1,2,1,2, n n-1-1转移到转移到B B上上, , 再把最后一个再把最后一个 盘子转移到盘子转移到C C上上, , 然后把然后把B B上的上的n n-1-1个个 圆盘转移到柱圆盘转移到柱C C上上. . 转移完毕转移完毕. . l l这运用的是递归算法这运用的是递归算法n n=2=2时给出了算时给出了算 法法; ; n n=3=3时先利用时先利用n n=2=2时的算法把圆盘时的算法把圆盘 1, 21, 2移移B B上上; ; 再把圆盘再把圆盘3 3转移到柱转移到柱C C上上; ; 再利用再利用n n=2=2时的算法把时的算法把B B上两个圆盘上两个圆盘 转移到柱转移到柱C C上上. . n n=4,5,=4,5,以此类推以此类推. . (2)(2) 算法分析算法分析：令：令h h n n 表示表示n n个圆盘所需要个圆盘所需要 的转移次数的转移次数. . 根据算法先把前面根据算法先把前面n n-1-1个个 盘子转移到盘子转移到B B上上; ; 然后把第然后把第n n个盘子转个盘子转 移到移到C C上上; ; 最后再一次将最后再一次将B B上的上的n n-1-1个个 盘子转到盘子转到C C上上. . l l算法算法可实现性可实现性可用归纳法得到可用归纳法得到. . 因因n n=2=2 时对时对, , 假定假定n n-1-1对对, , 那么那么n n自然也对自然也对. . l l关于转移次数容易得到一个递归关系关于转移次数容易得到一个递归关系 : : h hn n =2=2h hn n- -1 1+1 , +1 , h h 1 1 =1.=1. 例例1010：解：解h h n n =3h=3hn-1 n-1-4n (n -4n (n1) h1) h 0 0 =2=2 步步骤总结骤总结骤总结骤总结 求求齐齐齐齐次关系的一般解次关系的一般解 求非求非齐齐齐齐次关系的一个特解次关系的一个特解 将一般解和特解将一般解和特解联联联联合，按初始条件求系数合，按初始条件求系数 困困难难难难在于特解的求解。在于特解的求解。 例例1111： h h n n =2h=2hn-1 n-1+3 +3 n n (n (n1) 1) h h 0 0 =2=2 例例1212：h h n n =3h=3hn-1 n-1+3 +3 n n (n (n1) 1) h h 0 0 =2=2 例例1313： h h n n =h=hn-1 n-1+n +n 3 3 (n (n1)1) h h 0 0 =0=0 7.47.4 生成函数（母函数）生成函数（母函数） l l母函数就象一根晒衣绳母函数就象一根晒衣绳, , 我们把需要我们把需要 得到的一列数就挂在它上面得到的一列数就挂在它上面. . l l假定我们的问题的解是一列数假定我们的问题的解是一列数: : a a0 0, ,a a1 1, ,a a2 2 , , ,a a n n , , . . 我们想知道这个数我们想知道这个数 列是什么列是什么, , 我们期望得到怎样的答案我们期望得到怎样的答案? ? l l当然当然, , 最好的答案就是关于最好的答案就是关于a a n n 的一个的一个 简单的公式简单的公式. . 比如诸如比如诸如a a n n = =n n 2 2 +3+3之类的之类的 表达式表达式. . 即即, , 通项公式通项公式. . l l 但是但是, , 如果一个未知数列没有简单公如果一个未知数列没有简单公 式式, , 或者即便存在或者即便存在, , 但是很复杂但是很复杂, , 很不很不 容易得到容易得到, , 我们也不知道我们也不知道, , 该怎么办该怎么办? ? l l 如果我们还希望研究这个数列如果我们还希望研究这个数列, , 讨论讨论 它的性质它的性质, , 该如何下手该如何下手? ? l l 举一个极端的例子举一个极端的例子, , 假定这个数列是假定这个数列是 2, 2, 3, 3, 5, 5, 7, 7, 11, 11, 13, 13, 17, 17, 19, 19, 23, 23, .,., 此处此处 a an n 是第是第n n个素数个素数. . 这样的情况这样的情况, , 期望任期望任 何简单的公式都是不合理的何简单的公式都是不合理的. . l l母函数母函数把数列的所有成员用一种非常把数列的所有成员用一种非常 巧妙的方法联系在一起巧妙的方法联系在一起, , 虽然这样做虽然这样做 并不一定能得到数列的简单公式并不一定能得到数列的简单公式, , 可可 是也许能够给出一个是也许能够给出一个幂级数和幂级数和的简单的简单 公式公式, , 展开这个和函数展开这个和函数, , 所得到的所得到的幂级幂级 数数的的系数系数就是我们所要找的就是我们所要找的数列数列. . l l比如后面我们将会学习到的比如后面我们将会学习到的FibonacciFibonacci 数列数列, , 它满足一个递归关系它满足一个递归关系 l l F Fn n+1 +1=F =F n n +F+Fn n-1 -1 ( (n n 2; F2; F 1 1 =F=F 2 2 =1).=1). 1. 1. 母函数概念母函数概念 l l设有设有a a, , b b, , c c三个不同的球三个不同的球, , 从中选取一从中选取一 个个, , 或选或选a a, , 或选或选b b, , 或选或选c c, , 把这些可能把这些可能 的选取形象地表示为的选取形象地表示为a a+ +b b+ +c c. . l l类似地类似地, , 从中选取二个从中选取二个, , 或选或选a a和和b b, , 或或 选选a a和和c c, , 或选或选b b和和c c. . 可形象地表示为可形象地表示为 abab+ +acac+ +bcbc, , 同样同样, , 从中选取三个从中选取三个, , 只有只有 一种方法一种方法, , 也可形象地表示为也可形象地表示为abcabc. . l l从多项式从多项式 (1+(1+axax)(1+b)(1+bx x)(1+c)(1+cx x) ) (7.2)(7.2) = =1 1+ +( (a+b+ca+b+c) )x+x+( (ab+ac+bcab+ac+bc) )x x 2 2 + +( (abcabc) )x x 3 3 中发现中发现, , 所有这些可能的选取方式正所有这些可能的选取方式正 好是好是x x幂的系数幂的系数. . 其中其中x x i i 的系数是从三的系数是从三 个球中选取个球中选取i i个的方法之形象表示个的方法之形象表示. . l l因子因子(1+(1+axax) )形象地指出形象地指出, , 对球对球a a, , 有两种有两种 选取方法选取方法: : 不选不选a a, , 或选或选a a. . 因子因子(1+(1+axax) ) 中的中的1 1表示不选表示不选a a, , 而而x x的系数的系数a a表示选表示选a a. . l l既然在上述多项式中既然在上述多项式中, , x x i i 的系数表明选的系数表明选 取取i i个球的方法个球的方法, , 那么那么 (1+(1+axax)(1+)(1+bxbx)(1+)(1+cxcx) ) 所表明的是所表明的是: : 对对a a, b, c, b, c三球三球, , 选取的方选取的方 法是法是, “, “选选a a或不选或不选a a” ”和和“ “选选b b或不选或不选b b” ” 以及以及“ “选选c c或不选或不选c c”. ”. l l多项式中多项式中x x的幂次表示选取球的个数的幂次表示选取球的个数, , 而其相应系数表示一切可能的选取方而其相应系数表示一切可能的选取方 法法. . l l如果我们只如果我们只关心关心不同组合方案的不同组合方案的数目数目, , 不关心不关心各种各种方案方案的罗列的罗列. . 可以在可以在(7.2)(7.2) 式中令式中令a a= =b b= =c c=1=1, , 则得到则得到 l l(1+(1+x x) ) 3 3 = C(3,0)+C(3,1) = C(3,0)+C(3,1)x x +C(3,2) +C(3,2)x x 2 2 +C(3,3)+C(3,3)x x 3 3 =1+3=1+3x x+3+3x x 2 2 + +x x 3 3 . . (7.3)(7.3) l l总方案数总方案数 N=C(3,0)+C(3,1)+C(3,2)+C(3,3)N=C(3,0)+C(3,1)+C(3,2)+C(3,3) =1+3+3+1=8. =1+3+3+1=8. l l(7.3)(7.3)就是一个关于形式变量就是一个关于形式变量x x的幂函的幂函 数数, , 这个幂函数中不同幂次的系数都这个幂函数中不同幂次的系数都 是一个组合数是一个组合数. . l l这可以推广到任意这可以推广到任意n n个不同球所有可个不同球所有可 能组合的方案数情况能组合的方案数情况. . 这其实就是我这其实就是我 们大家熟悉的二项式系数们大家熟悉的二项式系数. . 不过现在不过现在 我们是用形式级数的观点来看问题我们是用形式级数的观点来看问题. . l l利用这种形式级数不仅仅是一种不同利用这种形式级数不仅仅是一种不同 的表达形式的表达形式, , 还非常有用还非常有用. . 2. 2. 母函数定义母函数定义 定义定义7.17.1 利用给定序列利用给定序列a a 0 0, ,a a1 1, ,a a2 2 , ,所构造所构造 的函数的函数 F(F(x x)= )= a a 0 0 + +a a 1 1 x x+ +a a 2 2x x 2 2 + + 称为序列称为序列a a 0 0 , , a a 1 1 , , a a 2 2 , ,的的母函数母函数. . l l母函数定义中的级数是母函数定义中的级数是形式幂级数形式幂级数, , 不必关心收敛性不必关心收敛性, , x x只是一个形式变量只是一个形式变量. . l l有限序列有限序列 a a 0 0 , , a a 1 1 , , , a a n n 也可以定义它的也可以定义它的 母函数母函数. (. (后面添加后面添加0 0) ) 3. 3. 母函数的运算母函数的运算 设序列设序列 a a i i 的母函数的母函数A(xA(x)=)= a a i i x x i i , , b b i i 的的 母函数为母函数为B(B(x x)= )= b b i i x x i i . . 运算定义如下运算定义如下: : (1)(1) 相等相等: :A(A(x x)=)=B(B(x x) ) a a i i =b b i i a a i i = = b b i i , , i i=1,2,=1,2, (2)(2) 相加相加: : A(A(x x)+B()+B(x x)=)= ( (a a i i + +b b i i ) ) x x i i (3)(3) 相减相减: : A(A(x x)-B(x)-B(x)=)= ( (a a i i - -b b i i ) ) x x i i (4)(4) 数乘数乘: : cA(cA(x x)=)= ( (c ca a i i ) ) x x i i (5)(5) 相乘相乘: : A(A(x x)B()B(x x)=)= c c i i x x i i , , 其中其中 c c 0 0 =a=a 0 0b b0 0 , , c c 1 1 =a=a 0 0b b1 1 +a+a 1 1b b0 0 , , c c 2 2 =a=a 0 0b b2 2 +a+a 1 1b b1 1 +a+a 2 2b b0 0 , ., ., c c r r =a=a 0 0b br r +a+a 1 1b b r-1r-1+a +a r rb b0 0 , ., . (6)(6) 逆逆: : 如果如果A(A(x x)B()B(x x)=1)=1, , 则称则称B(B(x x) ) 为为A(A(x x) )的逆的逆, , 记为记为B(B(x x)=A)=A-1 -1( (x x) =1/A( ) =1/A(x x). ). ( (显然两者互为逆显然两者互为逆.) .) 例例1414 设设F(xF(x)= 1+)= 1+x x+ +x x 2 2 + +, , G(G(x x)=1-)=1-x x, , 由由 定义可以得到定义可以得到 F(F(x x)G()G(x x)=1,)=1, 因此因此 1/G(1/G(x x)=)= GG-1 -1( (x x)= )=F(F(x x), ), 即即 l l这同微积分中函数这同微积分中函数1/(1-1/(1-x x) )的幂级数展的幂级数展 开式是完全一致的开式是完全一致的. . 例例1515 设设 则则(F(F(x x)-G()-G(x x)(1-3)(1-3x x+2+2x x 2 2 )=)=x x. . 这说明这说明 l l这与把它们看成普通函数的运算是一致的这与把它们看成普通函数的运算是一致的. . 例例1616：令：令k k是一个整数，并令序列是一个整数，并令序列 h h0 0 ,h,h 1 1 ,h,h 2 2 ,h h n n ,使使h h n n 等于等于e e 1 1 +e+e 2 2 +e e k k =n=n的的 非负整数解的个数。非负整数解的个数。 例例1717：确定苹果、香蕉、橘子和梨的：确定苹果、香蕉、橘子和梨的n n组组 合的个数，其中在每个合的个数，其中在每个n n组合中苹果的个组合中苹果的个 数是偶数，香蕉的个数是奇数，橘子的个数是偶数，香蕉的个数是奇数，橘子的个 数在数在0 0和和4 4之间，而且至少要有一个梨。之间，而且至少要有一个梨。 例例1818：确定可以由苹果、香蕉、橘子和梨：确定可以由苹果、香蕉、橘子和梨 袋装水果的袋数袋装水果的袋数h h n n ，其中在每个袋子中苹，其中在每个袋子中苹 果数是偶数，香蕉数是果数是偶数，香蕉数是5 5的倍数，橘子数的倍数，橘子数 最多是最多是4 4个，梨的个数为个，梨的个数为0 0或或1 1。 例例1919：确定方程：确定方程e e 1 1 +e+e 2 2 +e e k k =n=n的非负奇整的非负奇整 数解数解e e 1 1,e ,e2 2 ,e e k k 的个数的个数h h n n 的母函数。的母函数。 例例2020：令：令h h n n 表示方程表示方程3e3e 1 1 +4e+4e 2 2 + 2e+ 2e 3 3 +5e+5e 4 4 =n =n 的非负整数解的个数。求的非负整数解的个数。求h h 0 0 ,h,h 1 1 ,h,h 2 2 ,h h n n , 的母函数的母函数g(xg(x) )。 例例2121：有无限多现成的一分、五分、一角：有无限多现成的一分、五分、一角 、两角五分和五角的硬币。确定用这些硬、两角五分和五角的硬币。确定用这些硬 币凑成币凑成n n分钱方法数分钱方法数h h n n 的母函数的母函数g(xg(x) )。 7.5 母函数与递归 例例2222 ( (HanoiHanoi塔问题塔问题) )：h h n n =2=2h hn n- -1 1+1 , +1 , h h 1 1 =1.=1. (7.4)(7.4) 令令 H(H(x x)=)=h h 1 1 x x+ +h h 2 2x x 2 2 + +h h 3 3x x 3 3 + + l l H(H(x x) )是序列是序列h h 1 1 , , h h 2 2 , , h h 3 3 , , 的母函数的母函数. . l l 给出了序列给出了序列, ,就可确定对应的母函数就可确定对应的母函数. .反过来也一反过来也一 样样, , 求得了母函数求得了母函数, , 对应得序列也就可得而知对应得序列也就可得而知. . l l 当然当然, , 利用递推关系利用递推关系(7.4)(7.4)也可迭代求得也可迭代求得h h 2 2 , , h h 3 3 , , . . 但现在我们一要寻找明确的公式但现在我们一要寻找明确的公式, , 二要显示母函二要显示母函 数的作用数的作用. . 令令H(xH(x)=h)=h 1 1 x+hx+h 2 2x x 2 2 +h+h 3 3x x 3 3 + + + + h h n nx x n n +为生为生 成函数，有以下方程：成函数，有以下方程： H(xH(x)=h)=h 1 1 x+hx+h 2 2x x 2 2 +h+h 3 3x x 3 3 + + + + h h n nx x n n + -2xH(x)=-2h-2xH(x)=-2h 1 1x x 2 2 -2h-2h 2 2x x 3 3 -2h-2h 3 3x x 4 4 - - -2-2h h n nx x n+1n+1- - 相加：相加： (1-2x)H(x)=h(1-2x)H(x)=h 1 1 x+(hx+(h 2 2 -2h-2h 1 1 )x)x 2 2 +(h+(h 3 3 -2h-2h 2 2 )x)x 3 3 + + +(+(h h n n -2h-2hn-1 n-1)x )xn n + + = x(1+x+x= x(1+x+x 2 2 + +x x 3 3+ + ) ) =x/(1-x) =x/(1-x) HH( (x x) )=x/=x/(1(1-x-x)(1)(1-2x-2x) ) (7.5)(7.5) l l这就是转移次数数列的母函数这就是转移次数数列的母函数. . l l但是我们希望得到但是我们希望得到显式显式表达式表达式. . l l这不难做到这不难做到. . 可以从母函数的幂级数可以从母函数的幂级数 展开式中求得数列展开式中求得数列h h 1 1 ,h,h 2 2 ,h,h 3 3 , ,. . l l我们下面所运用的方法是处理这种问我们下面所运用的方法是处理这种问 题的一个题的一个常规常规的方法的方法, , 初看起来可能初看起来可能 感觉不太适应感觉不太适应, , 用多了就习以为常了用多了就习以为常了. . l l这就是所谓的部分分数的算法这就是所谓的部分分数的算法. . (A+B)-(2A+B)x=x. l l 解得解得A=-1,B=1.A=-1,B=1. l l 其实一眼就可看出结果其实一眼就可看出结果. . 这里只是想这里只是想 说说 明方法而已明方法而已. . (3)(3) 算法评价算法评价: : h h n n 是要移动圆盘数是要移动圆盘数n n( (规规 模模) )的指数函数的指数函数, , 以以n n=60=60为例子为例子. . 可以可以 计算出计算出2 260 60 1.15292 1.15292 101018 18. . 这个数是一 这个数是一 个什么概念个什么概念? ? 假如你每秒钟移动一个假如你每秒钟移动一个 盘盘, , 按照上述算法按照上述算法, , 你移动你移动6060个盘的时个盘的时 间是间是: : l l真是不算不知道真是不算不知道, , 一算吓一跳一算吓一跳. . n n=60=60, , 数不过百数不过百, , 2 2也是很小的整数也是很小的整数, , 可是可是2 260 60 却是一个很大的数却是一个很大的数. . l l这就是所谓的这就是所谓的“ “指数爆炸指数爆炸” ”现象现象. . 一般一般 称复杂性为规模称复杂性为规模n n的指数函数的算法的指数函数的算法 为为“ “坏算法坏算法” ”. . 好算法好算法是指多项式算法是指多项式算法 或者线性算法或者线性算法. . 例例2323：确定平方项序列：确定平方项序列0,1,4,n0,1,4,n 2 2 ,的母的母 函数函数 例例2424：求解满足初始值：求解满足初始值h h 0 0 =1=1和和h h 1 1 =-2=-2的递的递 推关系推关系h h n n =5h=5hn-1 n-1-6h -6hn-2 n-2 (n (n2)2) 例例2525：令：令h h 0 0 ,h,h 1 1 ,h h n n ,是是满满满满足足递递递递推关系推关系 h hn n +h+hn-1 n-1-16h -16hn-2 n-2+20h +20hn-3 n-3=0 =0 (n(n3)3)的数列，其的数列，其 中中h h 0 0 =0,h=0,h 1 1 =1,h=1,h 2 2 =-1=-1。求。求h h n n 的一般公式。的一般公式。 定理定理7.5.17.5.1 令令h h 0 0 ,h,h 1 1 ,h h n n ,为满足为满足k k阶常系阶常系 数线性齐次递推关系数线性齐次递推关系h h n n -c-c 1 1h h n-1n-1-c-c 2 2h h n-2n-2-c c k kh h n-n- k k =0(c =0(c k k 0,0,n nk)k) 的数列。的数列。则则则则它的生成函数它的生成函数 g(xg(x) )形如形如g(xg(x)=)=p(x)/q(xp(x)/q(x) ) 其中，其中，q(xq(x) )为为为为具有非零常数具有非零常数项项项项的的k k次多次多项项项项 式，式，p(xp(x) )是小于是小于k k次的多次的多项项项项式。反之也成立式。反之也成立 。 l l一般母函数是用基函数一般母函数是用基函数1,1,x x, ,x x 2 2 ,来来 定义的定义的. . l l这种母函数对于这种母函数对于组合类型的数列组合类型的数列的研的研 究很有用究很有用. . 但是但是, , 对研究对研究排列类型的数排列类型的数 列列用起来很不方便用起来很不方便. . l l排列类型数列是用基函数排列类型数列是用基函数 1,1,x x, ,x x 2 2 /2!,/2!,来定义来定义, , 这样使用起来更这样使用起来更 方便一些方便一些. . l l基本思想并没有变基本思想并没有变, , 只是选择了新的只是选择了新的 基基. . 7.6 7.6 指数生成函数指数生成函数 l l基函数正好是出现在函数基函数正好是出现在函数e e x x 的幂级数的幂级数 展开式中的函数展开式中的函数: : l l设有数列设有数列a a 0 0, ,a a1 1, ,a a2 2 ,，则称下列函数为则称下列函数为 该数列的该数列的指数型母函数指数型母函数: : l l构造指数型母函数的目的是为了使得构造指数型母函数的目的是为了使得 母函数形式更简单母函数形式更简单, , 尤其对排列类型尤其对排列类型 的递归数列更是如此的递归数列更是如此. . 看几个简单例看几个简单例 子子. . 例例2626 设设n n为正整数为正整数, , 则数列则数列P(P(n n,0), ,0), P(P(n n,1), P(,1), P(n n,2), ,2), P(P(n n, ,n n) )的的指数型母函指数型母函 数数为为: : 其普通型母函数如何其普通型母函数如何? ? 例例2727 数列数列1,1,1,1,1,1,的指数型母函数为的指数型母函数为 更一般的更一般的, , 设设a a为任意实数为任意实数, , 数列数列a a 0 0 =1, =1, a a 1 1, , a a2 2 , , a a 3 3 ,的指数型母函数为的指数型母函数为 (a)(a) 设设n n= =n n 1 1 + +n n 2 2 +n n k k . . 若元素若元素a a 1 1 有有n n 1 1 个个, , 元素元素a a 2 2 有有n n 2 2 个个,元素元素a a k k 有有n n k k 个个, , 则由则由 这这n n个元素组成的不同的排列总数为个元素组成的不同的排列总数为 (b)(b)设设n n= =n n 1 1 + +n n 2 2 +n n k k . . 若元素若元素a a 1 1 有有n n 1 1 个个, , 元素元素a a 2 2 有有n n 2 2 个个, , , , 元素元素a a k k 有有n n k k 个个, , 由这由这n n 个元素中取个元素中取r r个排列数为个排列数为p p r r , , 则序列则序列p p 0 0, , p p1 1 ,p p n n 的指数