第06-07讲 组合数学——递推关系

第6-7讲递推关系,递推关系的定义递推关系的建立递推关系的求解常系数线性齐次递推关系求解非齐次递推关系的求解非线性递推关系的求解母函数解递推方程,递推关系的定义,定义对数列ai|i0和任意自然数n，一个关系到an和某些ai(in)的方程，称为递推关系。记作F(a0,a1,a2,an)=0初始条件a0=d0,a1=d1,.,ak=dk举例：汉诺塔问题,初始条件的个数与递推关系的阶相等,1块盘子问题,an-1块盘子问题,第6-7讲递推关系,递推关系的定义递推关系的建立递推关系的求解常系数线性齐次递推关系求解非齐次递推关系的求解非线性递推关系的求解母函数解递推方程,递推关系的建立,例1有一个小孩要爬上有n个台阶的楼梯，他一步可以爬一个台阶或者两个台阶。这个小孩爬上这n个台阶楼梯的不同方法的数目记作an，求an的递推关系。解：,例2设平面上有n条直线，其中每对直线都相交，但任意三条直线都不交于一点。这样的n条直线把平面分成的区域个数记作an，求an的递推关系。解：,递推关系的建立,例3在信道上传输由a,b,c三个字母组成的长为n的字符串，若字符串中有两个a连续出现，则信道就不能传输。令an表示信道可以传输的长为n的字符串的个数，求an满足的递推关系。解：,递推关系的建立,例4把n个相同的球放入k个不同盒子中，每个盒子中的球不少于2个又不多于4个。其不同的放法的数目记作an,k，求an,k的递推关系，如果这n个球取自3种颜色的球如何？解：,递推关系的建立,例5用an表示包含偶数个0和偶数个1的n位三进制序列的个数，用bn表示包含偶数个0和奇数个1的n位三进制序列的个数，用cn表示包含奇数个0和偶数个1的n位三进制序列的个数。求关于an,bn,cn(n=1,2.)的递推关系。解：,递推关系的建立,例6平面上有一点P，它是n个区域D1,D2,.Dn的共同交界点，现取k种颜色对n个区域着色，要求相邻区域着不同的颜色，试求着色方案。解：,递推关系的建立,r阶递推关系的一般形式,若e(n)=0，称其为齐次递推关系式若e(n)0，称其为非齐次递推关系式当ci(n)=ci时（i=1,2,r）称为常系数递推关系,第6-7讲递推关系,递推关系的定义递推关系的建立递推关系的求解常系数线性齐次递推关系求解非齐次递推关系的求解非线性递推关系的求解母函数解递推方程,递推关系的求解,经典解法母函数解法迭代法置换法归纳法相加削去法,常系数齐次线性递推关系,一般形式：特征方程：,（式1）,引理1,设m是非零实数或复数，则mn是递推关系式的解的充要条件是：m是上述递推关系式1的特征方程的特征根。,引理2,如果an1,an2都是递推关系式的解，B1,B2是常数，则B1an1+B2an2也是上述递推关系式1的解。,定理,若m1,m2,mr是特征方程的特征根，B1,B2,Br是常数，则也是上述递推关系式1的解。,定义,如果递推关系式1的每个解ans都可以选择一组常数B1,B2,Br使得成立，则称是递推关系式1的通解，其中：B1,B2,Br是任意常数。,无重特征根,定理：设m1,mr是递推关系式1的r个互不相等的特征根，则：是递推关系式1的通解。,有重特征根,定理：设m1,m2,mi是递推关系式1的全部互不相等的特征根，其重数分别为e1,e2,ei(e1+e2+ei=r)则递推关系式对应mi部分的通解是：而递推关系式1的通解为：,递推关系求解过程,列出特征方程对特征方程进行求解根据特征根写出通解根据初始条件确定待定系数,常系数齐次线性递推关系的求解,例7an-3an-1+3an-2-an-3=0,且a0=0,a1=1,a2=3,求an=?解：例810个数字(09)和4个运算符(+,-,)组成14个元素，求由其中的n个元素构成的排列组成的算术表达式的个数（含除数为0的情况）解：,例9n阶行列式,常系数齐次线性递推关系的求解,定理,r阶线性常系数非齐次递推关系的通解an是该非齐次递推关系的一个特解anp，加上其相应的齐次递推关系的通解anc即,多项式型非齐次递推关系,一般形式定理：当l是相应的齐次递推关系的k重特征根时（若l不是该齐次递推关系的根时，k=0）是该非齐次递推关系的一个特解。,求解过程求齐次递推关系的通解求非齐次递推关系的特解列出非齐次递推关系的通解形式根据初始条件确定待定系数,多项式型非齐次递推关系,例10an=2an-1+1,a1=1解：例11an=an-1+2(n-1),a0=2,求an=?解：,多项式型非齐次递推关系,指数型非齐次递推关系,一般形式定理：当b是对应的齐次递推关系的k重特征根时（若b不是特征根，则k=0）该非齐次递推关系的