普通生成函数

普通生成函数把索引 $n$ 变成幂次。乘以 $x$ 把每项向后移一格：$xA(x)$ 的常数项为零，$x^n$ 系数为 $a_{n-1}$（$n\ge 1$）；向前移一格则需先去掉常数项，得到 $(A(x)-a_0)/x$。这说明平移公式为什么总伴随初值修正。组合中，两个因子分别记录两类部件的大小，乘积按 $k+(n-k)=n$ 汇总所有大小分配，卷积因此成为计数操作。

系数记录总大小 ​

常数序列 $a_n=1$ 的生成函数为 $A(x)=1+x+x^2+\cdots =1/(1-x)$，因为逐系数计算 $(1-x)A(x)$，常数项留下 $1$，其余项两两抵消。作为数值级数需 $|x|<1$；作为形式等式不需要选取任何数值 $x$。

把两种部件的可能大小分别编码为 $1+x+x^2$ 与 $1+x^2$，乘积为 $1+x+2x^2+x^3+x^4$。$x^2$ 的系数为 $2$，因为总大小为 $2$ 可以来自 $(2,0)$ 或 $(0,2)$。乘法中的卷积并非记号技巧，而是在列举总大小的所有分解。

递推如何变成方程 ​

令 $F_0=0,F_1=1$，且 $F_n=F_{n-1}+F_{n-2}$（$n\ge 2$）。对 $F(x)=\sum _{n\ge 0}{F}_n{x}^n$，把递推两边乘以 $x^n$ 再从 $n=2$ 求和，得到

左侧减掉的 $x$ 来自初值 $F_1$；缺少初值就无法确定分子。可以复查前几项 $x+x^2+2x^3+3x^4+\cdots$，乘回 $1-x-x^2$ 后只剩 $x$。

形式运算的边界 ​

$\sum _{n\ge 0}n!x^n$ 是合法形式幂级数，却在每个非零实数 $x$ 处发散。因此不能仅凭有生成函数，就对它代入 $x=1$ 或使用解析积分。无限乘积也要逐系数可定义：例如 $\prod _{j\ge 1}(1-x^j{)}^{-1}$ 的 $x^n$ 系数只受前 $n$ 个因子影响，因而形式上有意义。

指数生成函数理路指数生成函数Exponential generating function · EGF以 a_n x^n/n! 编码带标号组合对象计数序列的形式幂级数。用 $x^n/n!$ 编码，乘法会带出分配标号的二项式系数；普通生成函数的卷积没有这个因子。两种编码不能在同一计数问题中不说明理由地互换。

序列理路序列Sequence以自然数为定义域的函数。进入形式幂级数理路形式幂级数Formal power series以系数序列为本体并按 Cauchy 卷积运算、不预设解析收敛的无穷级数。后，移位变成乘以 $x$，组合部件变成卷积。常系数齐次线性递推给出有理生成函数；不能省去“常系数、齐次”等条件而推广到任意线性递推。非齐次项本身的生成函数也会进入方程右端。

Catalan 数理路Catalan 数Catalan number从 Dyck 路的首次返回与首次越界反射证明 Catalan 计数，再用形式反演复算系数，并推出带一阶修正的渐近式。的首次返回给出唯一分解，因而得到代数方程 $C=1+x{C}^2$，它展示了超出有理函数的情形。该页逐系数证明形式解唯一，用首次越界反射及 Lagrange 反演分别复算精确系数，并从阶乘比推出渐近修正；其中 $C-1$ 只删去常数项，$(C-1)/x$ 才会移动正次下标。整数分拆则用乘积逐个记录每种部件出现次数。若进一步要估计系数增长，才引入收敛半径、奇点等解析条件，把形式计数问题接到解析方法上。

二项式序列变换理路二项式反演与序列变换Binomial inversion · Binomial transform证明二项式三角变换的显式逆，并分别推导OGF代换和EGF乘法，说明按大小合并的对称性前提。把 $b_n=\sum _k(\genfrac{}{}{0ex}{}{n}{k})a_k$ 翻译为 $B(z)=(1-z{)}^{-1}A(z/(1-z))$，展示了“选活跃标签”不仅是简单移位。Worpitzky恒等式理路Worpitzky 恒等式与幂的下降展开Worpitzky identity · Eulerian power identity用稳定排序把任意函数唯一分到下降模式，证明Worpitzky展开并推导幂和有理生成函数、Eulerian显式式与EGF。则用稳定排序得到 $\sum _{m\ge 0}{m}^n{t}^m=t{A}_n(t)/(1-t{)}^{n+1}$（$n\ge 1$），其分子是按下降数编码的Eulerian多项式。两例都在逐系数形式意义下成立，不需要先做数值求和。

格点伸缩提供一种有限分子证书。Ehrhart计数定理理路Ehrhart 伸缩计数定理Ehrhart theorem · Ehrhart polynomial · Ehrhart quasipolynomial · Ehrhart多项式 · Ehrhart准多项式证明有理多胞形的全部非负整数伸缩格点数按剩余类呈多项式，整数顶点时恢复单一多项式；以同高整圆锥和半开基本域给生成函数证书，处理周期折叠、低维切片和负系数。先将圆锥分成不交半开块，再把每块拆成有限基本域与非负整数步，得到分母为(1−z^q)的固定次幂；分子高度上界保证各剩余类公式从零开始准确。Ehrhart–Macdonald互反理路Ehrhart–Macdonald 格点互反Ehrhart–Macdonald reciprocity · Ehrhart-Macdonald reciprocity · 格点计数互反定理将闭多胞形的Ehrhart准多项式在负整数处按正确剩余类求值，恢复正伸缩的相对内部格点数；用互补半开基本域及有理生成函数反演证明，区分负伸缩、内部与边界分工。使用同一有理函数在z与1/z处的恒等式，再在零处重新展开；不能把无限负幂形式和直接当作非负幂级数。