组合数学第六章递推关系

第六章递推关系,递推关系是一种重要的组合计数方法,建立递推关系分析已有递推关系的性质求解递推关系,主要内容6.1递推关系的建立6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4*用生成函数求解递推关系6.5*用迭代归纳法求解递推关系及其应用,递推关系的定义递推关系的实例常系数线性齐次递推关系及其求解常系数线性非齐次递推关系及其求解,（1）等差数列（算术数列）h0,h0+q,h0+2q,h0+nq,递推关系：hn=hn-1+q一般项：hn=h0+nq前n+1项和：sn=(n+1)h0+q(n)(n+1)/2（2）等比数列（几何数列）h0,qh0,q2h0,qnh0,递推关系：hn=qhn-1一般项：hn=qnh0前n+1项和：sn=h0(1-qn+1)/(1-q),定义6.1.1给定一个数的序列H(0),H(1),H(n),若存在正整数n0，使得当nn0时，可以用等号(或小于，大于号)把H(n)和前面某些项H(i)，0in，联系起来，这样的式子叫做递推关系。递推关系也称递归关系，递归方程。从本质上讲，递推关系是研究整变量函数的或者说是研究数列的，与此对应的是连续论域中的微分方程。因此，我们可以类似的方法对它们进行研究。,利用递推关系和初值在某些情况下可以求出序列的通项表示式H(n)。但是对于大多数递推关系，目前还解不出H(n)的显式来，即使这样，对于给定的n也可以从初值开始，一步一步地计算出H(n)的值或者范围，而H(n)一般代表了某个组合计数问题的解，因此递推关系是组合计数的重要工具，同时也是算法分析的重要手段。,求解递推关系的常用方法（1）迭代归纳法；（2）特征根法；（3）生成函数法；,例6.1.1（爬楼梯问题）一个小孩要爬上n阶楼梯，每次可上一阶或两阶，问上n阶有多少种上法？解：,显然登上1阶台阶有1种方法，登上2台阶有2种方法，f(1）=1，f(2)=2,称为递推关系的初始条件。设有f(n)种方法，要登上这n阶台阶，最后迈上一个台阶或两个台阶完成.（1）若最后是迈上一个台阶完成的，则前面登上了n-1阶台阶，有f(n-1)种方法；（2）若最后是迈上两个台阶完成的，则前面登上了n-2阶台阶，有f(n-2)种方法，根据加法原理有递推关系：f(n)=f(n-1)+f(n-2).,例6.1.2Fibonacci数列问题是一个古老的数学问题，是于1202年提出的，问题表述如下:把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。问一年后围栏中有多少对兔子？这是一个数学模型的形象表示，不能真正用来表示兔子的繁殖规律。,对于n=1,2,令f(n)表示第n个月开始时围栏中的兔子对数，显然有f(1)=1,f(2)=2。在第n个月的开始，那些第n-1个月初已经在围栏中的兔子仍然存在，而且每对在第n-2个月初就存在的兔子将在第n-1个月开始将要生出一对新兔来，所以有：f(n)=f(n-1)+f(n-2)(n3,n为整数)f(1)=1,f(2)=2这是一个带有初值的递推关系。,如果规定f(0)=1,则上式变成：f(n)=f(n-1)+f(n-2)(n2,n为整数)f(0)=1,f(1)=1称满足这个式子的数列就成为Fibonacci数列，数列中的项叫做Fibonacci数.,例6.1.3（Hanoi塔问题）现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.1.1所示，要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上，问至少要搬多少次？,解：记f(n)为n个圆盘从A柱搬到C柱所需的最小次数.整个搬运过程可分成三个阶段；（1）将套在A柱上面的n-1个圆盘从A柱按要求搬到B柱，搬动次数为f(n-1);（2）把A柱上最下面的那个圆盘搬到C柱上，搬动次数为1;（3）把B柱上的n-1个圆盘按要求搬到C柱上，搬动次数为f(n-1);由加法原则知，f(n)=2f(n-1)+1又显然f(1)=1，所以有如下带有初值的递推关系:f(n)=2f(n-1)+1f(1)=1,解：信道上能够传输的长度为n的字符串可分成四类：（1）最左字符为b；（2）最左字符为c；（3）最左两个字符为ab；（4）最左两个字符为ac。前两类字符串分别有f(n-1)个，后两类字符串分别有f(n-2)个，容易求出f(1)=3，f(2)=8，从而得到,例6.1.4在信道上传输由a,b,c三个字母组成的长为n的字符串，若字符串有两个a连续出现，则信道就不能传输，令f(n)表示信道可以传输的长为n的字符串的字数，求f(n)满足的递推关系。,f(n)=2f(n-1)+2f(n-2)n3f(1)=3，f(2)=8,例6.1.5设P是平面上n个连通区域D1,D2,Dn的公共交界点，如下图所示。现用k种颜色对其着色，要求有公共边界的相邻区域着以不同的颜色，令f(n)表示不同的着色方案数，求它所满足的递推关系。,有：f(n)=(k-1)f(n-2)+(k-2)f(n-1)n4f(2)=k(k-1)，f(3)=k(k-1)(k-2),6.2常系数线性齐次递推关系的求解,设k是给定的正整数，若数列的相邻k+1项间满足关系对成立，其中k阶线性递推关系k阶常系数线性递推关系k阶常系数线性齐次递推关系递推关系的解如果一个数列满足以上递推关系,常系数线性齐次递推关系的一般形式为-(6.2.2),递推关系的特征方程方程xk-c1xk-1-c2xk-2-ck=0递推关系的特征根特征方程的k个根q1，q2qk(可能有重根)，其中qi(i=1,2,k)是复数。递推关系的解与特征根的关系？,引理6.2.1设q是非零复数.则f(n)=qn是常系数线性齐次递推关系的解，当且仅当q是它的特征根.证明设f(n)=qn是递推关系(6.2.2)的解，即因为，所以即是递推关系的特征根，反之亦然.如果qn是常系数线性齐次递推关系的解，还有吗？如果有，那么是否可以特征根构造递推关系的所有解？即从特解如何构造通解？,引理6.2.2如果都是递推关系（6.2.2）的解，是常数，则也是递推关系（6.2.2）的解.证明因为都是递推关系（6.2.2）的解，所以=从而也是递推关系(6.2.2)的解.,由引理6.2.1和引理6.2.2知，若q1，q2，qk是递推关系6.2.2的特征根，则f(n)b1q1nb2q2nbkqkn是递推关系的解.（b1,b2,bk是常数）,定义6.2.3如果对于递推关系（6.2.2）的每个解h(n)，都可以选择一组常数，使得成立，则称f(n)b1q1nb2q2nbkqkn是递推关系（6.2.2）的通解，其中，为任意常数。,定理6.2.1设是递推关系（6.2.2）的个互不相等的特征根，则f(n)b1q1nb2q2nbkqkn是递推关系（6.2.2）的通解。证明由前面的分析可知,f(n)是递推关系(6.2.2)的解.设h(n)是这个递推关系的任意一个解，则由k个初值h(0)=a0,h(1)=a1,.,h(k-1)=ak-1唯一地确定，所以有(6.2.4),如果方程组（6.2.4）有唯一解，这说明可以找到这k个常数，使得h(n)b1q1nb2q2nbkqkn成立，从而b1q1nb2q2nbkqkn是该递推关系的通解.考察方程组（6.2.4），它的系数行列式为这是著名的Vandermonde行列式.因为互不相等，所以该行列式不等于零，这也就是说方程组（6.2.4）有唯一解.,常系数线性齐次递推关系的求解步骤根据题意求递推关系利用递推关系得到特征方程解特征方程，求特征根利用特征根写递推关系通解根据初值确定通解中的系数给出递推关系的解关于微分方程求解的已知结论:对于4次以及4次以下的方程,目前已有代数解法.(在复数域内求解)阿贝尔定理:5次以及更高次的代数方程没有一般的代数解法.,例6.2.1求Fibonacci数的递推关系,例6.2.2,例6.2.3,由定理6.2.1，可知3n是此递推关系的解（不考虑初值），我们不妨试一试n3n，将其带入此递推关系。,这说明n3n也是递推关系的解，而且与线性3n无关，所以原递推关系的通解为,代入初值，得：,设递推关系的特征方程为令,如果q是P(x)=0的二重根，这q也是Pn(x)=0的二重根，也是Pn(x)=0的根，Pn(x)是Pn(x)的微商，即,因此，q也是xPn（x）=0的根，而,代入x=q，得,这说明nqn是原递推关系的解。可以证明以下的结论：如果q是P(x)=0的e重根,则qn,nqn,n2qn,ne-1qn都是原递推关系的解.,定理6.2.2设q1，q2，qt是递推关系f(n)=a1f(n-1)+a2f(n-2)+akf(n-k)(nk，ak0),的不相等的特征根，其重数分别为e1，e2，et(e1+e2+et=k),则这个递推关系的通解是：f(n)=f1(n)+f2(n)+ft(n)其中：fi(n)c1qinc2nqin,例6.2.5.求解递推关系,对,对,通解为,解方程组，得c1=5,c2=2,c3=-4所以原递推关系的解为f（n)=5*2n+2n*2n-4*3n,一般形式：f(n)=c1f(n-1)+c2f(n-2)+ckf(n-k)+g(n)(nk,ck0,g(n)0),其通解是齐次通解与特解之和，即f(n)=f(n)+f(n)其中f(n)是原递推关系的特解；f(n)是所对应的齐次递推关系f(n)=c1f(n-1)+c2f(n-2)+ckf(n-k)的通解。下面主要介绍f(n)的求解方法。,6.3常系数线性非齐次递推关系的求解,对于一般g(n)没有普遍的解法，只对一些简单的情况可以用待定系数法求f(n)。,一般方法总结:求齐次关系的一般解求非齐次关系的一个特解将一般解和特解结合,通过初始条件确定一般解中出现的常系数值.,比较等式两边,例6.3.1求解递推关系,解：因为4不是特征方程的根，所以该递推关系的非齐次特解为,，将其代入递推关系，得,的系数，得,从而a=2.,而相应