生成函数(解析)

设想你有一个无穷数列 a_0、a_1、a_2、……——比如某物在每个尺寸上的计数。生成函数把整个数列打包成单一对象:让这些数充当一个幂级数的系数。这就像把数列挂在 x 的幂构成的晾衣绳上,使整个数列变成一个你可以操作的解析函数。

数列 (a_n) 的普通生成函数是幂级数 G(x) = sum_{n=0}^无穷 a_n x^n。当该级数有正的收敛半径时,G 是一个名副其实的解析函数,而对函数的运算恰好对应于对数列的运算:两个生成函数相乘对应于数列的卷积(柯西乘积),求导则平移并缩放指标,如此等等。G 的闭式表达式于是编码了关于 a_n 的事实。

解析视角带来超越纯形式记账的真正威力。由于 G 是解析的,它的奇点——最近的爆破点——通过收敛半径以及更精细的渐近分析掌控着系数 a_n 的增长率。一点诚实的告诫:生成函数有时纯作形式使用,仅当记账工具而不主张任何收敛性;解析理论恰恰适用于级数在 0 附近确实收敛的情形。