关于生成函数

基础

普通生成函数

对于数列 $a_i$ ，它的普通生成函数( $\text{OGF}$ )为 $A(x)=\sum a_ix^i$

这个 $x^i$ 刚开始并没有实际意义，即为形式幂级数，实际这个 $i$ 甚至可以不是一个整数，如 $\text{FWT}$ 中的指数为集合幂指数

普通生成函数常用于解决无序的组合计数问题，如背包问题

常见背包的生成函数

我们让 $x^i$ 项表示选择了 $i$ 个物品，则可以构造生成函数

一个01背包，每一个物品的生成函数为 $A(x)=x+1$ ，其中 $x$ 项表示多选了一个，1项表示空着不选

同理，对于一个有限背包，每个物品上限 $m_i$ ，则 $A_i(x)=\sum_{j=0}^{m_i} x^j$

一个完全背包的生成函数为 $\begin{aligned} A(x)=\sum_{i=0}^{\infty} x^i=\frac{1-x^{\infty} } {1-x}=\frac{1} {1-x}\end{aligned}$ (因为我们所求的答案是前若干项，无穷项没有意义)

那么多个物品的组合就可以通过这些生成函数相乘来轻松表示，因此也容易被多项式的快速运算优化

用生成函数描述递推关系

一个最简单的例子，设斐波那契数列的普通生成函数为 $F(x)$

我们知道 $F_i=F_{i-1}+F_{i-2},F_0=0,F_1=1$

则可以用生成函数表示斐波那契数列的递推关系 $F(x)=x F(x)+x^2 F(x)+x$

其中 $xF(x)$ 对应递推式的 $F_{i-1}$ ， $x^2F(x)$ 对应递推式的 $F_{i-2}$ ， $x$ 对应 $F_1$ 的值

类似的问题还包括数列的线性递推，即 $a_i=\sum b_ja_{i-j}$ ，但是这个求解比较复杂。。。

$\$

基于概率期望的生成函数

取自集训队论文 2018 - 1 浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙

对于随机非负离散变量 $x$ ，令它的概率生成函数是 $F(z)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)z^i\end{aligned}$ ，则可以看到这里的指数代表 $x$ 的值

$x$ 的值不一定能够相加，但是利用这个生成函数，可以快速表达期望，方差等，具体见下式

1. $F(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)=1\end{aligned}$

2. $F'(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i=E(x)\end{aligned}$

3. $E(x^{\underline{k} })=F^{(k)}(1)$ ( $x$ 的 $k$ 阶下降幂，( $k$ )表示 $k$ 阶导数)

4. $x$ 的方差 $=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot (i-E(x))^2\end{aligned}=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i^2-2P(x=i)\cdot i\cdot E(x)+P(x=i)\cdot E^2(x)\end{aligned}$

$=E(x^2)-2E^2(x)+E^2(x)=E(x^2)-E^2(x)=E(x^{\underline{2} })+E(x)-E^2(x)=F’’(1)+F’(1)-(F’(1))^2$

可以作为导数在生成函数推导中应用的一个例子

$\$

指数生成函数

对于数列 $a_i$ ，它的指数生成函数( $\text{EGF}$ )为 $\begin{aligned} A(x)=\sum \frac{a_ix^i} {i!}\end{aligned}$

指数型生成函数是处理有序排列问题的一大利器，因此，指数上的 $i$ 通常表示个数

为什么 $\frac{1} {i!}$ 可以简化排列问题，可以参见这样的一个例子

用若干类物品排成一个排列，每一类有 $m_i$ 个，则不同的排列个数为 $\begin{aligned} \frac{(\sum m_i)!} {\prod m_i!}\end{aligned}$

这个式子的意义就是: 假设先随便排列，由于每一类相同，因此类之内的排列都要除掉

可以看到， $\frac{1} {i!}$ 描述的就是类内的排列，因此最后求得答案项还要乘上 $n!$

如果一类物品任意个数加入排列，则其指数生成函数为 $\begin{aligned} A(x)=\sum_{i=0}^{\infty}\frac{x^i} {i!}=e^x\end{aligned}$

根据 $e^{-x}=\sum_i \frac{(-x)^i} {i!}$ ,还能得到:

限制为偶数个的指数生成函数 $\begin{aligned} A(x)=\sum_{2|i}^{\infty}\frac{x^i} {i!}=\frac{e^x+e^{-x} } {2}\end{aligned}$

限制为奇数个的指数生成函数 $\begin{aligned} A(x)=\sum_{2|i}^{\infty}\frac{x^i} {i!}=\frac{e^x-e^{-x} } {2}\end{aligned}$

限制为 $n$ 的倍数个，较为复杂，需要用到单位根反演

$e^{x}$ 在排列问题叠加上的应用

若有一类等价排列子问题，其指数型生成函数为 $F(x)$ ，则任意叠加其得到的排列问题指数型生成函数为

$\begin{aligned} \sum_{i=0}^{\infty} \frac{F^i(x)} {i!}=e^{F(x)}\end{aligned}$ ，其中 $\frac{1} {i!}$ 表示除去子问题之间等价

$\$

orangejuice's blog

按ctrl会跳搜索，右上角选择day/night mode 似乎修好了搜索