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

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

1、组合数学,帅天平,北京邮电大学数学系,Email: ,TP SHUAI,2,第二章:递推关系与母函数,1,递推关系引入，Fibonacci数列 2,常系数递推关系求解 3,母函数及其性质 4,用母函数求解递推关系 5,母函数的应用-整数剖分 6指数型母函数及其应用 7,非线性递推关系举例-几类特殊组合数,TP SHUAI,3,2.1 递推关系-引入1,利用递推关系进行计数的方法在算法分析中经常用到。,D.H.Greene and D.E.Knuth, Mathematics for the analysis of algorithms Birkhauser,Boston 1st, 1981;

2、3rd,1999. 中对递推关系及其应用有更广泛的叙述。,TP SHUAI,4,例1,Hanoi问题： 这是组合数学中的一个著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,2.1 递推关系-引入2,TP SHUAI,5,Hanoi问题是个典型的组合问题,第一步要设计 算法，进而估计它的复杂性，及估计工作量。,2.1 递推关系-引入3,算法：,N=2时,第一步先把最上面的一个圆盘套在B上, ,第二步把下面的一个圆盘移到C

3、上, ,最后把B上的圆盘移到C上,到此转移完毕,TP SHUAI,6,对于一般n个圆盘的问题，,假定n-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,2.1 递推关系-引入4,TP SHUAI,7,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。,2.1 递推关系-引入5,TP SHUAI,8,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1

4、个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,2.1 递推关系-引入6,算法复杂度为：,利用递推关系(a)式也可以依次求得h(1), h(2) , h(3) ，这样的连锁反应关系，叫做递推关系。,TP SHUAI,9,Fibonacci数列是递推关系的又一个典型问题，该数列的本身有着许多应用。,问题：有雌雄兔子一对，假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？,设满n个月时兔子对数为 Fn其中当月新生兔数目设为Nn 对。第n-1个月留下的兔子数目设为 On

5、对。,2.1 递推关系-Fibonacci数列1,TP SHUAI,10,但,即第n-2个月所产的兔子到第n个月都有繁殖能力了.,由递推关系(1)式可依次得到,2.1 递推关系-Fibonacci数列2,TP SHUAI,11,趣味结论,2.1 递推关系-Fibonacci数列7,TP SHUAI,12,证明：,2.1 递推关系-Fibonacci数列8,TP SHUAI,13,证明：,2.1 递推关系- -Fibonacci数列9,TP SHUAI,14,证明：,2.1 递推关系-Fibonacci数列10,TP SHUAI,15,确定一个数列an的最常用的方法是 给出一般项an的表达式 得

6、到该数列的母函数 建立数列所满足的递推关系即建立一种规则，使得通过这种规则数列的每一项可由其 前面的项唯一确定.,2.1 递推关系,更一般的递推关系。,TP SHUAI,16,递推关系可分为有限阶和无限阶两种,2.1 递推关系,一个r-阶递推关系定义为：有正整数r 以及一个 r+1元函数F，使得对所有nr, 有关系式,TP SHUAI,17,定义1 如果序列an满足,则(2)称为an的 k 阶常系数线性递推关系,(2i)称为an 的初始条件。若b(n)=0，称为齐次的，否则称为非齐次的。,2.1 递推关系-线性常系数递推关系,TP SHUAI,18,2.1递推关系-线性常系数递推关系,定义2

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

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

9、第二个色子就只有 一种可能的选法 按乘法法则有5*1=5种,注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，这些选法互斥且穷尽了出现6点的一切可能的选法，按加法法则，共有2+2+1=5种不同选法。,TP SHUAI,24,但碰到用三个或四个色子掷出n点，上述两方法就不胜其烦了。这就需要引进新的方法。,2.2 母函数-引入3,TP SHUAI,25,2.2 母函数-引入4,TP SHUAI,26,这种对应把组合问题的加法法则和幂级数的t的 乘幂的相加对应起来。,故使两个色子掷出6点的方法数等价于求,2.2 母函数-引入5,TP SHUAI,27,母函数的思想很简单

10、 即:把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造.,再看下面的例子.,2.2 母函数-引入6,TP SHUAI,28,2.2 母函数-引入7,中所有的项包括 n个元素a1，a2， an中取两个组合的全体；同理 x3 项系数包含了从 n个元素a1，a2， an中取3个元素组合全体。以此类推。,若令a1=a2= =an=1，在（2-1-1）式,项系数,中每一个组合有1个贡献,其他各项以此类推.,TP SHUAI,29,2.2 母函数-引入8,故有：,另一方面：,TP SHUAI,30,比较等号两端项对应系数，可得一等式

11、,2.2 母函数-引入9,TP SHUAI,31,2.2 母函数-引入10,用类似的方法可得等式：,证法如下：,TP SHUAI,32,比较等式两端的常数项，即得公式(2-1-3),2.2 母函数-引入11,TP SHUAI,33,又如等式：,令x=1 可得,2.2 母函数-引入12,TP SHUAI,34,(2-1-2)式等号的两端对x求导可得：,等式(2-1-5)两端令x =1，得：,2.2 母函数-引入13,TP SHUAI,35,2.2 母函数-引入14,用类似的方法还可以得到：,等式两端对x求导再令x =1，得：,TP SHUAI,36,2.2 母函数-引入15,已可见函数,还可以类

12、似地推出一些等式，但通过上面一些例子,的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：,在研究序列,TP SHUAI,37,2.2 母函数-引入16,TP SHUAI,38,利用母函数求解Fibonacci数列（Fn=Fn-1+Fn-2， F1=F2=1）：设,2.2 母函数-引入17,TP SHUAI,39,2.2 母函数-引入18,TP SHUAI,40,2.2 母函数-引入19,TP SHUAI,41,其中,2.2 母函数-引入20,TP SHUAI,42,42,几个基本的母函数,TP SHUAI,43,43,几个基本的母函数,TP SHUAI,44,2.3母函数的性

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

14、性质4,TP SHUAI,48,证：,2.3母函数的性质5,TP SHUAI,49,性质3：,若,则,2.3母函数的性质6,TP SHUAI,50,2.3母函数的性质7,证：,TP SHUAI,51,例. 已知,2.3母函数的性质8,TP SHUAI,52,类似可得：,2.3母函数的性质9,TP SHUAI,53,性质4,则,2.3母函数的性质10,TP SHUAI,54,证,2.3母函数的性质11,TP SHUAI,55,2.3母函数的性质12,TP SHUAI,56,例,则,性质5,2.3母函数的性质13,TP SHUAI,57,性质5和性质6的结论是显而易见的。,性质6,2.3母函数的性

15、质14,TP SHUAI,58,性质7,若,则,2.3母函数的性质15,TP SHUAI,59,证:,2.3母函数的性质16,TP SHUAI,60,已知,例1.,则,2.3母函数的性质17,TP SHUAI,61,2.4 母函数求解线性常系数递推关系1,以二阶齐次线性常系数递推关系为例,TP SHUAI,62,2.4 母函数解线性常系数递推关系2,TP SHUAI,63,2.4 母函数解线性常系数递推关系3,TP SHUAI,64,2.4 母函数解线性常系数递推关系4,TP SHUAI,65,2.4 母函数解线性常系数递推关系5,TP SHUAI,66,2.4 母函数解线性常系数递推关系6,

16、证明:(1) r1，r2为两相异的实根.,TP SHUAI,67,2.4 母函数解线性常系数递推关系7,TP SHUAI,68,2.4 母函数解线性常系数递推关系8,故,TP SHUAI,69,2.4母函数求解线性常系数递推关系9,TP SHUAI,70,2.4 母函数求解线性常系数递推关系10,TP SHUAI,71,2.4母函数求解线性常系数递推关系11,TP SHUAI,72,2.4母函数求解线性常系数递推关系12,TP SHUAI,73,例4：求下列n阶行列式dn 的值.,2.4母函数求解线性常系数递推关系13,TP SHUAI,74,根据行列式性质,对应的特征方程为,故m=1是二重根

17、,2.4母函数求解线性常系数递推关系14,TP SHUAI,75,即,时有,时有,2.4母函数求解线性常系数递推关系15,TP SHUAI,76,2.4母函数解线性常系数递推关系16,考虑如下k阶常系数线性齐次递推关系: 数列an满足,上面母函数的方法可以推广到解一般的常系数线性递推关系,TP SHUAI,77,设an 的母函数G(x)为,根据(2-4-1)，有,2.4母函数解线性常系数递推关系17,TP SHUAI,78,将这些式子两边分别相加，得到,即,其中,2.4母函数解线性常系数递推关系18,TP SHUAI,79,特征多项式,2.4母函数解线性常系数递推关系19,TP SHUAI,8

18、0,因此,是k次多项式。,2.4母函数解线性常系数递推关系20,C(x)=0 在复数域中有k个根，故设,TP SHUAI,81,则,于是,2.4母函数解线性常系数递推关系21,TP SHUAI,82,(2-5-3)式是有理式,且分子的次数低于分母的次数, 有分项表示，即,2.4母函数解线性常系数递推关系22,TP SHUAI,83,定理2.4.2：设 P(x)/Q(x)是有理分式，多项式P(x)的次数低于Q(x) 的次数。则它有分项表示，且表示唯一.,2.4母函数解线性常系数递推关系23,TP SHUAI,84,证明：设 Q(x) 的次数为n，对n用数学归纳法,n=1时，P(x) 是常数，命题

19、成立。,假设对小于n的正整数，命题成立。,下面证明对正整数n命题成立.,设是Q(x)的k重根，,2.4母函数解线性常系数递推关系24,TP SHUAI,85,不妨设P(x)与Q(x)互素，设,2.4母函数解线性常系数递推关系25,TP SHUAI,86,P(x) 的次数低于Q(x)。根据归纳假设，,可分项表示。因此，,可分项表示。由前几式可知表示是唯一的.,2.4母函数解线性常系数递推关系18,TP SHUAI,87,以下分别各种情况讨论具体计算的问题。,设,(2-4-4)可简化为C(x),（1）特征多项式C(x)无重根,2.4母函数解线性常系数递推关系19,TP SHUAI,88,可由线性方

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

21、TP SHUAI,93,因此，an是 与n的k-1次多项式的乘积。,的系数,2.4母函数解线性常系数递推关系25,TP SHUAI,94,2.4母函数解线性常系数递推关系26,总之，我们有如下定理,TP SHUAI,95,2.4母函数解线性常系数递推关系27,TP SHUAI,96,例5：求,同理,相减得,2.4母函数解线性常系数递推关系28,TP SHUAI,97,同理,对应的特征方程为,2.4母函数解线性常系数递推关系29,TP SHUAI,98,m=1是三重根,即,这就证明了,2.4母函数解线性常系数递推关系30,TP SHUAI,99,例6：求,同理,相减得,2.4母函数解线性常系数递

22、推关系31,TP SHUAI,100,同理,对应的特征方程为,相减得,同理,2.4母函数解线性常系数递推关系32,TP SHUAI,101,r=1是四重根,依据 得关于A、B、C、D的连立方程组：,2.4母函数解线性常系数递推关系33,TP SHUAI,102,于是,2.4母函数解线性常系数递推关系34,TP SHUAI,103,已知Sn是n的3次式，故不妨令,确定待定系数时，比较方便，无需解一联立方程组。例如,2.4母函数解线性常系数递推关系35,TP SHUAI,104,2.4母函数解线性常系数递推关系36,TP SHUAI,105,2.5 线性常系数非齐次递推关系1,常系数线性非齐次递推

23、关系的一般形式如下,结论证明:只要把它代入(1)式的左端验证即可.,齐次递推关系较易求解,故问题的关键是求特解.下面我们考虑如何求特解,一般来说,没有普遍的解法.在某些简单的情形可以用待定系数法求之.先看一个例子.,TP SHUAI,106,2.5 线性常系数非齐次递推关系2,TP SHUAI,107,2.5 线性常系数非齐次递推关系3,TP SHUAI,108,2.5 线性常系数非齐次递推关系4,TP SHUAI,109,2.5 线性常系数非齐次递推关系5,TP SHUAI,110,我们很直观的看出上式解不出p1 和 p2.这是 因为当原递推关系的特征根是1时.如果所设的特 解中n的最高次幂

24、的次数与f(n)的次数一样时,代入 原递推关系后,等式左边的n的最高次幂就会消去. 因此等式左边的多项式比右边的多项式的次数低. 为此 在设特解时要将n的最高次幂提高,并且可以不设常数项,2.5 线性常系数非齐次递推关系6,TP SHUAI,111,2.5 线性常系数非齐次递推关系7,TP SHUAI,112,2.5 线性常系数非齐次递推关系8,TP SHUAI,113,2.5 线性常系数非齐次递推关系9,TP SHUAI,114,2.5 线性常系数非齐次递推关系10,TP SHUAI,115,2.5 线性常系数非齐次递推关系11,TP SHUAI,116,综上所述,我们可得如下定理,2.5

25、线性常系数非齐次递推关系12,TP SHUAI,117,特解,2.5 线性常系数非齐次递推关系13,TP SHUAI,118,2.5 线性常系数非齐次递推关系14,TP SHUAI,119,所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。 记p(n,k)为把n拆分成恰好k个正整数的和的拆分数。,2.6 整数的拆分-问题描述,TP SHUAI,120,2.6 整数的拆分-问题举例,例1：若有1克、

26、2克、3克、4克的砝码各一枚， 问能称出那几种重量？有几种可能方案？,TP SHUAI,121,同样，,故称出6克的方案有2，称出10克的方案有1,2.6 整数的拆分-问题举例,从右端的母函数知可称出从1克到10克,系数便是方案数。例如右端有 项, 即称出5克的方案有2,TP SHUAI,122,例2：求用1分、2分、3分的邮票贴出不同数 值的方案数。,解:因邮票允许重复，故母函数为,2.6 整数的拆分-问题举例,TP SHUAI,123,例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？,2.6 整数的拆分-问题举例,解:作母函数,TP SHU

27、AI,124,2.6 整数的拆分-问题举例,TP SHUAI,125,2.6 整数的拆分-问题举例,TP SHUAI,126,2.6 整数的拆分-问题举例,例 6 对N进行无序且允许重复的任意剖分，设剖分数为 P(N),求P(N)的母函数G(y)。,解: 这相当于把N无序剖分成1,2,3,.,n,且允许重复，类似上例，我们有,TP SHUAI,127,例 7 对N进行无序且允许重复的剖分，使得剖分后的正整 数都是奇数，求这种剖分方案数P0(N)的生成函数G0(y).,2.6 整数的拆分-问题举例,解：这是把N剖分成1,3,5,且允许重复。 类似于上例，我们有,例 8 对N进行无序剖分,使得剖分

28、后的整数各不相等,求这种剖分方案数Pd(N)的生成函数Gd(y),解：这相当于把N剖分成1,2,3,.,n,且不允许重复，类似于(b)式，有,TP SHUAI,128,例 9 对N进行无序剖分，使得剖分后的整数都是2的幂，求这种剖分方法数Pt(N)的母函数Gt(y).,2.6 整数的拆分-问题举例,解：这相当于把N剖分成1,2,4,8,16,但不允许重复，类似于(a)可得,例10: 整数n拆分成1，2，3，m的和，并允许重复，若其中m至少出现一次，其母函数如何？,若整数n拆分成1，2，3，m的和，并允许重复，由(d)式，其母函数为：,TP SHUAI,129,若拆分中m至少出现一次，其母函数则

29、为：,2.6 整数的拆分-问题举例,显然有,TP SHUAI,130,等式(g)的组合意义：即整数n拆分成1到m的和的拆分数减 去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆 分数。,2.6 整数的拆分-问题举例,从以上例子可以归结如下的结论,TP SHUAI,131,定理1 整数剖分成不同数的和的剖分数等于剖分成奇整数的剖分数.,2.6 整数的拆分-问题举例,证明：设bN表示N剖分成不同正整数和的剖分数，则序列bN的生成函数为,TP SHUAI,132,定理 2 N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数。,2.6 整数的拆分-问题举例,证明：

30、 N剖分成其他数之和但重复数不超过2的剖分数所构成序列的母函数为,TP SHUAI,133,2.6 整数的拆分-问题举例,TP SHUAI,134,2.6 整数的拆分-问题举例,定理 3 N被剖分成其重复度不超过k次的数的和，其剖分 数等于被剖分成不被k+1除尽的数的和的剖分数。,定理4 对一切N，有Pt(N)=1.,TP SHUAI,135,2.6 整数的拆分-问题举例,定理 5 设Pod(N)=N被剖分成奇数个不同正整数的和的剖 分数； Pev(N)=N被剖分成偶数个不同正整数的和的剖分 数，则,TP SHUAI,136,例11：若有1、2、4、8、16、32克的砝码各一枚, 问能称出那几

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

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

33、第一列都是 格，对应于 ，第二行，第二列各 格,对应于 . 以此类推.由此得到的Ferres图像是共轭的.反过来也一样。,2.7 Ferrers图像,(b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。,TP SHUAI,142,例如,对应为Ferrers图像为,9+5+3=17,2.7 Ferrers图像,图(2-7-3),利用Ferrers图像可以证明 定理 4 正整数N剖分成不超过k个数的和的剖分数等于将N+k剖分成恰好k个数的剖分数,TP SHUAI,143,2.8 指数型母函数-问题提出,TP SHUAI,144,从x4的系数可知,这8个元素中取4个组

34、合，其组合数为10.这10个组合可从下面展开式中得到,2.8 指数型母函数-解的分析,TP SHUAI,145,2.8 指数型母函数-解的分析,TP SHUAI,146,其中4次方项有,(2-8-1)表达了从8个元素(a1,a3各3个,a2 2个)中取4个的组合。例如 为一个 ， 3个 的组合， 为两个 ，两个 的组合，以此类推。,2.8 指数型母函数-解的分析,TP SHUAI,147,六种。同样,1个 a1 3个 a3 的不同排列数为,2.8 指数型母函数-解的分析,即,若研究从中取4个的不同排列总数,以x12x32对 应的两个不同排列为例,其不同排列数为,TP SHUAI,148,以此类

35、推。故从(2-8-1)式可得问题的解，其不同的排列数为,2.8 指数型母函数-解的分析,即,TP SHUAI,149,为便于计算,利用上述特点,形式地引进函数,2.8 指数型母函数解的分析,TP SHUAI,150,2.8 指数型母函数-解的分析,TP SHUAI,151,从(2-8-2)式计算结果可以得出：取一个的排列数为3，取两个的排列数为29/2=9 取3个的排列数为 3!14/3=28，取4个的排列数为 4!35/12=70 ，如此等等。把(2-8-2)式改写成下面形式便一目了然了。,2.8 指数型母函数-解的分析,TP SHUAI,152,称为是序列 的指数型母函数,2.8 指数型母

36、函数-解的分析,TP SHUAI,153,若元素 a1有n1个，元素a2有n2 个，元素ak有nk个；由此组成的n个元素中取r个排列，设其不同的排列数为pr 。则序列 p0, p1, p2,pn的指数型母函数为,2.8 指数型母函数-解的分析,综上可得如下结论：,TP SHUAI,154,2.8 指数型母函数-举例,TP SHUAI,155,下面简单介绍指数型母函数的性质,2.8 指数型母函数-分析,TP SHUAI,156,2.8 指数型母函数-举例,TP SHUAI,157,2.8 指数型母函数-举例,TP SHUAI,158,2.8 指数型母函数-举例,TP SHUAI,159,2.8

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

38、 数，其他1，5，9出现次数不加限制。,2.8 指数型母函数-举例,TP SHUAI,164,由于,2.8 指数型母函数-举例,TP SHUAI,165,2.8 指数型母函数-举例,TP SHUAI,166,166,例5 用红绿蓝三种颜色去涂1n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。,2.8 指数型母函数-举例,TP SHUAI,167,167,递推关系解法的补充,1、母函数法,2、迭代法,3、归纳法,4、置换法,5、相加消去法,TP SHUAI,168,168,例1：求下列递推关系的解,解：用置换法：,解特征方程可得：,递推关系解法的补充,TP SHUAI,1

39、69,169,递推关系解法的补充,TP SHUAI,170,170,递推关系解法的补充,TP SHUAI,171,171,例2：求下列递推关系的解,解：用置换法：,令,递推关系解法的补充,TP SHUAI,172,2.9 非线性递推关系举例-多项式系数,n个有区别的球放到两个有区别的盒子里.若要求第1个盒子放k个球,第二个盒子放n-k个球(k=0,1,2,n) 的方案数是,依据加法法则有,多项式系数,TP SHUAI,173,推广: n个有区别的球放到m个有区别的盒子 里，要求m个盒子放的球数分别是,其不同方案数用下式表示：,2.9非线性递推关系举例-多项式系数,TP SHUAI,174,从n

40、个有区别的球中取出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 非线性递推关系举例-多项式系数,TP SHUAI,175,依此类推，根据乘法法则可得,2.9 非线性递推关系举例-多项式系数,TP SHUAI,176,n个有区别的球，放到m个有标志的盒子的问题，也可以考虑把n个有区别的球进行全排列。对于每一个排列依次取n1个放到第1个盒子里，取n

41、2个放到第2个盒子里,最后nm个放到第m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为,结果和前式一致。,2.9 非线性递推关系举例-多项式系数,TP SHUAI,177,n项中,每项各取一个元素相乘而得到的.,记多项式,2.9 非线性递推关系举例-多项式系数,TP SHUAI,178,令第i 个因子项对应于第i个有标志的球，从 第i个因子项中取xj对应于把第i个有标志的球 放到第j个盒子。（2-9-2）式展开的一般项,表示第一个盒子有n1个球，第二个盒子有n2个球，等等。因此 项的系数应为,2.9 非线性递推关系举例-多项式系数,TP SHUAI,179,即,2.9 非线性

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

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

44、空盒,其方案有如下七种:,其中r表红球,y表黄球,b表蓝球,w表白球,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,187,由定义，我们有s(n,k)=S(n,k)=0,若kn s(0,0)=S(0,0)=1,定理4: 第二类Stirling数S(n,k)有下列性质:,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,188,(c)设有n个不相同的球b1,b2,bn从中取出球 b1,其余的n-1个球,每个都有与b1同盒,或不与b1同盒两种选择.但必须排除一种情况,即全体与b1同盒,因这时另一盒将是空盒.,故实际上只有2n-11种方案,即,证明:公式(

45、a) (b) (e)显然,只证(c)(d).,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,189,(d) n个球放到n-1个盒子里,不允许有一空盒,故 必有一盒有两个球,从n个有区别的球中取2个, 共有C(n,2)种组合方案.,定理5: 第二类Stirling数满足下面的递推关系.,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,190,证明: 设有n个有区别的球b1,b2,bn从中取一个球设为b1,把n个球放到m个盒子无一空盒的方案的全体可分为两类： (a) b1独占一盒, 其方案数显为 S(n-1,m-1) (b) b1不独占一盒,这相当于先

46、将剩下的 n-1个球放到m个盒子,不允许空盒,共S(n-1,m)种不同方案; 然后将b1球放进其中一盒,由乘法法则得 b1不独占一盒的方案数应为 mS(n-1,m),由加法法则有,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,191,上面证明递推公式(10-6)的过程，也就是给出构 造所有方案的办法。例如今将红、黄、蓝、白、 绿五个球放到无区别的两个盒子里。,先把绿球取走，余下的四个球放到两个盒子的方 案已见前面的例子。和前面一样用r，y，b，w分 别表示红,黄,蓝,白球;绿球用g表示.可得表 A,故共有15种不同的方案。,2.10 非线性递推关系举例-Stirling

47、系数,TP SHUAI,192,表 A,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,193,n个球放到m个盒子里,依球和盒子是否有区别,是否 允许空盒？共有 8种状态.其方案计数分别列于下.,n个球有区别，m个盒子有区别，有空盒时方案计数为mn,n个球有区别，m个盒子有区别，无空盒时方案计数为,n个球有区别，m个盒子无区别，有空盒时方案计数为,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,194,n个球有区别，m个盒子无区别，无空盒时方案计数为S(n,n),n个球无区别，m个盒子有区别，有空盒时方案计数为C(n+m-1,n),n个球无区别，m个

48、盒子有区别，无空盒时方案计数为,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,195,n个球无区别，m个盒子无区别，有空盒时方案计数为,n个球无区别，m个盒子无区别，无空盒时方案计数为,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,196,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,197,还可以如Pascal三角形一样得到下表。,利用,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,198,2.10 非线性递推关系举例-Stirling系数,TP SHUAI,199,2.10 非线性递推关系举例-

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

50、，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。,TP SHUAI,204,4 3 2 1， 3 4 1 2， 2 1 4 3。,第一列是4分别与1，2，3互换位置,其余两个元素错排.由此生成的。,2.10非线性递推关系举例- 错排问题,第2列是4分别与3，1，2（123的一个错排）的每一个数互换而得到的。即,TP SHUAI,205,2.10非线性递推关系举例-错

51、排问题,第三列则是由另一个错排231和4换位而得到,即,上面的分析结果，实际上是给出一种产生错排的 结果。,TP SHUAI,206,设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),它是一个非常系数的递推关系.,TP SHUAI,207,由于D1=0,D0=1故

52、得关于Dn的递推关系,2.10非线性递推关系举例-错排问题,一种解法:,TP SHUAI,208,令,2.10非线性递推关系举例-错排问题,TP SHUAI,209,2.10非线性递推关系举例-错排问题,TP SHUAI,210,2.10非线性递推关系举例-Catalan 数,Catalan数的递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.,定义1： 一个凸n边形,通过不相交于n边形内部的 对角线,把n边形拆分成若干三角形,不同拆分的数 目用hn表之，称为Catalan数.,TP SHUAI,211,1.递推关系,定理1：,2.10非线性递推关系举例- Catalan 数,TP

53、 SHUAI,212,以 v1vn+1 作为一个边 的三角形v1vkvn+1 ， 将凸n+1边形分割 成两部分，一部分 是k边形,一部分是n- k+2边形，k=2,3,n. 即vk点可以是v2,v3,vn 点中任意一点,证明 (a)的证明：如图 所示，,2.10非线性递推关系举例-Catalan 数,TP SHUAI,213,2.10非线性递推关系举例-Catalan 数,依据加法法则有,TP SHUAI,214,从 v1点向其它n-3 个 顶点v3,v4,vn-1 可引出n-3 条对角线。 对角线v1vk把 n边形 分割成两个部分，因此,图 2-10-3,(b)的证明：如图所示,2.10非线

54、性递推关系举例-Catalan 数,TP SHUAI,215,以v2,v3,vn 取代v1 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次，,以v1vk对角线作为拆分线的方案数为hkhn-k+2,vk可以是v3,v4,vn-1 中任一点，对所有这些点求和得,2.10非线性递推关系举例-Catalan 数,作,TP SHUAI,216,(2-10-7) 式并不给出剖分数，无疑其中是有重复 的。其重复度是由于一个凸n边形的剖分有n-3 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了n-3次，即该式给出的结果是hn的n-3倍。,2.10非线性递推关系举例-

55、Catalan 数,(2-10-5)式和(2-10-6)式都是非线性递推关系.,TP SHUAI,217,由(2-10-5)式及h2=1,故得,2.Catalan 数计算公式,2.10非线性递推关系举例-Catalan 数,TP SHUAI,218,由,整理得,令,2.10非线性递推关系举例-Catalan 数,TP SHUAI,219,即,2.10非线性递推关系举例-Catalan 数,TP SHUAI,220,2.10非线性递推关系举例-Catalan 数,TP SHUAI,221,设,3.母函数方法,2.10非线性递推关系举例-Catalan 数,TP SHUAI,222,2.10非线性

56、递推关系举例-Catalan 数,TP SHUAI,223,由二项式定理,2.10非线性递推关系举例-Catalan 数,TP SHUAI,224,2.10非线性递推关系举例-Catalan 数,TP SHUAI,225,2.10非线性递推关系举例-Catalan 数,TP SHUAI,226,的系数为正,且得,2.10非线性递推关系举例-Catalan 数,TP SHUAI,227,同样可推出,令,从递推关系,4.微分法,2.10非线性递推关系举例-Catalan 数,TP SHUAI,228,2.10非线性递推关系举例-Catalan 数,TP SHUAI,229,2.10非线性递推关系举

57、例-Catalan 数,TP SHUAI,230,即,2.10非线性递推关系举例-Catalan 数,TP SHUAI,231,5.举例,2.10非线性递推关系举例-Catalan 数,TP SHUAI,232,2.10非线性递推关系举例-Catalan 数,TP SHUAI,233,例2. 为n个数， 的乘积,依据乘法的结合律,不改变其顺序, 只用括号表示成对的乘积.试问有几种不同 的乘法方案?,例1.,见图2-10-4,2.10非线性递推关系举例-Catalan 数,TP SHUAI,234,令pn表示n个数乘积的n-1对括号插入的不同方案数.,令,故得,而且,2.10非线性递推关系举例-

58、Catalan 数,TP SHUAI,235,以n-4为例,P4是 Catalan数h5，下面建立(2-10-8)式 中不同的乘法顺序和一个5边形不同拆分的 一一对应关系，如图(2-10-5),2.10非线性递推关系举例-Catalan 数,TP SHUAI,236,ab运算用二分树表示，两片叶子分别表乘数和被乘数，分支点为运算符，如图,2.10非线性递推关系举例-Catalan 数,TP SHUAI,237,2.10非线性递推关系举例-Catalan 数,TP SHUAI,238,2.10非线性递推关系举例-Catalan 数,TP SHUAI,239,2.10非线性递推关系举例-Catal

59、an 数,TP SHUAI,240,例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非线性递推关系举例-Catalan 数,TP SHUAI,241,不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1 位上首先出现m+1个0的累计数，和m个1的累计数。 此后的2(n-m)-

60、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 数,TP SHUAI,242,反过来，任何一个由 n+1个0，n-1 个1组成的2n位 数，由于0的个数多2个，2n是偶数，故必在某一个 奇数位上出现0的累计数超过1的累计数。同样在后 面的部分，令0和1互换，使之成为由n个0和n个1组 成的2n位数。即n-1个0和n+1个1组成的2n位数，必 对应于一个

61、不合要求的数。,2.10非线性递推关系举例-Catalan 数,上述方法建立了由 n+1个0和n-1个1组成的2n位 数，与由n个0和n个1组成的2n位数中从左向右扫 描出现0的累计数超过1的累计数的数一一对应。,TP SHUAI,243,例如10100*101是由4个0和4个1组成的8位2进制 数。但从左而右扫描在第5位（打*号）出现0的 累计数3超过1的累计数2，它对应于由3个1，5个0 组成的10100010。 反过来10100*010对应于10100101 。,2.10非线性递推关系举例-Catalan 数,因而不合要求的2n位数与n+1个0，n-1个1组成的排 列一一对应，故有,TP

62、 SHUAI,244,2.10非线性递推关系举例-Catalan 数,TP SHUAI,245,解法2.这个问题可以一一对应于图2-10-6 中从原点(0,0)到(n,n)点的路径要求中途所 经过的点(a,b)满足关系a=b 对应的办法是从 (0,0)出发，对2n位数从左 而右扫描，若遇到1便沿y轴正方向走一格； 若遇到0便沿x轴正方向走一格。由于有n个0， n个1，故对应一条从(0,0)点到达(n,n)点的路,2.10非线性递推关系举例-Catalan 数,TP SHUAI,246,径，由于要求1的累计数不少于0的累计数， 故可以途经对角线 OA上的点，但不允许穿越 过对角线。反过来，满足这

63、条件的路径对应 一满足要求的2n位2进制数。见图2-10-7 问题导致求从 (0,0)出发，途经对角线 及对角线上方的点到达(n,n)点的路径数。,2.10非线性递推关系举例-Catalan 数,TP SHUAI,247,2.10非线性递推关系举例-Catalan 数,TP SHUAI,248,从一点到另一点的路径数的讨论见第1章例.见 图2-10-6,从O点出发经过OA及 OA上方的点 到达A点的路径对应一条从O点出发经过OA及 OA上方的点到达A点的路径,这是显而易见的. 从O点出发途经OA上的点到达A 点的路 径,即为从O点出发穿越OA 的点到达A点的 路径，故对应一条从B点出发穿越OA

64、 到达A点 的路径。,2.10非线性递推关系举例-Catalan 数,TP SHUAI,249,所以从O点出发经过OA及OA以上的点最后到达A 点的路径数，等于从O点出发到达A点的所有路 径数，减去从O点出发路经 OA上的点到达A点 的路径数。即,2.10非线性递推关系举例-Catalan 数,TP SHUAI,250,2.10非线性递推关系举例-Catalan 数,TP SHUAI,251,例4. 由n个1，n个0组成的2n位二进制数，要求从左向右扫描前2n-1位时1的累计数大于0的累计数，求满足这样条件的数的个数。此问题可归结为图2-10-7中从o点出发只经过对角线OA上方的点抵达A点，求这样的路径数。相当于求从O(0,1)点不经过对角线OA，抵达A(n-1,n)点的路径数，于是便转换为例3的问题。,2.10非线性递推关系举例-Catalan 数,TP SHUAI,252,2.10非线性递推关系举例-Catalan数,由例3的结果,从O(0,1)点通过OA的点，以及 OA上方的点到达A(n-1,n) 的路径数为,