《递推关系与生成函数精选文档.ppt》由会员分享，可在线阅读，更多相关《递推关系与生成函数精选文档.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、递推关系与生成函数推关系与生成函数1本讲稿第一页，共五十一页摘要摘要线性齐次递推关系线性齐次递推关系 生成函数生成函数 递归和生成函数递归和生成函数一个几何的例子一个几何的例子指数生成函数指数生成函数作业作业 2本讲稿第二页，共五十一页线性齐次递推关系线性齐次递推关系3本讲稿第三页，共五十一页线性递推关系线性递推关系令令 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本讲稿第四页，共五十一页例子 错位排列数列错位排列数列 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本讲稿第五页，共五十一页齐次的齐次的 如果如果bn=0，则线性递推关系，则线性递推关系 hn=a1hn-1+a2hn-2+akhn-k+bn,(n k)称为称为齐次的齐次的.如果如果a1,a2,ak 是常数是常数,则称线
3、性递推则称线性递推关系式具有关系式具有常系数常系数.6本讲稿第六页，共五十一页定理定理 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.21)叫做叫做 递推关系递推关系(7.20)的的特征方程特征方程，而它的，而它的 k 个根叫做个根叫做 特征根特征根.如果特征根如果特征根 互异互异,那么式那么式(7.22)就是式就是式(7.20)的的一般解一般解.8本讲稿第八页，共五十一页例题例题求解满足求解满足h0=1,h1=2 and h2=0的递推的递推关系关系 hn=2hn-1
5、+hn-2 2hn-3,(n 3).提示提示:这个递推关系的特征方程为这个递推关系的特征方程为 x3 2x2 x+2=0 而它的三个根而它的三个根 1,-1,2.根据定理根据定理7.2.1,hn=c11n+c2(-1)n+c32n 是一般解是一般解.9本讲稿第九页，共五十一页例题（续）例题（续）由三个字母由三个字母a,b,c组成的长度为组成的长度为n的一些的一些单词将在通信信道上传输，满足条件：单词将在通信信道上传输，满足条件：传输中不得有两个传输中不得有两个a连续出现在任一个单连续出现在任一个单词中。确定通信信道允许传输的单词个词中。确定通信信道允许传输的单词个数。数。10本讲稿第十页，共五
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本讲稿第十一页，共五十一页练习练习 一个一个 1n 棋盘棋盘.我们把每个方格都涂上我们把每个方格都涂上
7、红色或者蓝色红色或者蓝色.令令 hn 表示没有两个连续表示没有两个连续的方格被同时涂上红色的方法的个数的方格被同时涂上红色的方法的个数.找找到并且证明这样的一个递推关系到并且证明这样的一个递推关系hn.然后然后求得公式求得公式 hn.求解递推关系求解递推关系 hn=4hn-1 4hn-2,(n 2).12本讲稿第十二页，共五十一页注解注解 如果特征方程的根如果特征方程的根 q1,q2,qk 不是互不是互异的异的,那么那么 hn=c1q1n+c2q2n+ckqkn 就就不是递推关系的一个一般解不是递推关系的一个一般解.13本讲稿第十三页，共五十一页定理定理 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本讲稿第十四页，共五十一页例题例题求递推关系求递推关系 hn=4hn-1 4hn-2,(n 2).提示提示:特征方程是特征方程是 x2-4x+4=0.这样这样 2 是是重特征根重特征根.特征关系的一般
9、解为特征关系的一般解为 hn=c12n+c2n2n.15本讲稿第十五页，共五十一页练习练习 求特征关系求特征关系 hn=-hn-1+3hn-2+5hn-3+2hn-4,(n 4).16本讲稿第十六页，共五十一页生成函数生成函数 17本讲稿第十七页，共五十一页生成函数的方法生成函数的方法利用代数的方法计算一个问题可能性的利用代数的方法计算一个问题可能性的次数次数生成函数是无穷次可微函数的泰勒级数生成函数是无穷次可微函数的泰勒级数如果你可以找到一个函数和它的泰勒级如果你可以找到一个函数和它的泰勒级数数,那么泰勒级数的系数则给出这个问那么泰勒级数的系数则给出这个问题的解题的解.18本讲稿第十八页，共
10、五十一页生成函数的定义生成函数的定义令令 h0,h1,hn,是一个无穷的数列是一个无穷的数列.它的它的 生成生成函数函数 被定义为无穷级数被定义为无穷级数 g(x)=h0+h1x+h2x2+hnxn+在在 g(x)中，中，xn 的系数是这个序列的第的系数是这个序列的第n项项 hn,从而，从而，xn 作为作为hn的的“位置持有者位置持有者”。19本讲稿第十九页，共五十一页例题例题1.无限序列的生成函数无限序列的生成函数 1,1,1,1,它的每一项它的每一项都等于都等于1 g(x)=1+x+x2+xn+=1/(1-x)2.M是一个正整数是一个正整数.二项式序列二项式序列 c(m,0),c(m,1)
11、c(m,2),.,c(m,m)的生成函数是的生成函数是 gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+c(m,m)xm =(1+x)m (二项式定理二项式定理).20本讲稿第二十页，共五十一页练习练习 令令a为一个实数为一个实数.根据牛顿二项式定理根据牛顿二项式定理,二二项式系数项式系数 c(a,0),c(a,1),c(a,n),的无的无穷生成函数是什么？穷生成函数是什么？令令 k 是一个整数，是一个整数，并令序列并令序列 h0,h1,h2,hn,使得使得hn等于等于 e1+e2+ek=n的的非负整数的个数非负整数的个数.这个序列的生成函数是这个序列的生成函数是什么什么?21本讲
12、稿第二十一页，共五十一页复习 令令a是一个实数是一个实数.那么对于所有的那么对于所有的 x 和和 y（0|x|y|）,22本讲稿第二十二页，共五十一页又因为又因为|y|11)24本讲稿第二十四页，共五十一页例题（续）例题（续）确定苹果、香蕉、橘子和梨的确定苹果、香蕉、橘子和梨的n-组合的个数组合的个数,其中在其中在每个每个n-组合中苹果的个数是偶数，香蕉的个数是奇组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在数，橘子的个数在0和和4之间，而且至少要有一个之间，而且至少要有一个梨梨提示提示:该问题等价于找出该问题等价于找出 e1+e2+e3+e4=n.的非负整数解的个数的非负整数解的个数
13、25本讲稿第二十五页，共五十一页 其中其中 e1 是偶数是偶数(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本讲稿第二十六页，共五十一页练习练习 令令hn代表好几袋子苹果、香蕉、橘子和梨代表好几袋子苹果、香蕉、橘子和梨的总个数的总个数,并且每个袋子中苹果的个数是并且每个袋子中苹果的个数是偶数偶数,香蕉的
14、隔数是香蕉的隔数是 5的倍数的倍数,橘子的个数橘子的个数至多为至多为 4 并且梨的个数为并且梨的个数为 0 或者或者 1.提示提示:计算这个问题的生成函数的计算这个问题的生成函数的xn的系数的系数.27本讲稿第二十七页，共五十一页练习（续）练习（续）确定方程确定方程 e1+e2+ek=n非负整数解非负整数解e1,e2,ek 的个数的个数hn的生成函数。的生成函数。提示提示:k(x+x3+x5+x7+).28本讲稿第二十八页，共五十一页练习练习(续续)令令 hn 表示方程表示方程 3e1+4e2+2e3+5e4=n非负非负整数解的个数整数解的个数.找到找到h0,h1,h2,hn,.的生成函数的生
15、成函数 g(x)提示提示:令令 f1=3e1,f2=4e2,f3=2e3 并且并且 f4=5e4.于是于是hn 也等于也等于 f1+f2+f3+f4=n 的非的非负整数解的个数，其中负整数解的个数，其中 f1 是是 3的倍数的倍数,f2 是是 4的倍数的倍数,f3 是偶数是偶数 并且并且 f4 是是 5的倍数的倍数.29本讲稿第二十九页，共五十一页递归生成函数递归生成函数30本讲稿第三十页，共五十一页内容内容利用生成函数来求解常系数的线性齐次利用生成函数来求解常系数的线性齐次递推关系递推关系.牛顿二项定理的应用牛顿二项定理的应用.31本讲稿第三十一页，共五十一页复习复习:牛顿二项定理牛顿二项定
16、理如果如果 n是一个正整数是一个正整数 并且并且 r 是一个非零整数是一个非零整数,那么那么32本讲稿第三十二页，共五十一页例题例题确定平方项的序列确定平方项的序列 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本讲稿第三十三页，共五十一页例题例题(续续)求解满足初始值求解满足初始值
17、h0=1 和和 h1=-2的递推的递推关系关系 hn=5hn-1 6 hn-2,(n2).提示提示:令令 g(x)=h0+h1x+h2x2+hnxn+.为为 h0,h1,h2,hn 的生成函数。此的生成函数。此时，我们有下列方程时，我们有下列方程 34本讲稿第三十四页，共五十一页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+(
18、hn-5hn-1+6hn-2)xn+.=h0+(h1-5h0)x=1-7x因此因此,g(x)=(1-7x)/(1-5x+6x2)=5/(1-2x)4/(1-3x)35本讲稿第三十五页，共五十一页通过牛顿二项定理通过牛顿二项定理(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本讲稿第三十六页，共五十一页练习 满足满足h0=0,h1=1，h2=-1的递推关系的递推关系 hn+hn-1 16 hn-2+20hn-
19、3=0(n3)求求hn的一般公式。的一般公式。37本讲稿第三十七页，共五十一页一个几何的例子一个几何的例子38本讲稿第三十八页，共五十一页划分凸多边形的方法划分凸多边形的方法通过画出在区域内部不相交的对角线将具通过画出在区域内部不相交的对角线将具有有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,).3
20、9本讲稿第三十九页，共五十一页指数生成函数指数生成函数40本讲稿第四十页，共五十一页复习复习:ex的泰勒级数的泰勒级数41本讲稿第四十一页，共五十一页指数生成函数的定义指数生成函数的定义 序列序列 h0,h1,h2,hn,的指数生成函数的指数生成函数 42本讲稿第四十二页，共五十一页例子例子 令令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本讲稿第四十
21、三页，共五十一页因此因此,(1+x)n 既是序列既是序列P(n,0),P(n,1),P(n,2),P(n,n)的指数生成函数又是序列的指数生成函数又是序列C(n,0),C(n,1),C(n,2),C(n,n)的常规生成函数的常规生成函数.44本讲稿第四十四页，共五十一页练习练习(续续)序列序列1,1,1,1,.的指数生成函数是的指数生成函数是更一般的更一般的,如果如果a是一个实数是一个实数,那么序列那么序列a0=1,a,a2,an,.的指数生成函数是的指数生成函数是45本讲稿第四十五页，共五十一页定理定理令令S为多重集为多重集 n1.a1,n2.a2,nk.ak,其中其中 n1,n2,nk 均
22、为非负整数均为非负整数.令令hn 是是S的的n-排列数排列数.则序列则序列h0,h1,h2,hn,的指数生成函数的指数生成函数g(e)(x)由由 g(e)(x)=fn1(x)fn2(x).fnk(x)给定给定 其中其中,对于对于 i=1,2,k,fni(x)=1+x+x2/2!+xni/ni!.46本讲稿第四十六页，共五十一页例题例题如果把一个如果把一个1*n的棋盘上的偶数个方格染成红的棋盘上的偶数个方格染成红,白白,蓝三种颜色蓝三种颜色,共有多少种染色方案共有多少种染色方案?线索线索:令令 hn表示这样的染色方案数表示这样的染色方案数,定义定义h0=1.此时此时hn 等于三种颜色的多重集的等
23、于三种颜色的多重集的n-排列数排列数,其其中每一种颜色都有无穷重复数中每一种颜色都有无穷重复数,且红色出现偶且红色出现偶数次数次.因此因此,h0,h1,h2,hn,的指数生成函的指数生成函数是红数是红,白白,蓝因子的乘积蓝因子的乘积:47本讲稿第四十七页，共五十一页因此因此,hn=(3n+1)/2.48本讲稿第四十八页，共五十一页练习练习确定每个数字都是奇数的确定每个数字都是奇数的n位数的个数位数的个数,其中要求其中要求1和和3出现偶数次出现偶数次.线索线索:令令 h0=1.hn 等于多重集等于多重集S=1,3,5,7,9的的n-排列的个数排列的个数,其中要其中要求求1和和3出现偶数次出现偶数次.49本讲稿第四十九页，共五十一页练习练习(续续)用红用红,白白,蓝三种颜色给一个蓝三种颜色给一个1*n的棋盘染的棋盘染色色,如果有偶数方格必须染成红色如果有偶数方格必须染成红色,并且并且至少有一个蓝色的至少有一个蓝色的,求一共有多少种染色求一共有多少种染色方案方案?50本讲稿第五十页，共五十一页作业作业625(ii)3137(iv).51本讲稿第五十一页，共五十一页