关于生成函数

基础

普通生成函数

对于数列$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 似乎修好了搜索