递推关系和生成函数.ppt_第1页
递推关系和生成函数.ppt_第2页
递推关系和生成函数.ppt_第3页
递推关系和生成函数.ppt_第4页
递推关系和生成函数.ppt_第5页
已阅读5页,还剩47页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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 = h0 s1 = 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= 3n 5,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,对于 n 1 个一般位置上互相交替的圆已经在平面是画出,它们形成hn1个区域。再加上第n个圆使得在一般位置上放置n 个互相交替的圆。 前n 1个圆的每一个与第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数列由此而得名。这一数列的增长速度是很快的。其中,第二年年底兔子有50 000对,第三年年底兔子有15 000 000对,第 55 项就超过了1万亿对。第一列下来单独定义。 我们已经算出 f1 = 1, f2 = 1, f3 = 2, f4 = 3。,18,则由各月兔子数不难证得如下递推式成立: f n = f n-1 + f n-2 (n 3) 在第n月时,围栏内的兔子可以分为两个部分:一是第n-1月时围栏已经有的兔子数,二是第n-1月出生的新兔子数,由于兔子的成熟期是一个月,每对兔子只生一对小兔,第n-1月出生的新兔子数就是第n-2月拥有的老兔子对数。,19,由此我们可以求出下列兔子数: f 5 = f 4 + f 3 = 3 + 2 = 5 f 6 = f 5 + f 4 = 5 + 3 = 8 f 7 = f 6 + f 5 = 8 + 5 = 13 f 8 = f 7 + f 6 = 13 +8 =21 f 9 = f 8 + f 7 = 21 +13 = 34 f 10 = f 9 + f 8 = 34 +21 =55 f 11 = f 10 + f 9 = 55 +34= 89 ,20,如果定义 f 0 = 0, f 2 = f 1 + f 0 =1+0=1 满足 关系和初始条件: f n = f n-1 + f n-2 (n 2) f 0 = 0 ; f 1 = 1 的数列叫做斐波那契序列。序列的项叫做斐波那契数。公式中的递推关系叫做斐波那契递归。 斐波那契序列有许多的性质,通过下面的,21,两个例题给出两个性质: 例:斐波那契序列的项的部分和为: Sn = f0 + f1 + f2 + fn = fn+2 1 解:用归纳法证明: 当n=0时 左 = f0 = f2 1=1 1=0 成立 令n0时对Sn成立,证明用n+1取代n后公式仍成立。,22,Sn+1 = f0 + f1 + f2 + fn+1 = fn+2 1 + fn+1 =fn+2 + fn+1 1 = fn+3 1 公式成立 例:斐波那契数是偶数当且仅当n能够被3整数. 解:由前三个数f 0 , f 1 ,f 2的值。 f 0 =0, f 1 =1,f 2 =1;由它们三项求的f 3 : f 3 =f 2+ f 1=1+1=2 是偶数,其项数n=3能被3整除.,23,它们的奇偶性有下列特征: f3 是:偶+奇+奇=偶; f4=f3+f2 是:偶+奇=奇; f5=f4+f3 是:奇+偶 =奇; f6=f5+f4 是:奇+奇=偶; f 6 的项数n=6也能被3整除。 ,24,斐波那契递推公式 由斐波那契递推公式 f n = f n-1 + f n-2 得到: f n f n-1 f n-2 = 0 假设斐波那契数具有幂函数形式:f n = qn 其中q是一个非零数。代入上式:qn qn-1qn-2= 0 解这个方程 qn-2 (q2 q 1)= 0 只能是 q2 q 1 = 0,25,因此 由于两个解都是斐波那契关系的特解,由斐波那契递推关系是线性的和齐次的,一般的通解:,将n=0,1时f n 的初值代入确定系数C1,C2,26,n=0,时: n=1 ,时:,将上述值代入公式得到下列公式:,27,定理7.1.1 Fibonacci(斐波那契) 数满足公式 虽然斐波那契数(兔子数)都是整数,可是在公式中却包含了无理数,而求f n 时这些无理数又神奇地消失了,这个表达式也就是斐波那契序列的通项公式。,28,例:令f0, f1, f2, , fn, 满足下面给出的斐波那 契递推关系和改变的初始条件: fn = fn-1 + fn-2 (n 2) 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 的二根为、,分解多项式:,注意区别于前面方程:q2 q 1 = 0根的关系。,33,34,由幂级数展开公式:当x1时,我们可以将公式中的两个分式展开成级数形式:,35,36,由于,那么,与原来的公式比较要少一项,这正是我们省掉了0这第一项后得到地斐波那契数列的近似计算公式。,37,比较这相邻两个斐波那契数的关系有:,这个数字正好是建筑、美学等领域的黄金分割位。 ,f n,f n-1= 0.618f n,38,关于斐波那契数,我们用竖式加法证明一些关系 1) f 1+ f 2+ f n= f n+21; 证明:由 f n+2= f n+ f n+1 得: f 1= f 3 f 2 ; f 2= f 4 f 3 ; +) f n= f n+2 f n-1 ; f 1+ f 2+ f n= f n+2 f 2 = f n+21 证毕,39,2) f 1+ f 3+ f 2n-1 = f 2n ; 证明:由 f n+2= f n+ f n+1 得: f 1= f 2 = 1 ; f 3= f 4 f 2 ; f 5= f 6 f 4 ; +) f 2n-1= f 2n f 2n-2 ; f 1+ f 3+ f 2n-1 = f 2n 证毕,40,3) f12 + f22 + f32 + fn2 = f n f n+1 ; 证明:由 f n+2= f n+ f n+1 得: f12 = f 1 f 1 = f 2 f 1 f22 = f 2 f 2 = f 2(f 3 f 1) = f 2f 3 f 2 f 1 f32 = f 3 f 3 = f 3(f 4 f 2) = f 3f 4 f 3 f 2 +) fn2= f n f n = f n (fn+1 fn-1) = fnfn+1 f n f n-1 f12 + f22 + f32 + fn2 = f n f n+1 ; 证毕,41,例:确定2n棋盘用多米诺骨牌完美覆盖的 方法数hn 解: h1=1 ; h2=2 h3=3 ; 将hn分为两 种情况:A B A是左边第一个骨牌必须竖直摆放,其余n-1个骨牌不限制位置的覆盖的集合。B是左边第一,2 n,2 n,42,骨牌不竖直摆放,即水平摆放(同时还有一个) 其余n-2个骨牌不限制位置的覆盖的集合。 所以A中的完美覆盖数就等于2(n-1)棋盘的完美覆盖数: |A| =hn-1 B中的完美覆盖数就等于2(n-2)棋盘的完美覆盖数,由于骨牌是相同的,B中前两个水平放置的骨牌没有上下区分; |B| = hn-2,43,由加法原理 故 hn=|A|+|B|=hn-1+hn-2 (n 2) 定义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,本次授课到此结束,作业如下:P162 1(ii) ,(iii), 6, 8 1.设f0, f1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论