组合2母函数递推关系.ppt

《组合2母函数递推关系.ppt》由会员分享，可在线阅读，更多相关《组合2母函数递推关系.ppt（252页珍藏版）》请在三一办公上搜索。

1、组合数学,帅天平,北京邮电大学数学系,Email:,第二章:递推关系与母函数,1,递推关系引入，Fibonacci数列2,常系数递推关系求解3,母函数及其性质4,用母函数求解递推关系5,母函数的应用-整数剖分6指数型母函数及其应用7,非线性递推关系举例-几类特殊组合数,2.1 递推关系-引入1,利用递推关系进行计数的方法在算法分析中经常用到。,and,Mathematics for the analysis of algorithms Birkhauser,Boston 1st,1981;3rd,1999.中对递推关系及其应用有更广泛的叙述。,例1,Hanoi问题：这是组合数学中的一个著名问题

2、。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,2.1 递推关系-引入2,Hanoi问题是个典型的组合问题,第一步要设计算法，进而估计它的复杂性，及估计工作量。,2.1 递推关系-引入3,算法：,N=2时,第一步先把最上面的一个圆盘套在B上,第二步把下面的一个圆盘移到C上,最后把B上的圆盘移到C上,到此转移完毕,对于一般n个圆盘的问题，,假定n-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下

3、面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,2.1 递推关系-引入4,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。,2.1 递推关系-引入5,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,2.1 递推关系-引入6,算法复杂度为：,利用递推关系(a)式也可以依次求得h

4、(1),h(2),h(3)，这样的连锁反应关系，叫做递推关系。,Fibonacci数列是递推关系的又一个典型问题，该数列的本身有着许多应用。,问题：有雌雄兔子一对，假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？,设满n个月时兔子对数为 Fn其中当月新生兔数目设为Nn 对。第n-1个月留下的兔子数目设为 On 对。,2.1 递推关系-Fibonacci数列1,但,即第n-2个月所产的兔子到第n个月都有繁殖能力了.,由递推关系(1)式可依次得到,2.1 递推关系-Fibonacci数列2,趣味结论,2.1 递推关系-Fibonacci数列7,证明：,2.1 递推关系-F

5、ibonacci数列8,证明：,2.1 递推关系-Fibonacci数列9,证明：,2.1 递推关系-Fibonacci数列10,确定一个数列an的最常用的方法是给出一般项an的表达式得到该数列的母函数建立数列所满足的递推关系即建立一种规则，使得通过这种规则数列的每一项可由其 前面的项唯一确定.,2.1 递推关系,更一般的递推关系。,递推关系可分为有限阶和无限阶两种,2.1 递推关系,一个r-阶递推关系定义为：有正整数r 以及一个r+1元函数F，使得对所有nr,有关系式,定义1 如果序列an满足,则(2)称为an的 k 阶常系数线性递推关系,(2i)称为an 的初始条件。若b(n)=0，称为齐

6、次的，否则称为非齐次的。,2.1 递推关系-线性常系数递推关系,2.1递推关系-线性常系数递推关系,定义2 如果序列an满足,称为an 的特征多项式.C(x)=0称为an的特征方程.,则(2-1)称为an的 k阶常系数线性齐次递推关系,(2-2)称为an 的初始条件。,2.1递推关系,例：1n 棋盘用红、白、蓝三种颜色着色,不允许相邻两格都着红色,求着色方案数.解:设an 表示满足条件的着色方案数.,2.1递推关系,在该棋盘上着色,其方案可分成如下四类:1)1着白色,余下的是1(n-1)的棋盘,它所满足条件的着色方案数是an-1;2)1着蓝色,余下的是1(n-1)的棋盘,它所满足条件的着色方案

7、数是 an-13)1着红色,2着蓝色,余下的是1(n-2)的棋盘,它所满足条件的着色方案数是an-2;4)1着红色,2着白色,余下的是1(n-2)的棋盘,它所满足条件的着色方案数是an-2.,2.1递推关系,故总的着色方案数为:,2.2 母函数-引入1,母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著概率解析理论。,两个色子掷出6点，有多少种选法？,我们来看如下的例子,2.2 母函数-引入2,我们也可以从另一角度来看，要使两个色子掷出6点，第一个色子除了6以外的都可选，这有5种选法，一旦第一个选定，第二个色子就只有一种可能的选法按乘法法则有

8、5*1=5种,注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，这些选法互斥且穷尽了出现6点的一切可能的选法，按加法法则，共有2+2+1=5种不同选法。,但碰到用三个或四个色子掷出n点，上述两方法就不胜其烦了。这就需要引进新的方法。,2.2 母函数-引入3,2.2 母函数-引入4,这种对应把组合问题的加法法则和幂级数的t的乘幂的相加对应起来。,故使两个色子掷出6点的方法数等价于求,2.2 母函数-引入5,母函数的思想很简单 即:把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造.,再看下面的例

9、子.,2.2 母函数-引入6,2.2 母函数-引入7,中所有的项包括 n个元素a1，a2，an中取两个组合的全体；同理 x3 项系数包含了从 n个元素a1，a2，an中取3个元素组合全体。以此类推。,若令a1=a2=an=1，在（2-1-1）式,项系数,中每一个组合有1个贡献,其他各项以此类推.,2.2 母函数-引入8,故有：,另一方面：,比较等号两端项对应系数，可得一等式,2.2 母函数-引入9,2.2 母函数-引入10,用类似的方法可得等式：,证法如下：,比较等式两端的常数项，即得公式(2-1-3),2.2 母函数-引入11,又如等式：,令x=1 可得,2.2 母函数-引入12,(2-1-

10、2)式等号的两端对x求导可得：,等式(2-1-5)两端令x=1，得：,2.2 母函数-引入13,2.2 母函数-引入14,用类似的方法还可以得到：,等式两端对x求导再令x=1，得：,2.2 母函数-引入15,已可见函数,还可以类似地推出一些等式，但通过上面一些例子,的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：,在研究序列,2.2 母函数-引入16,利用母函数求解Fibonacci数列（Fn=Fn-1+Fn-2，F1=F2=1）：设,2.2 母函数-引入17,2.2 母函数-引入18,2.2 母函数-引入19,其中,2.2 母函数-引入20,42,几个基本的母函数,43,

11、几个基本的母函数,2.3母函数的性质1,一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，特别酷似离散序列的Z变换。如前的例子所示的那样，为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。,最后求逆变换，即从已求得的母函数G(x)得到序列an。关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。,2.3母函数的性质2,性质1:,证:,2.3母函数的性质3,性质2:,则,若,2.3母函数的性质4,证：,2.3母函数的性质5,性质

12、3：,若,则,2.3母函数的性质6,2.3母函数的性质7,证：,例.已知,2.3母函数的性质8,类似可得：,2.3母函数的性质9,性质4,则,2.3母函数的性质10,证,2.3母函数的性质11,2.3母函数的性质12,例,则,性质5,2.3母函数的性质13,性质5和性质6的结论是显而易见的。,性质6,2.3母函数的性质14,性质7,若,则,2.3母函数的性质15,证:,2.3母函数的性质16,已知,例1.,则,2.3母函数的性质17,2.4 母函数求解线性常系数递推关系1,以二阶齐次线性常系数递推关系为例,2.4 母函数解线性常系数递推关系2,2.4 母函数解线性常系数递推关系3,2.4 母函

13、数解线性常系数递推关系4,2.4 母函数解线性常系数递推关系5,2.4 母函数解线性常系数递推关系6,证明:(1)r1，r2为两相异的实根.,2.4 母函数解线性常系数递推关系7,2.4 母函数解线性常系数递推关系8,故,2.4母函数求解线性常系数递推关系9,2.4 母函数求解线性常系数递推关系10,2.4母函数求解线性常系数递推关系11,2.4母函数求解线性常系数递推关系12,例4：求下列n阶行列式dn 的值.,2.4母函数求解线性常系数递推关系13,根据行列式性质,对应的特征方程为,故m=1是二重根,2.4母函数求解线性常系数递推关系14,即,时有,时有,2.4母函数求解线性常系数递推关系

14、15,2.4母函数解线性常系数递推关系16,考虑如下k阶常系数线性齐次递推关系:数列an满足,上面母函数的方法可以推广到解一般的常系数线性递推关系,设an 的母函数G(x)为,根据(2-4-1)，有,2.4母函数解线性常系数递推关系17,将这些式子两边分别相加，得到,即,其中,2.4母函数解线性常系数递推关系18,特征多项式,2.4母函数解线性常系数递推关系19,因此,是k次多项式。,2.4母函数解线性常系数递推关系20,C(x)=0 在复数域中有k个根，故设,则,于是,2.4母函数解线性常系数递推关系21,(2-5-3)式是有理式,且分子的次数低于分母的次数,有分项表示，即,2.4母函数解线

15、性常系数递推关系22,定理：设 P(x)/Q(x)是有理分式，多项式P(x)的次数低于Q(x)的次数。则它有分项表示，且表示唯一.,2.4母函数解线性常系数递推关系23,证明：设 Q(x)的次数为n，对n用数学归纳法,n=1时，P(x)是常数，命题成立。,假设对小于n的正整数，命题成立。,下面证明对正整数n命题成立.,设是Q(x)的k重根，,2.4母函数解线性常系数递推关系24,不妨设P(x)与Q(x)互素，设,2.4母函数解线性常系数递推关系25,P(x)的次数低于Q(x)。根据归纳假设，,可分项表示。因此，,可分项表示。由前几式可知表示是唯一的.,2.4母函数解线性常系数递推关系18,以下

16、分别各种情况讨论具体计算的问题。,设,(2-4-4)可简化为C(x),（1）特征多项式C(x)无重根,2.4母函数解线性常系数递推关系19,可由线性方程组,解出.,2.4母函数解线性常系数递推关系20,上式的系数矩阵的行列式是范德蒙行列式,不难看出它有唯一解。,2.4母函数解线性常系数递推关系21,（2）特征多项式C(x)有共轭复根,设1,2是C(x)的一对共轭复根。,2.4母函数解线性常系数递推关系22,其中,2.4母函数解线性常系数递推关系23,在具体计算时,可先求出各对共轭复根，再求待定系数A、B,避免中间过程的复数运算.,（3）特征多项式C(x)有重根,设是C(x)的k重根，则(2-4

17、-4)可简化为,2.4母函数解线性常系数递推关系24,因此，an是 与n的k-1次多项式的乘积。,的系数,2.4母函数解线性常系数递推关系25,2.4母函数解线性常系数递推关系26,总之，我们有如下定理,2.4母函数解线性常系数递推关系27,例5：求,同理,相减得,2.4母函数解线性常系数递推关系28,同理,对应的特征方程为,2.4母函数解线性常系数递推关系29,m=1是三重根,即,这就证明了,2.4母函数解线性常系数递推关系30,例6：求,同理,相减得,2.4母函数解线性常系数递推关系31,同理,对应的特征方程为,相减得,同理,2.4母函数解线性常系数递推关系32,r=1是四重根,依据 得关

18、于A、B、C、D的连立方程组：,2.4母函数解线性常系数递推关系33,于是,2.4母函数解线性常系数递推关系34,已知Sn是n的3次式，故不妨令,确定待定系数时，比较方便，无需解一联立方程组。例如,2.4母函数解线性常系数递推关系35,2.4母函数解线性常系数递推关系36,2.5 线性常系数非齐次递推关系1,常系数线性非齐次递推关系的一般形式如下,结论证明:只要把它代入(1)式的左端验证即可.,齐次递推关系较易求解,故问题的关键是求特解.下面我们考虑如何求特解,一般来说,没有普遍的解法.在某些简单的情形可以用待定系数法求之.先看一个例子.,2.5 线性常系数非齐次递推关系2,2.5 线性常系数

19、非齐次递推关系3,2.5 线性常系数非齐次递推关系4,2.5 线性常系数非齐次递推关系5,我们很直观的看出上式解不出p1 和 p2.这是因为当原递推关系的特征根是1时.如果所设的特解中n的最高次幂的次数与f(n)的次数一样时,代入原递推关系后,等式左边的n的最高次幂就会消去.因此等式左边的多项式比右边的多项式的次数低.为此 在设特解时要将n的最高次幂提高,并且可以不设常数项,2.5 线性常系数非齐次递推关系6,2.5 线性常系数非齐次递推关系7,2.5 线性常系数非齐次递推关系8,2.5 线性常系数非齐次递推关系9,2.5 线性常系数非齐次递推关系10,2.5 线性常系数非齐次递推关系11,综

20、上所述,我们可得如下定理,2.5 线性常系数非齐次递推关系12,特解,2.5 线性常系数非齐次递推关系13,2.5 线性常系数非齐次递推关系14,所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。记p(n,k)为把n拆分成恰好k个正整数的和的拆分数。,2.6 整数的拆分-问题描述,2.6 整数的拆分-问题举例,例1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？,同样

21、，,故称出6克的方案有2，称出10克的方案有1,2.6 整数的拆分-问题举例,从右端的母函数知可称出从1克到10克,系数便是方案数。例如右端有 项,即称出5克的方案有2,例2：求用1分、2分、3分的邮票贴出不同数值的方案数。,解:因邮票允许重复，故母函数为,2.6 整数的拆分-问题举例,例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？,2.6 整数的拆分-问题举例,解:作母函数,2.6 整数的拆分-问题举例,2.6 整数的拆分-问题举例,2.6 整数的拆分-问题举例,例 6 对N进行无序且允许重复的任意剖分，设剖分数为P(N),求P(N)的母函

22、数G(y)。,解:这相当于把N无序剖分成1,2,3,.,n,且允许重复，类似上例，我们有,例 7 对N进行无序且允许重复的剖分，使得剖分后的正整数都是奇数，求这种剖分方案数P0(N)的生成函数G0(y).,2.6 整数的拆分-问题举例,解：这是把N剖分成1,3,5,且允许重复。类似于上例，我们有,例 8 对N进行无序剖分,使得剖分后的整数各不相等,求这种剖分方案数Pd(N)的生成函数Gd(y),解：这相当于把N剖分成1,2,3,.,n,且不允许重复，类似于(b)式，有,例 9 对N进行无序剖分，使得剖分后的整数都是2的幂，求这种剖分方法数Pt(N)的母函数Gt(y).,2.6 整数的拆分-问题

23、举例,解：这相当于把N剖分成1,2,4,8,16,但不允许重复，类似于(a)可得,例10:整数n拆分成1，2，3，m的和，并允许重复，若其中m至少出现一次，其母函数如何？,若整数n拆分成1，2，3，m的和，并允许重复，由(d)式，其母函数为：,若拆分中m至少出现一次，其母函数则为：,2.6 整数的拆分-问题举例,显然有,等式(g)的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。,2.6 整数的拆分-问题举例,从以上例子可以归结如下的结论,定理1 整数剖分成不同数的和的剖分数等于剖分成奇整数的剖分数.,2.6 整数的拆分-问题举例,证明：

24、设bN表示N剖分成不同正整数和的剖分数，则序列bN的生成函数为,定理 2 N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数。,2.6 整数的拆分-问题举例,证明：N剖分成其他数之和但重复数不超过2的剖分数所构成序列的母函数为,2.6 整数的拆分-问题举例,2.6 整数的拆分-问题举例,定理 3 N被剖分成其重复度不超过k次的数的和，其剖分数等于被剖分成不被k+1除尽的数的和的剖分数。,定理4 对一切N，有Pt(N)=1.,2.6 整数的拆分-问题举例,定理 5 设Pod(N)=N被剖分成奇数个不同正整数的和的剖分数；Pev(N)=N被剖分成偶数个不同正整数的和

25、的剖分数，则,例11：若有1、2、4、8、16、32克的砝码各一枚,问能称出那几种重量？有几种可能方案？,2.6 整数的拆分-问题举例,从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。,这问题可以推广到证明任一十进制数n,可表示为,而且是唯一的。,2.6 整数的拆分-问题举例,2.7 Ferrers图像,图 2-7-1,Ferrers图像具有如下性质：1.每一层至少有一个格子。2.第一行与第一列互换，第二行于第二列互换，即图(2-7-1)绕虚线轴旋转所得的图仍然是Ferrers图像.,2.7 Ferrers图像,两个Ferrers 图像称为一对共轭的Ferrers

26、图像。,利用Ferrers图像可得关于整数拆分的十分有趣的结果.,(a)整数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的拆分数相等。,因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如：,24=6+6+5+4+3 5个数，最大数为6,24=5+5+5+4+3+2 6个数，最大数为5,图(2-7-2),2.7 Ferrers图像,(c)整数n拆分成互不相同的若干奇数的和的的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等.,构造一个Ferrers图像，其第一行，第一列都是 格，对应于，第二行，第二列各 格,对应于.以此

27、类推.由此得到的Ferres图像是共轭的.反过来也一样。,2.7 Ferrers图像,(b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。,例如,对应为Ferrers图像为,9+5+3=17,2.7 Ferrers图像,图(2-7-3),利用Ferrers图像可以证明定理 4 正整数N剖分成不超过k个数的和的剖分数等于将N+k剖分成恰好k个数的剖分数,2.8 指数型母函数-问题提出,从x4的系数可知,这8个元素中取4个组合，其组合数为10.这10个组合可从下面展开式中得到,2.8 指数型母函数-解的分析,2.8 指数型母函数-解的分析,其中4次方项有,(2-8-

28、1)表达了从8个元素(a1,a3各3个,a2 2个)中取4个的组合。例如 为一个，3个 的组合，为两个，两个 的组合，以此类推。,2.8 指数型母函数-解的分析,六种。同样,1个 a1 3个 a3 的不同排列数为,2.8 指数型母函数-解的分析,即,若研究从中取4个的不同排列总数,以x12x32对应的两个不同排列为例,其不同排列数为,以此类推。故从(2-8-1)式可得问题的解，其不同的排列数为,2.8 指数型母函数-解的分析,即,为便于计算,利用上述特点,形式地引进函数,2.8 指数型母函数解的分析,2.8 指数型母函数-解的分析,从(2-8-2)式计算结果可以得出：取一个的排列数为3，取两个

29、的排列数为29/2=9 取3个的排列数为 3!14/3=28，取4个的排列数为 4!35/12=70，如此等等。把(2-8-2)式改写成下面形式便一目了然了。,2.8 指数型母函数-解的分析,称为是序列 的指数型母函数,2.8 指数型母函数-解的分析,若元素 a1有n1个，元素a2有n2 个，元素ak有nk个；由此组成的n个元素中取r个排列，设其不同的排列数为pr。则序列 p0,p1,p2,pn的指数型母函数为,2.8 指数型母函数-解的分析,综上可得如下结论：,2.8 指数型母函数-举例,下面简单介绍指数型母函数的性质,2.8 指数型母函数-分析,2.8 指数型母函数-举例,2.8 指数型母

30、函数-举例,2.8 指数型母函数-举例,2.8 指数型母函数-举例,2.8 指数型母函数-举例,例3：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。,2.8 指数型母函数-举例,解:设满足上述条件的r位数为ar序列a1,a2,a10的指数型母函数为,由此可见满足条件的5位数共215个。,2.8 指数型母函数-举例,例4:求1，3，5，7，9五个数字组成的n 位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。,2.8 指数型母函数-举例

31、,由于,2.8 指数型母函数-举例,2.8 指数型母函数-举例,166,例5 用红绿蓝三种颜色去涂1n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。,2.8 指数型母函数-举例,167,递推关系解法的补充,1、母函数法,2、迭代法,3、归纳法,4、置换法,5、相加消去法,168,例1：求下列递推关系的解,解：用置换法：,解特征方程可得：,递推关系解法的补充,169,递推关系解法的补充,170,递推关系解法的补充,171,例2：求下列递推关系的解,解：用置换法：,令,递推关系解法的补充,2.9 非线性递推关系举例-多项式系数,n个有区别的球放到两个有区别的盒子里.若要求第

32、1个盒子放k个球,第二个盒子放n-k个球(k=0,1,2,n)的方案数是,依据加法法则有,多项式系数,推广:n个有区别的球放到m个有区别的盒子里，要求m个盒子放的球数分别是,其不同方案数用下式表示：,2.9非线性递推关系举例-多项式系数,从n个有区别的球中取出n1个放到第1个盒子里去，其选取方案数为C(n,n1)；当第1个盒子的n1个球选定后,第2个盒子里的n2个球则是从n-n1个中选取的，其方案数应为 C(n-n1,n2),第3个盒子的n3个球则是从余下的n-n1 n2个球中选取，其方案数C(n-n1-n2,n3).,计算如下,2.9 非线性递推关系举例-多项式系数,依此类推，根据乘法法则可

33、得,2.9 非线性递推关系举例-多项式系数,n个有区别的球，放到m个有标志的盒子的问题，也可以考虑把n个有区别的球进行全排列。对于每一个排列依次取n1个放到第1个盒子里，取n2个放到第2个盒子里,最后nm个放到第m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为,结果和前式一致。,2.9 非线性递推关系举例-多项式系数,n项中,每项各取一个元素相乘而得到的.,记多项式,2.9 非线性递推关系举例-多项式系数,令第i 个因子项对应于第i个有标志的球，从第i个因子项中取xj对应于把第i个有标志的球放到第j个盒子。（2-9-2）式展开的一般项,表示第一个盒子有n1个球，第二个盒子有n

34、2个球，等等。因此 项的系数应为,2.9 非线性递推关系举例-多项式系数,即,2.9 非线性递推关系举例-多项式系数,2.9非线性递推关系举例-多项式系数,从m个中取n个作允许重复的组合的全体，对于每个球都有m个盒子可供选择，根据乘法法则有,2.9 非线性递推关系举例-多项式系数,(2)Stirling数,第一类和第二类Stirling数分别是把因子积展成幂和幂展成因子积的系数，由James Stirling 于1730年引入。18-19世纪吸引了许多数学家的研究。1939年 C.Jordan的经典著作Calculus of finite differences 更是激发了人们对该数的研究兴趣

35、。,2.10 非线性递推关系举例-Stirling系数,称 s(n,0),s(n,1),s(n,n)为第一类Stirling数,显然，由,定义1,2.10 非线性递推关系举例-Stirling系数,有如下递推关系,2.10 非线性递推关系举例-Stirling系数,2.10 非线性递推关系举例-Stirling系数,定义2:n个有区别的球放到k个相同的盒子中,要求无一空盒,其不同的方案数用S(n,k)表示,称为第二类Stirling数.,例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种:,其中r表红球,y表黄球,b表蓝球,w表白球,2.10 非线性递推关系

36、举例-Stirling系数,由定义，我们有s(n,k)=S(n,k)=0,若kn s(0,0)=S(0,0)=1,定理4:第二类Stirling数S(n,k)有下列性质:,2.10 非线性递推关系举例-Stirling系数,(c)设有n个不相同的球b1,b2,bn从中取出球 b1,其余的n-1个球,每个都有与b1同盒,或不与b1同盒两种选择.但必须排除一种情况,即全体与b1同盒,因这时另一盒将是空盒.,故实际上只有2n-11种方案,即,证明:公式(a)(b)(e)显然,只证(c)(d).,2.10 非线性递推关系举例-Stirling系数,(d)n个球放到n-1个盒子里,不允许有一空盒,故 必

37、有一盒有两个球,从n个有区别的球中取2个,共有C(n,2)种组合方案.,定理5:第二类Stirling数满足下面的递推关系.,2.10 非线性递推关系举例-Stirling系数,证明:设有n个有区别的球b1,b2,bn从中取一个球设为b1,把n个球放到m个盒子无一空盒的方案的全体可分为两类：(a)b1独占一盒,其方案数显为 S(n-1,m-1)(b)b1不独占一盒,这相当于先将剩下的 n-1个球放到m个盒子,不允许空盒,共S(n-1,m)种不同方案;然后将b1球放进其中一盒,由乘法法则得 b1不独占一盒的方案数应为 mS(n-1,m),由加法法则有,2.10 非线性递推关系举例-Stirlin

38、g系数,上面证明递推公式(10-6)的过程，也就是给出构造所有方案的办法。例如今将红、黄、蓝、白、绿五个球放到无区别的两个盒子里。,先把绿球取走，余下的四个球放到两个盒子的方案已见前面的例子。和前面一样用r，y，b，w分别表示红,黄,蓝,白球;绿球用g表示.可得表 A,故共有15种不同的方案。,2.10 非线性递推关系举例-Stirling系数,表 A,2.10 非线性递推关系举例-Stirling系数,n个球放到m个盒子里,依球和盒子是否有区别,是否允许空盒？共有 8种状态.其方案计数分别列于下.,n个球有区别，m个盒子有区别，有空盒时方案计数为mn,n个球有区别，m个盒子有区别，无空盒时方

39、案计数为,n个球有区别，m个盒子无区别，有空盒时方案计数为,2.10 非线性递推关系举例-Stirling系数,n个球有区别，m个盒子无区别，无空盒时方案计数为S(n,n),n个球无区别，m个盒子有区别，有空盒时方案计数为C(n+m-1,n),n个球无区别，m个盒子有区别，无空盒时方案计数为,2.10 非线性递推关系举例-Stirling系数,n个球无区别，m个盒子无区别，有空盒时方案计数为,n个球无区别，m个盒子无区别，无空盒时方案计数为,2.10 非线性递推关系举例-Stirling系数,2.10 非线性递推关系举例-Stirling系数,还可以如Pascal三角形一样得到下表。,利用,2

40、.10 非线性递推关系举例-Stirling系数,2.10 非线性递推关系举例-Stirling系数,2.10 非线性递推关系举例-Stirling系数,第二类Stirling数的显式表示,2.10 非线性递推关系举例-Stirling系数,第一类Stirling数的显式表示,2.10 非线性递推关系举例-Stirling系数,2.10非线性递推关系举例-错排问题,Df1:n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排,有的叫重排。,以1，2，3，4四个数的错排为例，分析其结构，找出规律性的东西来。,1 2的错排是唯一的，即2 1。,即,1

41、2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1，2换位而得的.,2.10非线性递推关系举例-错排问题,1 2 3 4的错排有,4 3 2 1，4 1 2 3，4 3 1 2，3 4 1 2，3 4 2 1，2 4 1 3，2 1 4 3，3 1 4 2，2 3 4 1。,4 3 2 1，3 4 1 2，2 1 4 3。,第一列是4分别与1，2，3互换位置,其余两个元素错排.由此生成的。,2.10非线性递推关系举例-错排问题,第2列是4分别与3，1，2（123的一个错排）的每一个数互换而得到的。即,2.10非线性递推关系举例-错排问题,第三列则是由另一个错排231和

42、4换位而得到,即,上面的分析结果，实际上是给出一种产生错排的结果。,设n个数1，2，n错排的数目为Dn,任取其中一数i,数i分别与其他的n-1个数之一互换，其余n-2个数进行错排，共得(n-1)Dn-2个错排。另一部分为数i以外的n-1个数进行错排，然后i与其中每个数互换，得(n-1)Dn-1个错排。,2.10非线性递推关系举例-错排问题,综合以上分析结果得递推关系,Dn=(n-1)(Dn-1+Dn-2)，D1=0,D2=1(2-10-3),它是一个非常系数的递推关系.,由于D1=0,D0=1故得关于Dn的递推关系,2.10非线性递推关系举例-错排问题,一种解法:,令,2.10非线性递推关系举

43、例-错排问题,2.10非线性递推关系举例-错排问题,2.10非线性递推关系举例-Catalan 数,Catalan数的递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.,定义1：一个凸n边形,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同拆分的数目用hn表之，称为Catalan数.,1.递推关系,定理1：,2.10非线性递推关系举例-Catalan 数,以 v1vn+1 作为一个边的三角形v1vkvn+1，将凸n+1边形分割成两部分，一部分是k边形,一部分是n-k+2边形，k=2,3,n.即vk点可以是v2,v3,vn 点中任意一点,证明(a)的证明：如图 所示，,

44、2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,依据加法法则有,从 v1点向其它n-3 个顶点v3,v4,vn-1 可引出n-3 条对角线。对角线v1vk把 n边形分割成两个部分，因此,图 2-10-3,(b)的证明：如图所示,2.10非线性递推关系举例-Catalan 数,以v2,v3,vn 取代v1 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，,以v1vk对角线作为拆分线的方案数为hkhn-k+2,vk可以是v3,v4,vn-1 中任一点，对所有这些点求和得,2.10非线性递推关系举例-Catalan 数,

45、作,(2-10-7)式并不给出剖分数，无疑其中是有重复的。其重复度是由于一个凸n边形的剖分有n-3 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了n-3次，即该式给出的结果是hn的n-3倍。,2.10非线性递推关系举例-Catalan 数,(2-10-5)式和(2-10-6)式都是非线性递推关系.,由(2-10-5)式及h2=1,故得,2.Catalan 数计算公式,2.10非线性递推关系举例-Catalan 数,由,整理得,令,2.10非线性递推关系举例-Catalan 数,即,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,设,3

46、.母函数方法,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,由二项式定理,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,的系数为正,且得,2.10非线性递推关系举例-Catalan 数,同样可推出,令,从递推关系,4.微分法,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,即,2.10非线性递推关系举例-Catalan 数,5.举例,2.10非线性递推关

47、系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,例2.为n个数，的乘积,依据乘法的结合律,不改变其顺序,只用括号表示成对的乘积.试问有几种不同的乘法方案?,例1.,见图2-10-4,2.10非线性递推关系举例-Catalan 数,令pn表示n个数乘积的n-1对括号插入的不同方案数.,令,故得,而且,2.10非线性递推关系举例-Catalan 数,以n-4为例,P4是 Catalan数h5，下面建立(2-10-8)式中不同的乘法顺序和一个5边形不同拆分的一一对应关系，如图(2-10-5),2.10非线性递推关系举例-Catalan 数,ab运算用二分树表示，两片叶子分

48、别表乘数和被乘数，分支点为运算符，如图,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,2.10非线性递推关系举例-Catalan 数,例3.n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？,解法1.设p2n为这样所得的数的个数。在2n 位上填入n个1的方案数为C(2n,n)，不填1的其余n位自动填以数0,从C(2n,n)中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。,2.10非线性递

49、推关系举例-Catalan 数,不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1 位上首先出现m+1个0的累计数，和m个1的累计数。此后的2(n-m)-1位上有n-m个1，n-m-1个0。如若把后面这部分2(n-m)-1位，0与1交换，使之成为n-m个0，n-m-1个1，结果得一个由 n+1 个0和 n-1个1组成的2n位数，即一个不合要求的数对应于一个由 n-1个0和n+1个1组成的一个排列。,2.10非线性递推关系举例-Catalan 数,反过来，任何一个由 n+1个0，n-1 个1组成的2n位数，由于0的个数多2个，2n是偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。

50、同样在后面的部分，令0和1互换，使之成为由n个0和n个1组成的2n位数。即n-1个0和n+1个1组成的2n位数，必对应于一个不合要求的数。,2.10非线性递推关系举例-Catalan 数,上述方法建立了由 n+1个0和n-1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。,例如10100*101是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（打*号）出现0的累计数3超过1的累计数2，它对应于由3个1，5个0组成的10100010。反过来10100*010对应于10100101。,2.10非线性递推关系举例-Catalan