写在前面
本文除了例题 @.1 P4389 付公主的背包 使用 OGF 其她的均为 EGF
0 约定
0.1 一些形象的表达
- 收缩： 指一个式子由比较复杂的形式变简单。本文中大概率就是指一个生成函数用封闭形式来表达；
- 多项式的平移： 对于任意一个多项式 \(A(x)\)，向左平移 \(m\) 位指 \(\left(A(x)-\sum\limits_{i=0}^{m-1}a_ix^i\right)/x^m\)；向右平移 \(m\) 位指 \(A(x)\times x^m\)；
0.2 记号
- 如果没有特别说明，大写字母一般表示其小写字母的生成函数的封闭形式。
1 封闭形式的生成
- 由递推式生成： 将等式两边同时乘上形式元 \(z^n\) 并对 \(n\ge 0\) 求和。然后分开收缩之后再求和；
- 由数列生成： 将原数列的生成函数 \(F(x)\) 向右平移 \(1\) 位，然后求 \(xF(x)-F(x)\)，从而列出方程求解；
- 由多个生成函数运算生成：
- 复合： 直接带入就行；
- 两个生成函数以卷积形式相乘，就等价于她们的封闭形式相乘。
- 其她的，按运算法则算就好；
由一个封闭形式推另一个封闭形式的时候，系数中的 \(n\) 一定要转移到 \(z\) 的指数上去（大概率是求导。
2 指数生成函数 EGF
我们称满足如下形式的形式幂级数为 指数生成函数 (Exponential Generating Function, EGF)
\[\hat A(z)=\sum_{n\ge0}a_n\dfrac {z^n}{n!} \]特别地，我们会用 \(\left[\frac {z^n}{n!}\right]\) 来直接提取 \(a_n\)，而若用 \([z^n]\) 的话提取到的是 \(\frac {a_n}{n!}\) 。
也就是说 \(\left[\frac {z^n}{n!}\right]\) 和 \(n![z^n]\) 是等价的。
值得注意的是，EGF 的原生数列（系数数列），指的是用 \([z^n]\) 提取的值，是包含 \(n!\) 的。
2.1 运算法则
-
\(z^m\hat A(z)\) 在 OGF 的语境下为平移；而在 EGF 下，由于 \(n!\) 并不会改变，所以并不是直接平移，最终的数列应该是 \(\{a_{n-m}\cdot \frac {n!}{(n-m)!} \}\)。
-
\(\hat A^\prime(z)\) 在 OGF 的语境下为带系数的移位，生成 \(\{(n+1)a_{n+1} \}\)；而在 EGF 中，就是真正的向左平移（一位）了，而 \(\int_{0}^{z} \hat{A}(t) \mathrm{d} t\) 也就是向右平移了。
-
$\hat{C}(z)=\hat{A}(z) \hat{B}(z) $$ 在 OGF 语境下为普通卷积，在 EGF 语境下为二项卷积，也即：
\[c_{n}=\sum_{k}\binom{n}{k} a_{k} b_{n-k} \]
@ 例题
@.1 P4389 付公主的背包
用 dp 递推式生成封闭形式，再快速求解
定义 \(f_{i,j}\) 前 \(i\) 个物品，凑出容量为 \(j\) 的方案数。
有递推式：
\[f_{i,j}=\sum_{t\in\mathbb N}f_{i-1,j-v_it} \]然后用 1.1 的手法，配一个形式元上去：
\[f_{i,j}z_j=\sum_{t\in\mathbb N}f_{i-1,j-v_it}z^{j-v_it}\cdot\sum_{t\in\mathbb N}z^{v_it} \]进而：
\[F_i(z)=F_{i-1}(z)\cdot \dfrac 1 {1-z^{v_i}};F_0=1 \]后续的“计算”和生成函数本身无关。
@.2 贝尔数
将 \(\{1,2,3,\dots,n\}\) 划分为若干个非空子集的方案数 \(\omega_n\) 称为 贝尔数。
考虑 \(1\) 所在的子集，写出如下转移式：
\[\omega_n=\sum_{i=0}^{n-1}{n-1\choose i}\omega_{n-i-1} \]这实际上是划分集合的惯用 trick，即考虑一个特定元素最终所在集合。
继续用 1.1 的手法尝试：
\[\sum_{n\ge0}\omega_nz^{n-1}=\sum_{n\ge0}\omega_{n-i-1}z^{n-i-1}\cdot \sum_{i=0}^{n-1}{n-1\choose i}z^i \]发现 \({n-1\choose i}z^i\) 不能直接收拢欸。
注意到我们现在能继续的变形，只能把组合数拆成阶乘：
\[\sum_{n\ge0}\omega_n\dfrac {z^{n-1}}{(n-1)!}=\sum_{n\ge0}\omega_{n-i-1}\dfrac{z^{n-i-1}}{(n-i-1)!}\cdot \sum_{i=0}^{n-1}i!\dfrac{z^i}{i!} \]然后我们惊奇的发现，这三坨求和其实就是 EGF。
……