概念

普通生成函数

OGF 将数列 a_n 编码为 Σa_n x^n，乘法对应卷积，部分分式分解可将生成函数还原为显式通项公式。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

普通生成函数组合数学

01定义

普通生成函数（OGF）把数列

a_n

编码为形式幂级数

\sum a_nx^n

：乘法对应卷积、除法对应递推求解、部分分式分解直接读出通项。计数问题由此代数化——组合数学最有力的转换技巧。

OGF 工作流：数列 ⇄ 幂级数，计数化为代数

$A(x)B(x)$ 的 $x^n$ 系数是 $\sum_{i+j=n}a_ib_j$ ——「分成两部分各取其一」的计数自动成为乘积，无需手工分类。

斐波那契 OGF 由递推直接导出 $F(x)=x/(1-x-x^2)$ ；部分分式分解后立即得到含 $\varphi$ 的显式通项。

$\frac{1}{1-x}=\sum x^n$ 、 $\frac{1}{(1-x)^{k+1}}=\sum\binom{n+k}{k}x^n$ ——常用封闭形式与数列的对照表是组合学家的「字典」。

\sum_{n\ge 0}F_nx^n=\frac{x}{1-x-x^2}

\frac{1}{(1-x)^{k+1}}=\sum_{n\ge 0}\binom{n+k}{k}x^n

欧拉 1740 年代以生成函数研究分拆数（五边形数定理）；「形式幂级数」的严格观点由 20 世纪组合学派确立——不看收敛，只看系数。

算法分析（均摊复杂度的母函数法）、统计力学配分函数、队列论中的等待时间分布——把「数对象」转成「算级数」。

斐波那契的生成函数 F(x)=x/(1−x−x²)系数 = 斐波那契数；部分和逼近 F(x)

x0.40