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