递推关系和生成函数.ppt

1,第七章递推关系和生成函数7.1某些数列,许多组合学计数问题都涉及到一个参数，例如hn表示1,2,.n的排列数，hn=n!;那么hn就是n的函数形式，n就是参数；在本章里，我们将讨论涉及一个整数参数的某些计数问题的代数求解方法。我们或者能得到一个显式公式，或者能得到一个函数，即生成函数。,2,在高等数学“无穷级数”章节中，我们知道函数f(x)有n+1阶导数时可以转化成幂级数，例如：f(x)在x0=0处展开成麦克劳林级数：,3,或者在x0处展开成泰勒级数：,我们在二项式系数讨论中也有：,4,上述由函数展开成级数的问题，反过来就是由级数（数列）生成函数的问题。幂级数（有限或无限）是我们经常要用到的级数，也把它称为数列ak（k=1,2,）的生成函数或母函数。实际上决定幂级数性质的因素完全是xn的系数ak。,5,7.1某些数列本次课首先讨论由数列生成递归关系令h0,h1,h2,hn,是一个数列。其中hn称作该数列的通项或生成项。对于上述数列，定义其部分和如下：s0=h0s1=h0+h1,6,则由部分和s0,s1,s2,sn,亦然构成数列。我们熟悉的数列有：算术数列：其中每个后项比前项大一个常数q。几何数列：其中每个后项是前项的q倍。一旦我们指定了初始项h0和常数q，上述两个数列的序列就唯一确定了：算术数列：h0,h0+q,h0+hq,h0+nq.,7,通项为：hn=h0+nq(n1)相邻两项有关系：hn=hn-1+q(n1)前n项和公式：几何数列：h0,qh0,q2h0,q3h0,qnh0.通项为：hn=qnh0(n1)相邻两项有关系：hn=qhn-1(n1)前n项和公式：,8,例：算术序列：正偶数序列可以表示为：2,4,6,.2n.(n1)即：h0=2，q=2正奇数序列可以表示为：1,3,.2n-1.(n1)即：h0=1，q=2常数序列可以表示为：5,5,5,.5.即：h0=5，q=0,9,例：几何序列：幂指数序列可以表示为：1,2,4,.2n.(n0)即：h0=1，q=2通项hn=2n(n0)一般计数序列：5,35,325,.3n5,.(n0)h0=5，q=3通项hn=3n5,10,例：确定平面一般位置上的n个互相交叠的圆所形成的区域数？分析：设hn是由n个互相交叠的圆所形成的区域数。所谓相交是指两个圆的交点必须是2个并且仅仅2个，相切和相离都不成立。我们有h0=1；一个平面,11,区域；h1=2，一个圆围成的圆内和圆外平面区域；h2=4；如果是h3，在h2的基础上增加一个圆，围成的区域将增加4个，如图中红色的区域。h3=h2+x=h3+2(3-1)；再加一个兰色的圆将多6个区域h4=h3+y=h3+2(4-1),1,4,2,3,3,2,1,7,6,5,4,8,12,我们得到递推关系如下：设n2，对于n1个一般位置上互相交替的圆已经在平面是画出，它们形成hn1个区域。再加上第n个圆使得在一般位置上放置n个互相交替的圆。前n1个圆的每一个与第n个都交于两点，得到2(n1)个不同的点：p1,p2,p2(n-1)。他们把第n个圆分成2(n1)条弧：,13,p1p2,p2p3,p3p4,.这2(n1)条弧的每一条能将前(n1)个圆形成的区域一分为二，得到2(n1)个区域，就是说，增加第n个圆，就增加2(n-1)个区域。分析hn与hn-1的关系，我们能发现区域数量hn与画圆的数量n的关系：,14,hn=hn-1+2(n-1)=hn-2+2(n-2)+2(n-1)=hn-3+2(n-3)+2(n-2)+2(n-1).=h1+2(1)+2(2)+.+2(n-2)+2(n-1)=2+21+22+.+2(n-1),15,Fibonacci序列(斐波那契序列)意大利数学家Fibonacci在13世纪初提出过如下一个有趣问题：年前养了一对小兔（雌雄各一），这对兔子中的母兔从2月份开始每月都产下一对雌雄各一的小兔。每对新生小兔间隔一月后也开始每个月都产下一对新的小兔（雌雄各一）。如是而下去，,16,假定兔子都不死亡，兔子都不多生小兔，生的小兔性别比例保持不变，不考虑近亲繁殖的问题，问一年后共有多少对兔子？假定年初为1月份,年后为13月，若设fn为第n个月所有的兔子对数，不难推算各月兔子对数与月份数的关系为:,17,著名的Fibonacci数列由此而得名。这一数列的增长速度是很快的。其中，第二年年底兔子有50000对，第三年年底兔子有15000000对，第55项就超过了1万亿对。第一列下来单独定义。我们已经算出f1=1,f2=1,f3=2,f4=3。,18,则由各月兔子数不难证得如下递推式成立:fn=fn-1+fn-2(n3)在第n月时，围栏内的兔子可以分为两个部分：一是第n-1月时围栏已经有的兔子数，二是第n-1月出生的新兔子数，由于兔子的成熟期是一个月，每对兔子只生一对小兔，第n-1月出生的新兔子数就是第n-2月拥有的老兔子对数。,19,由此我们可以求出下列兔子数：f5=f4+f3=3+2=5f6=f5+f4=5+3=8f7=f6+f5=8+5=13f8=f7+f6=13+8=21f9=f8+f7=21+13=34f10=f9+f8=34+21=55f11=f10+f9=55+34=89,20,如果定义f0=0，f2=f1+f0=1+0=1满足关系和初始条件：fn=fn-1+fn-2(n2)f0=0；f1=1的数列叫做斐波那契序列。序列的项叫做斐波那契数。公式中的递推关系叫做斐波那契递归。斐波那契序列有许多的性质，通过下面的,21,两个例题给出两个性质：例：斐波那契序列的项的部分和为：Sn=f0+f1+f2+.+fn=fn+21解：用归纳法证明：当n=0时左=f0=f21=11=0成立令n0时对Sn成立，证明用n+1取代n后公式仍成立。,22,Sn+1=f0+f1+f2+.+fn+1=fn+21+fn+1=fn+2+fn+11=fn+31公式成立例：斐波那契数是偶数当且仅当n能够被3整数.解：由前三个数f0，f1，f2的值。f0=0，f1=1，f2=1；由它们三项求的f3：f3=f2+f1=1+1=2是偶数，其项数n=3能被3整除.,23,它们的奇偶性有下列特征：f3是：偶+奇+奇=偶；f4=f3+f2是：偶+奇=奇；f5=f4+f3是：奇+偶=奇；f6=f5+f4是：奇+奇=偶；f6的项数n=6也能被3整除。,24,斐波那契递推公式由斐波那契递推公式fn=fn-1+fn-2得到：fnfn-1fn-2=0假设斐波那契数具有幂函数形式：fn=qn其中q是一个非零数。代入上式:qnqn-1qn-2=0解这个方程qn-2(q2q1)=0只能是q2q1=0,25,因此由于两个解都是斐波那契关系的特解，由斐波那契递推关系是线性的和齐次的，一般的通解：,将n=0，1时fn的初值代入确定系数C1,C2,26,n=0，时:n=1，时:,将上述值代入公式得到下列公式：,27,定理7.1.1Fibonacci(斐波那契)数满足公式虽然斐波那契数(兔子数)都是整数，可是在公式中却包含了无理数，而求fn时这些无理数又神奇地消失了，这个表达式也就是斐波那契序列的通项公式。,28,例：令f0,f1,f2,fn,满足下面给出的斐波那契递推关系和改变的初始条件：fn=fn-1+fn-2(n2)f0=2;f1=1的数列，试给出fn的计算公式。解：将f0=2;f1=1代入斐波那契公式得：f0=2=C1+C2,29,解上述方程得：,如果将斐波那契递序列的前几项改变成f0=1，f1=1，f2=2，.；即去掉0这第一项，,30,对无穷级数来说，减少或增加有限项不会改变级数的敛散性，我们以1作为斐波那契递序列的第一、二项，递推关系不变，并且设斐波那契数列生成的函数为f(x)：,31,32,此斐波那契数列的又一个生成函数。设1-x-x2=0的二根为、，分解多项式:,注意区别于前面方程：q2q1=0根的关系。,33,34,由幂级数展开公式：当x1时,我们可以将公式中的两个分式展开成级数形式：,35,36,由于,那么,与原来的公式比较要少一项，这正是我们省掉了0这第一项后得到地斐波那契数列的近似计算公式。,37,比较这相邻两个斐波那契数的关系有：,这个数字正好是建筑、美学等领域的黄金分割位。,fn,fn-1=0.618fn,38,关于斐波那契数，我们用竖式加法证明一些关系1)f1+f2+.+fn=fn+21;证明：由fn+2=fn+fn+1得：f1=f3f2;f2=f4f3;.+)fn=fn+2fn-1;f1+f2+.+fn=fn+2f2=fn+21证毕,39,2)f1+f3+.+f2n-1=f2n;证明：由fn+2=fn+fn+1得：f1=f2=1;f3=f4f2;f5=f6f4;.+)f2n-1=f2nf2n-2;f1+f3+.+f2n-1=f2n证毕,40,3)f12+f22+f32.+fn2=fnfn+1;证明：由fn+2=fn+fn+1得：f12=f1f1=f2f1f22=f2f2=f2(f3f1)=f2f3f2f1f32=f3f3=f3(f4f2)=f3f4f3f2.+)fn2=fnfn=fn(fn+1fn-1)=fnfn+1fnfn-1f12+f22+f32.+fn2=fnfn+1;证毕,41,例：确定2n棋盘用多米诺骨牌完美覆盖的方法数hn解：h1=1；h2=2h3=3；将hn分为两种情况：ABA是左边第一个骨牌必须竖直摆放，其余n-1个骨牌不限制位置的覆盖的集合。B是左边第一,2n,2n,42,骨牌不竖直摆放，即水平摆放(同时还有一个)其余n-2个骨牌不限制位置的覆盖的集合。所以A中的完美覆盖数就等于2(n-1)棋盘的完美覆盖数：|A|=hn-1B中的完美覆盖数就等于2(n-2)棋盘的完美覆盖数,由于骨牌是相同的，B中前两个水平放置的骨牌没有上下区分；|B|=hn-2,43,由加法原理故hn=|A|+|B|=hn-1+hn-2(n2)定义n=1时，即空覆盖：h0=1，也是个斐波那契序列。下面说明斐波那契数作为二项式系数的和出现的。,44,定理7.1.2沿Pascal三角形图左边向上对角线上的二项式系数的和是斐波那契数，更精确地说，第n个斐波那契数是：,45,Pascal三角形图,f1=1,f2=1,f3=2,f4=3,f5=5,f6=8,f7=13,46,证明：由组合数的定义可知：当kn时所以我们可以把原式改写成：,下面只需要证明fn满足斐波那契递推关系：,47,应用Pascal公式，对于n2,48,我们得到结论:f0,f1,f2,.fn,.是斐波那契数列,49,总结,本次课我们介绍了一个重要的序列：斐波那契序列，并且引入了序列、生成函数、序列通项等概念，后面我们还将对上述问题作进一步的研究。,50,本次授课到此结束,作业如下:P1621(ii),(iii),6，81.设f0,f1,f2,.fn,.是斐波那契序列。通过用小的n