组合数学第七章 1

1、第七章 递推关系和生成函数,刘贵全 ,第七章 递推关系和生成函数,很多组合计数问题依赖于一个整数参数n，常常不是关心一个问题而是一个问题的序列。 例 记hn为1,2,n的排列数，则得到一个数列h0,h1,h2,hn, 其中通项hn=n！ 例 记gn为方程x1+x2+x3+x4=n的非负整数解的个数，则也得到一个序列：g0,g1,g2,gn, 其中gn=C(n+3,n),7.1 一些数列,设 h0, h1, h2, hn, 表示一个数列，可简记为hn。称hn为数列的一般项或通项。 算术数列： h0, h0+q, h0+2q, , h0+nq, 几何数列： h0, qh0, q2h0, , qnh

2、0,7.1 一些数列,数列hn的部分和也是一个数列sn，其通项sn定义为：sn =hk，即 s0=h0 s1=h0+h1 s2=h0+h1+h2 sn=h0+h1+h2+hn ,k=0,n,7.1 一些数列,对于算术数列，部分和,对于几何数列，部分和,q 1,q = 1,7.1 一些数列,例 n个两两相交的圆可以将平面划分成多少个区域？,h0=1 h1=2 h2=4 h3=8 h4=14,hn=hn-1+2(n-1) = hn-2 +2(n-2)+2(n-1) =h1+21+22+2(n-2)+2(n-1) =2+2n(n-1)/2=n2-n+2, (n2),7.1 一些数列,Fibonacc

3、i数列是递推关系的又一个典型问题，数列的本身有着许多应用。 问题：有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为Fn，其中当月新生兔数目设为Nn对。第n-1个月留下的兔子数目设为On对。 Fn= Nn + On,7.1 一些数列,7.1 一些数列,但,即第n-2个月的所偶兔子到第n个月都有繁殖能力了。,由递推关系式可依次得到,例 Fibonacci数Fn是偶数当且仅当n是3的倍数。 证 F0是偶数，F1是奇数，F2是奇数，然后，一个接一个计算后面的Fibonacci数时，奇+奇=偶，奇+偶=奇，偶+奇=奇， 如此循环下去，每3步出现一

4、个偶数。,7.1 一些数列,例,证明：,7.1 一些数列,7.1 一些数列,定理7.1.1 Fibonacci数满足公式,证：考虑递推关系Fn-Fn-1-Fn-2=0，(n2)。 先不理会初值F0和F1，设此递推关系的解具有形式Fn=qn，其中q是一个非零常数。则有qn-qn-1-qn-2=0，所以qn-2(q2-q-1)=0, 由于q0，故只能q2-q-1=0。,7.1 一些数列,解得,所以,都是递推关系的解。由于递推关系的线性性，知对任意常数c1和c2，,也是递推关系的解。由初值F0和F1，可以确定常数c1和c2：,7.1 一些数列,n=0: c1+c2=0.,n=1:,解线性方程组，得,

5、7.1 一些数列,例 设gn满足以下递推关系和初始条件： gn=gn-1+gn-2（n2） g0=2，g1= -1 求gn的一般项。 解 由于递推公式与Fibonacci数相同， n=0: c1+c2=2.,n=1:,解之即得,7.1 一些数列,例 确定用12的多米诺骨牌完美覆盖2n棋盘的方法数。 解 hn=hn-1+hn-2 h0=h1=1 例 确定用11和12骨牌完美覆盖1n棋盘的方法数。 解 解法同上。,定理7.1.2 Fibonacci数Fn等于Pascal三角(参见教材83页)的第n条从左下到右上的对角线上的元素之和，即 Fn=C(n-1,0)+C(n-2,1)+C(n-k,k-1)

6、,Pascal公式：C(n,k)=C(n-1,k)+C(n-1,k-1),7.1 一些数列,7.2 线性齐次递推关系,利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下： 例 Hanoi塔问题：N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,7.2 线性齐次递推关系,Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，即估计工作量。,算法：,N=2时,7.2 线性齐次递推关系,第一步先把最上面的一个

7、圆盘套在B上,7.2 线性齐次递推关系,第二步把最下面的一个圆盘移到C上,7.2 线性齐次递推关系,最后把B上的圆盘移到C上,到此转移完毕,7.2 线性齐次递推关系,对于一般n个圆盘的问题，,假定n-1个盘子的转移算法已经确定。,7.2 线性齐次递推关系,先把A上面的n-1个圆盘经过C转移到B。,7.2 线性齐次递推关系,第二步把A下面一个圆盘移到C上,7.2 线性齐次递推关系,最后再把B上的n-1个圆盘经过A转移到C上,7.2 线性齐次递推关系,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移

8、到柱C上。N=4，5，以此类推。,7.2 线性齐次递推关系,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,7.2 线性齐次递推关系,算法复杂度为： h(n)=2h(n-1)+1, h(1)=1 利用此公式可以依次求得h(0),h(1),h(2),这样的连锁反应关系，叫做递推关系。,7.2 线性齐次递推关系,定义 设有序列hn，如果存在a1,a2,ak(其中ak0)和bn，使得 hn=a1hn-1+a2hn-2+akh

9、n-k+bn, (nk) 成立，则称hn满足k阶线性递推关系。其中a1,a2,ak和bn可以是依赖于n的量。 例 错排数的数列Dn满足如下两个递推关系： Dn=(n-1)Dn-1+(n-1)Dn-2, (n2) Dn= nDn-1+(-1)n, (n1),例 Fibonacci数列满足二阶递推关系 fn=fn-1+fn-2, (n2) 例 阶乘数列满足一阶递推关系 hn=nhn-1 线性、齐次、常系数递推关系具有形式： hn=a1hn-1+a2hn-2+akhn-k, (nk) 其中， a1, a2, , ak是常数且ak 0,7.2 线性齐次递推关系,7.2 线性齐次递推关系,定理7.2.1

10、 设q0，则hn=qn是线性齐次常系数递推关系 hn-a1hn-1-a2hn-2-akhn-k=0 (ak0，nk) 的一个解当且仅当q是多项式方程（称之为特征方程） xk-a1xk-1-a2xk-2-ak=0 的一个根。 如果该多项式方程有k个不同的根q1,q2,qk,则 hn=c1q1n+c2q2n+ckqkn 是上述递推关系的通解。,7.2 线性齐次递推关系,通解的意义是指：无论初始条件h0,h1,hk-1如何给，总存在常数c1, c2, , ck使得hn是唯一的满足递推关系和初始条件的数列的通项。 证 hn=qn满足此递推关系当且仅当 qn-a1qn-1-a2qn-2-akqn-k=0

11、 由于q0，故又当且仅当 qk-a1qk-1-a2qk-2-ak=0,如果多项式方程有k个不同(这一点很重要)的根q1,q2,qk,则 hn=q1n，hn=q2n，hn=qkn 都是递推关系的解。由递推关系的线性性，知 hn=c1q1n+c2q2n+ckqkn 也是递推关系的解。 现在任意给定初始条件 h0=b0, h1=b1, hk-1=bk-1,7.2 线性齐次递推关系,则c1,c2,ck 必须满足方程组 (n=0) c1+c2+ck=b0 (n=1) c1q1 +c2q2 +ckqk=b1 (n=2) c1q12 +c2q22 +ckqk2 =b2 (n=k-1) c1q1k-1 +c2

12、q2k-1 +ckqkk-1 =bk-1 方程组的系数行列式是Vandermonde行列式，等于 (qj-qi)0 故有唯一解。,7.2 线性齐次递推关系,1ijk,例 求解递推关系 hn=2hn-1+hn-2-2hn-3, (n3) 初值h0=1, h1=2, h2=0. 解 特征方程x3-2x2-x+2=0有三个互异根： 1，-1，2 通解hn=c1+c2(-1)n+c32n 由初始条件解出c1=2, c2=-2/3, c3=-1/3, 所以hn=2-(-1)n2/3-2n/3,7.2 线性齐次递推关系,例 某个信道只允许传送由a、b、c三个字母组成的字，而且不许传送有连续两个a的字，问该

13、信道允许传送的长度为n的字有多少种？ 解 设该信道允许传送的长度为n的字有hn种。则 hn=2hn-1+2hn-2, (n2) h0=1, h1=3. 特征方程为x2-2x-2=0, 其特征根为,7.2 线性齐次递推关系,例 求递推关系式 hn-4hn-1+4hn-2=0, (n2) 的通解。 解 特征方程为x2-4x+4=(x-2)2=0，有重根2. hn=2n是递推关系的解。下面证明hn=n2n也是一个解。代入递推关系： hn-4hn-1+4hn-2=n2n-4(n-1)2n-1+4(n-2)2n-2=0 故hn=c12n+c2n2n是递推关系的通解。,7.2 线性齐次递推关系,设初始条件

14、h0=a, h1=b, 则 (n=0) c1=a (n=1) 2c1+2c2=b 解方程组得c1=a, c2=(b-2a)/2，故 ,7.2 线性齐次递推关系,7.2 线性齐次递推关系,定理7.2.2 设q1,q2,qt为线性齐次常系数递推关系 hn-a hn-1-a2hn-2-akhn-k=0 (ak0，nk) 的特征方程的t个不同的根。qi为si重根，则递推关系关于qi的通解为 Hn(i)=c1qin+c2nqin+csinsi-1qin =(c1+c2n+csinsi-1)qin 递推关系的整个通解为 hn=Hn(1)+Hn(2)+Hn(t),7.2 线性齐次递推关系,例 求解递推关系

15、hn= -hn-1+3hn-2+5hn-3+2hn-4, (n4) 初值h0=1, h1=0, h2=1, h3=2. 解 此递推关系的特征方程x4+x3-3x2-5x-2=0有根： -1,-1,-1,2。于是，一般解对应于根-1的部分是 Hn(1)= c1(-1)n+c2n(-1)n+c3n2(-1)n 一般解对应于根2的部分是 Hn(2)= c42n 一般解为 hn=Hn(1)+Hn(2)=c1(-1)n+c2n(-1)n+c3n2(-1)n+c42n ,7.3 非齐次递推关系,常系数线性非齐次递推关系的一般形式： C0 an+C1 an-1+Ck an-k = bn 其中：C0,C1,C

16、k为常数。bn0，可以与n有关。 下面介绍求解这种递推关系的一些方法。,7.3 非齐次递推关系,一、迭代法 例：求递推关系：,解：反复应用递推关系进行迭代有：,an=an-1+n, (n1),a0=1,an = an-1+n = an-2+(n-1)+n = an-3+(n-2)+(n-1)+n = a0+1+2+(n-2)+(n-1)+n =1+n(n+1)/2 =(n2+n+2)/2,7.3 非齐次递推关系,例：Hanoi塔问题。我们曾得到它的递推关系 h(n)=2h(n-1)+1, h(1)=1，(n2) 求解这个常系数线性非齐次递推关系。 例：平面被n个相交而不共交点的圆分割的问题。我

17、们曾得到递推关系 an=an-1+2(n-1), a0=2 (n1) 求解这个常系数线性非齐次递推关系。,7.3 非齐次递推关系,例：求递推关系：,解：非常系数线性递推关系，应用迭代法：,an=(4n-6)an-1, (n2),a1=1,an = (4n-6)an-1= (4n-6)4(n-1)-6an-2 = (4n-6)(4n-10)an-2 = 2n-1(135(2n-5)(2n-3) =(2n-2)!/(n-1)！,7.3 非齐次递推关系,二、当非齐次项是多项式时，可增加递推关系的阶，降低非齐次项的幂次，从而化成齐次递推关系求解。,7.3 非齐次递推关系,三、归纳法 例：求递推关系：,

18、解： h0=0=02,hn=hn-1+n3, (n1),h0=0,h1 = h0+13 = 0+1=1=(0+1)2 h2 = h1+23 = 9=(0+1+2)2 用数学归纳法证明结论： hn = (0+1+n)2,7.3 非齐次递推关系,四、前面讲的几种方法是比较特殊的求解非齐次递推关系的方法。还有一种稍微通用一点的解法是将递推关系的通解分成两部分之和：一部分是对应的齐次递推关系的通解（简称齐解），另一部分是满足非齐次递推关系的特解： 关于齐解的的求解方法已在前面作了详细介绍。因此问题归结为如何寻找递推关系的特解。寻找递推关系的特解，还没有求它的一般方法。通常根据bn的组成形式，由观察法来

19、决定特解。然而，当函数bn比较复杂时，用观察法来决定特解是相当困难的。,7.3 非齐次递推关系,当bn是某些特殊情况时，有一些规范的求特解的方法。下面讨论几种情况： 1、当bn是n的k次多项式时，可设递推关系的特解形式为：,其中A0, A1,Ak为待定系数。,7.3 非齐次递推关系,例：求递推关系：,解：先考虑对应齐次递推关系hn=3hn-1 (n1) 其特征方程为 x-3=0 该方程有一个特征根 x=3，并给出一般解 hn=c3n (n1) (1) 现在求原递推关系 hn=3hn-1-4n (n1) (2) 的一个特解。我们试图找出对于适当的数r和s的形如,hn=3hn-1-4n, (n1)

20、,h0=2,7.3 非齐次递推关系,hn=rn+s (3) 的解。为使(3)满足(2)，必须有 rn+s=3(r(n-1)+s)-4n=(3r-4)n+(-3r+3s) 其中n是变量，故 r = 3r-4 s = -3r+3s 解之得 r = 2 和 s = 3，从而 hn=2n+3 (4) 满足(2)。现在将(1)和(4)结合，得到 hn=c3n+2n+3 (5) 在(5)中代入初始条件h0=2，可求出c=-1。,7.3 非齐次递推关系,值的注意的是，当常系数线性齐次递推关系所导出的特征根为m重根时(m1)，特解不能为上式，这时特解可设为如下形式：,其中A0, A1,Ak为待定系数。,2、当

21、bn是dn的形式时，又可分为以下两种情况： 如果d不是对应的齐次递推关系的特征根，可设特解的形式为：,7.3 非齐次递推关系, 如果d是对应的齐次递推关系的m重特征根(m1)，可设特解的形式为：,7.3 非齐次递推关系,例：求递推关系：,解： 对应的齐次关系的一般解是hn=c3n,hn=3hn-1+3n, (n1),h0=2,若以 hn = p3n 作为一个特解，代入则得到p3n=3p3n-1+3n 这样得到p=p+1 显然不可能。因此尝试hn = pn3n 作为一个特解，代入之后即可求出上述递推关系的解。,7.3 非齐次递推关系,3、当bn是rnb(n)的形式时, 其中：b(n)是k次多项式

22、，r是对应的齐次递推关系的m重特征根,可设特解的形式为： an=(p0+p1n+pknk)nmrn,7.3 非齐次递推关系,例 求解递推关系： an+3an-1-10an-2 = (-7)nn 例 求解递推关系： an+3an-1-10an-2 = 2n(5+n),7.4 生成(母)函数,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,项的系数 中所有的项包括n个元素a1，a2， an中取两个组合的全体；同理项系数包含了从n个元素a1，a2， an中取3个元素组合的全体。以此类推。,

23、7.4 生成(母)函数,7.4 生成(母)函数,若令a1=a2= =an=1，在上式中 项系数： 中每一个组合有1个贡献，其他各项以此类推。故有：,7.4 生成(母)函数,考虑 ，设 ，用类似的方法可得等式：,证法如下：,7.4 生成(母)函数,比较等式两端的常数项，即得公式。,又如等式：,令x=1 可得,7.4 生成(母)函数,7.4 生成(母)函数,(1)式等号的两端对x求导可得：,上式两端令x=1，得：,7.4 生成(母)函数,用类似的方法还可以得到：,定义：对于序列 构造一函数：,还可以类似地推出一些等式，但通过上面一些例子已可见函数 在研究序列 的关系时所起的作用。对其他序列也有同样

24、的结果。现引进生成函数概念如下：,称函数G(x)是序列 的生成函数。,7.4 生成(母)函数,有穷数列h0,h1,h2,hn可以看成无穷数列 h0,h1,h2,hn,0,0,0,。 任一有穷数列h0,h1,h2,hn的母函数是一个多项式: g(x)=h0+h1x+h2x2+hnxn 例 数列1,1,1,1,的母函数为 g(x)=1+x+x2+x3+xn+=1/(1-x) 例 数列 的母函数是 (1+x)n,7.4 生成(母)函数,例 设为一实数，由牛顿二项式定理，无穷序列C(,0),C(,1),C(,2),C(,n), 的母函数为 (1+x)=C(,0)+C(,1)x+C(,2)x2+C(,n

25、)xn+ 其中C(,n)=(-1)(-2)(-n+1)/n!称为二项式系数。,7.4 生成(母)函数,一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。,7.4 生成(母)函数,最后求逆变换，即从已求得的母函数G(x)。得到序列an。不特别说明下面假设ak、bk两个序列对应的母函数分别为A(x)、B(x),7.4 生成(母)函数,7.4 生成(母)函数,性质1：,若 则,证：,例. 已知,则数列 b0=b1=bm-1=0， bm+k

26、=ak=1/k!, k=0,1,2, 的母函数为,7.4 生成(母)函数,7.4 生成(母)函数,性质2：若 ，,证：,7.4 生成(母)函数,7.4 生成(母)函数,例.,性质3：若 ，则,证：,7.4 生成(母)函数,7.4 生成(母)函数,7.4 生成(母)函数,例. 已知,类似可得：,7.4 生成(母)函数,性质4：若 收敛，则,7.4 生成(母)函数,7.4 生成(母)函数,性质5. 若 ，则 。,例.,则,7.4 生成(母)函数,7.4 生成(母)函数,性质5和性质6的结论是显而易见的。,性质6. 若 ，则,7.4 生成(母)函数,性质7. 若 则,证: 。,7.4 生成(母)函数

27、,7.4 生成(母)函数,例. 已知 则,7.4 生成(母)函数,例 设k为整数，hn为整数方程 e1+e2+ek=n 的非负整数解的个数，即hn=(n+k-1,n), (n0)则数列hn的母函数为：,g(x)=(1+x+x2+)(1+x+x2+)(1+x+x2+) =(1-x)-k,7.4 生成(母)函数,例 设整数方程e1+e2+e3=n的满足 0e15, 1 e22, 0e34 的解的个数为hn，求hn的母函数。,7.4 生成(母)函数,例 设hn为整数方程 3e1+4e2+2e3+5e4=n 的非负整数解的个数。求hn的母函数。 解 g(x) = (1+x3+x6+)(1+x4+x8+

28、) (1+x2+x4+)(1+x5+x10+) =1/(1-x3)(1-x4)(1-x2)(1-x5),例 所谓整数拆分即把整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。,7.4 生成(母)函数,7.4 生成(母)函数,例：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？,解：生成函数为 (1+x)(1+x2)(1+x3)(1+x4) = (1+x+x2+x3)(1+x3+x4+x7) =1+x+x2+2x3+2x4+2x5+2x7+x8+x9+x1

29、0,从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有 项，即称出5克的方案有2,同样，,故称出6克的方案有2，称出10克的方案有1,7.4 生成(母)函数,7.4 生成(母)函数,例：求用1分、2分、3分的邮票贴出不同数值的方案数。,因邮票允许重复，故母函数为,以其中x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即,7.4 生成(母)函数,例：若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种重量？各有几种方案？ 解：具体见下页。,7.4 生成(母)函数,7.4 生成(母)函数,例: 整数n拆分成1，2，3，m的和，并允许重复，求其母函数。如若其中m至少

30、出现一次，其母函数如何？,若整数n拆分成1，2，3，m的和，并允许重复，其母函数为：,7.4 生成(母)函数,若拆分中m至少出现一次，其母函数为：,7.4 生成(母)函数,7.4 生成(母)函数,显然有,上式的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。,7.4 生成(母)函数,例：若有1、2、4、8、16、32克的砝码各一枚，问能称出那几种重量？有几种可能方案？,7.4 生成(母)函数,从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。,这问题可以推广到证明任一十进制数n，可表示为,而且是唯一的。,7.5

31、 递归和生成(母)函数,前面已求出Hanoi塔问题算法复杂度为：,数列h(n)的母函数,7.5 递归和生成(母)函数,下面介绍如何求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。,根据递推关系，,或利用递推关系式求得,7.5 递归和生成(母)函数,上式左端为：,右端第一项为：,右端第二项为：,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,整理得,这两种做法得到的结果是一样的。即：,令,如何从母函数得到序列 ？下面介绍一种化为部分分数的算法。,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,由上式可得：,即：,7

32、.5 递归和生成(母)函数,因为：,7.5 递归和生成(母)函数,例. 求n位十进制数中出现偶数个5的数的个数。,先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数，若含有偶数个5，则 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。,7.5 递归和生成(母)函数,解法1：,令 位十进制数中出现偶数个5的数的 个数， 位十进制数中出现奇数个5的 数的个数。,故有：,7.5 递归和生成(母)函数,也有类似解释。,式中的 表达了含有偶数个5的n位十进制数的两个组成部分。 表达由含有偶数个5的n-1位十进制数 ，令

33、 取5以外的0,1,2,3,4,6,7,8,9九个数中的一个数构成的。 项表示当 是含有奇数个5的n-1位十进制数，令 而得 是含偶数个5的n位十进制数。,7.5 递归和生成(母)函数,设序列 的母函数为 ，序列 的母函数为 。,即：,7.5 递归和生成(母)函数,承前页：,7.5 递归和生成(母)函数,又：,故得关于母函数 和 得连立方程组：,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,解法二： n-1位的十进制数的全体共 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：,7.5 递归和生成(母)函数,令,7.5 递归和生成

34、(母)函数,7.5 递归和生成(母)函数,1）不出现某特定元素设为 ，其组合数为 ，相当于排除 后从 中取r个做允许重复的组合。,例：从n个元素 中取r个进行允许重复的组合。假定允许重复的组合数用 表示，其结果可能有以下两种情况。,7.5 递归和生成(母)函数,2）至少出现一个 ，取组合数为 相当于从 中取r-1个做允许重复的组合，然后再加上一个 得从n个元素中取r个允许重复的组合。,依据加法原则可得：,因 ，故令,7.5 递归和生成(母)函数,此递推关系带有两个参数n和r。,此式是关于 的递推关系，系数 不是常数。但,7.5 递归和生成(母)函数,由二项式定理,可得,7.5 递归和生成(母)

35、函数,设 为 的母函数,若,7.5 递归和生成(母)函数,则,将这些式子两边分别相加，得到,即,其中,7.5 递归和生成(母)函数,令 ，多项式 的次 数不大于 。,7.5 递归和生成(母)函数,定理7.5.1 设数列h0,h1,h2,hn,满足k次常系数线性齐次递推关系 hn+c1hn-1+ckhn-k=0, ck0, (nk) 则其母函数具有形式g(x)=p(x)/q(x)，其中q(x)是一个常数项不为0的k次多项式，p(x)是一个次数小于k的多项式。反之，给定这样两个多项式p(x)和q(x)，存在满足k次常系数线性齐次递推关系的数列，其母函数具有形式g(x)=p(x)/q(x)。,递推关

36、系的特征多项式,7.5 递归和生成(母)函数,因此，,是 次多项式，我们知道 在复数域中有 个根。但可能有重根，设,7.5 递归和生成(母)函数,则,于是,7.5 递归和生成(母)函数,分子的次数低于分母的次数，有分项表示，即：,即：,的系数是 是常数。,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,定理：设 是有理分式，多项式的 次数低于 的次数。则 有分项表示， 且表示唯一。,证明：设 的次数为n，对n用数学归纳法。,n=1时， 是常数，命题成立。,假设对小于n的正整数，命题成立。,下面证明对正整数n命题成立。设 是 的 重根，,7.5 递归和生成(母)函数,不妨设 与 互素

37、，设,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,的次数低于 。根据归纳假设，,可分项表示。因此，,可分项表示。且表示是唯一的。,以下分别各种情况讨论具体计算的问题。 （1）特征多项式 无重根 设 计算可简化为,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,的系数是,可由线性方程组,解出。,方程组的系数矩阵的行列式是Vandermond 行列式,方程组有唯一解。,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,（2）特征多项式 有共轭复根 设 是 的一对共轭复根。,中 的系数是,7.5 递归和生成(母)函数,其中,在具体计算时，可先求出各对共轭复根，再

38、求待定系数A，B，避免中间过程的复数运算。,（3）特征多项式 有重根 设 是 的 重根，则 对应的母函数为,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,的系数 。其中,是n的j-1次多项式。因此， 是 与n的k-1次多项式的乘积。,7.5 递归和生成(母)函数,为了简化计算，下面引入一些记号，介绍几个命题。,设x是任意变量，n是非负整数，令,7.5 递归和生成(母)函数,不难证明，多项式 可用 唯一线性表示。其中 是常数,7.5 递归和生成(母)函数,(2)若特征多项式 有不同的复根，可依照(1)的办法处理。不过任意复数 可写为 形式，设 是 的一个零点，其共轭复根为,7.5

39、递归和生成(母)函数,和 仍然是待定常数。即 有一对共轭复根 和 时，递推关系的解有对应的项,其中A，B是待定常数。,7.5 递归和生成(母)函数,(3)若 有k重根。不妨设 是k的重根。则递推关系的解对应于 的项为 其中 是k个待定常数。,7.5 递归和生成(母)函数,例：求,同理,相减得,7.5 递归和生成(母)函数,同理,对应的特征方程为,相减得,同理,7.5 递归和生成(母)函数,是四重根,依据 得关于A、B、C、D的连立方程组：,7.5 递归和生成(母)函数,已知 是n的3次式，更简单的办法是令,确定待定系数时，比较方便，无需解一联立方程组。 例如,7.5 递归和生成(母)函数,7.

40、5 递归和生成(母)函数,7.5 递归和生成(母)函数,例：求 中 的 系数。,解： 的特征多项式是,是3重根,是1重根,的根是,7.5 递归和生成(母)函数,因此可设,7.5 递归和生成(母)函数,通过做长除法，求得,7.5 递归和生成(母)函数,可知,利用 的值解得。 故,7.5 递归和生成(母)函数,通过上式，计算得 与用长除法得到的结果相同。,7.5 递归和生成(母)函数,7.5 递归和生成(母)函数,例：10个数字（0到9）和4个四则运算符(+,)组成的14个元素。求由其中的n个元素的排列构成一算术表达式的个数。 因所求的n个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字

41、。而第n-1位有两种可能，一是数字，一是运算符。,7.5 递归和生成(母)函数,如若第n-1位是十个数字之一，则前n-1位必然构成一算术表达式;如若不然，即第n-1位是4个运算符之一，则前n-2位必然是算术表达式。根据以上分析，令an表示第n个元素排列成算术表达式的个数。则,指的是从0到99的100个数，以及,7.5 递归和生成(母)函数,利用递推关系，得 特征多项式 。 它的根是,解方程,7.5 递归和生成(母)函数,得,7.6 一个几何的例子,凸集：平面或空间中的点集，连接集合中任意两点的线段上的点也都属于该集合。,非凸多边形,凸多边形,7.6 一个几何的例子,凸多边形的对角线：连接两个不

42、相邻的顶 点的线段。 凸n边形共有n(n-1)/2-n=n(n-3)/2条对角线。 可以选n-3条在多边形内部互不相交的对角 线将凸多边形划分成n-2个三角形区域。,7.6 一个几何的例子,定理7.6.1 设hn为用在内部不相交的对角线将一个凸n+1边形划分成三角形区域的方法数，定义h1=1. 则hn满足如下递推关系： hn=h1hn-1+h2hn-2+hn-1h1, (n2)。 此递推关系的解为： hn=C(2n-2,n-1)/n (n=1,2,3,),7.6 一个几何的例子,基边,证 h2=1=h1h1,7.6 一个几何的例子,设 g(x)=h1x+h2x2+hnxn+, 则 (g(x)2

43、= h12x2+(h1h2+h2h1)x3+(h1h3+h2h2+h3h1)x4 +(h1hn-1+h2hn-2+hn-1h1)xn+ = h2x2+h3x3+hnxn+ = g(x)-h1x=g(x)-x. 故g(x)满足方程(g(x)2-g(x)+x=0 ，解之得,7.6 一个几何的例子,由g(x)的定义，g(0)=0，只能是 g(x)=g2(x)=(1-(1-4x)1/2)/2,由二项式定理,7.6 一个几何的例子,7.6 一个几何的例子,中xn项的系数是,7.6 一个几何的例子,故,即,7.7 指数生成函数,设有n个元素，其中元素 重复了 次，元素 重复了 次， 重复了 次， 从中取r

44、个排列，求不同的排列数,如果 ，则是一般的排列问题。,7.7 指数生成函数,现在由于出现重复，故不同的排列计数便比较复杂。先考虑 个元素的全排列，若 个元素没有完全一样的元素，则应有 种排列。若考虑 个元素 的全排列数为 ，则真正不同的排列数为,7.7 指数生成函数,先讨论一个具体问题：若有8个元素，其中设 重复3次， 重复2次， 重复3次。从中取r个组合，其组合数为 ，则序列 的母函数为,7.7 指数生成函数,从 的系数可知，这8个元素中取4个组合，其组合数为10。这10个组合可从下面展开式中得到,7.7 指数生成函数,7.7 指数生成函数,其中4次方项有,上式表达了从8个元素( 各3个, 2个)中取4个的组合。例如 为一个 ，3个 的组合， 为两个 ，两个 的组合，以此类推。,7.7 指数生成函数,若研究从中取4个的