3-MathPreliminary1

1、第一章算法分析的数学基础生成函数 (母函数)在进行计数分析时， 常常会遇到递推方程，形如：an=Cn-1 *a n-1 + Cn-2*a n-2 + + Cr*ar (Cr 半 0)求解时有时需要使用生成函数的方法。e.g. Fibonacci 数列：满足关系 an=an-1+an-2该类数有很多好的性质)普通与指数生成函数 的定义：设ao, ai, a2,，an, 是某一数域实数，复数)上的 数的序列 ， W(x),i(k),是同一数域上2(x),n(x),相互独立的函数序列 ，则称函数F(x)=a 0 M(x)+ a是序歹U ao, ai, a2,a.,1 11l(x)+ a 2 p2(x

2、)+ a g(x)+的普通生成函数普母函数 )；称函数 G(x) =a+m(x)/n! +是序列ao, ai,a2, 的指数生成函数，ao M(x)/0! + a i (x)/" + a 2 p2(x)/2! +指母函数 ，和式形状类似于 ex 的展开形式)相互独立 ( independent )的函数序列：设 M0（X）,1（x）,2（x）,n（x）,是某一数域上的函数序列,（X的值以及 姝（X）（k=0,1,2,的值都在同一个数域中）任取姝(X)(k=0,1,2,0 P ,使得姝(x) =1）,不存在数域中的数0(X)+ - 2 皿(X)+ P 川P (x),即任何一个函数项姝（

3、X）不能被其它函数项线性表出。eg 1 , X , X2 , X3 ,序列与其生成函数之间没有1-1对应关系。xn, 是相互独立的，而1 , 1+X , 1-X , 1+X2, 1-X2,不是相互独立的, 1=1/2(1+x)+(1-x)。如使用第二个函数序列来构造普通生成函数，则序列1,0,0,0,和0,1/2,1/2,0,所对应的普通生成函数是相同的，函数序列的相互独立性保证了序列与其生成函数之间的1-1对应。生成函数的函数序列大多用1，x x2 x3 xn 在得到一个数列的生成函数之后，幕级数展开后xn前的系数就是数列的通项an。普通生成函数的 两种主要应用：1.解排列组合类问题2.求解

4、递归方程解排列组合类问题e.g. (1+x) nrci + cnx+cix2*+ c：xn (二项式定理)是序列c：，C：，c：的普通生成函数。令 x=-1,代入得 c：+C： + C4 + 二 c1n+c3 + cn + 。即从n个不同的物体中选取偶数个物体的方法数等于从n个不同的物体中选取奇数个物体的方法数。其它应用可参看组合数学/组合分析教材。求解递归方程a0=1 ，ai=1（边界条件），e.g. Fib on acci数 an=an-1+an-2则可以算出序列为1 , 1 , 2, 3, 5, 8,，an=?z i nn=0设 A(x)= W anx ,根据 an=an-1 +a n-

5、2 可有 anX =(a n-1+a n-2)X ,从2开始对等式两边分别求幕级数，得(an-1+an-2)Xncyn込an :n=2“由于艺 an x =A(x)-a 1x-a o，而c2(an-1+an-2)Xn =二 an-1X +: an-2Xn=x(A(x)-a o)+x 2A(x),二 A(x)-a ix-ao=x(A(x)-a o)+x2A(x),令 A(x)=z,则有z-x-1=x(z-1)+zx将 z 视为变量、 x 视为常量， 可解得：z=A(x)=1/(1-x-x2)。将 1/(1-x- x 2)作幂级数展开 后，xn 前的系数就是FibonaCCi 数列的通项 an。常

6、系数线性递归方程 (差分方程 )：Coan+C 1an-1+ +C ran-r =f(n)(*)(这里2e.g. 3a n-5a n-1+2a n-3 =n +5 线性：所有 ai 都是一次的。Co*Cr K0非线性：含有 ai2或如 aiaj 之类的乘积项。求解常系数线性递归方程Coan+Cian-l+c ran-r=f(n),需要 r 个连续的边界条件e.g. FibonaCCi 方程 r=2 ，求解该方程需要两个连续的边界条件。若 f(n) K,则称方程 Coan+cian-i +Cra n-r =f(n)是 非齐次的 ；若f(n)=0 ,则称方程Coan+Cian-l+C ran-r=

7、0是齐次的。类似于常微分方程，称 CoXr+ClXr-1+Cr=o （*）为方程Coa n+C ian-1 + +C ran-r =f(n)所对应的特征方程,求解方程Coan+Cian-l+Cran-r=f(n),有四个定理Th1 :若特征方程（*）恰有r个互不相同的特征根"1 , " 2 ,，r （即i K时有"i矜j），则齐次方程的通解（通常称为 齐通解，因解中含待定系数故称“通解”）斗A n . n. n为 an = A;。1 + A 2 + + ArS（AiAr为待定系数，可由r个连续的边界条件唯一确定）（将待定系数作为未知数，根据r个连续的边界条件可得r

8、个方程，方程的系数矩阵是范德蒙矩阵，其行列式值不为零，故有唯一解。a1a 21a2a 22a3a 23a4a 24ara 2ria2范德蒙矩阵之例:E.g. a n=an-1+an-2,边界条件 a0=a 1=1,特征方程为 x -x-1=0 两个（特征）根为"1 = （1+侖）/2，- 2=（1-/5）/2 ,互不相同,an= A1 0 1口 + A 2 2。把n=0和n=1的两个边界条件代入，得2个关于A1, A2的方程，算出 A1=（1+75）/（2 75），A2= - （1-/5）/（2/5）。（Fibo nacci数列的通项也可根据其生成函数展成的幕级数求出。）Th2 :若

9、"1，"旧-iO2是（*）方程的一对共扼复数根e和P e ，则这两个根对应解的部分为APncos（n y+BPnsin（n日）（A,B为实的待定系数）Eg2 :F述矩阵的行列式有an=a n-1 -an-2，00.010.00 0 11 1. 0 v0 0 0 . 1 1边界条件a1=1 , a2=0。特征方程为x2-x + 1=0 两个（特征）根为 1 = （1 + 73 i）/2 , 0 2=（1-点 i）/2 ,为一对共轭复数，由-1、2算出 p =1 , tg£=V3 , 0 = n /3,按 Th2，有 an =Apncos(n 日)+Bpnsin(n

10、日)=Acos(n n /3)+Bsin(nn /3)将边界条件a1=1 , a2=0代入，可得 A=1 , By3/3。Th3 :若-是(*)方程的k重根,贝卜对应的解的部分为cn + Czn" + C3nn + +Cknk- n(C1Ck为待定常数)Eg3 : an+6a n-1 +12a n-2 +8a n-3 =0 ,边界条件 ao=1 , a1=-2 , a2=8。特征方程为x3+6x2+12x+8=(x+2) 3=0 , a -2是三重根,由 Th3 知 an= (C1 + C2n + C 3n2)(-2)n,将边界条件ao=1 , a1=-2 , a2=8代入，可得 C

11、i=1 , C2=-1/2 , C3=1/2Eg4 :下述矩阵的行列式有an=2a n-1-an-2一阶矩阵：n阶矩阵为下图：对该矩阵所对应的行列式2100.0；1210.010 0 12 1. 0I按第一列的代数余子式展开计算，.1 2(20 0 . 0（n-1 阶）,11 0 . 01 0 . 0有 10 0 12 1. 01=2 I1 2 1. 010 0 0.10 . 1 2（n-1阶）.01. 0I =2a n-1 -00 . 1 2(n-2阶)1 0 . 01 2 1. 0I =2a n-1 -an-20 . 1 2故有an=2an-1 -an-2,即 an-2a n-1+a n-

12、2 =0 ,于是知，该递归方程所对应的特征方程为x2-2x+1=(x-1) 2=0 ,1是重根。易知边界条件有a1=2 , a2=3 ,由 Th3 知，an = (C1+ C2 n) * 1 n = (C1+ C2 n),用a1=2 , a2=3这两个边界条件，可求得C1= C2=1 ,丁"是有"an= n+1。另一计算方法：由 an -2a n-1+a n-2=0可得(a n-an-1 )-(a n-1-an-2 )=0，于是有(an-a n-1 )=(a n-1 -an-2 )。令 b n-1 = (a n -a n-1 )，贝9 b n-2 = (a n-1 -a n

13、-2 )， bn-1 =bn-2=bn-3 = =b1=a2-a1 = 1 ,即a1, a2,，an, 是一等差数列， an= a1+(n-1)d，由于 a1=2 , d=1 ,二 an= n+1。n-r=f(n)有f(n)巩非齐次),Th4 :若方程 coan+C1an-1 + + Cra个解(特解) ，且 q(n)是 coan+Cian-1 + +C ran-r=f(n)的则方程 Coan+Cian-1 + +Cran-r =f(n)的解为：方程的齐通解(含有待定系数) + q(n) (非齐特解) ，齐通解中的待定系数由边界条件唯一确定)Eg5 ：递归方程为 an+2an-1=n+3 ，边

14、界条件 a0=3。由上述方程及 ao=3，可算出ai=-2 , a2=9。于是特征方程为 x+2=0 ，特征根为 -2， f(n) 为 n+3 。故递归方程 an+2an-1=0 的齐通解为 A(-2) n，类似于常微分方程， 设非齐特解 q(n) 与 f(n) 同形 : q(n)=Bn+D ，将 q(n) 代入方程 an+2a n-1 =n+3 ，(q(n)代 an, q(n-1)代 an-i)得(Bn+D)+2(B(n-1)+D)=n+3于是有 3Bn+3D-2B=n+3 ，令 n=1 、2，根据递归方程和ai及a2，解得B=1/3 , D=11/9 ,故 an=A(-2) n+Bn+D=

15、A(-2) n+n/3+11/9 ，再由边界条件 ao=3，解得 A=16/9，于是 an=16/9(-2) n+n/3+11/9。Eg6 :递归方程为 an+2an-1+an-2=2n，则 f(n)为 2“;特征方程为x2+2x+1=(x+1) 2=0 ,特征根为-1 ,是二重根; 于是齐通解为(C1 + C 2n)(-1)n, C1、C2为两待定系数， 设特解 q(n) 与 f(n) 同形： q(n) =B2代入递归方程为则有 B(2n+2*2n-1+2n-2)=2n，解得B=4/9 ,于是an= (Ci+ C2 n)(-1) n+4/9*2 n，再由所给边界条件求出待定系数 C1、 C2

16、 (本题未给边界条件) 。找模式 ：给定一个数字串，再给定一个模式，从数字串第一个数字开始扫描，一旦在数字串中找到该模式， 则从下一位开始重新再找， 如扫到第 k 位时模式刚好找到， 则称该 模式在第 k 位出现e.g. 给定模式为 010 ，给定数字串为 110101010101 ，则模式 010 在(左起)第 5 、第 9 位出现，而第 7、第 11 位不是该模式出现。Eg7 ：求：在(左起) 第 n 位出现 010 的n 位二进制数序列有多少？解：设第 n位出现 010 的 n 位进序列共有 bn作如下考察：第 n 位出现 010 的序列必然形如XXXXXXXXX010 （X 有 n-3

17、 个）但并非此形状序列都是；如 7 位二进序列 1101010 就不满足条件。最右三位为 010 的 n 位二进制数序列共有 2n-3 个将其 分为两类 ：1.第n位出现010的n位二进序列，有bn个;2.第n位未出现010、形如XXXXXXXXX010 的位二进序列;考察：此类序列的n-1位为一，故010不可能在第n-1位出现，因此010必然是在序列的第n-2位出现（如010不在第n-2位出现， 则010就必在序列第n位出现，与本类序列的规定矛盾） 所有此类（即010未在其第n位出现）的n位二进序列都对应一个在序列的第 n-2位出现010的n-2位序列:,边界条件 b1=b2=0, b3=1

18、 ,2,-卄人，亠十、共有bn-2个；于是有: bn+bn-2=2n-3特征方程为x +1=0 ,两个（特征）根为7 1=i , 2=-i,为一对共轭复数，由2算出卩=1 ,日=n 12,于是其齐通解为 A/ncos(n日)+A2pnsin(n日)=A1cos(n n /2)+ Azlin(n n /2)设特解 q(n)与 f(n)同形：q(n)=B2 n-3，代入 bn+bn-2=2n'3 有 B2n-3+B2n-5=2n-3，于是有 B+B/4=1 ,解得 b=4/5, q(n)=4/5*2n-3二有 bn= A1cos(n n /2)+ A2Sin(n n /2)+4/5*2n-

19、3 ,代入边界条件 ( n=1,2 )b1=b 2=0 ，解得 A 1=2/5 ，A 2=-1/5 ，于是最终有 bn= 2/5cos(nn /2)1/5sin(nn /2)+4/5*2"3=1/5 (2cos(n n/2)-sin(n n/2)+2 n-1)。注意： 并不是所有情况下都能假定特解q(n) 与 f(n) 同形 。Eg8: a n=an-1+2(n-1) ，边界条件 a1=2，a2=4， 依递推式算出 a0=2。特征方程 x-1=0 ，特征根为 1 ，则齐通解为 A*1 n=A。设特解 q(n) 与 f(n) 同形： q(n)=Bn+D ，代入 an= an-1+2(n-1) ，得 Bn+D=B