1 基本概念
普通生成函数是将一个数列编码为幂级数的标准方法。对于数列 \(\{a_n\}_{n\ge 0}\)，通常记其普通生成函数为 \[ A(x)=\sum_{n\ge 0} a_n x^n. \] 在这一表示下，数列的每一项都对应幂级数中的一个系数，从而把离散对象的研究转化为代数运算与系数分析。
普通生成函数最重要的意义在于“编码”。它并不只是把数列写成一个形式表达式，而是借助幂级数的加法、乘法、求导、取系数等操作，建立数列之间的运算对应关系。因此，许多原本较难直接处理的递推、计数和卷积问题，都可以通过生成函数获得统一的处理框架。
1.1 数列与幂级数编码
普通生成函数把数列 \(\{a_n\}\) 视为幂级数 \(A(x)\) 的系数序列。若已知 \(A(x)\)，则可通过展开直接读出 \(a_n\)；反过来，若已知数列，也可写出对应的形式幂级数。这种对应关系在组合数学中尤为常见，因为很多离散结构都可以按“大小参数”分类，并将每类对象的数量写成系数。
例如，若 \(a_n\) 表示大小为 \(n\) 的对象数目，则 \(A(x)\) 以 \(x^n\) 的系数记录该类对象的计数信息。这样处理后，原本按项讨论的数列问题，常可转化为对一个函数式表达的研究。
1.2 形式幂级数视角
在普通生成函数理论中，幂级数往往被当作形式幂级数来使用，即更关注系数结构，而不是数值收敛性。此时 \(A(x)\) 的意义主要在于代数形式，而不必先讨论其在某个数值范围内是否收敛。
这种视角使生成函数具有很强的灵活性。许多操作只要在形式上合法，就可以进行，例如乘法对应卷积、除法对应某些递推解、复合对应特定组合结构。由于只处理符号和系数，形式幂级数特别适合离散数学中的结构化推导。
1.3 与其他生成函数的区别
普通生成函数是最直接的一类生成函数，其特点是使用 \(x^n\) 作为基本项，系数不含额外的阶乘权重。与其他类型的生成函数相比，它更适合描述按“顺序位置”或“大小参数”编码的普通计数问题。
1.3.1 指数生成函数
指数生成函数通常写作 \[ \sum_{n\ge 0} a_n \frac{x^n}{n!}, \] 与普通生成函数不同，它在每一项中引入了 \(n!\) 的归一化因子。这种形式常用于处理带标记元素的组合对象，尤其适合涉及排列、标号结构和微分性质的情形。
1.3.2 Dirichlet 生成函数
Dirichlet 生成函数一般写作 \[ \sum_{n\ge 1} \frac{a_n}{n^s}, \] 主要用于数论和乘法性函数的研究。它与普通生成函数在形式上差异明显，关注的核心问题也不同：前者常处理整数分解与乘法结构，后者则更偏向离散计数和递推分析。
2 构造方法
普通生成函数的构造方式多种多样，最直接的是从数列本身出发，也可以由递推关系、组合对象或结构描述反向建立。不同构造方法反映了同一数列在不同视角下的表达方式。
2.1 由数列直接构造
若数列 \(\{a_n\}\) 已知，则其普通生成函数可直接写为 \[ A(x)=a_0+a_1x+a_2x^2+\cdots. \] 这种构造最为简单，适合数列项有明确表达式或前若干项已知的情形。之后可以通过代数手段分析其规律，进而反推出一般项或递推关系。
2.2 由递推关系构造
很多数列并不是先给出通项，而是由递推定义。此时，将递推式两边乘以适当的幂并对所有项求和，通常可以得到生成函数方程，再求解出 \(A(x)\)。
2.2.1 线性递推的转换
对线性递推数列，生成函数方法尤为有效。若 \(a_n\) 满足常系数线性递推，则可把递推式转化为关于 \(A(x)\) 的代数方程，最后通过整理得到有理函数形式的生成函数。这一过程通常比逐项展开更高效，也更便于提取一般项。
2.2.2 非齐次递推的处理
若递推关系中含有外加项，如常数项、指数项或多项式项，则生成函数方程的右端会出现相应的附加部分。处理时通常先将非齐次部分单独编码，再与主递推结构合并。这样可以把复杂递推统一为一个可求解的函数关系。
2.3 由组合对象构造
在组合数学中，生成函数往往不是从数列出发，而是从对象的构造规则出发。只要能将对象按大小分层，就可以建立对应的普通生成函数。
2.3.1 选择型结构
选择型结构指从若干可选部件中选择若干个来组成对象，且各部件出现次数常独立计算。这类结构适合用乘法原则转化为生成函数的乘积形式。每个部件的贡献对应一个因子，整体对象则对应这些因子的组合。
2.3.2 序列型结构
序列型结构强调部件的先后次序。若对象是由若干子结构依次拼接而成，则其生成函数常体现为若干局部生成函数的组合，或通过几何级数方式展开。此类对象在路径、词语和分段问题中十分常见。
3 代数运算与基本性质
普通生成函数之所以强大，很大程度上在于它允许将数列运算转化为代数运算。不同的幂级数操作，对应着数列层面的特定规律。
3.1 加法与数列叠加
若两个数列分别对应生成函数 \(A(x)\) 和 \(B(x)\)，则它们的和对应 \[ A(x)+B(x). \] 在系数层面，这表示逐项相加，即新数列的第 \(n\) 项为 \(a_n+b_n\)。这种性质常用于把多个计数来源合并为统一表达。
3.2 乘法与卷积
幂级数相乘后，系数不再是简单相加，而会出现卷积结构。这一性质是生成函数在组合计数中的核心工具之一。
3.2.1 Cauchy 乘积
若 \[ A(x)=\sum_{n\ge 0} a_nx^n,\quad B(x)=\sum_{n\ge 0} b_nx^n, \] 则 \[ A(x)B(x)=\sum_{n\ge 0}\left(\sum_{k=0}^n a_k b_{n-k}\right)x^n. \] 这就是 Cauchy 乘积。它表明乘积的第 \(n\) 项由所有拆分方式累加而成，因此非常适合描述“分配总量”的计数问题。
3.2.2 卷积在计数中的意义
卷积对应把一个整体拆成两部分并分别计数。比如若总大小为 \(n\) 的对象可以由大小分别为 \(k\) 与 \(n-k\) 的两个子对象组成，那么总数通常就是两个子数列的卷积。这种机制在分拆、路径分段和子结构拼接中都很常见。
3.3 取系数与截断
生成函数的一个基本操作是取系数，即从幂级数中读出某一项的系数。记作 \([x^n]A(x)\)，表示 \(x^n\) 的系数。截断则是只保留到某一阶为止的有限部分，常用于近似计算或有限范围验证。
这类操作在证明中尤其重要。通过把目标数列转写为生成函数，再对特定项取系数，就能把抽象的等式还原为明确的计数结果。
3.4 幂、倒数与复合运算
对生成函数取幂，通常对应把结构重复多次；取倒数则常用于解递推或表示某种“补结构”关系。复合运算在普通生成函数中比在指数生成函数中更受限制，但在合适的组合场景下仍然很有用。
这些运算能够刻画更复杂的离散结构，例如由若干层次嵌套形成的对象、分段式计数模型，或某些自相似递归结构。
4 经典应用
普通生成函数在应用中最常见的作用，是把递推、计数、分析和概率问题统一到一个框架内处理。
4.1 递推方程求解
生成函数方法特别适合求解递推方程。通过把递推转为函数方程，很多问题能从“逐项计算”变为“代数求解”。
4.1.1 常系数线性递推
常系数线性递推的生成函数通常是有理函数。求解过程一般包括：写出递推、乘以 \(x^n\)、求和、整理边界项，最后得到关于 \(A(x)\) 的方程。解出后再展开或分解，即可得到通项表达式。
4.1.2 初值条件的引入
递推方程的生成函数往往会受到初值影响。初值决定低阶系数，因此在推导时必须单独处理。若遗漏初值，得到的生成函数可能在前几项上与原数列不符，进而导致整体结论错误。
4.2 组合计数
普通生成函数是组合计数中的基础工具，尤其适合处理“按大小分类”的对象。
4.2.1 分拆问题
在整数分拆中，每一类分拆方式都可以对应一个生成函数因子。把各个允许的部件组合起来后，整体生成函数往往是若干几何级数的乘积。通过展开或取系数，可以得到某个整数的分拆数。
4.2.2 路径计数问题
路径计数常通过生成函数分析。若一条路径可由若干步长组成，那么每种步长的贡献都可以写入生成函数，最终用乘法和取系数来统计满足条件的路径数量。此方法在网格路径、受限步行和到达问题中十分常用。
4.2.3 整数组合与装袋问题
整数组合问题常涉及把一个整数拆成若干部分，装袋问题则可理解为把若干单位物品分配到不同容器中。生成函数能够精确记录每种选择的数量，从而将问题转化为系数计算。
4.3 算法分析
在算法分析中，生成函数可以帮助研究递归算法的复杂度和规模增长。
4.3.1 复杂度递推
若某算法的时间复杂度满足递推式，则可构造对应生成函数并求解其渐近形式。这在分析分治算法、动态规划递推和某些递归程序时很有帮助。
4.3.2 递归树与生成函数
递归树展示了算法在不同层级上的代价分布，而生成函数则可把这种分层结构编码为幂级数。二者结合后，既能观察局部展开，也能得到整体增长规律。
4.4 概率模型
普通生成函数也可用于概率论中的离散模型，尤其是与离散型随机变量有关的分布分析。
4.4.1 概率母函数
若 \(p_n\) 是某离散随机变量取值为 \(n\) 的概率，则 \[ P(x)=\sum_{n\ge 0} p_n x^n \] 可视为概率母函数的一种形式。它能编码分布信息，并便于研究独立随机变量之和等问题。
4.4.2 矩与分布性质
通过对生成函数求导并在特定点代入，可以获得矩、期望和方差等信息。对于某些离散分布，生成函数还能揭示尾部增长、集中趋势及复合分布的结构特征。
5 解析技巧
普通生成函数不仅用于构造和代数变换，还常借助解析方法获得显式表达和渐近结果。
5.1 部分分式分解
当生成函数是有理函数时，部分分式分解是常见技巧。把复杂分母拆成若干简单因子后，便可将幂级数展开为若干基本项之和，从而提取通项公式或渐近形式。
5.2 幂级数展开
幂级数展开是从函数式表达恢复系数的基础手段。很多已知函数都可展开为幂级数，再与目标生成函数匹配。
5.2.1 二项式展开
二项式定理提供了最常见的展开形式之一。许多普通生成函数可通过 \[ (1-x)^{-\alpha} \] 一类表达式展开，进而得到系数的显式公式。这在组合计数中极为常见。
5.2.2 指数型展开的变换
某些函数虽然更自然地出现在指数生成函数或解析表达中，但通过适当变换，也可转化为普通生成函数可处理的形式。常见做法包括代换、重排或将表达式改写成标准幂级数结构。
5.3 系数提取技巧
系数提取是生成函数方法的核心步骤之一。关键在于把目标数量从整体函数中“读”出来。
5.3.1 代数化系数提取
在代数处理中，常通过乘法展开、公式变形或已知恒等式直接读出系数。这类方法不依赖复杂分析，适合大多数离散计数场景。
5.3.2 留数与解析方法
当生成函数具备较好解析性质时，可以利用复分析中的留数思想提取系数。该方法在处理复杂奇点、精细渐近和高阶项时特别有效。
5.4 渐近估计
除了精确系数，普通生成函数还可用于研究数列的增长速度。
5.4.1 主导奇点法
生成函数在复平面中的主导奇点常决定系数的主要增长行为。若能识别最接近原点的奇点类型，就能推断出系数的主导渐近项。
5.4.2 系数增长率分析
通过分析生成函数的奇点结构、展开阶数和局部性质，可以估计系数的增长率。这对理解组合对象数量随规模扩张的趋势非常有帮助。
6 典型生成函数
一些经典数列拥有广为人知的普通生成函数，它们常被用作范例或基础工具。
6.1 几何级数
几何级数 \[ 1+x+x^2+x^3+\cdots=\frac{1}{1-x} \] 是最基本的普通生成函数之一。它对应常数数列 \(\{1,1,1,\dots\}\)，也是许多更复杂生成函数的构建块。
6.2 二项式系数生成函数
二项式系数常由 \[ \sum_{n\ge 0} \binom{n+r}{r} x^n=\frac{1}{(1-x)^{r+1}} \] 一类形式表示。它在组合恒等式、分配问题和多重选择计数中出现频繁。
6.3 Fibonacci 数列的生成函数
Fibonacci 数列满足简单递推，因此其生成函数是典型的有理函数形式。通过该生成函数可以直接导出通项、增长率以及与黄金分割相关的性质。
6.4 Catalan 数的生成函数
Catalan 数在括号匹配、二叉树、路径计数等问题中极为常见。它的生成函数通常满足一个二次方程，解出后可得到封闭形式，并能推导出多种组合解释。
6.5 Bell 数与 Stirling 数相关生成函数
Bell 数与集合划分有关，Stirling 数则记录不同划分层次的数量。它们的生成函数常通过组合结构与指数关系相互联系，在离散结构分类中具有重要地位。
7 扩展与变体
普通生成函数虽然形式简单，但可以向多变量、结构化和更抽象的组合框架扩展。
7.1 多变量普通生成函数
若对象带有多个统计参数，例如大小、重量和颜色数等，就可以引入多个变量分别编码。多变量生成函数能够同时记录多个指标，适合更精细的组合分析。
7.2 标记生成与组合类
在更一般的组合类理论中，生成函数可与“标记”“结构分解”等概念配合使用。对象按构造规则分成若干基本类后，各类的生成函数通过代数规则组合起来，形成系统化的计数语言。
7.3 与递归结构的对应关系
很多递归结构都能直接映射到生成函数方程。一个对象若由若干子对象递归定义，其计数过程往往也满足相应的递推，因此生成函数成为描述递归结构的自然工具。
7.4 在符号方法中的位置
在符号方法中，普通生成函数常作为从“组合构造”到“代数方程”的桥梁。它把对象的并、积、序列、集合等构造操作转化为函数运算，从而建立统一的组合分析流程。
8 常见误区与使用注意
普通生成函数概念看似简单，但在实际使用中容易出现一些典型错误。
8.1 形式幂级数与收敛幂级数的区别
形式幂级数强调代数结构，不一定讨论数值收敛；而收敛幂级数则必须关注定义域和极限行为。把两者混为一谈，容易在无效区域使用展开式。
8.2 初值遗漏导致的错误
递推转化为生成函数时，低阶项通常会单独出现。如果忽略初值，方程虽然在形式上成立，但解出的生成函数可能对应另一个数列，进而影响最终结论。
8.3 系数索引偏移问题
普通生成函数对下标极为敏感。若把从 \(n=0\) 开始的数列误当成从 \(n=1\) 开始，或者在平移幂次时处理不当，就可能造成整体错位。此类错误在路径计数和递推证明中尤为常见。
8.4 运算规则适用范围
并非所有代数运算都能在任意生成函数上无条件使用。例如复合运算、倒数展开或某些极限交换，需要满足特定的形式条件。若忽视适用范围，可能得到不合法的表达式。
9 历史与发展
普通生成函数在组合数学的发展过程中逐渐成为标准工具，并不断扩展到更多学科领域。
9.1 早期组合分析中的使用
生成函数的思想在早期组合分析中就已出现，主要用于处理计数、分拆和递推问题。随着符号代数与离散分析的发展，这一方法逐步形成较为成熟的理论框架。
9.2 现代离散数学中的标准工具化
在现代离散数学中，普通生成函数已成为基础方法之一。它与递推、图论、组合结构和算法分析紧密结合，常作为证明与计算的标准工具被广泛使用。
9.3 在计算机科学中的推广
普通生成函数后来也被推广到计算机科学的多个方向，如算法复杂度分析、自动机计数、随机过程建模和形式语言研究。由于其可系统编码离散对象，因而在理论与应用层面都具有持续价值。