生成函数（generating function，简称 GF），一般只应用两种：OGF 和 EGF。

OGF 和 EGF 都是定义在一个数列上的。

【OGF】

【定义】

对于一个有限序列 \(\{a_i\}(i=0\sim N)\)，其 OGF 为 \(f(x)=\displaystyle\sum_{i=0}^Na_i\cdot x^i\)。

对于一个无限序列 \(\{a_i\}\)，其 OGF 为 \(f(x)=\displaystyle\sum_{i=0}^{+\infty}a_i\cdot x^i\)。

注意生成函数是一种形式幂级数，也就是一般情况下我们不考虑 \(x\) 具体的值，也不考虑 \(f(x)\) 是否收敛。

（我们把 \(\displaystyle\sum_{i=0}^{+\infty}a_i\cdot x^i\) 的形式称为级数）

例题：砝码称重

有 \(4\) 个砝码，分别为 \(1,2,3,4\) 克。问称出 \(n\) 克的方案数。（砝码只能放在一边）

令 \(G(x)=(1+x^1)(1+x^2)(1+x^3)(1+x^4)\)，发现 \(ans=[x^n]G(x)\)。（在一个多项式前加中括号，表示取中括号内的项的系数）

怎么理解呢？\(G(x)\) 每一个括号都代表一个砝码的选择：放或不放。

例题：取球方案

有 \(m\) 种颜色的球，要从里面取出 \(n\) 个球。问方案数。同时有两种情况：

• 每种颜色的球各一个。显然答案是 \((^m_n)\)。

• 每种颜色的球无限个。即求方程 \(x_1+x_2+\dots+x_m=n\) 非负整数解个数，隔板法 \((^{n+m-1}_{m-1})\)。

怎么用生成函数做？

当每种球只有一个，令 \(G(x)=(1+x)^m\)，\(ans=[x^n]G(x)\)。

当每种球有无限个，令 \(G(x)=(1+x+x^2+x^3+\dots)^m=(\dfrac{1}{1-x})^m=\dfrac{1}{(1-x)^m}\)