3MathPreliminary1.doc

第一章 算法分析的数学基础生成函数（母函数）在进行计数分析时，常常会遇到递推方程，形如：an=cn-1*an-1 + cn-2*an-2 + + cr*ar (cr0) 求解时有时需要使用生成函数的方法。e.g. Fibonacci数列：满足关系an=an-1+an-2（该类数有很多好的性质）普通与指数生成函数的定义： 设a0，a1，a2，an，是某一数域（e.g. 有理数，实数，复数）上的数的序列，0(x), 1(x), 2(x), ,n(x), 是同一数域上相互独立的函数序列，则称函数F(x)=a00(x)+ a11(x)+ a22(x)+ + ann(x)+ 是序列 a0，a1，a2，an，的普通生成函数（普母函数）；称函数G(x) = a00(x)/0! + a11(x)/1! + a22(x)/2! + +ann(x)/n! + 是序列a0，a1，a2，的指数生成函数，（指母函数，和式形状类似于ex的展开形式）相互独立（independent）的函数序列：设0(x), 1(x), 2(x), ,n(x), 是某一数域上的函数序列，（x的值以及k(x)（k=0,1,2, ）的值都在同一个数域中）任取k(x)（k=0,1,2, ），不存在数域中的数a1，a2，ap，使得k (x) = a1i1(x) + a2i2(x) + + apip(x) ，即任何一个函数项k(x)不能被其它函数项线性表出。e.g. 1，x，x2，x3，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-1对应。生成函数的函数序列大多用1，x，x2，x3，xn，在得到一个数列的生成函数之后，幂级数展开后xn前的系数就是数列的通项an。普通生成函数的两种主要应用：1. 解排列组合类问题 2. 求解递归方程解排列组合类问题e.g. (1+x)n=+x+x2+xn（二项式定理）是序列，的普通生成函数。令x=-1,代入得+ +=+ 。即从n个不同的物体中选取偶数个物体的方法数等于从n个不同的物体中选取奇数个物体的方法数。 其它应用可参看组合数学/组合分析教材。求解递归方程 e.g. Fibonacci数an=an-1+an-2 a0=1，a1=1(边界条件)，则可以算出序列为1，1，2，3，5，8，an=?设A(x)=, 根据an=an-1+an-2可有anxn=(an-1+an-2)xn,从2开始对等式两边分别求幂级数，得=(an-1+an-2)xn。由于=A(x)-a1x-a0，而(an-1+an-2)xn=an-1xn+an-2xn=x(A(x)-a0)+x2A(x),A(x)-a1x-a0=x(A(x)-a0)+x2A(x),令A(x)=z, 则有z-x-1=x(z-1)+zx2。将z视为变量、x视为常量，可解得：z=A(x)=1/(1-x-x2)。将1/(1-x- x2)作幂级数展开后，xn前的系数就是Fibonacci数列的通项an。常系数线性递归方程(差分方程)：c0an+c1an-1+cran-r=f(n) (*) (这里c0*cr0) e.g. 3an-5an-1+2an-3=n2+5线性：所有ai都是一次的。非线性：含有ai2或如aiaj之类的乘积项。求解常系数线性递归方程c0an+c1an-1+cran-r=f(n)，需要r个连续的边界条件 e.g. Fibonacci方程 r=2，求解该方程需要两个连续的边界条件。若f(n)0，则称方程c0an+c1an-1+cran-r=f(n)是非齐次的；若f(n)=0，则称方程c0an+c1an-1+cran-r=0是齐次的。类似于常微分方程，称c0xr+c1xr-1+cr=0 (*) 为方程c0an+c1an-1+cran-r=f(n)所对应的特征方程，求解方程c0an+c1an-1+cran-r=f(n)，有四个定理。Th1：若特征方程(*)恰有r个互不相同的特征根a1，a2，ar (即ij时有aiaj)，则齐次方程的通解（通常称为齐通解，因解中含待定系数故称“通解”）为an = A1a1n + A2a2n + + Ararn （A1Ar为待定系数，可由r个连续的边界条件唯一确定）（将待定系数作为未知数，根据r个连续的边界条件可得r个方程，方程的系数矩阵是范德蒙矩阵，其行列式值不为零，故有唯一解。）范德蒙矩阵之例： E.g. an=an-1+an-2,边界条件a0=a1=1,特征方程为x2-x-1=0 两个(特征)根为a1(1+)/2，a2=(1-)/2，互不相同，an= A1 a1n + A2 a2n。把n=0和n=1的两个边界条件代入， 得2个关于A1, A2的方程，算出A1=(1+)/(2)，A2= - (1-)/(2)。 （Fibonacci数列的通项也可根据其生成函数展成的幂级数求出。）Th2：若a1，a2是(*)方程的一对共扼复数根r和r，则这两个根对应解的部分为Arncos(nq)+Brnsin(nq) (A,B为实的待定系数)Eg2：下述矩阵的行列式有an=an-1-an-2，边界条件a1=1，a2=0。特征方程为x2-x+1=0 两个(特征)根为a1(1+i)/2，a2=(1-i)/2，为一对共轭复数，由a1、a2算出r=1，tgq=，q=/3， 按Th2，有an=Arncos(nq)+Brnsin(nq)= Acos(n/3)+Bsin(n/3)， 将边界条件a1=1，a2=0代入，可得A=1，B=/3。Th3：若a是(*)方程的k重根，则a对应的解的部分为C1an + C2nan + C3n2an + +Cknk-1an (C1Ck为待定常数)Eg3：an+6an-1+12an-2+8an-3=0，边界条件a0=1，a1=-2，a2=8。 特征方程为x3+6x2+12x+8=(x+2)3=0，-2是三重根，由Th3知an= (C1 + C2n + C3n2)(-2)n，将边界条件a0=1，a1=-2，a2=8代入， 可得C1=1，C2=-1/2，C3=1/2Eg4：下述矩阵的行列式有an=2an-1-an-2一阶矩阵： 二阶矩阵：三阶矩阵210 221121 12012n阶矩阵为下图：对该矩阵所对应的行列式按第一列的代数余子式展开计算，有=2-=2an-1-=2an-1-an-2故有an=2an-1-an-2，即an-2an-1+an-2=0，于是知，该递归方程所对应的特征方程为x2-2x+1=(x-1)2=0，1是二重根。易知边界条件有a1=2，a2=3，由Th3知，an = (C1+ C2 n) * 1n = (C1+ C2 n)，用a1=2，a2=3这两个边界条件，可求得C1= C2=1，于是有an= n+1。另一计算方法：由an-2an-1+an-2=0可得(an-an-1)-(an-1-an-2)=0，于是有(an-an-1)=(an-1-an-2)。令bn-1 = (an-an-1)，则bn-2 = (an-1-an-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。Th4：若方程c0an+c1an-1+cran-r=f(n)有f(n)0(非齐次)，且q(n)是c0an+c1an-1+cran-r=f(n)的一个解（特解），则方程c0an+c1an-1+cran-r=f(n)的解为：方程的齐通解（含有待定系数）+ q(n) （非齐特解）， （齐通解中的待定系数由边界条件唯一确定）。Eg5：递归方程为an+2an-1=n+3，边界条件a0=3。 由上述方程及a0=3，可算出a1=-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+2an-1=n+3，（q(n)代an，q(n-1)代an-1）得(Bn+D)+2(B(n-1)+D)=n+3，于是有3Bn+3D-2B=n+3，令n=1、2，根据递归方程和a1及a2，解得B=1/3，D=11/9，故an=A(-2)n+Bn+D=A(-2)n+n/3+11/9，再由边界条件a0=3，解得A=16/9，于是an=16/9(-2)n+n/3+11/9。Eg6：递归方程为an+2an-1+an-2=2n，则f(n)为2n；特征方程为x2+2x+1=(x+1)2=0，特征根为-1，是二重根；于是齐通解为(C1+ C2n)(-1)n，C1、C2为两待定系数，设特解q(n)与f(n)同形：q(n) =B2n 代入递归方程为则有B(2n+2*2n-1+2n-2)=2n，解得B=4/9， 于是an= (C1+ C2 n)(-1)n+4/9*2n，再由所给边界条件求出待定系数C1、C2（本题未给边界条件）。找模式：给定一个数字串，再给定一个模式，从数字串第一个数字开始扫描，一旦在数字串中找到该模式，则从下一位开始重新再找，如扫到第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个）但并非此形状序列都是；如7位二进序列1101010就不满足条件。最右三位为010的n位二进制数序列共有2n-3个，将其分为两类：1. 第n位出现010的n位二进序列，有bn个；2. 第n位未出现010、形如XXXXXXXXX010的n位二进序列；考察：此类序列的n-1位为一，故010不可能在第n-1位出现，因此010必然是在序列的第n-2位出现（如010不在第n-2位出现，则010就必在序列第n位出现，与本类序列的规定矛盾）。所有此类（即010未在其第n位出现）的n位二进序列都对应一个在序列的第n-2位出现010的n-2位序列：共有bn-2个；于是有：bn+bn-2=2n-3，边界条件b1=b2=0，b3=1， 特征方程为x2+1=0，两个(特征)根为a1=i，a2=-i，为一对共轭复数，由a1、a2算出r=1，q=/2，于是其齐通解为A1rncos(nq)+A2rnsin(nq)= A1cos(n/2)+ A2nsin(n/2)，设特解q(n)与f(n)同形：q(n)=B2n-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/2)+ A2sin(n/2)+4/5*2n-3，代入边界条件（n=1,2）b1=b2=0，解得A1=2/5，A2=-1/5，于是最终有bn= 2/5cos(n/2)-1/5sin(n/2)+4/5*2n-3=1/5（2cos(n/2)-sin(n/2)+2n-1）。注意：并不是所有情况下都能假定特解q(n)与f(n)同形。Eg8: an=an-1+2(n-1)，边界条件a1=2，a2=4，依递推式算出a0=2。特征方程x-1=0，特征根为1，则齐通解为A*1n=A。设特解q(n)与f(n)同形：q(n)=Bn+D， 代入an= an-1+2(n-1)，得Bn+D=B(n-1)+D+2(n-1)，即0=2(n-1)-B，得出B= n-2，不符合题意。原因是：只有1这个根，造成通解中不含n。如设q(n)=Bn2+Cn，代入an= an-1+2(n-1)，得Bn2+Cn= B(n-1)2+C(n-1)+2(n-1)，于是有0=B-2Bn-C+2(n-1)，将n=1及n=2代入上式，可得0=B-2B-C即B=-C（n=1代入上式），及0=B-4B-C+2即3B+C=2（n=2代入上式），将B=-C代入本式，得B=1，再由B=-C得C=-1，于是有an=A+n2-n。将边界条件a1=2代入该式，得A=2，于是有an=n2-n+2。（此递推式亦可用代入法求解）非齐次递推方程求解有时需要较为特殊的方法。再举一例：an-5an-1+6an-2=2n，特征方程x2-5x+6=(x-2)(x-3)=0，特征根为2和3。 于是齐通解为A1*2n+A2*3n，如仍设特解q(n)与f(n)同形：q(n)=B2n，代入an-5an-1+6an-2=2n，则有B(2n-5*2n-1+6*2n-2)=2n，即有B*2n-1 (2-5+3)=2n，得到0=2n，得出一个矛盾。原因在何处？因为一个特征根为2，齐通解中有A1*2n，故特解不能与f(n)同形。当Th1Th4无法使用时，或者特征方程的根难以求得时，只能用代入法、生成函数法等它方法来求解。