递推关系与生成函数优秀课件.ppt

《递推关系与生成函数优秀课件.ppt》由会员分享，可在线阅读，更多相关《递推关系与生成函数优秀课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递推关系与生成函数推关系与生成函数1第1页，本讲稿共51页摘要摘要线性齐次递推关系线性齐次递推关系 生成函数生成函数 递归和生成函数递归和生成函数一个几何的例子一个几何的例子指数生成函数指数生成函数作业作业 2第2页，本讲稿共51页线性齐次递推关系线性齐次递推关系3第3页，本讲稿共51页线性递推关系线性递推关系令令 h0,h1,hn,是一个数列，如果是一个数列，如果存在量存在量 a1,a2,ak,ak 0,和量和量bn(每每一个量一个量 a1,a2,ak,bn 可能依赖于可能依赖于 n)，使得，使得 hn=a1hn-1+a2hn-2+akhn-k+bn,(n k).则称该序列满足则称该序列满足

2、k阶线性递推关系阶线性递推关系.4第4页，本讲稿共51页例子 错位排列数列错位排列数列 D0,D1,D2,Dn 满足两满足两个递推关系个递推关系Dn=(n-1)Dn-1+(n-1)Dn-2,(n 2)Dn=nDn-1+(-1)n,(n 1).第一个递推关系的阶第一个递推关系的阶 是多少是多少 且且 a1，a2，bn等于多少。等于多少。第二个递推关系的第二个递推关系的.5第5页，本讲稿共51页齐次的齐次的 如果如果bn=0，则线性递推关系，则线性递推关系 hn=a1hn-1+a2hn-2+akhn-k+bn,(n k)称为称为齐次的齐次的.如果如果a1,a2,ak 是常数是常数,则称线性递推则称

3、线性递推关系式具有关系式具有常系数常系数.6第6页，本讲稿共51页定理定理 7.2.1令令q 为一个非零数为一个非零数.则则 hn=qn 是常系数线性递推关系是常系数线性递推关系 hn a1hn-1 a2hn-2 akhn-k=0,(ak 0,n k)(7.20)的解，当且仅当的解，当且仅当q是多项式是多项式 xk a1xk-1 a2xk-2 ak=0.(7.21)的一个根。的一个根。如果多项式方程有如果多项式方程有k个不同的根个不同的根 q1,q2,qk,则则 hn=c1q1n+c2q2n+ckqkn (7.22)是下述意义下式是下述意义下式 (7.20)的一般解的一般解:无论给定无论给定

4、h0,h1,什么初始值，什么初始值，都存在都存在 常数常数c1,c2,ck 使得式使得式(7.22)是满足递推关系是满足递推关系(7.20)和初始条件的唯一的序列和初始条件的唯一的序列.7第7页，本讲稿共51页注解注解 多项式方程多项式方程(7.21)叫做叫做 递推关系递推关系(7.20)的的特征方程特征方程，而它的，而它的 k 个根叫做个根叫做 特征根特征根.如果特征根如果特征根 互异互异,那么式那么式(7.22)就是式就是式(7.20)的的一般解一般解.8第8页，本讲稿共51页例题例题求解满足求解满足h0=1,h1=2 and h2=0的递推的递推关系关系 hn=2hn-1+hn-2 2h

5、n-3,(n 3).提示提示:这个递推关系的特征方程为这个递推关系的特征方程为 x3 2x2 x+2=0 而它的三个根而它的三个根 1,-1,2.根据定理根据定理7.2.1,hn=c11n+c2(-1)n+c32n 是一般解是一般解.9第9页，本讲稿共51页例题（续）例题（续）由三个字母由三个字母a,b,c组成的长度为组成的长度为n的一些的一些单词将在通信信道上传输，满足条件：单词将在通信信道上传输，满足条件：传输中不得有两个传输中不得有两个a连续出现在任一个单连续出现在任一个单词中。确定通信信道允许传输的单词个词中。确定通信信道允许传输的单词个数。数。10第10页，本讲稿共51页提示 首先首

6、先,找到特征关系式找到特征关系式 并且求出它的解并且求出它的解.令令 hn 表示允许传输的长度为表示允许传输的长度为 n的单词的个数的单词的个数.我我们有们有 h0=1 和和 h1=3.令令 n 2.如果第一个字母如果第一个字母是是 b 或者或者 c,那么这个单词就可以有那么这个单词就可以有 hn-1种方法构种方法构成成.如果第一个字母是如果第一个字母是 a,那么第二个字母是那么第二个字母是 b 或者或者 c.这样这样,hn=2 hn-1+2hn-2,(n 2).ba b11第11页，本讲稿共51页练习练习 一个一个 1n 棋盘棋盘.我们把每个方格都涂上我们把每个方格都涂上红色或者蓝色红色或者

7、蓝色.令令 hn 表示没有两个连续表示没有两个连续的方格被同时涂上红色的方法的个数的方格被同时涂上红色的方法的个数.找找到并且证明这样的一个递推关系到并且证明这样的一个递推关系hn.然后然后求得公式求得公式 hn.求解递推关系求解递推关系 hn=4hn-1 4hn-2,(n 2).12第12页，本讲稿共51页注解注解 如果特征方程的根如果特征方程的根 q1,q2,qk 不是互不是互异的异的,那么那么 hn=c1q1n+c2q2n+ckqkn 就就不是递推关系的一个一般解不是递推关系的一个一般解.13第13页，本讲稿共51页定理定理 7.2.2 令令 q1,q2,qt 为常系数线性齐次递推关为常

8、系数线性齐次递推关系系(7.20)的特征方程的互异的根的特征方程的互异的根.此时，此时，如果如果 qi是是 si重根重根,则该递推关系对则该递推关系对qi的部的部分一般解为分一般解为 Hn(i)=c1qin+c2nqin+csinsi-1qin =(c1+c2n+csinsi-1)qin 递推关系的一般解则是递推关系的一般解则是hn=Hn(1)+Hn(2)+Hn(t).14第14页，本讲稿共51页例题例题求递推关系求递推关系 hn=4hn-1 4hn-2,(n 2).提示提示:特征方程是特征方程是 x2-4x+4=0.这样这样 2 是是重特征根重特征根.特征关系的一般解为特征关系的一般解为 h

9、n=c12n+c2n2n.15第15页，本讲稿共51页练习练习 求特征关系求特征关系 hn=-hn-1+3hn-2+5hn-3+2hn-4,(n 4).16第16页，本讲稿共51页生成函数生成函数 17第17页，本讲稿共51页生成函数的方法生成函数的方法利用代数的方法计算一个问题可能性的利用代数的方法计算一个问题可能性的次数次数生成函数是无穷次可微函数的泰勒级数生成函数是无穷次可微函数的泰勒级数如果你可以找到一个函数和它的泰勒级如果你可以找到一个函数和它的泰勒级数数,那么泰勒级数的系数则给出这个问那么泰勒级数的系数则给出这个问题的解题的解.18第18页，本讲稿共51页生成函数的定义生成函数的定

10、义令令 h0,h1,hn,是一个无穷的数列是一个无穷的数列.它的它的 生生成函数成函数 被定义为无穷级数被定义为无穷级数 g(x)=h0+h1x+h2x2+hnxn+在在 g(x)中，中，xn 的系数是这个序列的第的系数是这个序列的第n项项 hn,从而，从而，xn 作为作为hn的的“位置持有者位置持有者”。19第19页，本讲稿共51页例题例题1.无限序列的生成函数无限序列的生成函数 1,1,1,1,它的每一它的每一项都等于项都等于1 g(x)=1+x+x2+xn+=1/(1-x)2.M是一个正整数是一个正整数.二项式序列二项式序列 c(m,0),c(m,1)c(m,2),.,c(m,m)的生成

11、函数是的生成函数是 gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+c(m,m)xm =(1+x)m (二项式定理二项式定理).20第20页，本讲稿共51页练习练习 令令a为一个实数为一个实数.根据牛顿二项式定理根据牛顿二项式定理,二二项式系数项式系数 c(a,0),c(a,1),c(a,n),的无的无穷生成函数是什么？穷生成函数是什么？令令 k 是一个整数，是一个整数，并令序列并令序列 h0,h1,h2,hn,使得使得hn等于等于 e1+e2+ek=n的的非负整数的个数非负整数的个数.这个序列的生成函数是这个序列的生成函数是什么什么?21第21页，本讲稿共51页复习 令令a是一个

12、实数是一个实数.那么对于所有的那么对于所有的 x 和和 y（0|x|y|）,22第22页，本讲稿共51页又因为又因为|y|11)24第24页，本讲稿共51页例题（续）例题（续）确定苹果、香蕉、橘子和梨的确定苹果、香蕉、橘子和梨的n-组合的个数组合的个数,其中其中在每个在每个n-组合中苹果的个数是偶数，香蕉的个数组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在是奇数，橘子的个数在0和和4之间，而且至少要有之间，而且至少要有一个梨一个梨提示提示:该问题等价于找出该问题等价于找出 e1+e2+e3+e4=n.的非负整数解的个数的非负整数解的个数25第25页，本讲稿共51页 其中其中 e1 是偶

13、数是偶数(e1 为苹果数为苹果数),e2 是奇数是奇数,0 e34,而而 e4 1.我们为每种类型的水果建立一我们为每种类型的水果建立一个因子，个因子，其中的指数为那种类型水果的其中的指数为那种类型水果的n-组组合中所允许的数合中所允许的数:g(x)=(1+x2+x4+)(x+x3+x5+)(1+x+x2+x3+x4)(x+x2+x3+x4+)26第26页，本讲稿共51页练习练习 令令hn代表好几袋子苹果、香蕉、橘子和梨代表好几袋子苹果、香蕉、橘子和梨的总个数的总个数,并且每个袋子中苹果的个数是并且每个袋子中苹果的个数是偶数偶数,香蕉的隔数是香蕉的隔数是 5的倍数的倍数,橘子的个数橘子的个数至

14、多为至多为 4 并且梨的个数为并且梨的个数为 0 或者或者 1.提示提示:计算这个问题的生成函数的计算这个问题的生成函数的xn的系数的系数.27第27页，本讲稿共51页练习（续）练习（续）确定方程确定方程 e1+e2+ek=n非负整数解非负整数解e1,e2,ek 的个数的个数hn的生成函数。的生成函数。提示提示:k(x+x3+x5+x7+).28第28页，本讲稿共51页练习练习(续续)令令 hn 表示方程表示方程 3e1+4e2+2e3+5e4=n非负非负整数解的个数整数解的个数.找到找到h0,h1,h2,hn,.的生成函数的生成函数 g(x)提示提示:令令 f1=3e1,f2=4e2,f3=

15、2e3 并且并且 f4=5e4.于是于是hn 也等于也等于 f1+f2+f3+f4=n 的非的非负整数解的个数，其中负整数解的个数，其中 f1 是是 3的倍数的倍数,f2 是是 4的倍数的倍数,f3 是偶数是偶数 并且并且 f4 是是 5的倍数的倍数.29第29页，本讲稿共51页递归生成函数递归生成函数30第30页，本讲稿共51页内容内容利用生成函数来求解常系数的线性齐次利用生成函数来求解常系数的线性齐次递推关系递推关系.牛顿二项定理的应用牛顿二项定理的应用.31第31页，本讲稿共51页复习复习:牛顿二项定理牛顿二项定理如果如果 n是一个正整数是一个正整数 并且并且 r 是一个非零整数是一个非

16、零整数,那那么么32第32页，本讲稿共51页例题例题确定平方项的序列确定平方项的序列 0,1,4,n2,.的生成函数的生成函数解答解答:把把 n=2、r=1带入上面的牛顿二项式带入上面的牛顿二项式,(1-x)-2=1+2x+3x2+nxn-1+.因此因此 x/(1-x)2=x+2x2+3x3+nxn+.微分微分,我们得到我们得到（1+x)/(1-x)3=1+22x+32x2+n2xn-1+.乘乘 x,得到得到 x(1+x)/(1-x)3.33第33页，本讲稿共51页例题例题(续续)求解满足初始值求解满足初始值 h0=1 和和 h1=-2的递推的递推关系关系 hn=5hn-1 6 hn-2,(n

17、2).提示提示:令令 g(x)=h0+h1x+h2x2+hnxn+.为为 h0,h1,h2,hn 的生成函数。此的生成函数。此时，我们有下列方程时，我们有下列方程 34第34页，本讲稿共51页g(x)=h0+h1x+h2x2+hnxn+.-5xg(x)=-5h0 x-5h1x2-5h2x3-5hn-1 xn-.6x2 g(x)=6h0 x2+6h1x3+6h2x4+6hn-2xn+.将三个方程相加将三个方程相加,得到得到(1-5x+6x2)g(x)=h0+(h1-5h0)x+(h2-5h1+6h0)x2+(hn-5hn-1+6hn-2)xn+.=h0+(h1-5h0)x=1-7x因此因此,g(

18、x)=(1-7x)/(1-5x+6x2)=5/(1-2x)4/(1-3x)35第35页，本讲稿共51页通过牛顿二项定理通过牛顿二项定理(1-2x)-1=1+2x+22x2+2nxn.(1-3x)-1=1+3x+32x2+3nxn.于是于是,g(x)=1+(-2)x+(-15)x2+(52n 43n)xn+可以得到可以得到 hn=52n 43n (n=0,1,2,).36第36页，本讲稿共51页练习 满足满足h0=0,h1=1，h2=-1的递推关系的递推关系 hn+hn-1 16 hn-2+20hn-3=0(n3)求求hn的一般公式。的一般公式。37第37页，本讲稿共51页一个几何的例子一个几何

19、的例子38第38页，本讲稿共51页划分凸多边形的方法划分凸多边形的方法通过画出在区域内部不相交的对角线将具通过画出在区域内部不相交的对角线将具有有n+1 条边的凸多边形区域分成三角形区域，令条边的凸多边形区域分成三角形区域，令hn 表示分成三角形区域的方法数。定义表示分成三角形区域的方法数。定义h1=1.则则 hn 满足递推关系满足递推关系 hn=h1hn-1+h2hn-2+hn-1h1,(n2).该递推关系的解为该递推关系的解为 hn=n-1C(2n-2,n-1),(n=1,2,3,).39第39页，本讲稿共51页指数生成函数指数生成函数40第40页，本讲稿共51页复习复习:ex的泰勒级数的

20、泰勒级数41第41页，本讲稿共51页指数生成函数的定义指数生成函数的定义 序列序列 h0,h1,h2,hn,的指数生成函数的指数生成函数 42第42页，本讲稿共51页例子例子 令令n为一正整数为一正整数.确定数列确定数列P(n,0),P(n,1),P(n,2),P(n,n),的指数生成函数的指数生成函数,其中其中 P(n,k)表示表示n-元素集的元素集的k-排列的个数排列的个数,对对于于k=0,1,n 其值为其值为n!/(n-k)!.指数生指数生成函数为成函数为43第43页，本讲稿共51页因此因此,(1+x)n 既是序列既是序列P(n,0),P(n,1),P(n,2),P(n,n)的指数生成函

21、数又是序列的指数生成函数又是序列C(n,0),C(n,1),C(n,2),C(n,n)的常规生成函数的常规生成函数.44第44页，本讲稿共51页练习练习(续续)序列序列1,1,1,1,.的指数生成函数是的指数生成函数是更一般的更一般的,如果如果a是一个实数是一个实数,那么序列那么序列a0=1,a,a2,an,.的指数生成函数是的指数生成函数是45第45页，本讲稿共51页定理定理令令S为多重集为多重集 n1.a1,n2.a2,nk.ak,其中其中 n1,n2,nk 均为非负整数均为非负整数.令令hn 是是S的的n-排列数排列数.则序列则序列h0,h1,h2,hn,的指数生成函数的指数生成函数g(

22、e)(x)由由 g(e)(x)=fn1(x)fn2(x).fnk(x)给定给定 其中其中,对于对于 i=1,2,k,fni(x)=1+x+x2/2!+xni/ni!.46第46页，本讲稿共51页例题例题如果把一个如果把一个1*n的棋盘上的偶数个方格染成红的棋盘上的偶数个方格染成红,白白,蓝三种颜色蓝三种颜色,共有多少种染色方案共有多少种染色方案?线索线索:令令 hn表示这样的染色方案数表示这样的染色方案数,定义定义h0=1.此时此时hn 等于三种颜色的多重集的等于三种颜色的多重集的n-排列数排列数,其其中每一种颜色都有无穷重复数中每一种颜色都有无穷重复数,且红色出现偶且红色出现偶数次数次.因此

23、因此,h0,h1,h2,hn,的指数生成函的指数生成函数是红数是红,白白,蓝因子的乘积蓝因子的乘积:47第47页，本讲稿共51页因此因此,hn=(3n+1)/2.48第48页，本讲稿共51页练习练习确定每个数字都是奇数的确定每个数字都是奇数的n位数的个数位数的个数,其中要求其中要求1和和3出现偶数次出现偶数次.线索线索:令令 h0=1.hn 等于多重集等于多重集S=1,3,5,7,9的的n-排列的个数排列的个数,其中要其中要求求1和和3出现偶数次出现偶数次.49第49页，本讲稿共51页练习练习(续续)用红用红,白白,蓝三种颜色给一个蓝三种颜色给一个1*n的棋盘染的棋盘染色色,如果有偶数方格必须染成红色如果有偶数方格必须染成红色,并且并且至少有一个蓝色的至少有一个蓝色的,求一共有多少种染色求一共有多少种染色方案方案?50第50页，本讲稿共51页作业作业625(ii)3137(iv).51第51页，本讲稿共51页