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

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

1、组合数学组合数学帅天平帅天平北京邮电大学数学系Email: 1TP SHUAI第二章:递推关系与母函数l1,递推关系引入，FibonacciFibonacci数列l2,常系数递推关系求解l3,母函数及其性质l4,用母函数求解递推关系l5,母函数的应用-整数剖分l6指数型母函数及其应用l7,非线性递推关系举例-几类特殊组合数2TP SHUAI2.1 2.1 递推关系递推关系- -引入引入1 1l利用递推关系进行计数的方法在算法分析中经常用到。D.H.Greene and D.E.Knuth, Mathematics for the analysis of algorithms Birkhause

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

3、 -引入引入3 3算法：算法：N=2时第一步先把最上面的一个圆盘套在B上z z第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完毕5TP SHUAI 对于一般n个圆盘的问题，l假定n-1个盘子的转移算法已经确定。 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上A B C 2.1 2.1 递推关系递推关系- -引入引入4 46TP SHUAI 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，

4、以此类推。 2.1 2.1 递推关系递推关系- -引入引入5 57TP SHUAI 算法分析：算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有 2.1 2.1 递推关系递推关系- -引入引入6 6算法复杂度为：利用递推关系(a)式也可以依次求得h(1), h(2) , h(3) ，这样的连锁反应关系，叫做递推关系递推关系。8TP SHUAI Fibonacci数列是递推关系的又一个典型问题，该数列的本身有着许多应用。问题

5、：问题：有雌雄兔子一对，假定过两月后每月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？ 设满n个月时兔子对数为 Fn其中当月新生兔数目设为Nn 对。第n-1个月留下的兔子数目设为 On 对。 2.1 2.1 递推关系递推关系- -FibonacciFibonacci数列数列1 19TP SHUAI 但即第n-2个月所产的兔子到第n个月都有繁殖能力了.由递推关系(1)式可依次得到 2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列2 210TP SHUAIl趣味结论趣味结论 2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列

6、7 711TP SHUAI 证明：证明： 2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列8 812TP SHUAI 证明：证明：2.1 2.1 递推关系递推关系- -Fibonacci- -Fibonacci数列数列9 913TP SHUAI 证明：证明： 2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列101014TP SHUAIl确定一个数列an的最常用的方法是l给出一般项an的表达式l得到该数列的母函数l建立数列所满足的递推关系递推关系即建立一种规则，即建立一种规则，使得通过这种规则数列的每一项可由其使得通过这种规则数列的

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

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

9、成如下四类:1)1着白色着白色,余下的是余下的是1(n-1)的棋盘的棋盘,它所满足条件的它所满足条件的着色方案数是着色方案数是an-1 ;2) 1着蓝色着蓝色,余下的是余下的是1(n-1)的棋盘的棋盘,它所满足条件的它所满足条件的着色方案数是着色方案数是 an-13) 1着红色着红色,2着蓝色着蓝色,余下的是余下的是1(n-2) 的棋盘的棋盘,它所满它所满足条件的着色方案数是足条件的着色方案数是an-2;4) 1着红色着红色,2着白色着白色,余下的是余下的是1(n-2) 的棋盘的棋盘,它所满它所满足条件的着色方案数是足条件的着色方案数是an-2.20TP SHUAI2.12.1递推关系递推关系

10、故总的着色方案数为故总的着色方案数为:21TP SHUAI2.2 2.2 母函数母函数- -引入引入1 1 母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著概率解析理论。两个色子掷出6点，有多少种选法？我们来看如下的例子我们来看如下的例子22TP SHUAI2.2 母函数-引入2我们也可以从另一角度来看，要使两个色子掷出6点，第一个色子除了6以外的都可选，这有5种选法，一旦第一个选定，第二个色子就只有一种可能的选法按乘法法则有5*1=5种注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，这些选法互斥且穷尽了出现

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

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

13、132TP SHUAI又如等式：令x=1 可得2.2 母函数-引入1233TP SHUAI(2-1-2)式等号的两端对x求导可得：等式(2-1-5)两端令x =1，得：2.2 母函数-引入1334TP SHUAI2.2 2.2 母函数母函数- -引入1414 用类似的方法还可以得到：等式两端对x求导再令x =1，得：35TP SHUAI2.2 2.2 母函数母函数- -引入1515已可见函数还可以类似地推出一些等式，但通过上面一些例子的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：在研究序列称函数G(x)是序列的母函数母函数定义定义1 1：对于序列构造一函数36TP SHU

14、AI2.2 2.2 母函数母函数- -引入1616 如若已知序列 则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。 序列可记为37TP SHUAI利用母函数求解Fibonacci数列（Fn=Fn-1+Fn-2， F1=F2=1）：设 2.2 2.2 母函数母函数- -引入1738TP SHUAI 2.2 2.2 母函数母函数- -引入1839TP SHUAI 2.2 2.2 母函数母函数- -引入1940TP SHUAI其中 2.2 2.2 母函数母函数- -引入2041TP SHUAI42几个基本的母函数几个基本的母函数42TP SHUAI4

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

16、质母函数的性质2 245TP SHUAI性质性质1:证证:若则2.32.3母函数的性质母函数的性质3 346TP SHUAI 性质性质2:则若2.32.3母函数的性质母函数的性质4 447TP SHUAI证：证：2.32.3母函数的性质母函数的性质5 548TP SHUAI性质性质3：若则2.32.3母函数的性质母函数的性质6 649TP SHUAI ): : : :1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab2.32.3母函数的性质母函数的性质7 7证：证：50TP SHUAI 例例. 已知2.32.3母函数的性质母函数的

17、性质8 851TP SHUAI类似可得：2.32.3母函数的性质母函数的性质9 952TP SHUAI性质4则2.32.3母函数的性质母函数的性质101053TP SHUAI证2.32.3母函数的性质母函数的性质111154TP SHUAI2.32.3母函数的性质母函数的性质121255TP SHUAI 例例则性质性质5 5若则2.32.3母函数的性质母函数的性质131356TP SHUAI性质5和性质6的结论是显而易见的。 性质性质6 6若则2.32.3母函数的性质母函数的性质141457TP SHUAI性质性质7 7若则2.32.3母函数的性质母函数的性质151558TP SHUAI证证:

18、2.32.3母函数的性质母函数的性质161659TP SHUAI已知例例1. 则2.32.3母函数的性质母函数的性质171760TP SHUAI2.4 2.4 母函数求解线性常系数递推关系母函数求解线性常系数递推关系1 1以二阶齐次线性常系数递推关系为例则可计算如下61TP SHUAI2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系2 262TP SHUAI2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系3 363TP SHUAI2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系4 464TP SHUAI2.4 2.4 母函数解线性常系

19、数递推关系母函数解线性常系数递推关系5 565TP SHUAI2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系6 6证明:(1) r1，r2为两相异的实根.66TP SHUAI2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系7 767TP SHUAI2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系8 8故68TP SHUAI2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系9 969TP SHUAI2.4 2.4 母函数求解线性常系数递推关系母函数求解线性常系数递推关系101070TP SHUAI2.42.4母函数求

20、解线性常系数递推关系母函数求解线性常系数递推关系111171TP SHUAI2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系121272TP SHUAI例例4 4：求下列n阶行列式dn 的值.2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系131373TP SHUAI根据行列式性质对应的特征方程为故m=1是二重根2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系141474TP SHUAI即时有时有2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系151575TP SHUAI2.42.4母函数解线性常系数递推关系母函数

21、解线性常系数递推关系1616 考虑如下k阶常系数线性齐次递推关系: 数列an满足上面母函数的方法可以推广到解一般的常系数线性递推关系76TP SHUAI设an 的母函数G(x)为根据(2-4-1)，有2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系171777TP SHUAI将这些式子两边分别相加，得到即其中2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系181878TP SHUAI多项式的次数不大于k-1特征多项式令,2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系191979TP SHUAI因此,是k次多项式。2.42.4母函数解线性常系数递

22、推关系母函数解线性常系数递推关系2020C(x)=0 在复数域中有k个根，故设80TP SHUAI则 于是2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系212181TP SHUAI(2-5-3)式是有理式,且分子的次数低于分母的次数, 有分项表示，即2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系222282TP SHUAI定理定理2.4.2：设 P(x)/Q(x)是有理分式，多项式P(x)的次数低于Q(x) 的次数。则它有分项表示，且表示唯一.2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系232383TP SHUAI证明：证明：设 Q(x)

23、 的次数为n，对n用数学归纳法 n=1时，P(x) 是常数，命题成立。假设对小于n的正整数，命题成立。下面证明对正整数n命题成立.设是Q(x)的k重根，2.42.4母函数解线性常母函数解线性常系数系数递推关系递推关系242484TP SHUAI不妨设P(x)与Q(x)互素，设2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系252585TP SHUAIP(x) 的次数低于Q(x)。根据归纳假设，可分项表示。因此，可分项表示。由前几式可知表示是唯一的.2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系181886TP SHUAI以下分别各种情况讨论具体计算的问题。设(

24、2-4-4)可简化为C(x)（1）特征多项式C(x)无重根2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系191987TP SHUAI可由线性方程组解出.2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系202088TP SHUAI上式的系数矩阵的行列式是范德蒙行列式不难看出它有唯一解。2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系212189TP SHUAI（2）特征多项式C(x)有共轭复根的系数是中设1,2是C(x)的一对共轭复根。2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系222290TP SHUAI 其中2.42.4母

25、函数解线性常系数递推关系母函数解线性常系数递推关系232391TP SHUAI在具体计算时,可先求出各对共轭复根，再求待定系数A、B,避免中间过程的复数运算.（3）特征多项式C(x)有重根设是C(x)的k重根，则(2-4-4)可简化为2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系242492TP SHUAI因此，an是 与n的k-1次多项式的乘积。的系数其中是n的j-1次多项式。2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系252593TP SHUAI2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2626总之，我们有如下定理94TP SHU

26、AI2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系272795TP SHUAI 例例5 5：求同理相减得2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系282896TP SHUAI同理12321=+nnnSSS210 3 , 1 , 0 033 321=+SSSSSSSnnnn对应的特征方程为0) 1(133323=+mmmm2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系292997TP SHUAIm=1是三重根22) 1)( CnBnACnBnASnn+=+=0 , 00=AS1 , 11=+=CBS1/2 , 342 , 32=+=CBC

27、BS即) 1(2121212+=+=nnnnSn) 1(21321+=+nnnL这就证明了2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系303098TP SHUAI例例6 6：求L22212222) 1(321 ) 1(321 +=+=nSnnSnnL21 nSSnn=同理221) 1( =nSSnn相减得12221=+nSSSnnn2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系313199TP SHUAI同理对应的特征方程为相减得同理2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3232100TP SHUAIr=1是四重根依据 得关于A、

28、B、C、D的连立方程组：2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3333101TP SHUAI于是2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3434102TP SHUAI已知Sn是n的3次式，故不妨令确定待定系数时，比较方便，无需解一联立方程组。例如 2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3535103TP SHUAI2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3636104TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系1常系数线性非齐次递推关系的一般形式如下结论证明:只要把它

29、代入(1)式的左端验证即可.齐次递推关系较易求解,故问题的关键是求特解求特解.下面我们考虑如何求特解,一般来说,没有普遍的解法.在某些简单的情形可以用待定系数法求之.先看一个例子.105TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系2106TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系3107TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系4108TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系5109TP SHUAI 我们很直观的看出上式解不出p1 和 p2.这是因为当原递推关系的特征根是1时

30、.如果所设的特解中n的最高次幂的次数与f(n)的次数一样时,代入原递推关系后,等式左边的n的最高次幂就会消去.因此等式左边的多项式比右边的多项式的次数低.为此 在设特解时要将在设特解时要将n n的最高次幂提高的最高次幂提高, ,并且可以不并且可以不设常数项设常数项2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系6110TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系7111TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系8112TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系9113TP SHUAI2.5 线性常系

31、数非齐次递推关系线性常系数非齐次递推关系10114TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系11115TP SHUAI综上所述,我们可得如下定理2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系12116TP SHUAI特解特解2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系13117TP SHUAI2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系14118TP SHUAI 所谓正整数拆分即把正整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总

32、数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。记p(n,k)为把n拆分成恰好k个正整数的和的拆分数。2.6 2.6 整数的拆分整数的拆分-问题描述问题描述119TP SHUAI2.6 2.6 整数的拆分整数的拆分-问题举例问题举例例例1 1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？120TP SHUAI同样，故称出6克的方案有2，称出10克的方案有12.6 2.6 整数的拆分整数的拆分-问题举例问题举例从右端的母函数知可称出从1克到10克,系数便是方案数。例如右端有 项, 即称出5克的方案有2121TP SHUAI例例2 2

33、：求用1分、2分、3分的邮票贴出不同数值的方案数。解:因邮票允许重复，故母函数为2.6 2.6 整数的拆分整数的拆分-问题举例问题举例 以其中x 为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即4122TP SHUAI例例3 3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚的砝码各一枚，问能称出那几种重量？各有几种方案？2.6 2.6 整数的拆分整数的拆分-问题举例问题举例解:作母函数123TP SHUAI2.6 2.6 整数的拆分整数的拆分-问题举例问题举例124TP SHUAI2.6 2.6 整数的拆分整数的拆分-问题举例问题举例125TP SHUAI2.6 2.6 整数的拆分整

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

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

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

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

38、问能称出那几种重量？有几种可能方案？2.6 2.6 整数的拆分整数的拆分-问题举例问题举例136TP SHUAI从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数n,可表示为而且是唯一的。2.6 2.6 整数的拆分整数的拆分-问题举例问题举例137TP SHUAI2.7 2.7 FerrersFerrers图像图像图 2-7-1一个从上而下的n层格子，m 为第i层的格子数，当 ,即上层的格子数不少于下层的格子数时,称之为Ferrers图像,如图(2-7-1)示.i138TP SHUAIFerrers图像具有如下性质： 1.每一层至少有

39、一个格子。 2.第一行与第一列互换，第二行于第二列互换， 即图(2-7-1)绕虚线轴旋转所得的图仍然是Ferrers图像.2.7 2.7 FerrersFerrers图像图像两个Ferrers 图像称为一对共轭的Ferrers图像。 利用Ferrers图像可得关于整数拆分的十分有趣的结果.(a)整数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的拆分数相等。因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如： 139TP SHUAI 24=6+6+5+4+3 5个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为5图

40、(2-7-2)2.7 2.7 FerrersFerrers图像图像140TP SHUAI (c)整数n拆分成互不相同的若干奇数的和的的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等.构造一个Ferrers图像，其第一行，第一列都是 格，对应于 ，第二行，第二列各 格,对应于 . 以此类推.由此得到的Ferres图像是共轭的.反过来也一样。2.7 2.7 FerrersFerrers图像图像，。设其中 (b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。141TP SHUAI例如对应为Ferrers图像为9+5+3=172.7 2.7 FerrersFe

41、rrers图像图像图(2-7-3)利用Ferrers图像可以证明定理定理 4 正整数N剖分成不超过k个数的和的剖分数等于将N+k剖分成恰好k个数的剖分数142TP SHUAI876543232543232232369109631 )1 ( )23321 ( )1)(1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxG+=+=+=2.8 2.8 指数型母函数指数型母函数-问题提出问题提出143TP SHUAI 从x4的系数可知,这8个元素中取4个组合，其组合数为10.这10个组合可从下面展开式中得到2.8 2.8 指数型母函数指数型母函数-解的分析解的分析144TP SHUAI

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

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

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

45、举例举例156TP SHUAI2.8 2.8 指数型母函数指数型母函数-举例举例157TP SHUAI2.8 2.8 指数型母函数指数型母函数-举例举例158TP SHUAI2.8 2.8 指数型母函数指数型母函数-举例举例159TP SHUAI2.8 2.8 指数型母函数指数型母函数-举例举例160TP SHUAI例例3 3：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现； 2出现次数不超过1次； 3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。2.8 2.8 指数型母函数指数型母函数-举例举例解:设满足上述条件的r位数为ar序

46、列a1,a2,a10的指数型母函数为161TP SHUAI由此可见满足条件的5位数共215个。2.8 2.8 指数型母函数指数型母函数-举例举例162TP SHUAI例例4: 求1，3，5，7，9五个数字组成的n 位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。2.8 2.8 指数型母函数指数型母函数-举例举例对应的指数型母函数为解:设满足条件的 n 位的个数为an ,则序列163TP SHUAI由于2.8 2.8 指数型母函数指数型母函数-举例举例164TP SHUAI2.8 2.8 指数型母函数指数型母函数-举例举例165TP SHUAI166 例5 用红绿蓝三

47、种颜色去涂1n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。 2.8 指数型母函数指数型母函数-举例举例166TP SHUAI167 递推关系解法的补充递推关系解法的补充1、母函数法、母函数法2、迭代法、迭代法3、归纳法、归纳法4、置换法、置换法5、相加消去法、相加消去法167TP SHUAI168例例1 1：求下列递推关系的解：求下列递推关系的解解：用置换法：解：用置换法：解特征方程可得：解特征方程可得：递推关系解法的补充递推关系解法的补充168TP SHUAI169递推关系解法的补充递推关系解法的补充169TP SHUAI170递推关系解法的补充递推关系解法的补充1

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

49、推关系举例非线性递推关系举例- -多项式系数多项式系数173TP SHUAI 从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 2.9 非线性递推关系举例非线性递推关系举例- -多项式系数多项式系数174TP SHUAI依此类推，根据乘法法则可得2.9 2.9 非线性递推关系举例非线性递推关系举例- -多项式系数多项式系数175TP SHU

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

51、因子项中取xj对应于把第i个有标志的球放到第j个盒子。（2-9-2）式展开的一般项表示第一个盒子有n1个球，第二个盒子有n2个球，等等。因此 项的系数应为2.9 2.9 非线性递推关系举例非线性递推关系举例- -多项式系数多项式系数178TP SHUAI即定理定理3：展开式的项数等于而且这些系数之和等于2.9 2.9 非线性递推关系举例非线性递推关系举例- -多项式系数多项式系数179TP SHUAI 和从m个元素 中取n个作允许重 复的组合一一对应。故得 展开式的项数等于 证明：证明：展开式中的项2.92.9非线性递推关系举例非线性递推关系举例- -多项式系数多项式系数180TP SHUAI

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

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

54、颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种:其中r表红球,y表黄球,b表蓝球,w表白球,2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数186TP SHUAI由定义，我们有s(n,k)=S(n,k)=0,若kn s(0,0)=S(0,0)=1 定理定理4: 第二类第二类Stirling数数S(n,k)有下列性质有下列性质:2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数187TP SHUAI(c)设有n个不相同的球b1,b2,bn从中取出球 b1,其余的n-1个球,每个都有与b1同盒,或不与b1同

55、盒两种选择.但必须排除一种情况,即全体与b1同盒,因这时另一盒将是空盒.故实际上只有2n-11种方案,即证明:公式(a) (b) (e)显然,只证(c)(d).2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数188TP SHUAI (d) n个球放到n-1个盒子里,不允许有一空盒,故 必有一盒有两个球,从n个有区别的球中取2个, 共有C(n,2)种组合方案.定理定理5 5: 第二类Stirling数满足下面的递推关系.2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数189TP SHUAI证明证明: 设有n个有区别的球b

56、1,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 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数190TP SHUAI上面证明递推公式(10-6)的过程，也就是给出构造所有方案的办法。例如今将红、黄、蓝、白、绿五个球放到无区别的两个盒子里。先把绿球取

57、走，余下的四个球放到两个盒子的方案已见前面的例子。和前面一样用r，y，b，w分别表示红,黄,蓝,白球;绿球用g表示.可得表 A故共有15种不同的方案。2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数191TP SHUAI表表 A2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数192TP SHUAI n个球放到m个盒子里,依球和盒子是否有区别,是否允许空盒？共有 8种状态.其方案计数分别列于下. n个球有区别，m个盒子有区别，有空盒时方案计数为mn n个球有区别，m个盒子有区别，无空盒时方案计数为 n个球有区别，m个盒子

58、无区别，有空盒时方案计数为2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数193TP SHUAI n个球有区别，m个盒子无区别，无空盒时方案计数为S(n,n) n个球无区别，m个盒子有区别，有空盒时方案计数为C(n+m-1,n) n个球无区别，m个盒子有区别，无空盒时方案计数为2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数194TP SHUAI n个球无区别，m个盒子无区别，有空盒时方案计数为 的项系数。 n个球无区别，m个盒子无区别，无空盒时方案计数为 的项系数。2.10 2.10 非线性递推关系举例非线性递推关系

59、举例- -Stirling系数系数195TP SHUAI2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数 n个球个球 k个盒个盒 f无限制无限制 f 单 f 满全不同全不同1) kn2) (k)n3) k!S(n,k)全同全不同4）c(n+k-1,n)5) C(k,n)6)C(n-1,k-1)全不同全同7）i=1kS(n,i)8）1 (nk)0 (nk)9） S(n,k)全同全同10) i=1kp(n,i)=p(n+k,k)11) 同8）12） p(n,k)196TP SHUAI还可以如Pascal三角形一样得到下表。利用2.10 2.10 非线性递推关系

60、举例非线性递推关系举例- -Stirling系数系数197TP SHUAIS(i,j+1)S(i,j)S(i+1,j+1)j+12.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数198TP SHUAIs(i,j+1)s(i,j)S(i+1,j+1)-i2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数199TP SHUAIl第二类Stirling数的显式表示2.10 2.10 非线性递推关系举例非线性递推关系举例- -Stirling系数系数200TP SHUAIl第一类Stirling数的显式表示2.10 2.10 非线

61、性递推关系举例非线性递推关系举例- -Stirling系数系数201TP SHUAI2.102.10非线性递推关系举例-错排问题错排问题 Df1: n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排,有的叫重排。以1，2，3，4四个数的错排为例，分析其结构，找出规律性的东西来。1 2的错排是唯一的，即2 1。202TP SHUAI即1 2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1，2换位而得的.2.102.10非线性递推关系举例-错排问题错排问题1 2 3 4的错排有4 3 2 1，4 1 2 3，4 3 1 2，

62、3 4 1 2，3 4 2 1，2 4 1 3，2 1 4 3，3 1 4 2，2 3 4 1。203TP SHUAI4 3 2 1，3 4 1 2，2 1 4 3。 第一列是4分别与1，2，3互换位置,其余两个元素错排.由此生成的。2.102.10非线性递推关系举例- 错排问题错排问题第2列是4分别与3，1，2（123的一个错排）的每一个数互换而得到的。即204TP SHUAI2.102.10非线性递推关系举例-错排问题错排问题 第三列则是由另一个错排231和4换位而得到,即上面的分析结果，实际上是给出一种产生错排的结果。205TP SHUAI 设n个数1，2，n错排的数目为Dn,任取其中一

63、数i,数i分别与其他的n-1个数之一互换，其余n-2个数进行错排，共得(n-1)Dn-2个错排。另一部分为数i以外的n-1个数进行错排，然后i与其中每个数互换，得 (n-1)Dn-1个错排。2.102.10非线性递推关系举例-错排问题错排问题综合以上分析结果得递推关系Dn=(n-1)(Dn-1+Dn-2)， D1=0,D2=1 (2-10-3)它是一个非常系数的递推关系.206TP SHUAI由于D1=0,D0=1故得关于Dn的递推关系2.102.10非线性递推关系举例-错排问题错排问题一种解法:207TP SHUAI令2.102.10非线性递推关系举例-错排问题错排问题208TP SHUAI

64、2.102.10非线性递推关系举例-错排问题错排问题209TP SHUAI2.10非线性递推关系举例-Catalan 数 Catalan数的递推关系是非线性的,许多有意义的计数问题都导致这样的递推关系.定义1： 一个凸n边形,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同拆分的数目用hn表之，称为Catalan数.图 2-10-1hn=5210TP SHUAI1.1.递推关系递推关系定理定理1 1：2.10非线性递推关系举例- Catalan 数211TP SHUAI以 v1vn+1 作为一个边的三角形v1vkvn+1 ，将凸n+1边形分割成两部分，一部分是k边形,一部分是n-

65、k+2边形，k=2,3,n.即vk点可以是v2,v3,vn 点中任意一点图 2-10-2证明证明 (a)的证明：如图 所示，2.10非线性递推关系举例-Catalan 数212TP SHUAI2.10非线性递推关系举例-Catalan 数依据加法法则有213TP SHUAI 从 v1点向其它n-3 个顶点v3,v4,vn-1 可引出n-3 条对角线。对角线v1vk把 n边形分割成两个部分，因此图 2-10-3(b)的证明：如图所示2.10非线性递推关系举例-Catalan 数214TP SHUAI以v2,v3,vn 取代v1 点也有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别

66、计算了一次，以v1vk对角线作为拆分线的方案数为hkhn-k+2,vk可以是v3,v4,vn-1 中任一点，对所有这些点求和得2.10非线性递推关系举例-Catalan 数作215TP SHUAI(2-10-7) 式并不给出剖分数，无疑其中是有重复的。其重复度是由于一个凸n边形的剖分有n-3 条对角线，而对其每一条边计数时该剖分都计数了一次，故重复了n-3次，即该式给出的结果是hn的n-3倍。2.10非线性递推关系举例-Catalan 数(2-10-5)式和(2-10-6)式都是非线性递推关系.216TP SHUAI由(2-10-5)式及h2=1,故得2.Catalan 2.Catalan 数

67、计算公式数计算公式2.10非线性递推关系举例-Catalan 数217TP SHUAI由整理得令2.10非线性递推关系举例-Catalan 数218TP SHUAI即2.10非线性递推关系举例-Catalan 数219TP SHUAI2.10非线性递推关系举例-Catalan 数220TP SHUAI设3.3.母函数方法母函数方法2.10非线性递推关系举例-Catalan 数221TP SHUAI2.10非线性递推关系举例-Catalan 数222TP SHUAI由二项式定理2.10非线性递推关系举例-Catalan 数后面将看到只有取才有意义.223TP SHUAI2.10非线性递推关系举例

68、-Catalan 数中项的系数为即224TP SHUAI2.10非线性递推关系举例-Catalan 数225TP SHUAI的系数为正xxxG2411)( =且得2.10非线性递推关系举例-Catalan 数226TP SHUAI同样可推出 令 从递推关系4.微分法2.10非线性递推关系举例-Catalan 数227TP SHUAI2.10非线性递推关系举例-Catalan 数228TP SHUAI2.10非线性递推关系举例-Catalan 数229TP SHUAI即2.10非线性递推关系举例-Catalan 数230TP SHUAI5.5.举例举例2.10非线性递推关系举例-Catalan

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

70、如图(2-10-5)2.10非线性递推关系举例-Catalan 数235TP SHUAIab运算用二分树表示，两片叶子分别表乘数和被乘数，分支点为运算符，如图图 2-10-52.10非线性递推关系举例-Catalan 数236TP SHUAI2.10非线性递推关系举例-Catalan 数237TP SHUAI2.10非线性递推关系举例-Catalan 数238TP SHUAI2.10非线性递推关系举例-Catalan 数239TP SHUAI例例3.3. n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？ 解法解法1. 设p2n为这样

71、所得的数的个数。在2n 位上填入n个1的方案数为C(2n,n) ，不填1的其余n位自动填以数0,从C(2n,n)中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。2.10非线性递推关系举例-Catalan 数240TP SHUAI 不合要求的数的特征是从左而右扫描时，必然在某一奇数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位数，即一个不

72、合要求的数对应于一个由 n-1个0和n+1个1组成的一个排列。2.10非线性递推关系举例-Catalan 数241TP SHUAI 反过来，任何一个由 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位数，必对应于一个不合要求的数。2.10非线性递推关系举例-Catalan 数上述方法建立了由 n+1个0和n-1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应

73、。242TP SHUAI例如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组成的排列一一对应，故有243TP SHUAI2.10非线性递推关系举例-Catalan 数244TP SHUAI解法解法2.这个问题可以一一对应于图2-10-6中从原点(0,0)到(n,n)点的路径要求中途所经过的点(a,b)满足关系a=b 对应的办法是从

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

75、递推关系举例-Catalan 数247TP SHUAI 从一点到另一点的路径数的讨论见第1章例.见图2-10-6,从O点出发经过OA及 OA上方的点到达A点的路径对应一条从O点出发经过OA及OA上方的点到达A点的路径,这是显而易见的. 从O点出发途经OA上的点到达A 点的路径,即为从O点出发穿越OA 的点到达A点的路径，故对应一条从B点出发穿越OA 到达A点的路径。2.10非线性递推关系举例-Catalan 数248TP SHUAI所以从O点出发经过OA及OA以上的点最后到达A点的路径数，等于从O点出发到达A点的所有路径数，减去从O点出发路经 OA上的点到达A点的路径数。即2.10非线性递推关

76、系举例-Catalan 数249TP SHUAI2.10非线性递推关系举例-Catalan 数250TP SHUAI例例4. 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 数251TP SHUAI2.10非线性递推关系举例-Catalan数由例3的结果,从O(0,1)点通过OA的点，以及OA上方的点到达A(n-1,n) 的路径数为252TP SHUAI