第二章 常用的数学工具
2.2 用生成函数求解递归方程 2.2.1 生成函数及其性质
一、生成函数的定义
定义2.1 令a0,a1,a2,?是一个实数序列，构造如下的函数：
G(z)?a0?a1z?a2z???2?ak?0?kzk （2.2.1）
则函数G(z)称为序列a0,a1,a2,?的生成函数。
例：函数
0122nn(1?x)n?Cn?Cnx?Cnx???Cnx
012n则函数(1?x)n便是序列Cn的生成函数。 ,Cn,Cn,?,Cn二、生成函数的性质
1. 加法 设G(z)??akzk是序列a0,a1,a2,?的生成函数，
k?0?H(z)??bzkk?0?k是序列b0,b1,b2,?的生成函数，则?G(z)??H(z)
???G(z)??H(z)???ak?0kzk???bzkk?0k
1
??(?ak?0?k??bk)zk
（2.2.2）
是序列?a0??b0,?a1??b1,?a2??b2,?的生成函数。
2．移位 设G(z)??akzk是序列a0,a1,a2,?的生成函数，则
k?0?zmG(z)
zG(z)?mk?m?a?k?mzk （2.2.3）
是序列0,?,0,a0,a1,a2,?的生成函数。
3．乘法 设G(z)??akzk是序列a0,a1,a2,?的生成函数，
k?0?H(z)??bzkk?0?k是序列b0,b1,b2,?的生成函数，则G(z)H(z)
G(z)H(z)?(a0?a1z?a2z2??)(b0?b1z?b2z2??)
?a0b0?(a0b1?a1b0)z?(a0b2?a1b1?a2b0)z2??
??ckzk
k?0?
n （2.2.4）
是序列c0,c1,c2,?的生成函数，其中，cn??akbn?k
k?04. z变换 设G(z)??akzk是序列a0,a1,a2,?的生成函数，则
k?0? 2
G(cz)
G(cz)?a0?a1(cz)?a2(cz)2?a3(cz)3??
?a0?ca1z?c2a2z2?c3a3z3?? （2.2.5）
是序列a0,ca1,c2a2,?的生成函数。
特别地，有： 1?1?cz?c2z2?c3z3?? 1?cz （2.2.6）
所以，
11?cz是序列1,c,c2,c3,?的生成函数。
当c?1时，有：
1?1?z?z2?? 1?z （2.2.7）
则
1是序列1,1,1,…的生成函数。 1?z利用：
1(G(z)?G(?z))?a0?a2z2?a4z4?? 2（2.2.8）
可以去掉级数中的奇数项；同样，利用
1(G(z)?G(?z))?a1z?a3z3?a5z5?? 2（2.2.9）
可以去掉级数中的偶数项。
5．微分和积分 设G(z)??akzk是序列a0,a1,a2,?的生成函数，
k?0?对G(z)求导数
G'(z)?a1?2a2z?3a3z???2?(k?1)ak?0?k?1zk （2.2.10）
3
显然，G'(z)是序列a1,2a2,3a3,?的生成函数。同样，对G(z)求积分
z?011G(t)dt?a0z?a1z2?a2z3???23z?kak?1?1k?1zk （2.2.11）
则积分?G(t)dt是a0,a1,a2,?的生成函数。
01213如果对（2.2.7）式求导数，可得：
1(1?z)2?1?2z?3z???2?(k?1)zk?0?k （2.2.12）
则
1(1?z)2是算术级数1,2,3…的生成函数。
如果对（2.2.7）式求积分，可得：
111ln?z?z2?z3???1?z23?k?1?1kz k （2.2.13）
则ln111是调和数1,,,?的生成函数。 1?z232.2.2 用生成函数求解递归方程
例2.1 汉诺塔（Hanoi）问题。
宝石针的编号为A、B、C，A针串着64片金盘。希望把它们移到B针或C针。有可n是金盘的数量，h(n)是移动n个金盘的移动次数
1． 当n?1时， h(1)=1。 2． 当n?2时， h(2)?2h(1)?1。 3． 当n?3时， h(3)?2h(2)?1。 递归关系式：
?h(n)?2h(n?1)?1 ?h(1)?1?
4
（2.2.14）
用h(n)作为系数，构造一个生成函数：
G(x)?h(1)x?h(2)x2?h(3)x3??
???h(k)xk?1k
令
G(x)?2xG(x)?h(1)x?h(2)x2?h(3)x3???2h(1)x2?2h(2)x3??
?h(1)x?(h(2)?2h(1))x2?(h(3)?2h(2))x3??
由（2.2.14）及（2.2.7）式得：
(1?2x)G(x)?x?x2?x3??
x ?1?x所以，
G(x)?x
(1?x)(1?2x)令：
G(x)?ABA?2Ax?B?Bx??(1?x)(1?2x)(1?x)(1?2x)
有：
A?B?0?2A?B?1
求得A??1,B?1。所以：
G(x)?11?
(1?2x)(1?x) ?(1?2x?22x2?23x3??)?(1?x?x2?x3??)
?(2?1)x?(22?1)x2?(23?1)x3??
??(2k?1?k?1)xk
h(n)?2n?1，它是式中第n项的系数。当n?64时，移动次数为264?1。
5
