线性常系数齐次递推关系确定一个数列课件

第二章

递推关系与母函数2.1递推关系2.2母函数2.3Fibonacci数列2.5母函数的性质2.6线性常系数齐次递推关系2.7关于线性常系数非其次递推关系2.8整数的拆分第二章

递推关系与母函数2.1递推关系2.1递推关系Hanoi塔问题：这是组合数学中的一个著名问题。n个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上，请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。首先要设计算法，进而估计它的复杂性，即估计工作量。2.1递推关系Hanoi塔问题：这是组合数学中的一个著名当n=2时，第一步把A柱的小圆盘移到B柱；第二步把A柱的大圆盘移到C柱；A

B

C第三步把B柱的小圆盘移到C柱，即完成移动。当n=2时，第一步把A柱的小圆盘移到B柱；第二步把A柱的大圆假定n-1个盘子的转移算法已经确定，对于一般n个圆盘的问题，ABC首先把A柱上面的n-1个圆盘移到B柱；然后把A柱最下面的圆盘移到C柱；最后把B柱的n-1个圆盘移到C柱，即完成移动。假定n-1个盘子的转移算法已经确定，对于一般n个圆盘的问题，令h(n)表示n个圆盘所需要的转移盘次。因此有：从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后将B的n-1个盘子转移到C上。下面我们利用母函数来得到h(n)的通项表达式。假设序列h(n)对应的母函数为H(x)，即令h(n)表示n个圆盘所需要的转移盘次。因此有：从这个递推关因此有因此有或者利用x2:x3:x4:+)同样可以得到：或者利用x2:x3:x4:+)同样可以得到：假设下面我们用幂级数展开的方法得到h(n).利用待定系数法容易得到A=1，B=-1，即即假设下面我们用幂级数展开的方法得到h(n).利用待定系数法容2.2母函数母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著—概率解析理论。我们来看如下的例子：两个骰子掷出6点，有多少种选法？注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，按加法法则，共有2+2+1=5种不同选法。或者，第一个骰子除了6以外都可选，有5种选法，一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有5×1=5种。2.2母函数母函数方法是一套非常有用的方法，应用极广。这但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想把骰子出现的点数1,2,…,6和t,t2,…,t6对应起来，则每个骰子可能出现的点数与(t+t2+…+t6)中t的各次幂一一对应。若有两个骰子，则其中t6的系数为5，显然来自于这表明，掷出6点的方法一一对应于得到t6的方法。但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f(t)称为母函数。母函数方法的基本思想：把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f再来看下面的例子：若令a1=a2=…=an=1，则有这就是二项式展开定理。再来看下面的例子：若令a1=a2=…=an=1，则有这就是比较等号两端项对应系数，可以得到恒等式：比较等号两端项对应系数，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：中令x=1可得又如在等式两端对x求导可得：再令x=1可得类似还可以得到中令x=1可得又如在等式两端对x求导可得：再令x=1可得还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+x)n在研究序列C(n,0),C(n,1),…,C(n,n)的关系时所起的作用。定义：对于序列a0,a1,a2,…，函数称为序列a0,a1,a2,…的母函数。例如函数(1+x)n就是序列C(n,0),C(n,1),…,C(n,n)的母函数。如若已知序列，则对应的母函数可根据定义给出。反之，如果已经求出序列的母函数G(x)，则该序列也随之确定。还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+2.3Fibonacci数列Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为Fn，其中当月新生兔数目设为Nn

对，上个月留下的兔子数目设为On对，则但是注意到On=Fn-1，Nn=On-1=Fn-2，因此有2.3Fibonacci数列Fibonacci数列是递推利用这个递推关系很容易可以得到：下面我们利用母函数来计算Fn的通项表达式。设Fn的母函数为G(x)，则x3:x4:+)利用这个递推关系很容易可以得到：下面我们利用母函数来计算Fn方程1-x-x2=0的两个根设为：则有利用待定系数法易有因此有即通项表达式为：方程1-x-x2=0的两个根设为：则有利用待定系数法易有因此线性常系数齐次递推关系确定一个数列课件线性常系数齐次递推关系确定一个数列课件线性常系数齐次递推关系确定一个数列课件2.5母函数的性质设序列ak,bk对应的母函数分别为A(x),B(x)。则下面的两个性质显然成立：(1)A(x)=B(x)当且仅当ak=bk。(2)若A(x)+B(x)=c0+c1x+c2x2+…，则ck=ak+bk。性质1：若则B(x)=xlA(x)。证:2.5母函数的性质设序列ak,bk对应的母函数分别为A则例4

已知性质2：若bk=ak+l，则则例5

已知则例4已知性质2：若bk=ak+l，则则例5已知性质3：若bk=a0+…+ak，则1:x:x2:xk:+)性质3：若bk=a0+…+ak，则1:x:x2:xk:+)则例6

已知则例6已知性质4：若bk=ak+ak+1+…，则1:x:x2:+)性质4：若bk=ak+ak+1+…，则1:x:x2:+)性质5：若bk=kak，则性质6：若bk=ak/(1+k)，则则例7

已知性质5：若bk=kak，则性质6：若bk=ak/(1+k)，性质7：若ck=a0bk+a1bk-1+…+ak-1b1+akb0，则1:x:x2:+)性质7：若ck=a0bk+a1bk-1+…+ak-1b1+a令例8

已知则令例8已知则线性常系数递推关系2.6线性常系数齐次递推关系2.7

线性常系数非齐次递推关系线性常系数递推关系2.6线性常系数齐次递推关系2.6.线性常系数齐次递推关系确定一个数列{an}的最常用的方法是：(1)给出一般项an的表达式;(2)得到该数列的母函数;(3)建立数列所满足的递推关系。一个r-阶递推关系定义为：有正整数r以及一个r+1元函数F，使得对所有nr,有关系式这样若已知这个数列的前r项a0,a1,…,ar-1(称为初始条件)，则可以通过递推关系逐项确定整个数列。2.6.线性常系数齐次递推关系确定一个数列{an}的最常定义：如果序列{an}满足如果b(n)=0，则称为齐次的，否则称为非齐次的。其中都是常数，则(1)称为一个k阶线性常系数递推关系，(2)称为初始条件。定义：如果序列{an}满足如果b(n)=0，则称为齐次的，否先考虑二阶线性常系数齐次递推关系，即令母函数为G(x)=a0+a1x+a2x2+…，则先考虑二阶线性常系数齐次递推关系，即令母函数为G(x)=a0因此有与分母相对应的方程x2+bx+c=0称为特征方程，它的根称为特征根。这样G(x)可以表示为：因此有与分母相对应的方程x2+bx+c=0称为特征方程，(1)如果r1≠r2，则下面要根据特征根来进行分类讨论。因此通项表达式为：其中常数A,B可以利用待定系数法确定，或者利用初始条件(A+B=a0,Ar1+Br2=a1)来确定。(1)如果r1≠r2，则下面要根据特征根来进行分类讨论。因(1)’如果r1≠r2，且是一对共轭复根，则可以假设这样就有：定义两个新的待定常数：则通项表达式为：其中k1,k2由初始条件决定。(1)’如果r1≠r2，且是一对共轭复根，则可以假设这样就(2)如果r1=r2，则可以令r=r1=r2=-b/2，因此通项表达式为：其中常数C,D可以利用初始条件来确定。例如，若已知a0,a1，则(2)如果r1=r2，则可以令r=r1=r2=-b/2，因例1

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例1求解递推关系：特征方程为因此通项表达式可以设为：解得例2

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例2求解递推关系：特征方程为因此通项表达式可以设为：解得例3Fibonacci数列：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例3Fibonacci数列：特征方程为因此通项表达式可以例4

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例4求解递推关系：特征方程为因此通项表达式可以设为：解得接下来讨论一般的k阶线性常系数齐次递推关系：类似的，令母函数为G(x)=a0+a1x+a2x2+…，则+)接下来讨论一般的k阶线性常系数齐次递推关系：类似的，令母函数整理得其中右端是次数不超过k-1次的多项式，设为P(x)。定义为特征方程，它在复数域内刚好有k个根，即其中k1+…+ki=k。这些根称为特征根。这样，等式左边的函数可以表示为：整理得其中右端是次数不超过k-1次的多项式，设为P(x)。定即即(1)如果所有特征根都互不相同，则下面同样要根据特征根来进行分类讨论。因此通项表达式为：其中常数A1,A2,…,Ak可以利用初始条件来确定。(1)如果所有特征根都互不相同，则下面同样要根据特征根来进(1)’如果有一对共轭复根(重数都为1)，重复以前的讨论，不妨假设这一对共轭复根是则an的通项表达式中对应于的项为：其中常数A1,A2和通项表达式中的其他常数一起由初始条件来决定。(1)’如果有一对共轭复根(重数都为1)，重复以前的讨论，(2)如果有重根，不妨假设a1是m重根，则母函数中对应于a1的项可以表示为因此通项表达式中对应于a1的部分为：注意到C(j+n-1,n)=C(j+n-1,j-1)是n的j-1次多项式，因此这部分也可以表示为(2)如果有重根，不妨假设a1是m重根，则母函数中对应于a例5

求下列n阶行列式的值dn：特征方程为根据行列式的性质有：例5求下列n阶行列式的值dn：特征方程为根据行列式的性质这是一个二重根，因此通项表达式可以设为：解得特征根为代入初始条件有因此n阶行列式的值为：这是一个二重根，因此通项表达式可以设为：解得特征根为代入初始例6

计算Sn=1+2+…+n。显然有Sn-Sn-1=n，但这不是一个齐次递推关系。注意到Sn-1-Sn-2=n-1，两式相减有再次利用两式相减得这是一个三阶线性常系数齐次递推关系。特征方程为解得特征根为这是一个三重根，因此可以设例6计算Sn=1+2+…+n。显然有Sn-Sn-1=n代入初始条件有因此有：代入初始条件有因此有：例7

计算Sn=12+22+…+n2。显然有Sn-Sn-1=n2，Sn-1-Sn-2=(n-1)2，两式相减有再次利用两式相减得特征方程为解得特征根为这是一个四重根，因此可以设再次利用两式相减得例7计算Sn=12+22+…+n2。显然有Sn-Sn-代入初始条件有因此有：代入初始条件有因此有：例8

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为例8求解递推关系：特征方程为因此通项表达式可以设为：解得代入初始条件有因此通项表达式为：代入初始条件有因此通项表达式为：2.7线性常系数非齐次递推关系对于一个k阶线性常系数非齐次递推关系：与一般的线性问题类似，它的通解可以表示为特解与对应的齐次问题通解的和，即其中an*是非齐次递推关系的一个特解，而an’是对应的齐次递推关系的通解。2.7线性常系数非齐次递推关系对于一个k阶线性常系数非齐关于齐次递推关系的通解，我们已经讨论完全了。因此关键在于如何得到非齐次递推关系的一个特解。下面我们针对一些特殊的右端项来讨论如何得到特解。例10

求递推关系：的一个特解。假设有如下形式的特解代入原递推关系，并整理后可得关于齐次递推关系的通解，我们已经讨论完全了。因此关键在于如何因此有因此可以得到一个特解解得因此有因此可以得到一个特解解得(1)一般来说，当右端项b(n)是n的k次多项式时，特解形式也可以设为k次多项式，即其中系数Ai由代入非齐次递推关系后确定。例11

求递推关系的一个特解。

假设有如下形式的特解代入原递推关系，并整理后易有但这是不可能的！(1)一般来说，当右端项b(n)是n的k次多项式时，特解形问题出在当1是原递推关系的特征根时，若把特解设为多项式，代入递推关系后，最高次会被消去。回到上例，因此1是一重特征根，因此特解设为代入原递推关系，并整理后可得(2)当右端项b(n)是n的k次多项式时，若1是递推关系的t重特征根，则特解的次数要提高t次，即易有A=B=7/2，即一个特解为：问题出在当1是原递推关系的特征根时，若把特解设为多项式，代入例12

求递推关系：的一个特解。假设有如下形式的特解代入原递推关系有化简得42A=42×16，即A=16。因此可以得到一个特解例12求递推关系：的一个特解。假设有如下形式的特解代入原例13

求递推关系：的一个特解。注意到2是递推关系的一个特征根，因此2n是对应齐次递推关系的解，即若把特解设为A×2n，则代入递推关系后，左端为0，无法解出A。代入原递推关系有化简求得A=-2。因此可以得到一个特解因此可以设特解形式为：例13求递推关系：的一个特解。注意到2是递推关系的一个特(3)当右端项b(n)是常数乘以sn的形式时，若s是递推关系的t重特征根，则特解形式可以设为其中系数A由代入非齐次递推关系后确定。注意这包含了s不是特征根的情形，即t=0.把上面三种情况综合在一起，我们有下面的结论：若右端项b(n)=f(n)sn，其中f(n)是n的k次多项式，s是递推关系的t(t=0,1,2,…)重特征根，则特解形式可以设为(3)当右端项b(n)是常数乘以sn的形式时，若s是递推关例14

求递推关系：的通解。显然特征根为-5,2，-7不是特征根，因此特解可设为代入原递推关系解得注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为其中A,B由初始条件确定。例14求递推关系：的通解。显然特征根为-5,2，-7不是例15

求递推关系：的通解。显然特征根为-5，2，2是1重根，因此特解可以设为代入原递推关系解得注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为其中A,B由初始条件确定。例15求递推关系：的通解。显然特征根为-5，2，2是1重例16

求Sn=12+22+…+n2。显然Sn满足Sn-Sn-1=n2，这是一个非齐次递推关系。由于1是递归关系的1重特征根，因此在设特解时需要把右端非齐次项中的多项式次数提高一次，即设另一方面，对应齐次递推关系的通解为常数，因此Sn应该是一个三次多项式，即可设为常数A,B,C,D代入初始条件即可确定。同样的技巧可以用来计算Sn=13+23+…+n3等。例16求Sn=12+22+…+n2。显然Sn满足Sn-S叠加原理：设右端项b(n)有如下形式：则非齐次递推关系的一个特解为其中ai是右端项为bi(n)时对应的特解。例17

求递推关系：的一个特解。根据叠加原理，问题变为求当右端项分别为42∙4n和2n时的特解，而这前面已经计算过了。因此特解为叠加原理：设右端项b(n)有如下形式：则非齐次递推关系的一个2.8整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。2.8整数的拆分所谓正整数拆分即把正整数分解成若干正整数例9

若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有2x5项，即称出5克的方案有2种：5=2+3=1+4。类似的，称出6克的方案也有2种：6=2+4=1+2+3。例9若有1克、2克、3克、4克的砝码各一枚，问能称出那几例10

求用1分、2分、3分的邮票贴出不同数值的方案数。以x4为例，其系数为4，即4拆分成1，2，3之和的允许重复的拆分数为4：4=1+1+1+1=1+1+2=1+3=2+2。注意邮票允许重复，因此母函数为：例10求用1分、2分、3分的邮票贴出不同数值的方案数。以例11若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种质量？各有几种方案？即可称出1至19克的质量，不同的方案数即为对应项前面的系数。母函数为：例11若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能例12把整数N无序拆分成整数a1,a2,…,an的和，且不允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程令bN表示不同的拆分数，则其对应的母函数为：特殊的，当ai=i时，对应的母函数为：例12把整数N无序拆分成整数a1,a2,…,an的和，且例13把整数N无序拆分成整数a1,a2,…,an的和，允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程令bN表示不同的拆分数，则其对应的母函数为：例13把整数N无序拆分成整数a1,a2,…,an的和，允特殊的，当ai=i时，对应的母函数为：特殊的，当ai=i时，对应的母函数为：例14把整数N无序拆分成奇整数的和，允许重复，求不同的拆分数。这相当于在上例中把ai取成奇数，因此拆分数对应的母函数为：例15把整数N无序拆分成2的幂次的和，求不同的拆分数。这相当于把N拆分成1,2,4,8,…的和，但不允许重复。因此拆分数对应的母函数为：例14把整数N无序拆分成奇整数的和，允许重复，求不同的拆例16把整数N无序拆分1,2,…,m的和，允许重复，求不同的拆分数。若要求m至少出现一次呢？若无要求，由例13可知其母函数为：若要求m至少出现一次，则拆分数对应的母函数为：例16把整数N无序拆分1,2,…,m的和，允许重复，求不这个等式的组合意义很明显：整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。显然有这个等式的组合意义很明显：整数n拆分成1到m的和的拆分数减去设bN表示N剖分成不同正整数和的剖分数，则其对应的母函数为：定理1

整数剖分成不同整数的和的剖分数(不允许重复)等于剖分成奇数的剖分数(允许重复)。设bN表示N剖分成不同正整数和的剖分数，则其对应的母函数为：设bN表示N剖分成重复数不超过2的正整数之和的剖分数，则其对应的母函数为：定理2

N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数。设bN表示N剖分成重复数不超过2的正整数之和的剖分数，则其对定理3

N被剖分成一些重复次数不超过k次的整数的和，其剖分数等于被剖分成不被k+1除尽的数的和的剖分数。定理4

对任意整数N，它被无序剖分成2的幂次的和的剖分方式一定唯一。定理3N被剖分成一些重复次数不超过k次的整数的和，其剖分例17若有1、2、4、8、16克的砝码各一枚，问能称出那几种质量？有几种可能方案？这说明用这些砝码可以称出从1克到31克的质量，而且方案都是唯一的。实际上这说明整数的二进制表示是唯一的。例17若有1、2、4、8、16克的砝码各一枚，问能称出那2.9Ferrers图像一个从上而下的n层格子组成的图像，mi为第i层的格子数。当mi≥mi+1，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如下图：每一层至少有一个格子。绕虚线轴旋转所得的图仍然是Ferrers图像。这样的两个Ferrers图像称为一对共轭的Ferrers图像。2.9Ferrers图像一个从上而下的n层格子组成的图像(1)整数n拆分成k个数的和的拆分数，与数n拆分成最大数为k的拆分数相等。因为整数n拆分成k个数的和的拆分可以用一个k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如：利用Ferrers图像可以得到一些关于整数拆分的结果：

24=6+6+5+4+35个数，最大数为6

24=5+5+5+4+3+26个数，最大数为5(1)整数n拆分成k个数的和的拆分数，与数n拆分成最大数为理由和(1)相类似。因此，拆分成最多不超过m个数的和的拆分数的母函数是：(2)整数n拆分成最多不超过m个数的和的拆分数，与n拆分成最大不超过m的拆分数相等。正好拆分成m个数的和的拆分数的母函数为理由和(1)相类似。因此，拆分成最多不超过m个数的和的拆分数(3)整数n拆分成互不相同的若干奇数的和的的拆分数，与n拆分成自共轭的Ferrers图像的拆分数相等。设整数n拆分为n=(2n1+1)+(2n2+1)+…+(2nk+1)，其中n1>n2>…>nk。构造一个Ferrers图像，第一行第一列都是n1+1格，对应于2n1+1，第二行第二列都是n2+1格，对应于2n2+1，依此类推。这样得到的Ferrers图像一定是自共轭的。反过来，自共轭的Ferrers图像也可以对应到一些不同奇数的和。(3)整数n拆分成互不相同的若干奇数的和的的拆分数，与n拆例如17=9+5+3对应的Ferrers图像为：(4)正整数n剖分成不超过k个数的和的剖分数，等于将n+k剖分成恰好k个数的剖分数。不超过k层的Ferrers图像的每一层加上一个格子，一一对应到一个刚好k层的Ferrers图像。例如17=9+5+3对应的Ferrers图像为：(4)正整2.11指数型母函数考虑n个元素组成的多重集，其中a1重复了n1次，a2

重复了n2次，…，ak重复了nk次，n=n1+n2+…+nk。从中取r个排列，求不同的排列数。若r=n，即考虑n个元素的全排列，则不同的排列数为：但是对于一般的r，情况就比较复杂了。2.11指数型母函数考虑n个元素组成的多重集，其中a1重876543232543232232369109631

)1(

)23321(

)1)(1)(1()(xxxxxxxxxxxxxxxxxxxxxxxxxG++++++++=++++++++=++++++++=先看一个具体的问题：假设有8个元素，其中a1重复3次，a2重复2次，a3重复3次。从中取r个组合，其组合数为cr，则其对应的母函数为：从x4的系数可知，从这8个元素中取4个组合，不同的组合数为10。这10个组合可从下面的展开式中得到：876543232543232232369109631)1

其中4次方项表示了所有从8个元素中取4个的组合方案。例如表示一个a1三个a3的组合，表示两个a1两个a3的组合，依此类推。其中4次方项表示了所有从8个元素中取4个的组合方案。例如接下来讨论从这8个元素中取4个的不同排列总数。以两个a1两个a3组合为例，不同排列数为4!/(2!2!)。同样一个a1三个a3的不同排列数为4!/(1!3!)。依此类推可以得到不同的排列总数为：接下来讨论从这8个元素中取4个的不同排列总数。以两个a1两个为了便于计算，利用上述特点，形式地引进函数从右边很容易可以看出，取2个的排列数为9，取3个的排列数为28，取4个的排列数为70…依此类推。为了便于计算，利用上述特点，形式地引进函数从右边很容易可以看定义：对于序列a0,a1,a2,…，函数称为序列a0,a1,a2,…对应的指数型母函数。这样，对于一个多重集，其中a1重复n1次，a2

重复n2次，…，ak重复nk次，从中取r个排列的不同排列数所对应的指数型母函数为：定义：对于序列a0,a1,a2,…，函数称为序列a0,a1,例18求下列数列的指数型母函数：例18求下列数列的指数型母函数：例19由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数最多3次，可以不出现；4出现次数为偶数。求满足上述条件的数的个数。设满足上述条件的r位数个数为cr，则其对应的指数型母函数为：例19由1，2，3，4四个数字组成的五位数中，要求数1出由此可见满足条件的5位数共215个。由此可见满足条件的5位数共215个。例20求由1，3，5，7，9五个数字组成的n位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。设满足上述条件的n位数个数为cn，则其对应的指数型母函数为：例20求由1，3，5，7，9五个数字组成的n位数的个数，因此因此例217个有区别的球放进4个有标志的盒子里，要求1，2两个盒子必须有偶数个球，第3个盒子有奇数个球，求不同的方案个数。这相当于从1234这4个数中取7个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。这样的排列数所对应的指数型母函数为：例217个有区别的球放进4个有标志的盒子里，要求1，2两因此因此例22r个有标志的球放进n个不同的盒子里，要求无一空盒，问有多少种不同的分配方案？这相当于从1到n这n个数字中取r个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。这样的排列数所对应的指数型母函数为：要求无一空盒即相当于要求每个数字至少出现一次。例22r个有标志的球放进n个不同的盒子里，要求无一空盒，问因此因此第二章

递推关系与母函数2.1递推关系2.2母函数2.3Fibonacci数列2.5母函数的性质2.6线性常系数齐次递推关系2.7关于线性常系数非其次递推关系2.8整数的拆分第二章

递推关系与母函数2.1递推关系2.1递推关系Hanoi塔问题：这是组合数学中的一个著名问题。n个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上，请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。首先要设计算法，进而估计它的复杂性，即估计工作量。2.1递推关系Hanoi塔问题：这是组合数学中的一个著名当n=2时，第一步把A柱的小圆盘移到B柱；第二步把A柱的大圆盘移到C柱；A

B

C第三步把B柱的小圆盘移到C柱，即完成移动。当n=2时，第一步把A柱的小圆盘移到B柱；第二步把A柱的大圆假定n-1个盘子的转移算法已经确定，对于一般n个圆盘的问题，ABC首先把A柱上面的n-1个圆盘移到B柱；然后把A柱最下面的圆盘移到C柱；最后把B柱的n-1个圆盘移到C柱，即完成移动。假定n-1个盘子的转移算法已经确定，对于一般n个圆盘的问题，令h(n)表示n个圆盘所需要的转移盘次。因此有：从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后将B的n-1个盘子转移到C上。下面我们利用母函数来得到h(n)的通项表达式。假设序列h(n)对应的母函数为H(x)，即令h(n)表示n个圆盘所需要的转移盘次。因此有：从这个递推关因此有因此有或者利用x2:x3:x4:+)同样可以得到：或者利用x2:x3:x4:+)同样可以得到：假设下面我们用幂级数展开的方法得到h(n).利用待定系数法容易得到A=1，B=-1，即即假设下面我们用幂级数展开的方法得到h(n).利用待定系数法容2.2母函数母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著—概率解析理论。我们来看如下的例子：两个骰子掷出6点，有多少种选法？注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，按加法法则，共有2+2+1=5种不同选法。或者，第一个骰子除了6以外都可选，有5种选法，一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有5×1=5种。2.2母函数母函数方法是一套非常有用的方法，应用极广。这但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想把骰子出现的点数1,2,…,6和t,t2,…,t6对应起来，则每个骰子可能出现的点数与(t+t2+…+t6)中t的各次幂一一对应。若有两个骰子，则其中t6的系数为5，显然来自于这表明，掷出6点的方法一一对应于得到t6的方法。但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f(t)称为母函数。母函数方法的基本思想：把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f再来看下面的例子：若令a1=a2=…=an=1，则有这就是二项式展开定理。再来看下面的例子：若令a1=a2=…=an=1，则有这就是比较等号两端项对应系数，可以得到恒等式：比较等号两端项对应系数，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：中令x=1可得又如在等式两端对x求导可得：再令x=1可得类似还可以得到中令x=1可得又如在等式两端对x求导可得：再令x=1可得还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+x)n在研究序列C(n,0),C(n,1),…,C(n,n)的关系时所起的作用。定义：对于序列a0,a1,a2,…，函数称为序列a0,a1,a2,…的母函数。例如函数(1+x)n就是序列C(n,0),C(n,1),…,C(n,n)的母函数。如若已知序列，则对应的母函数可根据定义给出。反之，如果已经求出序列的母函数G(x)，则该序列也随之确定。还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+2.3Fibonacci数列Fibonacci数列是递推关系的又一个典型问题，数列的本身有着许多应用。有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子？设满n个月时兔子对数为Fn，其中当月新生兔数目设为Nn

对，上个月留下的兔子数目设为On对，则但是注意到On=Fn-1，Nn=On-1=Fn-2，因此有2.3Fibonacci数列Fibonacci数列是递推利用这个递推关系很容易可以得到：下面我们利用母函数来计算Fn的通项表达式。设Fn的母函数为G(x)，则x3:x4:+)利用这个递推关系很容易可以得到：下面我们利用母函数来计算Fn方程1-x-x2=0的两个根设为：则有利用待定系数法易有因此有即通项表达式为：方程1-x-x2=0的两个根设为：则有利用待定系数法易有因此线性常系数齐次递推关系确定一个数列课件线性常系数齐次递推关系确定一个数列课件线性常系数齐次递推关系确定一个数列课件2.5母函数的性质设序列ak,bk对应的母函数分别为A(x),B(x)。则下面的两个性质显然成立：(1)A(x)=B(x)当且仅当ak=bk。(2)若A(x)+B(x)=c0+c1x+c2x2+…，则ck=ak+bk。性质1：若则B(x)=xlA(x)。证:2.5母函数的性质设序列ak,bk对应的母函数分别为A则例4

已知性质2：若bk=ak+l，则则例5

已知则例4已知性质2：若bk=ak+l，则则例5已知性质3：若bk=a0+…+ak，则1:x:x2:xk:+)性质3：若bk=a0+…+ak，则1:x:x2:xk:+)则例6

已知则例6已知性质4：若bk=ak+ak+1+…，则1:x:x2:+)性质4：若bk=ak+ak+1+…，则1:x:x2:+)性质5：若bk=kak，则性质6：若bk=ak/(1+k)，则则例7

已知性质5：若bk=kak，则性质6：若bk=ak/(1+k)，性质7：若ck=a0bk+a1bk-1+…+ak-1b1+akb0，则1:x:x2:+)性质7：若ck=a0bk+a1bk-1+…+ak-1b1+a令例8

已知则令例8已知则线性常系数递推关系2.6线性常系数齐次递推关系2.7

线性常系数非齐次递推关系线性常系数递推关系2.6线性常系数齐次递推关系2.6.线性常系数齐次递推关系确定一个数列{an}的最常用的方法是：(1)给出一般项an的表达式;(2)得到该数列的母函数;(3)建立数列所满足的递推关系。一个r-阶递推关系定义为：有正整数r以及一个r+1元函数F，使得对所有nr,有关系式这样若已知这个数列的前r项a0,a1,…,ar-1(称为初始条件)，则可以通过递推关系逐项确定整个数列。2.6.线性常系数齐次递推关系确定一个数列{an}的最常定义：如果序列{an}满足如果b(n)=0，则称为齐次的，否则称为非齐次的。其中都是常数，则(1)称为一个k阶线性常系数递推关系，(2)称为初始条件。定义：如果序列{an}满足如果b(n)=0，则称为齐次的，否先考虑二阶线性常系数齐次递推关系，即令母函数为G(x)=a0+a1x+a2x2+…，则先考虑二阶线性常系数齐次递推关系，即令母函数为G(x)=a0因此有与分母相对应的方程x2+bx+c=0称为特征方程，它的根称为特征根。这样G(x)可以表示为：因此有与分母相对应的方程x2+bx+c=0称为特征方程，(1)如果r1≠r2，则下面要根据特征根来进行分类讨论。因此通项表达式为：其中常数A,B可以利用待定系数法确定，或者利用初始条件(A+B=a0,Ar1+Br2=a1)来确定。(1)如果r1≠r2，则下面要根据特征根来进行分类讨论。因(1)’如果r1≠r2，且是一对共轭复根，则可以假设这样就有：定义两个新的待定常数：则通项表达式为：其中k1,k2由初始条件决定。(1)’如果r1≠r2，且是一对共轭复根，则可以假设这样就(2)如果r1=r2，则可以令r=r1=r2=-b/2，因此通项表达式为：其中常数C,D可以利用初始条件来确定。例如，若已知a0,a1，则(2)如果r1=r2，则可以令r=r1=r2=-b/2，因例1

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例1求解递推关系：特征方程为因此通项表达式可以设为：解得例2

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例2求解递推关系：特征方程为因此通项表达式可以设为：解得例3Fibonacci数列：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例3Fibonacci数列：特征方程为因此通项表达式可以例4

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为代入初始条件有因此通项表达式为：例4求解递推关系：特征方程为因此通项表达式可以设为：解得接下来讨论一般的k阶线性常系数齐次递推关系：类似的，令母函数为G(x)=a0+a1x+a2x2+…，则+)接下来讨论一般的k阶线性常系数齐次递推关系：类似的，令母函数整理得其中右端是次数不超过k-1次的多项式，设为P(x)。定义为特征方程，它在复数域内刚好有k个根，即其中k1+…+ki=k。这些根称为特征根。这样，等式左边的函数可以表示为：整理得其中右端是次数不超过k-1次的多项式，设为P(x)。定即即(1)如果所有特征根都互不相同，则下面同样要根据特征根来进行分类讨论。因此通项表达式为：其中常数A1,A2,…,Ak可以利用初始条件来确定。(1)如果所有特征根都互不相同，则下面同样要根据特征根来进(1)’如果有一对共轭复根(重数都为1)，重复以前的讨论，不妨假设这一对共轭复根是则an的通项表达式中对应于的项为：其中常数A1,A2和通项表达式中的其他常数一起由初始条件来决定。(1)’如果有一对共轭复根(重数都为1)，重复以前的讨论，(2)如果有重根，不妨假设a1是m重根，则母函数中对应于a1的项可以表示为因此通项表达式中对应于a1的部分为：注意到C(j+n-1,n)=C(j+n-1,j-1)是n的j-1次多项式，因此这部分也可以表示为(2)如果有重根，不妨假设a1是m重根，则母函数中对应于a例5

求下列n阶行列式的值dn：特征方程为根据行列式的性质有：例5求下列n阶行列式的值dn：特征方程为根据行列式的性质这是一个二重根，因此通项表达式可以设为：解得特征根为代入初始条件有因此n阶行列式的值为：这是一个二重根，因此通项表达式可以设为：解得特征根为代入初始例6

计算Sn=1+2+…+n。显然有Sn-Sn-1=n，但这不是一个齐次递推关系。注意到Sn-1-Sn-2=n-1，两式相减有再次利用两式相减得这是一个三阶线性常系数齐次递推关系。特征方程为解得特征根为这是一个三重根，因此可以设例6计算Sn=1+2+…+n。显然有Sn-Sn-1=n代入初始条件有因此有：代入初始条件有因此有：例7

计算Sn=12+22+…+n2。显然有Sn-Sn-1=n2，Sn-1-Sn-2=(n-1)2，两式相减有再次利用两式相减得特征方程为解得特征根为这是一个四重根，因此可以设再次利用两式相减得例7计算Sn=12+22+…+n2。显然有Sn-Sn-代入初始条件有因此有：代入初始条件有因此有：例8

求解递推关系：特征方程为因此通项表达式可以设为：解得特征根为例8求解递推关系：特征方程为因此通项表达式可以设为：解得代入初始条件有因此通项表达式为：代入初始条件有因此通项表达式为：2.7线性常系数非齐次递推关系对于一个k阶线性常系数非齐次递推关系：与一般的线性问题类似，它的通解可以表示为特解与对应的齐次问题通解的和，即其中an*是非齐次递推关系的一个特解，而an’是对应的齐次递推关系的通解。2.7线性常系数非齐次递推关系对于一个k阶线性常系数非齐关于齐次递推关系的通解，我们已经讨论完全了。因此关键在于如何得到非齐次递推关系的一个特解。下面我们针对一些特殊的右端项来讨论如何得到特解。例10

求递推关系：的一个特解。假设有如下形式的特解代入原递推关系，并整理后可得关于齐次递推关系的通解，我们已经讨论完全了。因此关键在于如何因此有因此可以得到一个特解解得因此有因此可以得到一个特解解得(1)一般来说，当右端项b(n)是n的k次多项式时，特解形式也可以设为k次多项式，即其中系数Ai由代入非齐次递推关系后确定。例11

求递推关系的一个特解。

假设有如下形式的特解代入原递推关系，并整理后易有但这是不可能的！(1)一般来说，当右端项b(n)是n的k次多项式时，特解形问题出在当1是原递推关系的特征根时，若把特解设为多项式，代入递推关系后，最高次会被消去。回到上例，因此1是一重特征根，因此特解设为代入原递推关系，并整理后可得(2)当右端项b(n)是n的k次多项式时，若1是递推关系的t重特征根，则特解的次数要提高t次，即易有A=B=7/2，即一个特解为：问题出在当1是原递推关系的特征根时，若把特解设为多项式，代入例12

求递推关系：的一个特解。假设有如下形式的特解代入原递推关系有化简得42A=42×16，即A=16。因此可以得到一个特解例12求递推关系：的一个特解。假设有如下形式的特解代入原例13

求递推关系：的一个特解。注意到2是递推关系的一个特征根，因此2n是对应齐次递推关系的解，即若把特解设为A×2n，则代入递推关系后，左端为0，无法解出A。代入原递推关系有化简求得A=-2。因此可以得到一个特解因此可以设特解形式为：例13求递推关系：的一个特解。注意到2是递推关系的一个特(3)当右端项b(n)是常数乘以sn的形式时，若s是递推关系的t重特征根，则特解形式可以设为其中系数A由代入非齐次递推关系后确定。注意这包含了s不是特征根的情形，即t=0.把上面三种情况综合在一起，我们有下面的结论：若右端项b(n)=f(n)sn，其中f(n)是n的k次多项式，s是递推关系的t(t=0,1,2,…)重特征根，则特解形式可以设为(3)当右端项b(n)是常数乘以sn的形式时，若s是递推关例14

求递推关系：的通解。显然特征根为-5,2，-7不是特征根，因此特解可设为代入原递推关系解得注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为其中A,B由初始条件确定。例14求递推关系：的通解。显然特征根为-5,2，-7不是例15

求递推关系：的通解。显然特征根为-5，2，2是1重根，因此特解可以设为代入原递推关系解得注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为其中A,B由初始条件确定。例15求递推关系：的通解。显然特征根为-5，2，2是1重例16

求Sn=12+22+…+n2。显然Sn满足Sn-Sn-1=n2，这是一个非齐次递推关系。由于1是递归关系的1重特征根，因此在设特解时需要把右端非齐次项中的多项式次数提高一次，即设另一方面，对应齐次递推关系的通解为常数，因此Sn应该是一个三次多项式，即可设为常数A,B,C,D代入初始条件即可确定。同样的技巧可以用来计算Sn=13+23+…+n3等。例16求Sn=12+22+…+n2。显然Sn满足Sn-S叠加原理：设右端项b(n)有如下形式：则非齐次递推关系的一个特解为其中ai是右端项为bi(n)时对应的特解。例17

求递推关系：的一个特解。根据叠加原理，问题变为求当右端项分别为42∙4n和2n时的特解，而这前面已经计算过了。因此特解为叠加原理：设右端项b(n)有如下形式：则非齐次递推关系的一个2.8整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。2.8整数的拆分所谓正整数拆分即把正整数分解成若干正整数例9

若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有2x5项，即称出5克的方案有2种：5=2+3=1+4。类似的，称出6克的方案也有2种：6=2+4=1+2+3。例9若有1克、2克、3克、4克的砝码各一枚，问能称出那几例10

求用1分、2分、3分的邮票贴出不同数值的方案数。以x4为例，其系数为4，即4拆分成1，2，3之和的允许重复的拆分数为4：4=1+1+1+1=1+1+2=1+3=2+2。注意邮票允许重复，因此母函数为：例10求用1分、2分、3分的邮票贴出不同数值的方案数。以例11若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种质量？各有几种方案？即可称出1至19克的质量，不同的方案数即为对应项前面的系数。母函数为：例11若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能例12把整数N无序拆分成整数a1,a2,…,an的和，且不允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程令bN表示不同的拆分数，则其对应的母函数为：特殊的，当ai=i时，对应的母函数为：例12把整数N无序拆分成整数a1,a2,…,an的和，且例13把整数N无序拆分成整数a1,a2,…,an的和，允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程令bN表示不同的拆分数，则其对应的母函数为：例13把整数N无序拆分成整数a1,a2,…,an的和，允特殊的，当ai=i时，对应的母函数为：特殊的，当ai=i时，对应的母函数为：例14把整数N无序拆分成奇整数的和，允许重复，求不同的拆分数。这相当于在上例中把ai取成奇数，因此拆分数对应的母函数为：例15把整数N无序拆分成2的幂次的和，求不同的拆分数。这相当于把N拆分成1,2,4,8,…的和，但不允许重复。因此拆分数对应的母函数为：例14把整数N无序拆分成奇整数的和，允许重复，求不同的拆例16把整数N无序拆分1,2,…,m的和，允许重复，求不同的拆分数。若要求m至少出现一次呢？若无要求，由例13可知其母函数为：若要求m至少出现一次，则拆分数对应的母函数为：例16把整数N无序拆分1,2,…,m的和，允许重复，求不这个等式的组合意义很明显：整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。显然有这个等式的组合意义很明显：整数n拆分成1到m的和的拆分数减去设bN表示N剖分成不同正整数和的剖分数，则其对应的母函数为：定理1

整数剖分成不同整数的和的剖分数(不允许重复)等于剖分成奇数的剖分数(允许重复)。设bN表示N剖分成不同正整数和的剖分数，则其对应的母函数为：设bN表示N剖分成重复数不超过2的正整数之和的剖分数，则其对应的母函数为：定理2

N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数。设bN表示N剖分成重复数不超过2的正整数之和的剖分数，则其对定理3

N被剖分成一些重复次数不超过k次的整数的和，其剖分数等于被剖分成不被k+1除尽的数的和的剖分数。定理4

对任意整数N，它被无序剖分成2的幂次的和的剖分方式一定唯一。定理3N被剖分成一些重复次数不超过k次的整数的和，其剖分例17若有1、2、4、8、16克的砝码各一枚，问能称出那几种质量？有几种可能方案？这说明用这些砝码可以称出从1克到31克的质量，而且方案都是唯一的。实际上这说明整数的二进制表示是唯一的。例17若有1、2、4、8、16克的砝码各一枚，问能称出那2.9Ferrers图像一个从上而下的n层格子组成的图像，mi为第i层的格子数。当mi≥mi+1，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如下图：每一层至少有一个格子。绕虚线轴旋转所得的图仍然是Ferrers图像。这样的两个Ferrers图像称为一对共轭的Ferrers图像。2.9Ferrers图像一个从上而下的n层格子组成的图像(1)整数n拆分成k个数的和的拆分数，与数n拆分成最大数为k的拆分数相等。因为整数n拆分成k个数的和的拆分可以用一个k行的图像表示。所得的Ferrers图像的共轭图像最上面一行