组合数学 第7章

第七章递推关系和生成函数,7.1某些数列,7.1某些数列令h0,h1,h2,hn,是一个数列。其中hn称作该数列的通项或生成项。对于上述数列，定义其部分和如下：s0=h0s1=h0+h1则s0,s1,s2,sn,亦然是数列。,若数列的通项hn=hn-1+g或hn=h0+ngn1则称该数列为算术数列，并且若数列的通项hn=qhn-1=qnh0n1则称该数列为几何数列，并且,7.1某些数列,7.1某些数列,例确定平面一般位置上的n个互相交叠的圆所形成的区域数？分析设hn是由n个互相交叠的圆所形成的区域数。分析hn与hn-1的关系，我们发现hn=hn-1+2(n-1)因此hnn2n+2n1,7.1某些数列,满足递推关系的数列f0,f1,f2,fn,叫fibonacci数列。例fibonacci数列的项的部分和为分析这一结论可通过归纳法加以证明。,7.1某些数列,定理7.1.1fibonacci数满足公式,7.1某些数列,例令g0,g1,g2,gn,满足的数列，试给出gn的计算公式。分析,7.1某些数列,例确定2n棋盘用domino牌完美覆盖的方法数hn。分析h1=1h2=2h3=3hn=|A|+|B|其中AB故hn=|A|+|B|=hn-1+hn-2n2h0=1h1=1,2n,2n,7.1某些数列,定理7.1.2,其中,证明,现只要证明gn满足Fibonacci递推关系和初始条件即可。,7.2线性齐次递推关系,7.2线性齐次递推关系设h0,h1,h2,hn,是一个数列，若存在a1,a2,ak(ak0)和bn，使得hn=a1hn-1+a2hn-2+akhn-k+bn(nk)则称该数列是一个满足k阶线性递推关系的数列。进一步，若bn是常数0，则称上述递推关系是k阶线性齐次递推关系。如果a1,a2,ak均是常数(ak0)，则称上述递推关系是k阶常系数线性递推关系。下面，我们来讨论k阶常系数线性齐次递推关系的求解问题。,7.2线性齐次递推关系,定理7.2.1设q是一非零数。则hnqn是如下k阶常系数线性齐次递推关系hna1hn-1a2hn-2akhn-k=0(ak0,nk)的解，当且仅当q是多项式方程xka1xk-1a2xk-2akxk-k=0的一个根。如果多项式方程有k个不同的根g1,g2,gk,则hnc1q1n+c2q2n+ckqkn是下述意义下，上述线性齐次递推关系的一般解：无论给定h0,h1,hk-1什么初始值，都存在常数c1,c2,ck，使得hnc1q1n+c2q2n+ckqkn是满足上述递推关系和给定初始条件h0,h1,hk-1的唯一的序列。,7.2线性齐次递推关系,证明此定理的证明过程分两步，这一过程也揭示了此类问题的求解过程：1.证明，hnqn是分式hna1hn-1a2hn-2akhn-k=0的解，当且仅当q是多项式方程xka1xk-1a2xk-2akxk-k=0的一个根。(因此要求出hnqn，我们需要解一个多项式方程),7.2线性齐次递推关系,2.如果多项式方程有k个不同的根，则递推关系的通解是hnc1q1n+c2q2n+ckqkn其中c1,c2,ck在任意指定的初始条件h0,h1,hk-1之后均可唯一确定。(此时，我们只需要解一个关于c1,c2,ck的线性方程组)。c1,c2,ck的唯一确定性是由k阶范德蒙(Vandermonde)矩阵的可逆性。即q1,q2,qk的互异性来保证。,7.2线性齐次递推关系,例求解满足初始条件h01，h12，h20的递推关系hn2hn1hn22hn3(n3)分析先求通解。为此，解特征方程得到3个特征根1，1，2。从而有通解第二步：由三个初始值，得到关于c1,c2,c3的线性方程组：解得其唯一解c12，c22/3,c3=1/3，因此求得特定递推关系的解,7.2线性齐次递推关系,例只由三个字母a，b，c组成长度为n的一些单词将在通信信道上传输。在传输中不允许有两个a连续出现在任一单词中。确定通信信道允许传输的单词个数。分析显然，对于不同的长度n，有不同的单词数hn，我们希望根据问题的本质，找出hn与hn-1,hn-2,hn-k的递推关系，并求此递推关系的解。关于此问题，有hn=2hn-1+2hn-2n2以及h0=1,h1=3,7.2线性齐次递推关系,以上我们讨论的仅限于特征方程的特征根无重根时的情况下。对于含有重根的处理方法，由以下定理的证明过程给出：定理7.2.2设为k阶常系数线性齐次递推关系,的特征方程,的互异的根。此时，若qi是si重根，则该递推关系对qi的部分通解为：递推关系的通解则是：,7.2线性齐次递推关系,例求递推关系hn4hn-14hn-2的通解。分析首先给出它的特征方程x24x40它有2重根x2。因此，通解是hnHn(c1c2n)2n显然，在给递推关系的初始条件h0，h1的情况下，我们可以唯一确定c1与c2。,7.2线性齐次递推关系,例求递推关系满足初始条件h01，h10，h21，h32的解。分析特征方程为的特征根是1和2。其1的重数是3，,最后由h01,h10,h21,h32确定c1,c2,c3,c4即可。,7.3非齐次递推关系,7.3非齐次递推关系问题的关键是：1.确定相应齐次递推关系的通解；2.确定非齐次递推关系的一个特解；3齐次递推关系的通解和非齐次递推关系的一个特解求和，即得到非齐次递推关系的通解。,7.4生成函数,7.4生成函数如果一个函数g(x)的无穷级数是则称函数g(x)是无穷数列h0,h1,h2,hn,的生成函数。研究生成函数的目标是:对于给定的无穷数列h0,h1,h2,hn,我们期望求出该数列的生成函数的有限表示形式，从而将一个无穷数列所包含的全部信息浓缩在一个有限的代数函数之中。,7.4生成函数,例无穷序列1，1，1，1，的生成函数是因为g(x)的无穷展开式是,7.4生成函数,例设m是正整数。关于二项式系数的生成函数是即,7.4生成函数,例设是一个实数。关于二项式系数的生成函数是,7.4生成函数,例设k是整数，并且序列h0,h1,h2,hn,使得hn等于方程e1+e2+ekn的非负整数解的个数。由于所以序列h0,h1,h2,hn,的生成函数是即,7.4生成函数,例是什么样的序列的生成函数？设,7.4生成函数,例确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个n-组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在0和4之间，且至少要有一个梨。分析苹果可表示为香蕉可表示为橘子可表示为梨可表示为于是便是满足上述要