版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第7章 递推关系和生成函数,7.1 一些数列,算术序列(等差数列) 几何序列(等比数列) 例1:确定平面一般位置上的n个互相交叠的圆所形成的区域数。,例2 (Fibonacci问题): Fibonacci数列是递推关系的又一典型问题, 数列的本身有着许多应用. (1) 问题的提出:假定初生的一对雌雄兔子, 从出生的第2个月之后每个月都可以生出另外一对雌雄兔. 如果第1个月只有一对初生的雌雄兔子, 问n个月之后共有多少对兔子?,1月,2月,3月,4月,5月,6月,(2) 求递推关系: 设满n个月时兔子对数为Fn,则第n-1个月留下的兔子数目为Fn-1对;当月新生兔数目为Fn-2对, 即第n-2个
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,,(3) Fibonacci数列的性质 部分和Sn=f0+f1+f2+fn=fn+2-1 Fibonacci数列是偶数当且仅当n能被3整除 Fibonacci数列满足公式,例3:令g0,g1,g2,gn,是满足下面给出的Fibonacci数列递推关系和初始条件:gn=gn-1+gn-2 (n2)
3、 g0=2,g1=-1 例4:确定2Xn棋盘用多米诺骨牌完美覆盖的方法数hn。 例5:确定用单牌和多米诺骨牌对1Xn棋盘完美覆盖的方法数bn。,定理7.1.2 沿Pascal三角形左下到右上对角线上的二项式系数的和是Fibonacci数,7.2 线性齐次递推关系,数列h0,h1,h2,hn, hn=a1hn-1+a2hn-2+akhn-k+bn (nk) 错排数列Dn=(n-1)(Dn-2+Dn-1) (n 2) Dn=nDn-1+(-1)n (n 1) Fibonacci数列 Fn= Fn-1+ Fn-2 (n 2) 阶乘序列hn=nhn-1 (n 1) 几何序列hn=qhn-1 (n 1)
4、,hn=a1hn-1+a2hn-2+akhn-k (nk) 其中a1,a2,ak 是常系数,称为常系数线性齐次递推关系。 定理7.2.1 令q为一非零数。则hn=qn是hn-a1hn-1-a2hn-2-akhn-k =0(ak0,nk) 的解,当且仅当q是多项式方程xk-a1xk-1-a2xk-2-ak=0的一个根。如果多项式方程有k个不同的根q1,q2,qk,则hn=c1q1n+c2q2n+ckqkn,例6:求满足初始值h0=1,h1=2,h2=0的递推关系hn=2hn-1+hn-2-2hn-3 (n3)的解 例7:只由三个字母a,b,c组成的长度为n的一些单词将在通信信道上传输,满足条件:
5、传输中不得有两个a连续出现在任一单词中。确定通信信道允许传输的单词个数。 例8:递推关系hn=4hn-1-4hn-2 (n2)的解 定理7.2.2 令q1,q2,qt为hn=a1hn-1+a2hn-2+akhn-k (ak0,nk) 的特征方程的互异的根。此时,如果qi是si重根,则对qi部分一般解为Hn(i)=(c1+c2n+csinsi-1)qin,7.3 非齐次递推关系,例9 (Hanoi塔问题):n个圆盘依其半径大小, 从下而上套在柱A上, 如图3.1所示. 每次只允许取一个转移到柱B或C上, 而且不允许大盘放在小盘上方. 若要求把A上的n个盘转移到C柱上. 请设计一种方法, 并估计要
6、移动几个盘次. 现在只有A, B, C三根柱子可供使用.,4,1,3,2,Hanoi塔是个经典问题. 对于这个问题, 我们先要设计算法, 进而估计算法的计算复杂性, 这里就是移动的总次数.,(1) 算法设计: n=2时, 圆盘1从A套在B上;把圆盘2从A转移到C上;把圆盘1从B上转移到C上. 完毕. n=3时, 把圆盘1从A转移到C上;把圆盘2从A转移到B上;把圆盘1从C上转移到B上; 把圆盘3从A套在C上; 把圆盘1从B再转移到A上; 把圆盘2从B转移到C上, 把圆盘1从A套在C上. 完毕. 看看n=3的演示过程.,A,B,C,假定n-1个盘子的转移算法已经确定. 对n个圆盘问题, 先把上面
7、的圆盘1,2, n-1转移到B上, 再把最后一个盘子转移到C上, 然后把B上的n-1个圆盘转移到柱C上. 转移完毕. 这运用的是递归算法n=2时给出了算法; n=3时先利用n=2时的算法把圆盘1, 2移B上; 再把圆盘3转移到柱C上;再利用n=2时的算法把B上两个圆盘转移到柱C上. n=4,5,以此类推.,(2) 算法分析:令hn表示n个圆盘所需要的转移次数. 根据算法先把前面n-1个盘子转移到B上; 然后把第n个盘子转移到C上; 最后再一次将B上的n-1个盘子转到C上. 算法可实现性可用归纳法得到. 因n=2时对, 假定n-1对, 那么n自然也对. 关于转移次数容易得到一个递归关系: hn=
8、2hn-1+1 , h1=1.,例10:解hn=3hn-1-4n (n1) h0=2 步骤总结 求齐次关系的一般解 求非齐次关系的一个特解 将一般解和特解联合,按初始条件求系数 困难在于特解的求解。 例11: hn=2hn-1+3n (n1) h0=2 例12:hn=3hn-1+3n (n1) h0=2 例13: hn=hn-1+n3 (n1) h0=0,7.4 生成函数(母函数),母函数就象一根晒衣绳, 我们把需要得到的一列数就挂在它上面. 假定我们的问题的解是一列数: a0,a1,a2,an, . 我们想知道这个数列是什么, 我们期望得到怎样的答案? 当然, 最好的答案就是关于an的一个简
9、单的公式. 比如诸如an=n2+3之类的表达式. 即, 通项公式.,但是, 如果一个未知数列没有简单公式, 或者即便存在, 但是很复杂, 很不容易得到, 我们也不知道, 该怎么办? 如果我们还希望研究这个数列, 讨论它的性质, 该如何下手? 举一个极端的例子, 假定这个数列是2, 3, 5, 7, 11, 13, 17, 19, 23, ., 此处an是第n个素数. 这样的情况, 期望任何简单的公式都是不合理的.,母函数把数列的所有成员用一种非常巧妙的方法联系在一起, 虽然这样做并不一定能得到数列的简单公式, 可是也许能够给出一个幂级数和的简单公式, 展开这个和函数, 所得到的幂级数的系数就是
10、我们所要找的数列. 比如后面我们将会学习到的Fibonacci 数列, 它满足一个递归关系 Fn+1=Fn+Fn-1 (n2; F1=F2=1).,1. 母函数概念 设有a, b, c三个不同的球, 从中选取一个, 或选a, 或选b, 或选c, 把这些可能的选取形象地表示为a+b+c. 类似地, 从中选取二个, 或选a和b, 或选a和c, 或选b和c. 可形象地表示为ab+ac+bc, 同样, 从中选取三个, 只有一种方法, 也可形象地表示为abc.,从多项式 (1+ax)(1+bx)(1+cx) (7.2) =1+(a+b+c)x+(ab+ac+bc)x2+(abc)x3 中发现, 所有这些
11、可能的选取方式正好是x幂的系数. 其中xi的系数是从三个球中选取i个的方法之形象表示. 因子(1+ax)形象地指出, 对球a, 有两种选取方法: 不选a, 或选a. 因子(1+ax)中的1表示不选a, 而x的系数a表示选a.,既然在上述多项式中, xi的系数表明选取i个球的方法, 那么 (1+ax)(1+bx)(1+cx) 所表明的是: 对a, b, c三球, 选取的方法是, “选a或不选a”和“选b或不选b”以及“选c或不选c”. 多项式中x的幂次表示选取球的个数, 而其相应系数表示一切可能的选取方法.,如果我们只关心不同组合方案的数目, 不关心各种方案的罗列. 可以在(7.2)式中令a=b
12、=c=1, 则得到 (1+x)3 = C(3,0)+C(3,1)x +C(3,2)x2+C(3,3)x3 =1+3x+3x2+x3. (7.3) 总方案数N=C(3,0)+C(3,1)+C(3,2)+C(3,3) =1+3+3+1=8.,(7.3)就是一个关于形式变量x的幂函数, 这个幂函数中不同幂次的系数都是一个组合数. 这可以推广到任意n个不同球所有可能组合的方案数情况. 这其实就是我们大家熟悉的二项式系数. 不过现在我们是用形式级数的观点来看问题. 利用这种形式级数不仅仅是一种不同的表达形式, 还非常有用.,2. 母函数定义 定义7.1 利用给定序列a0,a1,a2,所构造的函数 F(x
13、)= a0+a1x+a2x2+ 称为序列a0, a1, a2,的母函数. 母函数定义中的级数是形式幂级数, 不必关心收敛性, x只是一个形式变量. 有限序列 a0, a1, an也可以定义它的母函数. (后面添加0),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,(5) 相乘: A(x)B(x)=
14、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). (显然两者互为逆.),例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)的幂级数展开式是完全一致的.,例15 设,则(F(x)-G(x)(1-3x+2x2)=x. 这说明,这与把它们看成普通函数的
15、运算是一致的.,例16:令k是一个整数,并令序列h0,h1,h2,hn,使hn等于e1+e2+ek=n的非负整数解的个数。 例17:确定苹果、香蕉、橘子和梨的n组合的个数,其中在每个n组合中苹果的个数是偶数,香蕉的个数是奇数,橘子的个数在0和4之间,而且至少要有一个梨。 例18:确定可以由苹果、香蕉、橘子和梨袋装水果的袋数hn,其中在每个袋子中苹果数是偶数,香蕉数是5的倍数,橘子数最多是4个,梨的个数为0或1。,例19:确定方程e1+e2+ek=n的非负奇整数解e1,e2,ek的个数hn的母函数。 例20:令hn表示方程3e1+4e2+ 2e3+5e4 =n的非负整数解的个数。求h0,h1,h
16、2,hn,的母函数g(x)。 例21:有无限多现成的一分、五分、一角、两角五分和五角的硬币。确定用这些硬币凑成n分钱方法数hn的母函数g(x)。,7.5 母函数与递归,例22 (Hanoi塔问题):hn=2hn-1+1 , h1=1. (7.4) 令 H(x)=h1x+h2x2+h3x3+ H(x)是序列h1, h2, h3, 的母函数. 给出了序列,就可确定对应的母函数.反过来也一样, 求得了母函数, 对应得序列也就可得而知. 当然, 利用递推关系(7.4)也可迭代求得h2, h3, .但现在我们一要寻找明确的公式, 二要显示母函数的作用.,令H(x)=h1x+h2x2+h3x3 + + h
17、nxn+为生成函数,有以下方程: 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),这就是转移次数数列的母函数. 但是我们希望得到显式表达式. 这不难做到. 可以从母函数的幂级数展开式中求得数列h1,h2,h3,. 我们下面所运用的方法是处理这种问题的一个常规的方法, 初看起来可能感觉不
18、太适应, 用多了就习以为常了. 这就是所谓的部分分数的算法., (A+B)-(2A+B)x=x.,解得A=-1,B=1. 其实一眼就可看出结果. 这里只是想说 明方法而已.,(3) 算法评价: hn是要移动圆盘数n(规模)的指数函数, 以n=60为例子. 可以计算出260 1.152921018. 这个数是一个什么概念? 假如你每秒钟移动一个盘, 按照上述算法, 你移动60个盘的时间是:,真是不算不知道, 一算吓一跳. n=60, 数不过百, 2也是很小的整数, 可是260却是一个很大的数. 这就是所谓的“指数爆炸”现象. 一般称复杂性为规模n的指数函数的算法为“坏算法”. 好算法是指多项式算
19、法或者线性算法.,例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的一般公式。,定理7.5.1 令h0,h1,hn,为满足k阶常系数线性齐次递推关系hn-c1hn-1-c2hn-2-ckhn-k =0(ck0,nk) 的数列。则它的生成函数g(x)形如g(x)=p(x)/q(x) 其中,q(x)为具有非零常数项的k次多项式,p(x)是小于k次的多项式。反之
20、也成立。,一般母函数是用基函数1,x,x2,来定义的. 这种母函数对于组合类型的数列的研 究很有用. 但是, 对研究排列类型的数列用起来很不方便. 排列类型数列是用基函数1,x,x2/2!,来定义, 这样使用起来更方便一些. 基本思想并没有变, 只是选择了新的基.,7.6 指数生成函数,基函数正好是出现在函数ex的幂级数展开式中的函数:,设有数列a0,a1,a2,,则称下列函数为 该数列的指数型母函数:,构造指数型母函数的目的是为了使得母函数形式更简单, 尤其对排列类型的递归数列更是如此. 看几个简单例子. 例26 设n为正整数, 则数列P(n,0), P(n,1), P(n,2), P(n,n)的指数型母函数为:,其普通型母函数如何?,例27 数列1,1,1,的指数型母函数为,更一般的, 设a为任意实数, 数列a0=1, a1, a2, a3,的指数型母函数为,(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的指数型
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 药物化学概述专家讲座
- 血管活性药物安全使用管理及成效
- 红南果梨贮藏过程中果肉褐变的防治
- 西宁地区以胸痛为症状心理障碍与冠心病关系的临床研究
- 精神心理疾病治疗新策略分析
- 九年级道德与法治测试卷(2026-2027学年上学期单元测试)
- 针刺加耳穴贴压治疗过敏性鼻炎临床体会
- 2027年四川省高考三模化学试卷(完整版)
- 关于核实供应商资质的商洽函(7篇)范文
- 合同续约确认联系函件(6篇)范文
- 2026全球牙科诊疗椅人机工程学创新设计与用户体验提升分析报告
- 2025 重症脓毒症与感染性休克救治指南(中文版)完整原文 + 详细解读
- 洗衣机装配工岗前工艺控制考核试卷含答案
- 《数字人民币智能合约互联互通建设管理规范》编制说明
- 非煤露天矿山开采基础知识和重大事故隐患判定标准解读
- 消化内科护士进修汇报
- 高处作业培训安全带使用课件
- 亚马逊店铺出租合同范本
- 无创呼吸机气道湿化管理
- 专题01实数的混合运算(60题)专项训练数学北师大版2024八年级上学期
- 临床主动脉夹层患者护理个案汇报
评论
0/150
提交评论