组合数学 第二章第一节

1,第2章递推关系与母函数,2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列2.4优选法与Fibonacci序列的应用2.5母函数的性质(一)2.6线性常系数齐次递推关系(二)2.7关于常系数齐次递推关系(三)2.8整数的拆分(四)2.9ferrers图像2.10拆分数估计2.11指数型母函数(五)2.12广义二项式定理2.13应用举例(六)2.14非线性递推关系举例2.15递推关系解法的补充,2,2.1递推关系,例一.Hanoi塔问题：N个半径各不相同的圆盘，三根圆柱A,B,C;,算法：n=1时，直接把A柱的盘移到C上。,n1时，先把A柱最上面的n-1张盘通过C柱移到B上;然后再将A柱上最下面的盘移到C盘上;最后将B盘上的盘通过A盘移到C盘上。,递归是子程序或函数重复地调用自己,3,2.1递推关系,voidhanoi(charA,charB,charC,intn)if(n=1)printf(“movedisk1from%cto%c”A,C)elsehanoi(A,C,B,n-1);printf(“movedisk%dfrom%cto%c”,n,A,C)hanoi(B,A,C,n-1);,4,2.1递推关系,例一.Hanoi塔问题：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(intn,charA,charB,charC)if(n=1)printf(“Movedisk%dfromAtoC”,n);elsehanoi(n-1,A,C,B);printf(“Movedisk%dfromAtoC”,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,O(2n),*,例题,9,例2-2Fibonacci(费卜拉契）数列,问题：设有初生的雌、雄小兔一对，但第2个月过后便每月繁殖雌、雄各一的小兔一对，试问第n个月有雌、雄兔子多少对？,2.1递推关系,1，1，2，3，5，8，13，21,Fn=Fn-1+Fn-2,10,算法:,intfibonacci(intn)if(n=1|n=2)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2);,2.1递推关系,*,时间复杂性：f(n)=f(n-1)+f(n-2)+1,11,2.2母函数,例2-3：有红球两个，白球、黄球各一个，试求有多少种不同的组合方案，假设两个红球没有区别。,共有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)(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=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个水果组成一袋的可能组合，水果有苹果、香蕉、橘子和梨，其中在每个袋子中苹果数是偶数，香蕉数是5的倍数，橘子数最多是4个，而梨的个数是0和1。,解：单独苹果序列构成的母函数,单独香蕉序列构成的母函数,3、母函数在求组合数中的应用,22,解：单独苹果序列构成的母数,单独香蕉序列构成的母函数,单独橘子序列构成的母函数,单独梨子序列构成的母函数,3、母函数在求组合数中的应用,23,由20个水果组成一袋的可能组合数是21种,3、母函数在求组合数中的应用,24,假设h1,h2,hn的母函数为：G(x)=h0+h1x+h2x2+h3x3+,x:h1=2h0+1x2:h2=2h1+1x3:h3=2h2+1+),h1x+h2x2+,G(x)=,因此：G(x)=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-2Fibonacci(费卜拉契）数列,问题：设有初生的雌、雄小兔一对，但第2个月过后便每月繁殖雌、雄各一的小兔一对，试问第n个月有雌、雄兔子多少对？,2.1递推关系,1，1，2，3，5，8，13，21,Fn=Fn-1+Fn-2,28,令Fn的母函数为：G(x)=F1x+F2x2+,x3:F3=F2+F1x4:F4=F3+F2x5: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递推关