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

《组合2母函数递推关系.ppt》由会员分享，可在线阅读，更多相关《组合2母函数递推关系.ppt（252页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学组合数学帅天平帅天平北京邮电大学数学系Email:第二章:递推关系与母函数l1,递推关系引入，FibonacciFibonacci数列l2,常系数递推关系求解l3,母函数及其性质l4,用母函数求解递推关系l5,母函数的应用-整数剖分l6指数型母函数及其应用l7,非线性递推关系举例-几类特殊组合数2.1 2.1 递推关系递推关系-引入引入1 1l利用递推关系进行计数的方法在算法分析中经常用到。and,Mathematics for the analysis of algorithms Birkhauser,Boston 1st,1981;3rd,1999.中对递推关系及其应用有更广泛的叙

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

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

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

5、onacciFibonacci数列数列1 1 但即第n-2个月所产的兔子到第n个月都有繁殖能力了.由递推关系(1)式可依次得到 2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列2 2l趣味结论趣味结论 2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列7 7 证明：证明：2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列8 8 证明：证明：2.1 2.1 递推关系递推关系-Fibonacci-Fibonacci数列数列9 9 证明：证明：2.1 2.1 递推关系递推关系-Fibonacci-Fibona

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

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

8、 3 n-1 n 2.12.1递推关系递推关系在该棋盘上着色在该棋盘上着色,其方案可分成如下四类其方案可分成如下四类: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)的棋盘的棋盘,它所满它所满足条

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

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

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

12、函数母函数-引入1414 用类似的方法还可以得到：等式两端对x求导再令x=1，得：2.2 2.2 母函数母函数-引入1515已可见函数还可以类似地推出一些等式，但通过上面一些例子的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：在研究序列称函数G(x)是序列的母函数母函数定义定义1 1：对于序列构造一函数2.2 2.2 母函数母函数-引入1616 如若已知序列 则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。序列可记为利用母函数求解Fibonacci数列（Fn=Fn-1+Fn-2，F1=F2=1）：设 2.2 2.2 母函数母

13、函数-引入17 2.2 2.2 母函数母函数-引入18 2.2 2.2 母函数母函数-引入19其中 2.2 2.2 母函数母函数-引入2042几个基本的母函数几个基本的母函数43几个基本的母函数几个基本的母函数2.32.3母函数的性质母函数的性质1 1 一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，特别酷似离散序列的Z变换。如前的例子所示的那样，为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。最后求逆变换，即从已求得的母函数G(x)得到序列an。

14、关键在于要搭起从序列到母函数，从母函数到序列这两座桥。这一节便是以此为目的的。不特别说明,下面假设、为两个序列2.32.3母函数的性质母函数的性质2 2性质性质1:证证:若则2.32.3母函数的性质母函数的性质3 3 性质性质2:则若2.32.3母函数的性质母函数的性质4 4证：证：2.32.3母函数的性质母函数的性质5 5性质性质3：若则2.32.3母函数的性质母函数的性质6 6 ):1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab2.32.3母函数的性质母函数的性质7 7证：证：例例.已知2.32.3母函数的性质母函数的性质

15、8 8类似可得：2.32.3母函数的性质母函数的性质9 9性质4则2.32.3母函数的性质母函数的性质1010证2.32.3母函数的性质母函数的性质11112.32.3母函数的性质母函数的性质1212 例例则性质性质5 5若则2.32.3母函数的性质母函数的性质1313性质5和性质6的结论是显而易见的。性质性质6 6若则2.32.3母函数的性质母函数的性质1414性质性质7 7若则2.32.3母函数的性质母函数的性质1515证证:2.32.3母函数的性质母函数的性质1616已知例例1.则2.32.3母函数的性质母函数的性质17172.4 2.4 母函数求解线性常系数递推关系母函数求解线性常系数

16、递推关系1 1以二阶齐次线性常系数递推关系为例则可计算如下2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系2 22.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系3 32.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系4 42.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系5 52.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系6 6证明:(1)r1，r2为两相异的实根.2.4 2.4 母函数解线性常系数递推关系母函数解线性常系数递推关系7 72.4 2.4 母函数解线性常系数递推关系母函数解线性常系数

17、递推关系8 8故2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系9 92.4 2.4 母函数求解线性常系数递推关系母函数求解线性常系数递推关系10102.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系11112.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系1212例例4 4：求下列n阶行列式dn 的值.2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系1313根据行列式性质对应的特征方程为故m=1是二重根2.42.4母函数求解线性常系数递推关系母函数求解线性常系数递推关系1414即时有时有2.42.4母函数求解线性常系

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

19、常系数递推关系母函数解线性常系数递推关系2020C(x)=0 在复数域中有k个根，故设则 于是2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2121(2-5-3)式是有理式,且分子的次数低于分母的次数,有分项表示，即2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2222定理：定理：设 P(x)/Q(x)是有理分式，多项式P(x)的次数低于Q(x)的次数。则它有分项表示，且表示唯一.2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2323证明：证明：设 Q(x)的次数为n，对n用数学归纳法 n=1时，P(x)是常数，命题成立。假设对小于n的正整

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

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

22、数解线性常系数递推关系母函数解线性常系数递推关系2424因此，an是 与n的k-1次多项式的乘积。的系数其中是n的j-1次多项式。2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系25252.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2626总之，我们有如下定理2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2727 例例5 5：求同理相减得2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2828同理12321=+nnnSSS210 3 ,1 ,0 033 321=+SSSSSSSnnnn对应的特征方程为0)1(133323=+m

23、mmm2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系2929m=1是三重根22)1)(CnBnACnBnASnn+=+=0 ,00=AS1 ,11=+=CBS1/2 ,342 ,32=+=CBCBS即)1(2121212+=+=nnnnSn)1(21321+=+nnnL这就证明了2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3030例例6 6：求L22212222)1(321 )1(321 +=+=nSnnSnnL21 nSSnn=同理221)1(=nSSnn相减得12221=+nSSSnnn2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3

24、131同理对应的特征方程为相减得同理2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3232r=1是四重根依据 得关于A、B、C、D的连立方程组：2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3333于是2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系3434已知Sn是n的3次式，故不妨令确定待定系数时，比较方便，无需解一联立方程组。例如 2.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系35352.42.4母函数解线性常系数递推关系母函数解线性常系数递推关系36362.5 线性常系数非齐次递推关系线性常系数非齐次递推关系1常系数

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

26、代入原递推关系后,等式左边的n的最高次幂就会消去.因此等式左边的多项式比右边的多项式的次数低.为此 在设特解时要将在设特解时要将n n的最高次幂提高的最高次幂提高,并且可以不并且可以不设常数项设常数项2.5 线性常系数非齐次递推关系线性常系数非齐次递推关系62.5 线性常系数非齐次递推关系线性常系数非齐次递推关系72.5 线性常系数非齐次递推关系线性常系数非齐次递推关系82.5 线性常系数非齐次递推关系线性常系数非齐次递推关系92.5 线性常系数非齐次递推关系线性常系数非齐次递推关系102.5 线性常系数非齐次递推关系线性常系数非齐次递推关系11综上所述,我们可得如下定理2.5 线性常系数非齐

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

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

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

30、例 8 对N进行无序剖分,使得剖分后的整数各不相等,求这种剖分方案数Pd(N)的生成函数Gd(y)解：这相当于把N剖分成1,2,3,.,n,且不允许重复，类似于(b)式，有例 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)式，其母函数为：若拆分中m至少出现一次，其母函数则为：2

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

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

33、6 整数的拆分整数的拆分-问题举例问题举例从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数n,可表示为而且是唯一的。2.6 2.6 整数的拆分整数的拆分-问题举例问题举例2.7 Ferrers2.7 Ferrers图像图像图 2-7-1一个从上而下的n层格子，m 为第i层的格子数，当 ,即上层的格子数不少于下层的格子数时,称之为Ferrers图像,如图(2-7-1)示.iFerrers图像具有如下性质：1.每一层至少有一个格子。2.第一行与第一列互换，第二行于第二列互换，即图(2-7-1)绕虚线轴旋转所得的图仍然是Ferrers图像

34、.2.7 Ferrers2.7 Ferrers图像图像两个Ferrers 图像称为一对共轭的Ferrers图像。利用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 Ferrers2.7 Ferrers图像图像(c)整数n拆分成互不相同的若干奇数的和的的拆分数,和n拆分成自共轭的Ferrer

35、s图像的拆分数相等.构造一个Ferrers图像，其第一行，第一列都是 格，对应于 ，第二行，第二列各 格,对应于 .以此类推.由此得到的Ferres图像是共轭的.反过来也一样。2.7 Ferrers2.7 Ferrers图像图像，。设其中(b)整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。例如对应为Ferrers图像为9+5+3=172.7 Ferrers2.7 Ferrers图像图像图(2-7-3)利用Ferrers图像可以证明定理定理 4 正整数N剖分成不超过k个数的和的剖分数等于将N+k剖分成恰好k个数的剖分数87654323254323223236910

36、9631)1()23321()1)(1)(1()(xxxxxxxxxxxxxxxxxxxxxxxxxG+=+=+=2.8 2.8 指数型母函数指数型母函数-问题提出问题提出 从x4的系数可知,这8个元素中取4个组合，其组合数为10.这10个组合可从下面展开式中得到2.8 2.8 指数型母函数指数型母函数-解的分析解的分析 2.8 2.8 指数型母函数指数型母函数-解的分析解的分析其中4次方项有(2-8-1)表达了从8个元素(a1,a3各3个,a2 2个)中取4个的组合。例如 为一个 ，3个 的组合，为两个 ，两个 的组合，以此类推。2.8 2.8 指数型母函数指数型母函数-解的分析解的分析六种

37、。同样,1个 a1 3个 a3 的不同排列数为 2.8 2.8 指数型母函数指数型母函数-解的分析解的分析即若研究从中取4个的不同排列总数,以x12x32对应的两个不同排列为例,其不同排列数为以此类推。故从(2-8-1)式可得问题的解，其不同的排列数为2.8 2.8 指数型母函数指数型母函数-解的分析解的分析即 为便于计算,利用上述特点,形式地引进函数2.8 2.8 指数型母函数指数型母函数解的分析解的分析 2.8 2.8 指数型母函数指数型母函数-解的分析解的分析 从(2-8-2)式计算结果可以得出：取一个的排列数为3，取两个的排列数为29/2=9 取3个的排列数为 3!14/3=28，取4

38、个的排列数为 4!35/12=70，如此等等。把(2-8-2)式改写成下面形式便一目了然了。2.8 2.8 指数型母函数指数型母函数-解的分析解的分析称为是序列 的指数型母函数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 2.8 指数

39、型母函数指数型母函数-分析分析2.8 2.8 指数型母函数指数型母函数-举例举例2.8 2.8 指数型母函数指数型母函数-举例举例2.8 2.8 指数型母函数指数型母函数-举例举例2.8 2.8 指数型母函数指数型母函数-举例举例2.8 2.8 指数型母函数指数型母函数-举例举例例例3 3：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。2.8 2.8 指数型母函数指数型母函数-举例举例解:设满足上述条件的r位数为ar序列a1,a2,a10的指数型母函数为由此可

40、见满足条件的5位数共215个。2.8 2.8 指数型母函数指数型母函数-举例举例例例4:求1，3，5，7，9五个数字组成的n 位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。2.8 2.8 指数型母函数指数型母函数-举例举例对应的指数型母函数为解:设满足条件的 n 位的个数为an,则序列由于2.8 2.8 指数型母函数指数型母函数-举例举例2.8 2.8 指数型母函数指数型母函数-举例举例166 例5 用红绿蓝三种颜色去涂1n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。2.8 指数型母函数指数型母函数-举例举例167 递推关系解法的补充递推

41、关系解法的补充1、母函数法、母函数法2、迭代法、迭代法3、归纳法、归纳法4、置换法、置换法5、相加消去法、相加消去法168例例1 1：求下列递推关系的解：求下列递推关系的解解：用置换法：解：用置换法：解特征方程可得：解特征方程可得：递推关系解法的补充递推关系解法的补充169递推关系解法的补充递推关系解法的补充170递推关系解法的补充递推关系解法的补充171例例2 2：求下列递推关系的解：求下列递推关系的解解：用置换法：解：用置换法：令令递推关系解法的补充递推关系解法的补充2.9 2.9 非线性递推关系举例非线性递推关系举例-多项式系数多项式系数n个有区别有区别的球放到两个有区别有区别的盒子里.

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

43、1-n2,n3).计算如下2.9 2.9 非线性递推关系举例非线性递推关系举例-多项式系数多项式系数依此类推，根据乘法法则可得2.9 2.9 非线性递推关系举例非线性递推关系举例-多项式系数多项式系数 n个有区别的球，放到m个有标志的盒子的问题，也可以考虑把n个有区别的球进行全排列。对于每一个排列依次取n1个放到第1个盒子里，取n2个放到第2个盒子里,最后nm个放到第m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为结果和前式一致。2.9 2.9 非线性递推关系举例非线性递推关系举例-多项式系数多项式系数n项中,每项各取一个元素相乘而得到的.的展开式是由(2-9-2)式右端的记

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

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

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

47、r表红球,y表黄球,b表蓝球,w表白球,2.10 2.10 非线性递推关系举例非线性递推关系举例-Stirling系数系数由定义，我们有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系数系数(c)设有n个不相同的球b1,b2,bn从中取出球 b1,其余的n-1个球,每个都有与b1同盒,或不与b1同盒两种选择.但必须排除一种情况,即全体与b1同盒,因这时另一盒将是空盒.故实际上只有2n-11种方案,即证明:公式(a)(b

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

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

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