第06_07讲组合数学——递推关系.ppt

第6-7讲 递推关系;递推关系的定义;第6-7讲 递推关系;递推关系的建立;例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 阶递推关系的一般形式;第6-7讲 递推关系;递推关系的求解;常系数齐次线性递推关系;引理1;引理2;定理;定义;无重特征根;有重特征根;递推关系求解过程;常系数齐次线性递推关系的求解;例9 n阶行列式 ;定理;多项式型非齐次递推关系;求解过程 求齐次递推关系的通解 求非齐次递推关系的特解 列出非齐次递推关系的通解形式 根据初始条件确定待定系数;例10 an=2an-1+1, a1=1 解： 例11 an=an-1+2(n-1), a0=2, 求an =? 解：;指数型非齐次递推关系;例12 an-2an-1=2n-1, a1=3 解： 例13 求n位十进制正整数中出现偶数个5的个数 解：;求n位二进制数最后三位出现010图像的个数。 参考答案：