第7章 递推关系和生成函数优秀课件.ppt

第7章 递推关系和生成函数第1页，本讲稿共55页7.1 一些数列一些数列算术序列（等差数列）算术序列（等差数列）几何序列（等比数列）几何序列（等比数列）例例1：确定平面一般位置上的：确定平面一般位置上的n个互相交叠个互相交叠的圆所形成的区域数。的圆所形成的区域数。第2页，本讲稿共55页例例2(Fibonacci问题问题):Fibonacci数列是递推关系的又一典型问数列是递推关系的又一典型问题题,数列的本身有着许多应用数列的本身有着许多应用.(1)问题的提出问题的提出：假定初生的一对雌雄兔子：假定初生的一对雌雄兔子,从出生的第从出生的第2个月之后每个月都可以生出个月之后每个月都可以生出另外一对雌雄兔另外一对雌雄兔.如果第如果第1个月只有一对个月只有一对初生的雌雄兔子初生的雌雄兔子,问问n个月之后共有多少个月之后共有多少对兔子？对兔子？第3页，本讲稿共55页1月月2月月3月月4月月第4页，本讲稿共55页5月月6月月第5页，本讲稿共55页(2)求递推关系求递推关系:设满设满n个月时兔子对数为个月时兔子对数为Fn,则第则第n-1个月留下的兔子数目为个月留下的兔子数目为Fn-1对对;当月新生兔数目为当月新生兔数目为Fn-2对对,即第即第n-2个月的个月的所有兔子到第所有兔子到第n个月都有繁殖能力个月都有繁殖能力 Fn=Fn-1+Fn-2,F1=F2=1 (7.1)由递推关系由递推关系(7.1)式可依次得到式可依次得到 F3=F1+F2=2,F4=F2+F3=3,F5=F3+F4=3+2=5,前几项为：前几项为：0，1，1，2，3，5，8，13，21，34，55，89，144，233，第6页，本讲稿共55页(3)Fibonacci数列的性质数列的性质I.部分和部分和Sn n=f0 0+f1 1+f2 2+fn n=fn+2n+2-1II.Fibonacci数列是偶数当且仅当数列是偶数当且仅当n能被能被3整整除除III.Fibonacci数列满足公式数列满足公式第7页，本讲稿共55页例例3：令：令g0,g1,g2,gn,是满足下面给是满足下面给出的出的Fibonacci数列递推关系和初始条件：数列递推关系和初始条件：gn n=gn-1n-1+gn-2n-2 (n2)g0 0=2,g1 1=-1例例4：确定：确定2Xn棋棋盘盘用多米用多米诺诺骨牌完美覆骨牌完美覆盖的方法数盖的方法数hn n。例例5：确定用：确定用单单牌和多米牌和多米诺诺骨牌骨牌对对1Xn棋棋盘盘完美覆盖的方法数完美覆盖的方法数bn n。第8页，本讲稿共55页定理定理7.1.2 沿沿Pascal三角形左下到右上三角形左下到右上对角线上的二项式系数的和是对角线上的二项式系数的和是Fibonacci数数第9页，本讲稿共55页7.2 线性齐次递推关系线性齐次递推关系数列数列h0 0,h1 1,h2 2,hn n,hn=a1 1hn-1n-1+a2 2hn-2n-2+ak khn-kn-k+bn n(nk)错排数列排数列Dn n=(n-1)(Dn-2n-2+Dn-1n-1)(n 2)Dn n=nDn-1n-1+(-1)n (n 1)Fibonacci数列数列 Fn=Fn-1+Fn-2(n 2)阶乘序列乘序列hn n=nhn-1n-1(n 1)几何序列几何序列hn n=qhn-1n-1(n 1)第10页，本讲稿共55页hn n=a1 1hn-1n-1+a2 2hn-2n-2+ak khn-kn-k(nk)其中其中a1 1,a2 2,ak k 是常系数，称为常系数线性齐是常系数，称为常系数线性齐次递推关系。次递推关系。定理定理7.2.1 令令q为一非零数。则为一非零数。则hn n=qn是是hn n-a1 1hn-1n-1-a2 2hn-2n-2-ak khn-kn-k=0(ak k0,nk)的解，当的解，当且且仅当当q是多是多项式方程式方程xk-a1 1xk-1-a2 2xk-2-ak k=0的一个根。如果多项式方程有的一个根。如果多项式方程有k个不同个不同的根的根q1,q2,qk，则，则hn=c1q1n+c2q2n+ckqkn第11页，本讲稿共55页例例6：求满足初始值：求满足初始值h0=1,h1=2,h2=0的递推关的递推关系系hn=2hn-1+hn-2-2hn-3(n3)的解的解例例7：只由三个字母：只由三个字母a,b,c组成的成的长度度为n的的一些一些单词将在通信信道上将在通信信道上传输，满足条件：足条件：传输中不得有两个中不得有两个a连续出出现在任一在任一单词中。中。确定通信信道允确定通信信道允许传输的的单词个数。个数。例例8：递推关系推关系hn=4hn-1-4hn-2(n2)的解的解定理定理7.2.2 令令q1 1,q2 2,qt t为为hn n=a1 1hn-1n-1+a2 2hn-n-2 2+ak khn-kn-k(ak k0,nk)的特征方程的互异的的特征方程的互异的根。此根。此时，如果，如果qi i是是si i重根，重根，则对qi i部分一部分一般解般解为Hn n(i)=(c1 1+c2 2n+csi sinsi-1)qi in第12页，本讲稿共55页7.3 非齐次递推关系非齐次递推关系例例9(Hanoi塔问题塔问题)：n个圆盘依其半径大个圆盘依其半径大小小,从下而上套在柱从下而上套在柱A上上,如如图图3.1所示所示.每次只允许取一个转移到柱每次只允许取一个转移到柱B或或C上上,而且而且不允许大盘放在小盘上方不允许大盘放在小盘上方.若要求把若要求把A上上的的n个盘转移到个盘转移到C柱上柱上.请设计一种方法请设计一种方法,并估计要移动几个盘次并估计要移动几个盘次.现在只有现在只有A,B,C三根柱子可供使用三根柱子可供使用.第13页，本讲稿共55页图图ABC4132lHanoi塔是个经典问题塔是个经典问题.对于这个问题对于这个问题,我们先要设计算法我们先要设计算法,进而估计算法的计算进而估计算法的计算复杂性复杂性,这里就是这里就是移动的总次数移动的总次数.第14页，本讲稿共55页(1)算法设计：算法设计：ln=2时时,圆盘圆盘1从从A套在套在B上；把圆盘上；把圆盘2从从A转移到转移到C上；把圆盘上；把圆盘1从从B上转移到上转移到C上上.完毕完毕.ln=3时时,把圆盘把圆盘1从从A转移到转移到C上；把圆盘上；把圆盘2从从A转移到转移到B上；把圆盘上；把圆盘1从从C上转移到上转移到B上上;把圆盘把圆盘3从从A套在套在C上上;把圆盘把圆盘1从从B再转移再转移到到A上上;把圆盘把圆盘2从从B转移到转移到C上上,把圆盘把圆盘1从从A套在套在C上上.完毕完毕.l看看看看n=3的演示过程的演示过程.第15页，本讲稿共55页A AB BC C C C第16页，本讲稿共55页l假定假定n-1个盘子的转移算法已经确定个盘子的转移算法已经确定.l对对n个圆盘问题个圆盘问题,先把上面的圆盘先把上面的圆盘1,2,n-1转移到转移到B上上,再把最后一个盘子转移到再把最后一个盘子转移到C上上,然后把然后把B上的上的n-1个圆盘转移到柱个圆盘转移到柱C上上.转移完毕转移完毕.l这运用的是递归算法这运用的是递归算法n=2时给出了算法时给出了算法;n=3时先利用时先利用n=2时的算法把圆盘时的算法把圆盘1,2移移B上上;再把圆盘再把圆盘3转移到柱转移到柱C上上;再利用再利用n=2时时的算法把的算法把B上两个圆盘转移到柱上两个圆盘转移到柱C上上.n=4,5,以此类推以此类推.第17页，本讲稿共55页(2)算法分析算法分析：令：令hn表示表示n个圆盘所需要的个圆盘所需要的转移次数转移次数.根据算法先把前面根据算法先把前面n-1个盘子个盘子转移到转移到B上上;然后把第然后把第n个盘子转移到个盘子转移到C上上;最后再一次将最后再一次将B上的上的n-1个盘子转到个盘子转到C上上.l算法算法可实现性可实现性可用归纳法得到可用归纳法得到.因因n=2时时对对,假定假定n-1对对,那么那么n自然也对自然也对.l关于转移次数容易得到一个递归关系关于转移次数容易得到一个递归关系:hn=2hn-1+1,h1=1.第18页，本讲稿共55页例例10：解：解hn=3hn-1-4n(n1)h0=2步步骤总结I.求求求求齐齐次关系的一般解次关系的一般解次关系的一般解次关系的一般解II.求非求非求非求非齐齐次关系的一个特解次关系的一个特解次关系的一个特解次关系的一个特解III.将一般解和特解将一般解和特解将一般解和特解将一般解和特解联联合，按初始条件求系数合，按初始条件求系数合，按初始条件求系数合，按初始条件求系数困困难在于特解的求解。在于特解的求解。例例11：hn=2hn-1+3n(n1)h0=2例例12：hn=3hn-1+3n(n1)h0=2 例例13：hn=hn-1+n3(n1)h0=0第19页，本讲稿共55页7.4 生成函数（母函数）生成函数（母函数）l母函数就象一根晒衣绳母函数就象一根晒衣绳,我们把需要得我们把需要得到的一列数就挂在它上面到的一列数就挂在它上面.l假定我们的问题的解是一列数假定我们的问题的解是一列数:a0,a1,a2,an,.我们想知道这个数我们想知道这个数列是什么列是什么,我们期望得到怎样的答案我们期望得到怎样的答案?l当然当然,最好的答案就是关于最好的答案就是关于an的一个简单的一个简单的公式的公式.比如诸如比如诸如an=n2+3之类的表达式之类的表达式.即即,通项公式通项公式.第20页，本讲稿共55页l l但但是是,如如果果一一个个未未知知数数列列没没有有简简单单公公式式,或或者者即即便便存存在在,但但是是很很复复杂杂,很很不不容容易易得得到到,我们也不知道我们也不知道,该怎么办该怎么办?l l如如果果我我们们还还希希望望研研究究这这个个数数列列,讨讨论论它它的的性质性质,该如何下手该如何下手?l举举一一个个极极端端的的例例子子,假假定定这这个个数数列列是是2,3,5,7,11,13,17,19,23,.,此此处处an是是第第n个个素素数数.这这样样的的情情况况,期期望望任任何何简简单单的的公公式都是不合理的式都是不合理的.第21页，本讲稿共55页l母函数母函数把数列的所有成员用一种非常巧妙的把数列的所有成员用一种非常巧妙的方法联系在一起方法联系在一起,虽然这样做并不一定能得虽然这样做并不一定能得到数列的简单公式到数列的简单公式,可是也许能够给出一个可是也许能够给出一个幂级数和幂级数和的简单公式的简单公式,展开这个和函数展开这个和函数,所得到的所得到的幂级数幂级数的的系数系数就是我们所要找就是我们所要找的的数列数列.l比如后面我们将会学习到的比如后面我们将会学习到的Fibonacci 数数列列,它满足一个递归关系它满足一个递归关系l Fn+1=Fn+Fn-1 (n 2;F1=F2=1).第22页，本讲稿共55页1.母函数概念母函数概念 l设有设有a,b,c三个不同的球三个不同的球,从中选取一个从中选取一个,或选或选a,或选或选b,或选或选c,把这些可能的选把这些可能的选取形象地表示为取形象地表示为a+b+c.l类似地类似地,从中选取二个从中选取二个,或选或选a和和b,或选或选a和和c,或选或选b和和c.可形象地表示为可形象地表示为ab+ac+bc,同样同样,从中选取三个从中选取三个,只有只有一种方法一种方法,也可形象地表示为也可形象地表示为abc.第23页，本讲稿共55页l从多项式从多项式 (1+ax)(1+bx)(1+cx)(7.2)=1+(a+b+c)x+(ab+ac+bc)x2+(abc)x3 中发现中发现,所有这些可能的选取方式正好是所有这些可能的选取方式正好是x幂的系数幂的系数.其中其中xi的系数是从三个球中选的系数是从三个球中选取取i个的方法之形象表示个的方法之形象表示.l因子因子(1+ax)形象地指出形象地指出,对球对球a,有两种选有两种选取方法取方法:不选不选a,或选或选a.因子因子(1+ax)中的中的1表示不选表示不选a,而而x的系数的系数a表示选表示选a.第24页，本讲稿共55页l既然在上述多项式中既然在上述多项式中,xi的系数表明选取的系数表明选取i个球的方法个球的方法,那么那么 (1+ax)(1+bx)(1+cx)所表明的是所表明的是:对对a,b,c三球三球,选取的方法选取的方法是是,“选选a或不选或不选a”和和“选选b或不选或不选b”以及以及“选选c或不选或不选c”.l多项式中多项式中x的幂次表示选取球的个数的幂次表示选取球的个数,而而其相应系数表示一切可能的选取方法其相应系数表示一切可能的选取方法.第25页，本讲稿共55页l如果我们只如果我们只关心关心不同组合方案的不同组合方案的数目数目,不不关心关心各种各种方案方案的罗列的罗列.可以在可以在(7.2)式中令式中令a=b=c=1,则得到则得到l(1+x)3 =C(3,0)+C(3,1)x+C(3,2)x2+C(3,3)x3=1+3x+3x2+x3.(7.3)l总方案数总方案数N=C(3,0)+C(3,1)+C(3,2)+C(3,3)=1+3+3+1=8.第26页，本讲稿共55页l(7.3)就是一个关于形式变量就是一个关于形式变量x的幂函数的幂函数,这个幂函数中不同幂次的系数都是一个这个幂函数中不同幂次的系数都是一个组合数组合数.l这可以推广到任意这可以推广到任意n个不同球所有可能组个不同球所有可能组合的方案数情况合的方案数情况.这其实就是我们大家这其实就是我们大家熟悉的二项式系数熟悉的二项式系数.不过现在我们是用不过现在我们是用形式级数的观点来看问题形式级数的观点来看问题.l利用这种形式级数不仅仅是一种不同的利用这种形式级数不仅仅是一种不同的表达形式表达形式,还非常有用还非常有用.第27页，本讲稿共55页2.母函数定义母函数定义定义定义7.1 利用给定序列利用给定序列a0,a1,a2,所构造的所构造的函数函数 F(x)=a0+a1x+a2x2+称为序列称为序列a0,a1,a2,的的母函数母函数.l母函数定义中的级数是母函数定义中的级数是形式幂级数形式幂级数,不必关不必关心收敛性心收敛性,x只是一个形式变量只是一个形式变量.l有限序列有限序列 a0,a1,an也可以定义它的母函也可以定义它的母函数数.(后面添加后面添加0)第28页，本讲稿共55页3.母函数的运算母函数的运算 设序列设序列ai的母函数的母函数A(x)=aixi,bi的母的母函数为函数为B(x)=bixi.运算定义如下运算定义如下:(1)相等相等:A(x)=B(x)ai=biai=bi,i=1,2,(2)相加相加:A(x)+B(x)=(ai+bi)xi(3)相减相减:A(x)-B(x)=(ai-bi)xi(4)数乘数乘:cA(x)=(cai)xi 第29页，本讲稿共55页(5)相乘相乘:A(x)B(x)=cixi,其中其中 c0=a0b0,c1=a0b1+a1b0,c2=a0b2+a1b1+a2b0,.,cr=a0br+a1br-1+arb0,.(6)逆逆:如果如果A(x)B(x)=1,则称则称B(x)为为A(x)的逆的逆,记为记为B(x)=A-1(x)=1/A(x).(显然两者互为逆显然两者互为逆.)第30页，本讲稿共55页例例14 设设F(x)=1+x+x2+,G(x)=1-x,由定由定义可以得到义可以得到 F(x)G(x)=1,因此因此1/G(x)=G-1(x)=F(x),即即这这同同微微积积分分中中函函数数1/(1-x)的的幂幂级级数数展展开开式式是完全一致的是完全一致的.第31页，本讲稿共55页例例15 设设则则(F(x)-G(x)(1-3x+2x2)=x.这说明这说明这与把它们看成普通函数的运算是一致的这与把它们看成普通函数的运算是一致的.第32页，本讲稿共55页例例16：令：令k是一个整数，并令序列是一个整数，并令序列h0,h1,h2,hn,使使hn等于等于e1+e2+ek=n的非负整数解的个数。的非负整数解的个数。例例17：确定苹果、香蕉、橘子和梨的：确定苹果、香蕉、橘子和梨的n组合组合的个数，其中在每个的个数，其中在每个n组合中苹果的个数是组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在偶数，香蕉的个数是奇数，橘子的个数在0和和4之间，而且至少要有一个梨。之间，而且至少要有一个梨。例例18：确定可以由苹果、香蕉、橘子和梨：确定可以由苹果、香蕉、橘子和梨袋装水果的袋数袋装水果的袋数hn，其中在每个袋子中苹果，其中在每个袋子中苹果数是偶数，香蕉数是数是偶数，香蕉数是5的倍数，橘子数最多的倍数，橘子数最多是是4个，梨的个数为个，梨的个数为0或或1。第33页，本讲稿共55页例例19：确定方程：确定方程e1+e2+ek=n的非负奇整的非负奇整数解数解e1,e2,ek的个数的个数hn的母函数。的母函数。例例20：令：令hn表示方程表示方程3e1+4e2+2e3+5e4=n的的非负整数解的个数。求非负整数解的个数。求h0,h1,h2,hn,的的母函数母函数g(x)。例例21：有无限多现成的一分、五分、一角、：有无限多现成的一分、五分、一角、两角五分和五角的硬币。确定用这些硬币两角五分和五角的硬币。确定用这些硬币凑成凑成n分钱方法数分钱方法数hn的母函数的母函数g(x)。第34页，本讲稿共55页7.5 母函数与递归母函数与递归 例例例例2222(HanoiHanoi塔问题塔问题塔问题塔问题)：h hn n=2=2h hn n-1 1+1,+1,h h1 1=1.=1.(7.4)(7.4)令令令令 H(H(x x)=)=h h1 1x x+h h2 2x x2 2+h h3 3x x3 3+H(H(x x)是序列是序列是序列是序列h h1 1,h h2 2,h h3 3,的母函数的母函数的母函数的母函数.给出了序列给出了序列给出了序列给出了序列,就可确定对应的母函数就可确定对应的母函数就可确定对应的母函数就可确定对应的母函数.反过来也一样反过来也一样反过来也一样反过来也一样,求得了母函数求得了母函数求得了母函数求得了母函数,对应得序列也就可得而知对应得序列也就可得而知对应得序列也就可得而知对应得序列也就可得而知.当然当然当然当然,利用递推关系利用递推关系利用递推关系利用递推关系(7.4)(7.4)也可迭代求得也可迭代求得也可迭代求得也可迭代求得h h2 2,h h3 3,.但现但现但现但现在我们一要寻找明确的公式在我们一要寻找明确的公式在我们一要寻找明确的公式在我们一要寻找明确的公式,二要显示母函数的作用二要显示母函数的作用二要显示母函数的作用二要显示母函数的作用.第35页，本讲稿共55页令令H(x)=h1x+h2x2+h3x3+hnxn+为生成为生成函数，有以下方程：函数，有以下方程：H(x)=h1x+h2x2+h3x3+hnxn+-2xH(x)=-2h1x2-2h2x3-2h3x4-2hnxn+1-相加：相加：(1-2x)H(x)=h1x+(h2-2h1)x2+(h3-2h2)x3+(hn-2hn-1)xn+=x(1+x+x2+x3+)=x/(1-x)H(x)=x/(1-x)(1-2x)(7.5)第36页，本讲稿共55页l这就是转移次数数列的母函数这就是转移次数数列的母函数.l但是我们希望得到但是我们希望得到显式显式表达式表达式.l这不难做到这不难做到.可以从母函数的幂级数展可以从母函数的幂级数展开式中求得数列开式中求得数列h1,h2,h3,.l我们下面所运用的方法是处理这种问题的我们下面所运用的方法是处理这种问题的一个一个常规常规的方法的方法,初看起来可能感觉不太初看起来可能感觉不太适应适应,用多了就习以为常了用多了就习以为常了.l这就是所谓的部分分数的算法这就是所谓的部分分数的算法.第37页，本讲稿共55页(A+B)-(2A+B)x=x.解得解得A=-1,B=1.其实一眼就可看出结果其实一眼就可看出结果.这里只是想说这里只是想说 明方法而已明方法而已.第38页，本讲稿共55页第39页，本讲稿共55页(3)算法评价算法评价:hn是要移动圆盘数是要移动圆盘数n(规模规模)的指数函数的指数函数,以以n=60为例子为例子.可以计算出可以计算出260 1.15292 1018.这个数是一个什么这个数是一个什么概念概念?假如你每秒钟移动一个盘假如你每秒钟移动一个盘,按照按照上述算法上述算法,你移动你移动60个盘的时间是个盘的时间是:第40页，本讲稿共55页l真是不算不知道真是不算不知道,一算吓一跳一算吓一跳.n=60,数不数不过百过百,2也是很小的整数也是很小的整数,可是可是260却是一却是一个很大的数个很大的数.l这就是所谓的这就是所谓的“指数爆炸指数爆炸”现象现象.一般称复一般称复杂性为规模杂性为规模n的指数函数的算法为的指数函数的算法为“坏算法坏算法”.好算法好算法是指多项式算法或者线性算法是指多项式算法或者线性算法.第41页，本讲稿共55页例例23：确定平方项序列：确定平方项序列0,1,4,n2,的母的母函数函数例例24：求解满足初始值：求解满足初始值h0=1和和h1=-2的递推的递推关系关系hn=5hn-1-6hn-2(n2)例例25：令：令h0,h1,hn,是是满足足递推关系推关系hn+hn-1-16hn-2+20hn-3=0(n3)的数列，其的数列，其中中h0=0,h1=1,h2=-1。求。求hn的一般公式。的一般公式。第42页，本讲稿共55页定理定理7.5.1 令令h0,h1,hn,为满足为满足k阶常系数阶常系数线性齐次递推关系线性齐次递推关系hn n-c1 1hn-1n-1-c2 2hn-2n-2-ck khn-kn-k=0(ck k0,nk)的数列。的数列。则它的生成函数它的生成函数g(x)形形如如g(x)=p(x)/q(x)其中，其中，q(x)为具有非零常数具有非零常数项的的k次多次多项式，式，p(x)是小于是小于k次的多次的多项式。反之也成立。式。反之也成立。第43页，本讲稿共55页l一般母函数是用基函数一般母函数是用基函数1,x,x2,来定来定义的义的.l这种母函数对于这种母函数对于组合类型的数列组合类型的数列的研的研 究究很有用很有用.但是但是,对研究对研究排列类型的数列排列类型的数列用用起来很不方便起来很不方便.l排列类型数列是用基函数排列类型数列是用基函数1,x,x2/2!,来定义来定义,这样使用起来更这样使用起来更方便一些方便一些.l基本思想并没有变基本思想并没有变,只是选择了新的只是选择了新的基基.7.6 指数生成函数指数生成函数第44页，本讲稿共55页l基函数正好是出现在函数基函数正好是出现在函数ex的幂级数展开的幂级数展开式中的函数式中的函数:设有数列设有数列a0,a1,a2,，则称下列函数为则称下列函数为 该数列的该数列的指数型母函数指数型母函数:第45页，本讲稿共55页l构造指数型母函数的目的是为了使得母函数构造指数型母函数的目的是为了使得母函数形式更简单形式更简单,尤其对排列类型的递归数列更尤其对排列类型的递归数列更是如此是如此.看几个简单例子看几个简单例子.例例26 设设n为正整数为正整数,则数列则数列P(n,0),P(n,1),P(n,2),P(n,n)的的指数型母函数指数型母函数为为:其普通型母函数如何其普通型母函数如何?第46页，本讲稿共55页例例27 数列数列1,1,1,的指数型母函数为的指数型母函数为更一般的更一般的,设设a为任意实数为任意实数,数列数列a0=1,a1,a2,a3,的指数型母函数为的指数型母函数为第47页，本讲稿共55页(a)设设n=n1+n2+nk.若元素若元素a1有有n1个个,元素元素a2有有n2个个,元素元素ak有有nk个个,则由则由 这这n个元素组成的不同的排列总数为个元素组成的不同的排列总数为(b)设设n=n1+n2+nk.若元素若元素a1有有n1个个,元素元素a2有有n2个个,元素元素ak有有nk个个,由这由这n个元素中取个元素中取r个排列数为个排列数为pr,则序列则序列p0,p1,pn的指数型母函数为的指数型母函数为:第48页，本讲稿共55页xr项的系数项的系数为为ar=pr/r!.pr=arr!第49页，本讲稿共55页定理定理 令令S为多重集为多重集n1.a1,n2.a2,nk.ak,其中其中n1,n2,nk均为非负整数。令均为非负整数。令hn是是S的的n排列数，则序列排列数，则序列h1,h2,hn的指数生的指数生成函数由成函数由 给定，其中，给定，其中，第50页，本讲稿共55页例例28 若有若有8个元素个元素,其中设其中设a1重复重复3次，次，a2重重复复2次次,a3重复重复3次次.从中取从中取r个元素的排列个元素的排列数数pr,则序列则序列p0,p1,p2,p8的指数型母的指数型母函数为函数为:如何得出如何得出pr?例如：例如：p4=4!(35/12)=70.第51页，本讲稿共55页例例29 确定用确定用红红、绿绿、蓝蓝三色对三色对1 n棋盘的方格进棋盘的方格进棋盘的方格进棋盘的方格进行染色的方案数行染色的方案数行染色的方案数行染色的方案数an n,并且使得并且使得并且使得并且使得绿色绿色的方格数为的方格数为偶偶数数.解解 约定约定a0=1.显然显然 an为三种颜色组成的为三种颜色组成的n阶排阶排列列,每种颜色的重复数没有限制每种颜色的重复数没有限制,但是绿色但是绿色在排列中必须出现偶数次在排列中必须出现偶数次.这样这样an的指数的指数型母函数为型母函数为第52页，本讲稿共55页例例30：令令hn表示数字表示数字1，2或或3组成的组成的n位数字位数字数的个数，其中数的个数，其中1的个数为偶数，的个数为偶数，2的个数的个数至少是至少是3，3的个数最多是的个数最多是4。确定结果数列。确定结果数列h1,h2,hn的指数生成函数。的指数生成函数。例例31：确定每位数字都是奇数的确定每位数字都是奇数的n位数的个位数的个数数hn，其中，其中1和和3出现偶数次。出现偶数次。例例32：确定用红色、白色和蓝色对确定用红色、白色和蓝色对1行行n列棋列棋盘的方格涂色的方法数盘的方格涂色的方法数hn，其中红方格的个，其中红方格的个数是偶数并且至少有一个蓝方格数是偶数并且至少有一个蓝方格。第53页，本讲稿共55页例例33 一个凸一个凸n边形边形,通过不相交于通过不相交于n边形内部边形内部的对角线的对角线,把把n边形拆分成若干三角形边形拆分成若干三角形,不不同拆分的数目用同拆分的数目用hn表之表之.五边形有如下五种拆分方案五边形有如下五种拆分方案,故故h5=5.7.7 一个几何的例子一个几何的例子第54页，本讲稿共55页定理定理 通过画出区域内部不相交的对角线将通过画出区域内部不相交的对角线将具有具有n+1条边的凸多边形区域分割成三角形条边的凸多边形区域分割成三角形区域，令区域，令hn表示分成三角形区域的方法数。表示分成三角形区域的方法数。定义定义h1=1。则。则hn满足递推关系满足递推关系 该递推关系的解为该递推关系的解为第55页，本讲稿共55页