离散数学 第2版 教学课件 作者 王元元 离散第7讲 递归关系.ppt

《离散数学 第2版 教学课件 作者 王元元 离散第7讲 递归关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室指挥自动化学院计算机系回顾定义6.5：集合{1，2，3，…，n}的全排列，使得每个数i都不在第i位上，称这样的排列为{1，2，3，…，n}的一个错置。定理6.15：集合{1，2，3，…，n}的错置的总数(记为Dn)是约定D0=1。2第6讲重集的排列与组合回顾(1)Dn=(n-1)(Dn-2+Dn-1)(2)Dn=nDn-1+(-1)n证.(1)设{1，2，3，…，n}的一个错置是a1a2…ak…an，因为a1≠1，所以a1有n-1种取法。设a1=i(2≤i≤n)，

2、分两种情况讨论：(1.1)ai=1。这时取决于其余n-2个数的错置，这些错置的数目是Dn-2。(1.2)ai≠1。这时取决于其余n-1个数的错置：“1不可放置在第i位，其它各数j不可放置在第j位”，这些错置的数目是Dn-1。因此，由加法原理和乘法原理Dn=(n-1)(Dn-2+Dn-1)3第6讲重集的排列与组合PowerPointTemplate_Sub1一个重要的递归关系2递归关系的求解4第6讲重集的排列与组合递归关系Page96to103《离散数学》第7讲内容提要递归关系递归关系的定义和实例用递归关系构造模型用递

3、归关系为实际问题建模递归关系的迭代求解常系数线性齐次递归关系的求解什么是常系数线性齐次递归关系常系数线性齐次递归关系的特征根求解方法6第6讲重集的排列与组合前言有多少个n位二进制串不包含两个连续的0？解：令an表示这样的n位二进制串数，a1=2(0,1)a2=3(00,01,10,11)a3=5(000,001,010,011,100,101,110,111)(010,110,011,101,111)an分为以0和以1结尾两种情况对以0结尾的情况：是任何不含2个连续0的n－2位二进制串加上10组成的，有an-2个对以

4、1结尾的情况：是任何不含2个连续0的n－1位二进制串加上1组成的，有an-1个an=an-1+an-2这个等式叫做递归关系，和初始条件一起唯一地确定了序列{an}。递归关系是求解组合数学问题的重要工具，几乎在所有的数学分支中都有重要应用.许多计数问题用上一章讨论的方法不易求解，但可以通过找到序列的项之间的关系间接求解.7第6讲重集的排列与组合递归关系(recurrencerelation)定义1：关于序列{an}的递归关系是一个等式，它把an用序列中排在an前面的一项或多项来表示，这里n≥n0，n0是一个非负整数。如

5、果一个序列的项满足某个递归关系，这个序列就叫做该递归关系的解(或通项,通项公式)。8第6讲重集的排列与组合递归关系举例确定序列{an}是否为递归关系an=2an-1–an-2(n=2,3,4,…)的解，这里an=3n，n是非负整数。若an=2n或an=5呢？解：(1)假设对每一个非负整数n，an=3n。对n≥2，可看出2an-1–an-2=2·3(n-1)-3(n-2)=6n-6-3n+6=3n=an∴{an=3n}是该递归关系的解(2)假设对每一个非负整数n，an=2n。a0=1，a1=2，a2=4，2a1–a0=

6、2·2-1=3≠a2∴{an=2n}不是该递归关系的解(3)假设对每一个非负整数n，an=5。对n≥2，有2an-1–an-2=2·5-5=5=an，因此{an=5}是该递归关系的解9第6讲重集的排列与组合说明序列的初始条件说明了在递归关系起作用的首项之前的那些项递归关系和初始条件唯一地确定一个序列，这是因为一个递归关系和初始条件一起提供了这个序列的递归定义只要使用足够多次，序列的任意一项都可以从初始条件开始通过递归关系求出但对于某些特定类型的序列，可以有更好的办法通过它的递归关系和初始条件来计算它的通项10第6讲重

7、集的排列与组合用递归关系构造模型复合利息。假设一个人在银行的账户上存了10000美元，复合年利息是11%。那么30年后账上将有多少钱？解：令Pn表示n年后账上的钱。因为n年后的钱等于n-1年后账上的钱加上第n年的利息，所以序列{Pn}满足递归关系Pn=Pn-1+0.11·Pn-1=1.11Pn-1P0=10000P1=1.1110000P2=1.11P1=1.11210000……Pn=1.11Pn-1=1.11n10000证明：下面用数学归纳法验证Pn=1.11n10000的正确性归纳基础：n=0时显然成立归

8、纳推理：假设n=k时，Pk=1.11k10000。那么由递归关系和归纳假设知Pk+1=1.11Pk=1.11k+110000归纳完成，结论成立11第6讲重集的排列与组合用递归关系构造模型平面上n条直线两两相交，且没有任何三条直线交于一点，求共有多少个交点？解：设n(n≥2)条直线的交点数目为h(n)。如果增加第n+1条直线，它将与前n条直线