组合数学课件--第二章第一节 递推关系.ppt

1、1,第2章 递推关系与母函数,2.1 递推关系 2.2 母函数(生成函数) 2.3 Fibonacci数列 2.4 优选法与Fibonacci序列的应用 2.5 母函数的性质 (一) 2.6 线性常系数齐次递推关系 (二) 2.7 关于常系数齐次递推关系 (三) 2.8 整数的拆分 (四) 2.9 ferrers图像 2.10 拆分数估计 2.11 指数型母函数 (五) 2.12 广义二项式定理 2.13 应用举例 (六) 2.14 非线性递推关系举例 2.15 递推关系解法的补充,2,2.1 递推关系,例一.Hanoi塔问题：N个半径各不相同的圆盘，三根圆柱A,B,C;,算法： n=1时，直

2、接把A柱的盘移到C上。,n1时，先把A柱最上面的n-1张盘通过C柱移到B上; 然后再将A柱上最下面的盘移到C盘上; 最后将B盘上的盘通过A盘移到C盘上。,递归是子程序或函数重复地调用自己,3,2.1 递推关系,void hanoi(char A,char B,char C,int n) if (n=1) printf(“move disk1 from %c to %c” A,C) else hanoi(A,C,B,n-1); printf(“move disk %d from %c to %c”,n,A,C) hanoi(B,A,C,n-1); ,4,2.1 递推关系,例一.Hanoi塔问题：

3、N个半径各不相同的圆盘，三根圆柱A,B,C;,算法： n=1时，1次,n1时，hn=2hn-1+1,求总共需要移动多少次？,设分别为h1,h2,hn,5,2.1 递推关系,递推关系的定义: 对于数列a1,a2,an,除了前面的若干数外,其余各项an与它前面的若干个数关联起来的方程叫做递推关系。,边界条件(初始条件)：在求解递推关系时，前面必须知道若干个数，这若干个已知的数称为初始条件，或边界条件。,常系数递推关系。线性递推关系。,6,2.1 递推关系,用迭代法求解递推关系,7,例一、求解盘片为n的汉诺塔的算法如下： hanoi(int n,char A,char B,char C) if (n

4、=1) printf(“Move disk %d from A to C”,n); else hanoi(n-1,A,C,B); printf(“Move disk %d from A to C”,n); hanoi(n-1,B,A,C); ,求时间复杂性,8,解：设n张盘需执行h(n)次,h(n)=2h(n-1)+2,h(n-1)=2h(n-2)+2,h(n-2)=2h(n-3)+2,h(3)=2h(2)+2,h(2)=2h(1)+2,h(1)=2,h(2)=22+2,h(3)=23+22+2,h(n-1)=2n-1+2n-2+2,h(n)=2n+2n-1+22+2,h(n)=2n+1-2,

5、O(2n),*,例 题,9,例2-2 Fibonacci(费卜拉契）数列,问题：设有初生的雌、雄小兔一对，但第2个月过后便每月繁殖雌、雄各一的小兔一对，试问第n个月有雌、雄兔子多少对？,2.1 递推关系,1，1，2，3，5，8，13，21,Fn= Fn-1+Fn-2,10,算法:,int fibonacci(int n) if (n=1|n=2) return(1); else return(fibonacci(n-1)+fibonacci(n-2); ,2.1 递推关系,*,时间复杂性：f(n)=f(n-1)+f(n-2)+1,11,2.2 母函数,例2-3：有红球两个，白球、黄球各一个，试

6、求有多少种不同的组合方案，假设两个红球没有区别。,共有1+3+4+3+1=12种组合方案。,解：一、用组合方法来解：,一个都不选:1种方案,选1个球，3种方案,选2个球，4种方案,选3个球，3种方案,选4个球，1种方案,12,二、用函数的方法,解：设r，w，y分别代表红球，白球，黄球；,单独红球的组合方式为1，1，1：,构造函数：1+r+r2,单独白球与单独黄球的组合方式分别为： 1,1和 1,1,分别构造函数1+w和1+y。,2.2 母函数,13,(1+r+r2) (1+w)(1+y),=1+(r+w+y)+(r2+rw+ry+wy) +(r2w+r2y+rwy)+r2wy,(1+x+x2)

7、(1+x)(1+x),这个函数的系数正好与取不同球数的组合数相等，这就是母函数的方法。,把r,w,y都用x来表示，可得：,= (1+x+x2)(1+2x+ x2) =1+3x+4x2+3x3+x4,2.2 母函数,14,定义：对于序列a0,a1,a2, 构造函数：G(x)= a0+a1x+a2x2+ ,称函数G(x)是序列a0,a1,a2,的母函数。,2.2 母函数,15,例2-4：某单位有8个男同志，5个女同志，现要组织一个有数目为偶数的男同志和数目不少于2个的女同志组成的小组，试求有多少种组合方式。,解:令an为从8位男同志中抽取出n个的允许组合数。,a1 = a3 = a5 = a7 =

8、0,a0=1,a2=C(8,2)=28, a4=C(8,4)=70, a6=C(8,6)=28, a8=C(8,8)=1,1、母函数在求组合中的应用,16,数列a0,a8对应的数值是 1,0,28,0,70,0,28,0,1。构造母函数为：,类似的方法可得女同志的允许组合数对应的母函数为：,1、母函数在求组合中的应用,17,1、母函数在求组合中的应用,18,如果令a1=a2= =an=1，,如果令x=1，就得到如下组合公式：,1、母函数在求组合中的应用,*,19,2、几个基本的母函数,20,2、几个基本的母函数,21,例2-5：求由20个水果组成一袋的可能组合，水果有苹果、香蕉、橘子和梨，其中

9、在每个袋子中苹果数是偶数，香蕉数是5的倍数，橘子数最多是4个，而梨的个数是0和1。,解：单独苹果序列构成的母函数,单独香蕉序列构成的母函数,3、母函数在求组合数中的应用,22,解：单独苹果序列构成的母数,单独香蕉序列构成的母函数,单独橘子序列构成的母函数,单独梨子序列构成的母函数,3、母函数在求组合数中的应用,23,由20个水果组成一袋的可能组合数是21种,3、母函数在求组合数中的应用,24,假设h1,h2,hn的母函数为：G(x)=h0+h1x+h2x2+h3x3+,x: h1=2h0+1 x2:h2=2h1+1 x3:h3=2h2+1 +),h1x+h2x2+,G(x)=,因此： G(x)

10、=x/(1-x)(1-2x),=2xG(x)+x+x2+,2xG(x)+x/(1-x),3、用母函数求解递推关系,25,3、用母函数求解递推关系,第n项系数为A+B2n,代入边界条件：h0=0,h1=1,26,得A=-1，B=1,则：hn=2n-1,3、用母函数求解递推关系,第n项系数为A+B2n,代入边界条件：h0=0,h1=1,27,例2-2 Fibonacci(费卜拉契）数列,问题：设有初生的雌、雄小兔一对，但第2个月过后便每月繁殖雌、雄各一的小兔一对，试问第n个月有雌、雄兔子多少对？,2.1 递推关系,1，1，2，3，5，8，13，21,Fn= Fn-1+Fn-2,28,令Fn的母函数

11、为：G(x)=F1x+F2x2+,x3: F3=F2+F1 x4: F4=F3+F2 x5: F5=F4+F3 +).,G(x)-x-x2=xG(x)-x+x2G(x),F3x3+F4x4+=G(x)- F1x-F2x2= G(x)-x-x2,F2x3+F3x4+=x(F2x2+F3x3+ )= x(G(x)-x),F1x3+F2x4+=x2(F1x+F2x2+ )= x2G(x),整理后得 (1-x-x2)G(x)=x,3、用母函数求解递推关系,29,3、用母函数求解递推关系,30,3、用母函数求解递推关系,*,31,2.5、母函数的性质,性质1,如果,那么,性质2,如果：,那么：,32,2.5、母函数的性质,性质3,如果,那么,性质4,如果：,那么：,33,2.5、母函数的性质,性质5,如果,那么,性质6,如果：,那么：,34,第2章 递推关系与母函数,2.1 递推关系 2.2 母函数(生成函数) 2.3