组合数学课件第二章母函数与递推关系.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《组合数学课件第二章母函数与递推关系.ppt》由会员分享,可在线阅读,更多相关《组合数学课件第二章母函数与递推关系.ppt(356页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第二章 母函数与递推关系组合数学组合数学2.1 2.1 母函数母函数 递推关系是计数的一个强有力的工具,特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处,但这主要是介绍解递推关系上的应用。例如2.1 2.1 母函数母函数 项的系数 中所有的项包括n个元素a1,a2,an中取两个组合的全体;同理项系数包含了从n个元素a1,a2,an中取3个元素组合的全体。以此类推。2.1 2.1 母函数母函数 若令a1=a2=an=1 1,在(2-1-1)式中 项系数:中每一个组合有1个贡献,其他各项以此类推。故有:2.1 2.1 母函数母函数 另一方面:2.1 2.1 母函
2、数母函数比较等号两端项对应系数,可得一等式2.1 2.1 母函数母函数 同样对于 ,(设 ),用类似的方法可得等式:正法如下:2.1 2.1 母函数母函数比较等式两端的常数项,即得公式(2-1-3)2.1 2.1 母函数母函数又如等式:令x=1 可得2.1 2.1 母函数母函数(2-1-2)式等号的两端对x求导可得:等式(2-1-5)两端令x=1,得:2.1 2.1 母函数母函数 用类似的方法还可以得到:定义:定义:对于序列 构造一函数:2.1 2.1 母函数母函数 还可以类似地推出一些等式,但通过上面一些例子已可见函数 在研究序列 的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概
3、念如下:称函数G(x)是序列 的母函数序列 可记为 。如若已知序列 则对应的母函数G(x)便可根据定义给出。反之,如若以求得序列的母函数G(x),则该序列也随之确定。2.1 2.1 母函数母函数 例如 是序列 的母函数。2.2 2.2 递推关系递推关系 利用递推关系进行计数这个方法在算法分析中经常用到,举例说明如下:例一.Hanoi问题:这是个组合数学中的著名问题。N个圆盘依其半径大小,从下而上套在A柱上,如下图示。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来,并估计要移动几个盘次。现在只有A、B、C三根柱子可用。2.2 2.2
4、递推关系递推关系 Hanoi问题是个典型的问题,第一步要设计算法,进而估计它的复杂性,集估计工作量。算法:算法:N=2时第一步先把最上面的一个圆盘套在B上z z第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕A B C2.2 2.2 递推关系递推关系z 对于一般n个圆盘的问题,z 假定n-1个盘子的转移算法已经确定。z 先把上面的n-1个圆盘经过C转移到B。z 第二步把A下面一个圆盘移到C上z 最后再把B上的n-1个圆盘经过A转移到C上A B C2.2 2.2 递推关系递推关系 上述算法是递归的运用。n=2时已给出算法;n=3时,第一步便利用算法把上面两个盘移到B上,第二
5、步再把第三个圆盘转移到柱C上;最后把柱B上两个圆盘转移到柱C上。N=4,5,以此类推。2.2 2.2 递推关系递推关系 算法分析:算法分析:令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转到C上;最后再一次将B上的n-1个盘子转移到C上。n=2时,算法是对的,因此,n=3是算法是对的。以此类推。于是有2.2 2.2 递推关系递推关系算法复杂度为:H(x)是序列 的母函数。给定了序列,对应的母函数也确定了。反过来也一样,求得了母函数,对应的序列也就可得而知了。当然,利用递推关系(2-2-1)式也可以依次求得 ,这样的连锁反应关系,叫做递推关系。2
6、.2 2.2 递推关系递推关系 下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时,一如有限项的代数式一样。2.2 2.2 递推关系递推关系 根据(2-2-1),或利用递推关系(2-2-1)有2.2 2.2 递推关系递推关系 上式左端为:右端第一项为:右端第二项为:2.2 2.2 递推关系递推关系 整理得 这两种做法得到的结果是一样的。即:2.2 2.2 递推关系递推关系 令 如何从母函数得到序列?下面介绍一种化为部分分数的算法。2.2 2.2 递推关系递推关系 由上式可得:即:2.2 2.2 递推关系递推关系因为:2.2 2.2 递
7、推关系递推关系 例例2.求n位十进制数中出现偶数个5的数的个数。先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数,若含有偶数个5,则 取5以外的0,1,2,3,4,6,7,8,9九个数中的一个,若 只有奇数个5,则取 ,使 成为出现偶数个5的十进制数。2.2 2.2 递推关系递推关系 解法解法1:令 位十进制数中出现5的数的个数,位十进制数中出现奇数个5的数 的个数。故有:也有类似解释。2.2 2.2 递推关系递推关系 (2-2-2)式中的 表达了含有偶数个5的n位十进制数的两个组成部分。表达由含有偶数个5的n-1位十进制数 ,令 取5以外的0,1,2,3,4,6,7,8,9
8、九个数中的一个数构成的。项表示当 是含有奇数个5的n-1位十进制数,令 而得 是含偶数个5的n位十进制数。(2-2-2)是关于序列 和 的连立关系。2.2 2.2 递推关系递推关系 设序列 的母函数为 ,序列 的母函数为 。即:2.2 2.2 递推关系递推关系承前页:2.2 2.2 递推关系递推关系 又:故得关于母函数 和 得连立方程组:2.2 2.2 递推关系递推关系2.2 2.2 递推关系递推关系2.2 2.2 递推关系递推关系 解法二:解法二:n-1位的十进制数的全体共 从中去掉含有偶数个5的数,余下的便是n-1位中含有奇数个5的数。故有:2.2 2.2 递推关系递推关系令2.2 2.2
9、 递推关系递推关系 1)不出现某特定元素设为 ,其组合数为 ,相当于排除 后从 中取r个做允许重复的组合。2.2 2.2 递推关系递推关系 例三:例三:从n个元素 中取r个进行允许重复的组合。假定允许重复的组合数用 表示,其结果可能有以下两种情况。2.2 2.2 递推关系递推关系 2)至少出现一个 ,取组合数为 相当于从 中取r-1个做允许重复的组合,然后再加上一个 得从n个元素中取r个允许重复的组合。依据加法原则可得:因 ,故令2.2 2.2 递推关系递推关系 递推关系(2-2-3)带有两个参数n和r。2.2 2.2 递推关系递推关系 (2-2-3)式是关于 的递推关系,但系数 不是常数。但
10、2.2 2.2 递推关系递推关系 由二项式定理 可得2.3 2.3 母函数的性质母函数的性质2.32.3母函数的性质母函数的性质 一个序列和它的母函数一一对应。给了序列便得知它的母函数;反之,求得母函数序列也随之而定。这种关系颇像数学中的积分变换,特别酷似离散序列的Z变换。如2的例子所示的那样,为了求满足某种第推关系的序列,可把它转换为求对应的母函数 ,可能满足一代数方程,或代数方程组,甚至于是微分方程。2.32.3母函数的性质母函数的性质 最后求逆变换,即从已求得的母函数 得到序列 。关键在于要搭起从序列到母函数,从母函数到序列这两座桥。这一节便是以此为目的的。不特别说明下面假设 、两个序列
11、对应的母函数分别为 、2.32.3母函数的性质母函数的性质 性质性质1:若 则证:证:2.32.3母函数的性质母函数的性质 例例.已知则2.32.3母函数的性质母函数的性质 性质性质2:若 ,则2.32.3母函数的性质母函数的性质证:证:2.32.3母函数的性质母函数的性质 例例.2.32.3母函数的性质母函数的性质 性质性质2:若 ,则证:证:2.32.3母函数的性质母函数的性质2.32.3母函数的性质母函数的性质 例例.已知2.32.3母函数的性质母函数的性质 类似可得:2.32.3母函数的性质母函数的性质 性质性质2:若 收敛,则2.32.3母函数的性质母函数的性质2.32.3母函数的性
12、质母函数的性质 性质性质5.5.若 ,则 。例例.则2.32.3母函数的性质母函数的性质性质5和性质6的结论是显而易见的。性质性质6 6.若 ,则 2.32.3母函数的性质母函数的性质 性质性质7 7.若 则 2.32.3母函数的性质母函数的性质证证:。2.32.3母函数的性质母函数的性质 例例.已知 则 2.4 2.4 FibonacciFibonacci数列数列2.4.12.4.1递推关系递推关系 Fibonacci数列是递推关系的又一个典型问题,数列的本身有着许多应用。问题:问题:有雌雄兔子一对,假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子?设满n个月时兔子对数为
13、其中当月新生兔数目设为 对。第n-1个月留下的兔子数目设为 对。2.4.12.4.1递推关系递推关系 但即第n-2个月的所偶兔子到第n个月都有繁殖能力了。由递推关系(2-3-1)式可依次得到2.4.22.4.2问题的求解问题的求解 设2.4.22.4.2问题的求解问题的求解 承前页2.4.22.4.2问题的求解问题的求解承前页2.4.22.4.2问题的求解问题的求解承前页2.4.22.4.2问题的求解问题的求解 其中2.4.32.4.3若干等式若干等式 1)证明:证明:2.4.32.4.3若干等式若干等式 2)证明:证明:2.4.32.4.3若干等式若干等式 3)证明:证明:2.4.42.4.
14、4在选优法上的应用在选优法上的应用 设函数 在区间 上有一单峰极值点,假定为极大点。所谓单峰极值,即只有一个极值点 ,而且当x与 偏离越大,偏差 也越大。如下图:2.4.42.4.4在选优法上的应用在选优法上的应用 设函数 在 点取得极大值。要求用若干次试验找到 点准确到一定的程度。最简单的方法,把 三等分,令:如下图:2.4.42.4.4在选优法上的应用在选优法上的应用 依据 的大小分别讨论如下:当 ,则极大点 必在 区间上,区间 可以舍去。2.4.42.4.4在选优法上的应用在选优法上的应用 当 ,则极大点 必在 区间上,区间 可以舍去。2.4.42.4.4在选优法上的应用在选优法上的应用
15、 当 ,则极大点 必在 区间上,区间 和 均可以舍去。2.4.42.4.4在选优法上的应用在选优法上的应用 可见做两次试验,至少可把区间缩至原来区间的2/3,比如 ,进一步在 区间上找极值点。若继续用三等分法,将面对着这一实事,即其中 点的试验没发挥其作用。为此设想在 区间的两个对称点 分别做试验。2.4.42.4.4在选优法上的应用在选优法上的应用 设保留 区间,继续在 区间的下面两个点 处做试验,若则前一次 的点的试验,这一次可继续使用可节省一次试验。由(2-3-6)式有2.4.42.4.4在选优法上的应用在选优法上的应用 这就是所谓的0.618优选法。即若在 区间上找单峰极大值时,可在
16、点做试验。比如保留区间 ,由于 ,故只要在 点作一次试验。2.4.42.4.4在选优法上的应用在选优法上的应用 优选法中可利用Fibonacci数列,和0.618法不同之点在于它预先确定试验次数,分两种情况介绍其方法。(a)所有可能试验数正好是某个 。2.4.42.4.4在选优法上的应用在选优法上的应用 这时两个试验点放在 和 两个分点上,如果 分点比较好,则舍去小于 的部分;如果 点更好,则舍去大于 的部分。在留下的部分共 个分点,其中第 和第 二试验点,恰好有一个是刚才留下来的试验可以利用。可见在 个可能试验中,最多用n-1次试验便可得到所求的极值点2.4.42.4.4在选优法上的应用在选
17、优法上的应用 (b)利用Fibonacci数列进行优选不同于 0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比 小,但比 大时,可以虚加几个点凑成 个点,但新增加的点的试验不必真做,可认定比其他点都差的点来处理。2.4.42.4.4在选优法上的应用在选优法上的应用 下面给出两个定理作为这一节的结束。定理:定理:测试n次可将包含单峰极值点的区间缩小到原区间的 ,其中 是任意小的正整数,2.4.42.4.4在选优法上的应用在选优法上的应用 证:证:对n用数学归纳法。n=2时,将区间 平分成 段。在分点(包括端点a,b)分别标上 。在1点的两侧取 ,在 与 两点上测试,
18、无论哪一点较优,保留下来的区间长度均为 ,命题成立。2.4.42.4.4在选优法上的应用在选优法上的应用 假设对于n-1,命题成立 对于n,将 平分成 段,对分点(包括端点a,b)依次标上 。先在 点与 点测试,无论哪一点较优,保留下来的区间均为 段。根据归纳假设,再做n-1次测试(内含前两次测试之一)可将含极值点的区间缩小到 段,即原区间 的 。2.4.42.4.4在选优法上的应用在选优法上的应用 因 ,当n较大时,可将相继的两个测试点取在待测区间的0.618及1-0.618处。由 可知,0.618法比 法最多多测试一次。0.618 法的优点是不必事先定测试次数。2.4.42.4.4在选优法
19、上的应用在选优法上的应用 定理:定理:设在给定区间内有单峰极值点。如果包含极值点在内的可测点为 个,则测试n次必可找到极值点,。证:证:对n用数学归纳法。n=2时,命题成立2.4.42.4.4在选优法上的应用在选优法上的应用 下面证明对n命题成立。设可测试点的标号依次是 。先在 点及 点测试。无论哪一点较优,保留下来的可测点都为 个。根据归纳假设,再测试n-1必可找到极值点。而在保留的 个可测试点中,有一点(或 )的测试结果下一次比较好时正好用上,这样总测试次数为n。假设对于n-1,命题成立2.5 2.5 线性常系数递推关系线性常系数递推关系 2.5 2.5 线性常系数递推关系线性常系数递推关
20、系 定义定义 如果序列 满足 及 是常数,则称为 的 阶常系数线性递推关系,称为 的初始条件,称为 的特征多项式2.5 2.5 线性常系数递推关系线性常系数递推关系 设 为 的母函数根据(2-5-1),有2.5 2.5 线性常系数递推关系线性常系数递推关系将这些式子两边分别相加,得到即其中2.5 2.5 线性常系数递推关系线性常系数递推关系 令 ,多项式 的次数不大于 。特征多项式2.5 2.5 线性常系数递推关系线性常系数递推关系因此,是 次多项式,我们知道 在复数域中有 个根。设2.5 2.5 线性常系数递推关系线性常系数递推关系则 于是2.5 2.5 线性常系数递推关系线性常系数递推关系
21、(2-5-3)式是有理式,且分子的次数低于分母的次数,有分项表示,即:2.5 2.5 线性常系数递推关系线性常系数递推关系承上页:的系数是 。是常数。2.5 2.5 线性常系数递推关系线性常系数递推关系 定理:定理:设 是有理分式,多项式的 次数低于 的次数。则 有分项表示,且表示唯一2.5 2.5 线性常系数递推关系线性常系数递推关系 证明:证明:设 的次数为n,对n用数学归纳法。n=1时,是常数,命题成立。假设对小于n的正整数,命题成立。下面证明对正整数n命题成立。设 是 的 重根,2.5 2.5 线性常系数递推关系线性常系数递推关系不妨设 与 互素,设2.5 2.5 线性常系数递推关系线
22、性常系数递推关系 的次数低于 。根据归纳假设,可分项表示。因此,可分项表示。由(2-5-6)式及(2-5-7)式可知表示是唯一的。2.5 2.5 线性常系数递推关系线性常系数递推关系以下分别各种情况讨论具体计算的问题。(1)特征多项式 无重根 设 可见化为2.5 2.5 线性常系数递推关系线性常系数递推关系 的系数是可由线性方程组解出。2.5 2.5 线性常系数递推关系线性常系数递推关系 的系数矩阵的行列式是Vander mond 行列式不难看出 有唯一解。2.5 2.5 线性常系数递推关系线性常系数递推关系(2)特征多项式 有共轭复根 设 是 的一对共轭复根。中 的系数是2.5 2.5 线性
23、常系数递推关系线性常系数递推关系 2.5 2.5 线性常系数递推关系线性常系数递推关系其中在具体计算时,可先求出各对共轭复根,再求待定系数A,B,避免中间过程的复数运算。(3)特征多项式 有重根设 是 的 重根,则(2-5-4)可简化为2.5 2.5 线性常系数递推关系线性常系数递推关系 的系数 。其中是n的j-1次多项式。因此,是 与n的k-1次多项式的乘积。2.5 2.5 线性常系数递推关系线性常系数递推关系 为了简化计算,下面引入一些记号,介绍几个命题。设x是任意变量,n是非负整数,令2.5 2.5 线性常系数递推关系线性常系数递推关系 不难证明,多项式可用 唯一线性表示。其中 是常数2
24、.5 2.5 线性常系数递推关系线性常系数递推关系 设 是给定序列,令 称为 的 阶差分。不难证明,如果对任意的n有 ,则有因而序列 的特征多项式为2.5 2.5 线性常系数递推关系线性常系数递推关系 不难证明,如果 是n的r次多项式,则 是n的r+1次多项式。以上几个命题作为习题,请读者自己证明。2.5 2.5 线性常系数递推关系线性常系数递推关系 总之:总之:(1)若特征多项式 有n个不同零点 则递推关系(2-5-1)的解其中 是待定系数,有初始条件(2-5-2)来确定。2.5 2.5 线性常系数递推关系线性常系数递推关系 (2)若特征多项式 有不同的复根,可依照(1)的办法处理。不过任意
25、复数 可写为 形式,设 是 的一个零点,其共轭复根为2.5 2.5 线性常系数递推关系线性常系数递推关系 和 仍然是待定常数。即 有一对共轭复根 和 时,递推关系(2-5-1)的解有对应的项其中A,B是待定常数。2.5 2.5 线性常系数递推关系线性常系数递推关系 (3)若 k重根。不妨设 是k的重根。则递推关系(2-5-1)的解对应于的项为 其中 是k个待定常数。2.5 2.5 线性常系数递推关系线性常系数递推关系 例例1 1:求下列n阶行列式 的值。2.5 2.5 线性常系数递推关系线性常系数递推关系根据行列式性质对应的特征方程为故 是二重根2.5 2.5 线性常系数递推关系线性常系数递推
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合数学课件 第二章母函数与递推关系 组合 数学 课件 第二 函数 关系
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内