组合数学递推关系省公共课一等奖全国赛课获奖课件.pptx

第第2章章 递推关系与母函数递推关系与母函数 2.1 2.1 递推关系递推关系 2.2 2.2 母函数母函数(生成函数生成函数)2.3 Fibonacci 2.3 Fibonacci数列数列 2.4 2.4 优选法与优选法与FibonacciFibonacci序列应用序列应用 2.5 2.5 母函数性质母函数性质 (一一)2.6 2.6 线性常系数齐次递推关系线性常系数齐次递推关系 (二二)2.7 2.7 关于常系数齐次递推关系关于常系数齐次递推关系 (三三)2.8 2.8 整数拆分整数拆分 (四四)2.9 ferrers2.9 ferrers图像图像2.10 2.10 拆分数预计拆分数预计 2.11 2.11 指数型母函数指数型母函数 (五五)2.12 2.12 广义二项式定理广义二项式定理 2.13 2.13 应用举例应用举例 (六六)2.14 2.14 非线性递推关系举例非线性递推关系举例 2.15 2.15 递推关系解法补充递推关系解法补充1第1页2.1 递推关系递推关系 例一例一.Hanoi.Hanoi塔问题：塔问题：N N个半径各不相同个半径各不相同圆盘，三根圆柱圆盘，三根圆柱A,B,C;A,B,C;算法：算法：n=1n=1时，直接把时，直接把A A柱盘移到柱盘移到C C上。上。n1 n1时，先把时，先把A A柱最上面柱最上面n-1n-1张盘经过张盘经过C C柱柱移到移到B B上上;然后再将然后再将A A柱上最下面盘移到柱上最下面盘移到C C盘上盘上;最终将最终将B B盘上盘经过盘上盘经过A A盘移到盘移到C C盘上。盘上。递归是子程序或函数重复地调用自己递归是子程序或函数重复地调用自己2第2页2.1 递推关系递推关系void hanoi(char A,char B,char C,int n)void hanoi(char A,char B,char C,int n)if(n=1)if(n=1)printf(“move disk1 from%c to%c”A,C)printf(“move disk1 from%c to%c”A,C)else else hanoi(A,C,B,n-1);hanoi(A,C,B,n-1);printf(“move disk%d from%c to printf(“move disk%d from%c to%c”,n,A,C)%c”,n,A,C)hanoi(B,A,C,n-1);hanoi(B,A,C,n-1);3第3页2.1 递推关系递推关系 例一例一.Hanoi.Hanoi塔问题：塔问题：N N个半径各不相同个半径各不相同圆盘，三根圆柱圆盘，三根圆柱A,B,C;A,B,C;算法：算法：n=1 n=1时，时，1 1次次 n1 n1时，时，h hn n=2h=2hn-1n-1+1+1 求总共需要移动多少次？求总共需要移动多少次？设分别为设分别为h h1 1,h,h2 2,h,hn n4第4页2.1 递推关系递推关系 递推关系定义递推关系定义:对于数列对于数列a a1 1,a,a2 2,a,an n,除了前面若干数外除了前面若干数外,其余各项其余各项a an n与它前面若干个数关联起来方程叫做与它前面若干个数关联起来方程叫做递推关系。递推关系。边界条件边界条件(初始条件初始条件)：在求解递推关系时，：在求解递推关系时，前面必须知道若干个数，这若干个已知数称为前面必须知道若干个数，这若干个已知数称为初始条件，或边界条件。初始条件，或边界条件。常系数递推关系。线性递推关系。常系数递推关系。线性递推关系。5第5页2.1 递推关系递推关系用迭代法求解递推关系用迭代法求解递推关系6第6页 例一、求解盘片为例一、求解盘片为n n汉诺塔算法以下：汉诺塔算法以下：hanoi(int n,char A,char B,char C)hanoi(int n,char A,char B,char C)if(n=1)if(n=1)printf(“Move disk%d from A to printf(“Move disk%d from A to C”,n);C”,n);else else hanoi(n-1,A,C,B);hanoi(n-1,A,C,B);printf(“Move disk%d from A to printf(“Move disk%d from A to C”,n);C”,n);hanoi(n-1,B,A,C);hanoi(n-1,B,A,C);求时间复杂性求时间复杂性7第7页解：设解：设n n张盘需执行张盘需执行h(n)h(n)次次h(n)=2h(n-1)+2h(n)=2h(n-1)+2h(n-1)=2h(n-2)+2h(n-1)=2h(n-2)+2h(n-2)=2h(n-3)+2h(n-2)=2h(n-3)+2h(3)=2h(2)+2h(3)=2h(2)+2h(2)=2h(1)+2h(2)=2h(1)+2h(1)=2h(1)=2h(2)=2h(2)=22 2+2+2h(3)=2h(3)=23 3+2+22 2+2+2h(n-1)=2h(n-1)=2n-1n-1+2+2n-2n-2+2+2h(n)=2h(n)=2n n+2+2n-1n-1+2+22 2+2+2h(n)=2h(n)=2n+1n+1-2-2O(2O(2n n)*例例 题题8第8页例例2-2 Fibonacci(费卜拉契）数列费卜拉契）数列 问题：设有初生雌、雄小兔一对，问题：设有初生雌、雄小兔一对，但第但第2 2个月过后便每个月繁殖雌、雄各一个月过后便每个月繁殖雌、雄各一小兔一对，试问第小兔一对，试问第n n个月有雌、雄兔子多个月有雌、雄兔子多少对？少对？2.1 递推关系递推关系 1 1，1 1，2 2，3 3，5 5，8 8，1313，2121Fn=Fn-1+Fn-2 9第9页算法算法: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)+110第10页2.2 母函数母函数 例例2-32-3：有红球两个，白球、黄球各一个，：有红球两个，白球、黄球各一个，试求有多少种不一样组合方案，假设两个红球没试求有多少种不一样组合方案，假设两个红球没有区分。有区分。共有共有1+3+4+3+1=121+3+4+3+1=12种组合方案。种组合方案。解：一、用组合方法来解：解：一、用组合方法来解：一个都不选一个都不选:1种方案种方案选选1个球，个球，3种方案种方案选选2个球，个球，4种方案种方案选选3个球，个球，3种方案种方案选选4个球，个球，1种方案种方案11第11页二、用函数方法二、用函数方法解：设解：设r r，w w，y y分别代表红球，白球，黄球；分别代表红球，白球，黄球；单独红球组合方式为单独红球组合方式为1 1，1 1，1 1：结构函数：结构函数：1+r+r2单独白球与单独黄球组合方式分别为：单独白球与单独黄球组合方式分别为：1,1和和 1,1分别结构函数分别结构函数1+w和和1+y1+y。2.2 母函数母函数12第12页 (1+r+r2)(1+w)(1+y1+y)=1=1+(r+w+y y)+(r2+rw+ry+wy y)+(r2w+r2y y+rwy y)+r2wy y(1+x+x2)(1+x)(1+x)这个函数系数恰好与取不一样球数组合数相这个函数系数恰好与取不一样球数组合数相等，这就是母函数方法。等，这就是母函数方法。把把r,w,yr,w,y都用都用x x来表示，可得：来表示，可得：=(1+x+x2)(1+2x+x2)=1+3x+4x2+3x3+x42.2 母函数母函数13第13页 定义：对于序列定义：对于序列a0 0,a1 1,a2 2,结构函结构函数：数：G(x)=G(x)=a0 0+a1 1x+a2 2x2+,+,称函数称函数G(x)G(x)是序列是序列a0 0,a1 1,a2 2,母函数。母函数。2.2 母函数母函数14第14页 例例2-42-4：某单位有：某单位有8 8个男同志，个男同志，5 5个女同个女同志，现要组织一个有数目为偶数男同志和志，现要组织一个有数目为偶数男同志和数目不少于数目不少于2 2个女同志组成小组，试求有多个女同志组成小组，试求有多少种组合方式。少种组合方式。解解:令令an为从为从8 8位男同志中抽取出位男同志中抽取出n 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)=11、母函数在求组合中应用、母函数在求组合中应用15第15页 数列数列a0,a8 8对应数值是对应数值是1,0,28,0,70,0,28,0,1。结构。结构母函数为：母函数为：类似方法可得女同志允许组合类似方法可得女同志允许组合数对应母函数为：数对应母函数为：1、母函数在求组合中应用、母函数在求组合中应用16第16页1、母函数在求组合中应用、母函数在求组合中应用17第17页 假如令假如令a1=a2=an=1 1，假如令假如令x=1，就得到以下组合公式：，就得到以下组合公式：1、母函数在求组合中应用、母函数在求组合中应用*18第18页2、几个基本母函数、几个基本母函数19第19页2、几个基本母函数、几个基本母函数20第20页 例例2-5：求由：求由20个水果组成一袋可能组合，水果个水果组成一袋可能组合，水果有苹果、香蕉、橘子和梨，其中在每个袋子中有苹果、香蕉、橘子和梨，其中在每个袋子中苹果数是偶数，香蕉数是苹果数是偶数，香蕉数是5倍数，橘子数最多是倍数，橘子数最多是4个，而梨个数是个，而梨个数是0和和1。解：单独苹果序列组成母函数解：单独苹果序列组成母函数 单独香蕉序列组成母函数单独香蕉序列组成母函数3、母函数在求组合数中应用、母函数在求组合数中应用21第21页 解：单独苹果序列组成母数解：单独苹果序列组成母数 单独香蕉序列组成母函数单独香蕉序列组成母函数 单独橘子序列组成母函数单独橘子序列组成母函数 单独梨子序列组成母函数单独梨子序列组成母函数3、母函数在求组合数中应用、母函数在求组合数中应用22第22页由由20个水果组成一袋可能组合数是个水果组成一袋可能组合数是21种种3、母函数在求组合数中应用、母函数在求组合数中应用23第23页假设假设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)=x/(1-x)(1-2x)=2xG(x)+x+x2+2xG(x)+x/(1-x)3、用母函数求解递推关系、用母函数求解递推关系24第24页3、用母函数求解递推关系、用母函数求解递推关系第第n n项系数为项系数为A+B2A+B2n n代入边界条件：代入边界条件：h h0 0=0,h=0,h1 1=1=125第25页得得A=-1A=-1，B=1B=1则：则：hn=2n-13、用母函数求解递推关系、用母函数求解递推关系第第n n项系数为项系数为A+B2A+B2n n代入边界条件：代入边界条件：h h0 0=0,h=0,h1 1=1=126第26页例例2-2 Fibonacci(费卜拉契）数列费卜拉契）数列 问题：设有初生雌、雄小兔一对，问题：设有初生雌、雄小兔一对，但第但第2 2个月过后便每个月繁殖雌、雄各一个月过后便每个月繁殖雌、雄各一小兔一对，试问第小兔一对，试问第n n个月有雌、雄兔子多个月有雌、雄兔子多少对？少对？2.1 递推关系递推关系 1 1，1 1，2 2，3 3，5 5，8 8，1313，2121Fn=Fn-1+Fn-2 27第27页令令Fn母函数为：母函数为：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-x2F2x3+F3x4+=x(F2x2+F3x3+)=x(G(x)-x)F1x3+F2x4+=x2(F1x+F2x2+)=x2G(x)整理后得整理后得 (1-x-x2)G(x)=x3、用母函数求解递推关系、用母函数求解递推关系28第28页3、用母函数求解递推关系、用母函数求解递推关系29第29页3、用母函数求解递推关系、用母函数求解递推关系*30第30页2.5、母函数性质、母函数性质性质性质1 1假如那么 性质性质2 2假如：那么：31第31页2.5、母函数性质、母函数性质性质性质3 3假如那么 性质性质4 4假如：那么：32第32页2.5、母函数性质、母函数性质性质性质5 5假如那么 性质性质6 6假如：那么：33第33页第第2章章 递推关系与母函数递推关系与母函数 2.1 2.1 递推关系递推关系 2.2 2.2 母函数母函数(生成函数生成函数)2.3 Fibonacci2.3 Fibonacci数列数列2.4 2.4 优选法与优选法与FibonacciFibonacci序列应用序列应用 2.5 2.5 母函数性质母函数性质 2.6 2.6 线性常系数齐次递推关系线性常系数齐次递推关系 2.7 2.7 关于常系数齐次递推关系关于常系数齐次递推关系 2.8 2.8 整数拆分整数拆分 2.9 ferrers 2.9 ferrers图像图像 2.10 2.10 拆分数预计拆分数预计 2.11 2.11 指数型母函数指数型母函数 2.12 2.12 广义二项式定理广义二项式定理 2.13 2.13 应用举例应用举例 2.14 2.14 非线性递推关系举例非线性递推关系举例 2.15 2.15 递推关系解法补充递推关系解法补充34第34页