形式陈述

序列 $(a_n)_{n\ge0}$$(a_n{)}_{n\ge 0}$ 的普通生成函数是形式幂级数

$$ A(x)=\sum_{n\ge0}a_nx^n. $$$$A(x)=\sum _{n\ge 0}{a}_n{x}^n.$$

若系数位于交换含幺环 $R$$R$，则 $A(x)\in R[[x]]$$A(x)\in R[[x]]$。加法逐系数进行，乘法由 Cauchy 卷积定义：

$$ [A(x)B(x)]_{x^n}=\sum_{k=0}^n a_kb_{n-k}. $$$$[A(x)B(x){]}_{x^n}=\sum _{k=0}^n{a}_k{b}_{n-k}.$$

作为形式级数时，$x$$x$ 是记号，等式指每个系数相等，不要求级数在任何数值 $x$$x$ 处收敛。

直觉

生成函数把整条序列装进一个代数对象，使移位、卷积和递推变成乘法、除法与方程。它更像“系数数据库”而不是先作为解析函数。

例子与边界

常数序列 $a_n=1$$a_n=1$ 的 OGF 满足形式恒等式

$$ A(x)=1+x+x^2+\cdots=\frac1{1-x}, $$$$A(x)=1+x+x^2+\cdots =\frac{1}{1-x},$$

因为 $(1-x)A(x)=1$$(1-x)A(x)=1$ 在系数层面成立。数值解释只在 $|x|<1$$|x|<1$ 收敛；形式恒等式则在 $R[[x]]$$R[[x]]$ 中无需这一条件。普通生成函数与指数生成函数 $\sum a_nx^n/n!$$\sum a_n{x}^n/n!$ 不同。

推论与应用

OGF 把序列卷积编码为乘积，用于计数、线性递推、分拆和渐近分析。需要从系数增长推导解析性质时，才进一步研究收敛半径和复平面奇点。

参考资料

• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994，Ch. 7。
• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，Ch. 4。