Chapt18 递推关系与生成函数

1、第十八章第十八章 递推关系与生成函数递推关系与生成函数1在组合数学中在组合数学中, 递推关系和生成函数递推关系和生成函数是解决计数问是解决计数问题的两个有密切联系的重要工具题的两个有密切联系的重要工具.本章主要讨论两方面的内容：本章主要讨论两方面的内容：1、递推关系式的建立、递推关系式的建立求解；求解；2、若干高级计数法。、若干高级计数法。18.1 递推关系及其解法递推关系及其解法定义定义18.1.1 给定一个数的序列给定一个数的序列H(0),H(1),H(n),将将H(n)和若干和若干H(i)(0 in)联系起来的等式叫做一个联系起来的等式叫做一个递推关系递推关系。2例如例如，上一章错置排序

2、数的递推关系有：，上一章错置排序数的递推关系有：10( 1)1nnnDnDD2101(1)()1,0nnnDnDDDD递推关系的建立递推关系的建立例例1、在一个平面上有一个圆和在一个平面上有一个圆和n条直线，这些直条直线，这些直线中的每一条在圆内都同其他的直线相交。如果线中的每一条在圆内都同其他的直线相交。如果没有没有多于两条多于两条的直线相交于一点，试问这些直线的直线相交于一点，试问这些直线将圆分成多少个不同区域？将圆分成多少个不同区域？ 要求解这个问题，首先必须建立递推关系，然后要求解这个问题，首先必须建立递推关系，然后求解递推关系即可。求解递推关系即可。2()(1)(1)(0)12()2

3、H nH nnnHnnH n求求 解解 递递 推推 关关 系系 得得解：解：设这设这n条直线将圆分成的区域数条直线将圆分成的区域数为为H(n)，如果有如果有n-1条直线将圆条直线将圆分成分成H(n-1)个个区域，那么再加入第区域，那么再加入第n条直条直线与在圆内的其他线与在圆内的其他n-1条直线相交条直线相交。显然显然，这条直线在圆内被分成，这条直线在圆内被分成n条线段，而每条线段条线段，而每条线段又将第又将第n条直线在圆内经过条直线在圆内经过的每个区域的每个区域分成两个区域分成两个区域。这样这样，加入第，加入第n条直线后，圆内就增加了条直线后，圆内就增加了n个区域。而个区域。而对于对于n=0

4、，显然，显然有有H(0)=1，于是对于每个整数，于是对于每个整数 n，可以，可以建立如下带初值的递推关系建立如下带初值的递推关系 （求解（求解方法稍后再方法稍后再介绍介绍）( )(1) 2(1)(2)(1)2H nH nnnH例例2、在一个平面中，有在一个平面中，有n个圆两两相交，但任二个圆个圆两两相交，但任二个圆不相切，任三个圆无公共点，求这不相切，任三个圆无公共点，求这n个圆把平面分成个圆把平面分成多个区域？多个区域？ 解：解：设这设这n个圆将平面个圆将平面分成分成H(n)个个区域区域。易。易见见 ，H(1)=2。假设假设前前n-1个圆将平面分成个圆将平面分成了了H(n-1)个个区域区域，

5、当，当加入第加入第n个个圆时，由题圆时，由题设这个设这个圆与前面的圆与前面的n-1个圆一定交个圆一定交于于2(n-1)个点个点，这这2(n-1)个点把第个点把第n个个圆分成圆分成2(n-1)条弧，而每条弧正好将条弧，而每条弧正好将前面前面的的 n-1个圆分成的区域中的其个圆分成的区域中的其经过的经过的每个区域分成每个区域分成2个个区域。区域。故故新加入的第新加入的第n个圆使所成的区域个圆使所成的区域数数增加增加了了2(n-1) 。建立如下的。建立如下的递推关系：递推关系：递推关系的建立递推关系的建立Hanoi塔问题塔问题例例3、有有A、B、C三根柱子。三根柱子。A上有上有n个圆盘，自下个圆盘，

6、自下而上由大到小地叠在一起。而上由大到小地叠在一起。ABCn现要将A上的全部圆盘移到B上，并要求：(1)每次只能移动一个圆盘；(2)任何时刻都不允许将较大的圆盘压在较小的圆盘上；(3)圆盘只能在A、B、C三个柱子间移动。n求至少需要多少次移动？nHanoi塔的解可以很自然地看成这样一个过程塔的解可以很自然地看成这样一个过程：(1)先将先将A上面上面n1个盘借助个盘借助 B移至移至C。 (2)再将再将A上剩下上剩下的的1个盘移至个盘移至B。 (3)最后将最后将C上的上的n1个盘借助个盘借助A移至移至B。 解解：设设an表示将表示将n个盘全部转个盘全部转移到另一根柱子上所需的移移到另一根柱子上所需

7、的移动次数，则动次数，则( )2(1)1(2)(1)1( )21nH nH nnHH n求求解解递递推推关关系系得得 11( )( )()(2)(1)1,(2)1nkH nH kH nknHH连乘积的结合方式连乘积的结合方式例例4、设有设有n个数个数b1,b2,.,bn的连乘积为的连乘积为b1 b2 . bn。试求不同的结合方式数（加括号的方式）。试求不同的结合方式数（加括号的方式）。 解：解：设设n个数的连乘积不同个数的连乘积不同的结合方式数的结合方式数为为H(n)。定义定义H(1)=1，显然，显然有有H(2)=1。对乘积的任一结合方式，必有某一个对乘积的任一结合方式，必有某一个k使得最后的

8、使得最后的运算为运算为b1 b2 bn= （b1 b2 bk） （bk+1 bk+2 bn）H(k) 种结合方式种结合方式H(n-k)种结合方式种结合方式由乘法法则知，对某一个由乘法法则知，对某一个k 共有共有H(k)H(n-k)种种不同的结合方式不同的结合方式。再再由加法法则即得如下的递推关系由加法法则即得如下的递推关系递推关系的求解递推关系的求解以上以上各例均为经典组合数学问题，各例均为经典组合数学问题，在算法分析在算法分析中中常用。常用。对对普通的递推关系无一般规则可普通的递推关系无一般规则可解，下面介绍解，下面介绍一些特别的递推关系的解法。一些特别的递推关系的解法。 常系数线性齐次递推

9、常系数线性齐次递推关系关系定义定义18.1.1 递推关系递推关系 912( )(1)(2)()0(18.1)kH na H na H na H nk(1,2, )0iknkaika其中， 是常数且；12120(18.2)kkkkkkxa xa xa x称为称为常系数线性齐次常系数线性齐次递推递推关系关系，而而方程方程称为称为(18.1)式的式的特征特征方程，方程，该方程的根称为递推该方程的根称为递推关系的关系的特征根。特征根。常系数线性齐次递推常系数线性齐次递推关系求解关系求解1012,kq qq设为特征根，1122( )nnnkkH nc qcqcq(1,2, )H(n)ic ik其中是任意

10、常数，其值由的初值确定。111111211( )()rnrH nCCnCnq 221212222()rnrCCnCnq 112()ttrntttrtCCnCnq解特征方程求解递推关系解特征方程求解递推关系11( )4(1)4(2)2(0)0,(1)1H nH nH nnHH0442 xx221 xx解解: 特征方程特征方程,解此方程得解此方程得所以所以 nnCCnH2)()(21,代入初值得代入初值得 12)( , 0211CCC解得解得120,1/2.CC从而得从而得12221)(nnnnnH练一练练一练( )2(1)(2)2(3)(3)(0)1,(1)2,(2)0H nH nH nH nn

11、HHH( )2(2 3)( 1)(1 3) 2nnH n故故该该递递推推关关系系的的解解为为代入法来求解递推关系代入法来求解递推关系.13也可以利用定义，用代入法求解递推关系也可以利用定义，用代入法求解递推关系( )(2)(1)1(0)2H nnH nnH解解: 由)(nH的定义,有( )(2)(1)(2)(1)(2)(2)(1)3(0)H nnH nnnH nnnH(2) (1)3 2(2)!nnn练一练练一练1、求解、求解【例例1】中的递推关系中的递推关系2解： ( )(1)(2)(1)(0)12(1)(1)2122H nH nnH nnnHnnn nnnH nH nnnH()(1)(1)

12、(0)12、求解、求解【例例2】中的递推关系中的递推关系( )(1) 2(1)(2)(1)2H nH nnnH2解： ( )(1)2 (1)(2)2 (2)2 (1)(1)21222 (2)2 (1)(1)2222H nH nnH nnnHnnn nnn3、求解、求解【例例3】中中Hanio塔问题的递推关系塔问题的递推关系H nH nnH( )2 (1) 1(2)(1) 123212解： ( )2 (1)12 (2 (2)1)12(2)212(3)2212(1)22121nnnH nH nH nH nH nH实际问题中满足要求的递推关系的建立及求解实际问题中满足要求的递推关系的建立及求解目前还

13、没有固定的程式可循。目前还没有固定的程式可循。只能通过分析问题中对应于前后几个变元的函只能通过分析问题中对应于前后几个变元的函数值之间的关系来求解。数值之间的关系来求解。下面通过实例来讨论递推关系的建立及求解。下面通过实例来讨论递推关系的建立及求解。17兔子问题兔子问题(Fibonacci)在一年开始之际买来一对新兔子放入栏中在一年开始之际买来一对新兔子放入栏中,已知每月已知每月每每对栏中对栏中的母兔生出一对新的性别不同的兔子的母兔生出一对新的性别不同的兔子,满二满二个月后的每对新兔子也生出一对兔子个月后的每对新兔子也生出一对兔子,问一年以后栏问一年以后栏中有多少对兔子中有多少对兔子?解解:

14、设设第第n个月初时栏中的个月初时栏中的兔子兔子Fn对。对。则则Fn可分成两部分：可分成两部分： n-1个月初时已经在围栏中的兔子个月初时已经在围栏中的兔子,有有Fn-1对对; 第第n个月初出生的小兔，有个月初出生的小兔，有Fn-2对。对。于是有：于是有：121231,1nnnFFFnFF按按题意题意,即求即求F13，可将初值代入逐步迭代得，可将初值代入逐步迭代得F13=233190)251()251(51nFnnn对于对于(18.3)式的一般解式的一般解Fn,可以用求特征根的方法求得可以用求特征根的方法求得:nFn称为第称为第个个斐波那契斐波那契(Fibonacci)数数,它在数学上十分重要它

15、在数学上十分重要,很多计数问题都将归结为求很多计数问题都将归结为求Fibonacci数数.20nnxaxaxaaxf22110)(,210naaaa定义定义18.2.1 设是一个序列.作幂级数)(xf,210naaaa称为序列的生成函数.例如例如:nnxxx222122,2,2, 2, 12210nnaaaa就是的生成函数.18.2 生成函数生成函数生成函数是可重复排列和组合问题中处理特殊约束生成函数是可重复排列和组合问题中处理特殊约束的一个方便工具的一个方便工具.例例 确定下列数列的一般生成函数确定下列数列的一般生成函数21(1) 1, 1,1,( 1) ,;n解解:xxxxxxfnn11)

16、 1(1)(321( 1)11(2) ,( 1),;0!1!2!nn解解:21111( )( 1)0!1!2! nnxf xxxxen22(3) ),1( ,3 , 2 , 1n12321)(nnxxxxf解解:注意到nxxxxx32111上式两边对x微分得122321)1 (1nnxxxx于是 21( )(1)f xx23,kkkcba).(),(),(xCxBxA定义定义18.2.2 设是已知的序列,它们的生成函数分别为,kkba)()(xAxB)(xA(1) 若为常数,则称为的常数倍.kkkbac)()()(xBxAxC)(xA)(xB(2) 若,则称为与的和.Kiikikbac1)()

17、()(xBxAxC)(xA)(xB(3)若,则称为与的乘积.2412,Sr为 的 组合数， krSaaab例例 设设,k22(1) (1)nnxxxxxx )1 (2nxxx解解: 考虑下面个形式幂级数的乘积它的展开式中每一项rx有如下形式rrrrxxxxkrrrrk21,21krrrxxx21kk其中分别取自上面个幂级乘积的第一个,个因子. 第二个,第25如果将第一个因子与1a对应; 第二个因子与2a对应; kka,第个因子与对应. irxrrrrk21irxSrrbrb由于,所以,的系数表示的组合数,因而序列的生成函数为: knxxxxf)1 ()(2而 xxxxn111226所以rkxrrkkkxkkkxxxf!) 1() 1(! 2) 1(1)1 (1)(2从而 rrkrCkrkr