第一章 算法分析的数学基础
生成函数（母函数）
在进行计数分析时，常常会遇到递推方程，形如：
an=cn-1*an-1 + cn-2*an-2 + … + cr*ar (cr≠0) 求解时有时需要使用生成函数的方法。 e.g. Fibonacci数列：满足关系an=an-1+an-2 （该类数有很多好的性质） 普通与指数生成函数的定义：
设{a0，a1，a2，…，an，…}是某一数域 （e.g. 有理数，实数，复数）上的数的序列， {μ0(x), μ1(x), μ2(x), … ,μn(x), …}
是同一数域上相互独立的函数序列，则称函数 F(x)=a0μ0(x)+ a1μ1(x)+ a2μ2(x)+ … + anμn(x)+ … 是序列{ a0，a1，a2，…，an，…}的普通生成函数 （普母函数）；称函数G(x) =
a0μ0(x)/0! + a1μ1(x)/1! + a2μ2(x)/2! + … +anμn(x)/n! + …是序列{a0，a1，…，a2，…}的指数生成函数， （指母函数，和式形状类似于e的展开形式） 相互独立（independent）的函数序列： 设{μ0(x), μ1(x), μ2(x), … ,μn(x), …}是
x
某一数域上的函数序列，
（x的值以及μk(x)（k=0,1,2, …）的值都在同一个数域中）
任取μk(x)（k=0,1,2, …），不存在数域中的数?1，?2，…，?p，使得μk (x) = ?1μi1(x) + ?2μi2(x) + … + ?pμip(x) ， 即任何一个函数项μk(x)不能被其它函数项线性表出。 e.g. {1，x，x，x，…，x，…}是相互独立的， 而{1，1+x，1-x，1+x，1-x，…}不是相互独立的， ∵1=1/2((1+x)+(1-x))。
如使用第二个函数序列来构造普通生成函数， 则序列{1,0,0,0, …}和{0,1/2,1/2,0, …} 所对应的普通生成函数是相同的， 序列与其生成函数之间没有1-1对应关系。 ∴函数序列的相互独立性
保证了序列与其生成函数之间的1-1对应。
2
3
n
2
2
2
3
n
生成函数的函数序列大多用{1，x，x，x，…，x，…}， 在得到一个数列的生成函数之后，
幂级数展开后x前的系数就是数列的通项an。 普通生成函数的两种主要应用：
1. 解排列组合类问题 2. 求解递归方程
n
解排列组合类问题
e.g. (1+x)=C+Cx+Cx+…+Cx（二项式定理）
012nnnnnn2n
是序列{C，C，…，C}的普通生成函数。
01nnnn令x=-1,代入得C+C+C +…=C+C+C+… 。
02n4n135nnnn即从n个不同的物体中选取偶数个物体的方法数等于 从n个不同的物体中选取奇数个物体的方法数。 其它应用可参看组合数学/组合分析教材。 求解递归方程
e.g. Fibonacci数an=an-1+an-2 a0=1，a1=1(边界条件)， 则可以算出序列为{1，1，2，3，5，8，…}，an=? 设
A(x)=?anxn?0?n, 根据an=an-1+an-2可有anx=(an-1+an-2)x,
nn
从2开始对等式两边分别求幂级数，得
?n(a?ax=?n-1+an-2)x。由于?ax=A(x)-a1x-a0，而
n?2nnnn?2n?2?n
??(an-1+an-2)xn=?an-1xn+?an-2xn=x(A(x)-a0)+x2A(x),
n?2n?2n?2???∴A(x)-a1x-a0=x(A(x)-a0)+xA(x),令A(x)=z, 则有
2
2
z-x-1=x(z-1)+zx。将z视为变量、x视为常量，可解得： z=A(x)=1/(1-x-x)。将1/(1-x- x)作幂级数展开后， x前的系数就是Fibonacci数列的通项an。
n
2
2
常系数线性递归方程(差分方程)：
c0an+c1an-1+…+cran-r=f(n) (*) (这里c0*cr≠0) e.g. 3an-5an-1+2an-3=n+5 线性：所有ai都是一次的。
非线性：含有ai或如aiaj之类的乘积项。
求解常系数线性递归方程c0an+c1an-1+…+cran-r=f(n)， 需要r个连续的边界条件 e.g. Fibonacci方程 r=2，
求解该方程需要两个连续的边界条件。 若f(n)≠0，则称方程c0an+c1an-1+…+cran-r=f(n) 是非齐次的；
2
2
若f(n)=0，则称方程c0an+c1an-1+…+cran-r=0是齐次的。 类似于常微分方程，
称c0x+c1x+…+cr=0 (**) 为方程
c0an+c1an-1+…+cran-r=f(n)所对应的特征方程， 求解方程c0an+c1an-1+…+cran-r=f(n)，有四个定理。 Th1：若特征方程(**)恰有r个互不相同的特征根 ?1，?2，…，?r (即i≠j时有?i≠?j)，则齐次方程的通解 （通常称为齐通解，因解中含待定系数故称“通解”）
r
r-1
为
nnn
an = A1?1 + A2?2 + … + Ar?r
（A1～Ar为待定系数，可由r个连续的边界条件唯一确定） （将待定系数作为未知数，
根据r个连续的边界条件可得r个方程， 方程的系数矩阵是范德蒙矩阵， 其行列式值不为零，故有唯一解。）
??1?2??1?...?i??1?范德蒙矩阵之例：...???r?1?22?2...i?2...r?2?32?3...i?3...r?3?42?4...i?4...r?4...?r??2...?r??......?i...?r??......? r?...?r?2
E.g. an=an-1+an-2,边界条件a0=a1=1,特征方程为x-x-1=0 两个(特征)根为?1＝(1+5)/2，?2=(1-5)/2，互不相同，
nn
∴an= A1 ?1 + A2 ?2。把
n=0和n=1的两个边界条件代入，
得2个关于A1, A2的方程，
算出A1=(1+5)/(25)，A2= - (1-5)/(25)。 （Fibonacci数列的通项
也可根据其生成函数展成的幂级数求出。）