离散组合数学2线性齐次递推关系

1、离散数学组合数学 2 / 26序列/数列 sequence of numberfnnN: f0, f1, f2, , fn, fn+1, 若 f : NR, 令 fn = f (n) , 可得数列fnnN数列是以自然数集N (或它的子集) 为定义域的函数, 是一列有序的数. 数列中的每一个数都叫做这个数列的项. 排在第一位的数称为该数列的第1项 (首项), , 排在第n位的数称为该数列的第n项, 常用fn表示.通项公式: 数列的第n项fn与项的序数n之间的关系可以用一个公式fn= f (n)来表示, 这个公式叫做该数列的通项公式 3 / 26序列/数列 通项公式fnnN: f0, f1, f2

2、, , fn, fn+1, 三角形点阵序列 f1=1, f2=3, f3=6, , fn, fn = n(n+1)/2, n1正方形点阵序列 f1=1, f2=4, f3=9, , fn, fn = n2, n1银行存款 fn = 存款数额(1+年利率)n斐波那契数列 f0=f1=1, f2=2, f3=3, f4=5, , fn, fn = f (n) = ? 4 / 26序列/数列 递推公式/递推关系fnnN: f0, f1, f2, , fn, fn+1, 斐波那契数列 f0=f1=1, f2=2, f3=3, f4=5, , fn, fn = fn2+fn1 , n2递推公式: 如果数

3、列fnnN的第n项与它前一项或几项的关系可以用一个式子来表示, 那么这个公式叫做该数列的递推公式(递推关系). 5 / 26序列,递推关系,初值,通解,解fn = fn2 + fn1 , n2f0 =1, f1 =1f0 =2, f1 =5fn = fn2 + fn1 , n22, 5, 7, 12, 19, 序列递推关系初值/初始条件1, 1, 2, 3, 5, 序列递推关系通项公式/解通项公式/解初值/初始条件通解任意指定c1, c2, 则fn确定一个序列nNnN 6 / 26递推关系与递归定义一个序列的递归定义指定了一个或多个初始的项以及一个由前项确定后项的规则(递归关系). 在递归和递

4、推关系之间存在重要的联系. 递归算法依据较小规模的同一问题的一个或者多个实例的解得到规模为n的问题的解. 因此, 当分析一个递归算法的复杂性时, 可以得到一个递推关系, 它把求解规模为n的问题需要的运算次数用求解一个或多个小规模实例的同一问题所需要的运算次数来表示. 7 / 26序列/数列示例集合S=a1, a2, , an的r组合数, rN集合S=a1, a2, , an的r排列数, rN多重集S=n1a1, n2a2, , nkak的r组合数, rN多重集S=n1a1, n2a2, , nkak的r排列数, rNS给定的情况下, n = n1+n2+nk. 令br表示S的r组合数, cr表

5、示S的r排列数序列brr0: b0, b1, b2, , bn, 0, 0, 序列crr0: c0, c1, c2, , cn, 0, 0, 8 / 26序列/数列示例续顺序插入排序归并排序快速排序令fn表示规模为n时需要的基本运算次数序列fnn1: f1, f2, , fn, 9 / 26序列/数列示例续包含偶数个0的n位十进制数字串有多少个?不包含两个连续0的n位二进制位串有多少个?Hanoi塔 把n个盘子从A柱移到C柱需要多少次移动?找一个长度为n的序列的最大和最小元需多少次比较?二分搜索 规模为n时需要多少次比较?整数的快速乘法 2个n位二进制整数相乘快速矩阵乘法 2个n阶矩阵相乘n个

6、点中最接近点对问题计数1,2,n放入堆栈后的不同的输出个数令fn表示规模为n时需要的基本运算次数序列fnn1: f1, f2, , fn, 10 / 26序列/数列示例续n+1个数的乘积x0 x1x2xn中加括号来规定乘法的次序的方式数错位排列多项式x(x1)(x2)(xn+1)的展开式xr系数将给定的正整数n表示成若干个正整数之和.四种情况: 有序/无序, 不重复/重复x1+x2+xk=n非负整数解的个数令fn表示规模为n时的方式数序列fnn1: f1, f2, , fn, 11 / 26递推关系与生成函数递推关系 通解递推关系 + 初值 通解 + 初值 解(通项公式) 用形式幂级数(生成函

7、数)f0 x0+f1x1+f2x2+f3x3+求解计数问题, 其中xn的系数fn代表我们感兴趣的序列的项. 生成函数还可用于求解递推关系以及证明组合恒等式. 12 / 26用递推关系构造模型例 对于不含2个连续0的n位二进位串的个数找出递推关系和初始条件. 有多少个这样的5位二进位串?.01n位串 ann-1位串 an-111n-2位串 an-20解 令an表示满足条件的n位串的个数an =a1=2, a2=3a3=5, a4=8, a5=13按第n位的值分2类处理an1+ an2, n3 13 / 26用递推关系构造模型续例 编码字的枚举 一个计算机系统把一个十进制数字串作为一个编码字, 如

8、果它包含偶数个0, 就是有效的. 设an是有效的n位编码字的个数, 找出一个关于an的递推关系. 解令an表示n位有效编码的个数按第n位的值(0,1,2,9)分10类处理an = 9an1+(10n1an1) = 8an1+10n1, n2a1=9, a2=82 14 / 26例例 Hanoi塔 从A柱将这些圆盘移到C柱上去. 如果把一个圆盘从一个柱子移到另一个柱子称作一次移动, 在移动和放置时允许使用B柱, 但不允许大圆盘放到小圆盘的上面. 问把所有的圆盘的从A移到C总计需要多少次移动?解 设移动n个盘子的总次数为T(n)T(n) = 2T(n1) +1, T(1)=1 15 / 26例例

9、插入排序解 设排序(升序) n 个数比较次数为W(n)aw(n)w(n-1)pW(n) = W(n1) + n1, W(1)=0 16 / 26例例 归并排序(分治算法)解W(n) = 2W(n/2) + n1, W(1)=0W(n)W(n/2)W(n/2)pq13682457 17 / 26Catalan数例 求关于Cn的递推关系, 其中Cn是通过对n+1个数的乘积 a0 1 a1 2 a2 3 k-1 ak-1 k ak k+1 n an中加括号来规定乘法的次序的方式数.解 按最后一次计算的乘号k分n类处理(1kn). 第k类: k出现在ak-1和ak之间, 即先计算a0 1 a1 2 k

10、-1 ak-1, 再计算ak k+1 ak+1 k+2 n an, 最后计算k.分步处理: 1.计算a0 1 a1 2 k-1 ak-1, 方式数Ck-12.计算ak k+1 ak+1 k+2 n an, 方式数Cn-k 18 / 26Catalan数续定义 一个凸n+1边形, 通过不相交于n+1边形内部的对角线把n+1边形划分成三角形, 划分方案个数记作hn, 称为Catalan数. 如h2=1, h4=5递推方程: 考虑n+1边形, 端点A1,An+1的边记为a, 对于任意的k=1,2,n1, 以Ak+1A1为边, An+1Ak+1为另一边, 与a构成三角形T, T将多边形划分成R1和R2

11、两个部分, 分别为k+1边形和nk+1边形.递推方程 19 / 26线性递推关系模型中递推关系很多. 某些递推关系可以用迭代或者其他的特定技术求解. 但是, 有一类重要的递推关系可以用一种系统的方法明确地求解. 在这种递推关系中, 序列的项由它的前项的线性组合来表示.定义 一个常系数k阶线性齐次递推关系是形如an = c1an1 + c2an2 + + ckank的递推关系, 其中c1,c2,ck是实数, ck0.线性: an是若干序列前项的线性组合齐次: 出现的各项都是aj (1次方)的倍数, 序列各项的系数都是常数而不是依赖于n的函数 k阶: 因为an由序列中其前面的k项来表示. 20 /

12、 26求解常系数线性齐次递推关系定理 an= rn 是递推关系 an=c1an1+c2an2+ckank 的解, 当且仅当 rn = c1rn1+c2rn2+ckrnkrkc1rk1c2rk2ck1rck = 0 (*)(*)式叫做该递推关系的特征方程. 方程的解叫做递推关系的特征根. 可以用这些特征根给出这种递推关系的所有解( 通解 ). 21 / 26定理 设c1,c2,ckR, 方程rkc1rk1ck=0有t个不等的根 r1, r2 , rt , 其重数分别为 m1, m2, , mt, 满足mi1, i=1,2,t, 且m1+m2+mt=k. 则序列an是递推关系an=c1an1+c2

13、an2+ckank的解, 当且仅当求解常系数线性齐次递推关系续例 方程r3+r2r1 = (r1)(r+1)2 = 0根与重数r1 = 1, m1 = 1; r2 = -1, m2 = 2注意: 该定理提到的解是具体的序列, 此时所有的系数bi,j必须确定在没有初值的情况下, 求出通解即可, 此时bi,j是任意的实数 22 / 26求解常系数线性齐次递推关系续定理 设c1和c2是实数. 假设 r2c1rc2=0 有两个不同的根r1和r2, 则序列an是递推关系an=c1an1 +c2an2的解, 当且仅当 an=b1r1n+b2r2n, n0, b1和b2是常数.充分性b1r1n+b2r2n

14、= c1(b1r1n-1+b2r2n-1) + c2(b1r1n-2+b2r2n-2)b1r1n-2(r12c1r1c2) + b2r2n-2(r22c1r2c2) = 0必要性: a0 = b1+b2b1 = (a1a0r2) / (r1r2)a1 = b1r1+b2r2b2 = (a0r1a1) / (r1r2)注意: 证明必要性时, 确定两个常数b1和b2的表达式依赖于r1r2的事实, 因此, 当r1=r2时, 这个定理不成立. 23 / 26求解常系数线性齐次递推关系续定理 设c1和c2是实数, c20. 假设 r2c1rc2=0 有二重根r. 则序列an是递推关系an=c1an1+c2an2的解, 当且仅当 an= b1rn+b2n