【学习笔记】生成函数入门

$1.1$ 普通生成函数 $OGF$：$F(x)={\sum }_{n=0}^{\infty }{f}_n{x}^n$

定义$SE{Q}_A$是$A$中元素排成的序列组成的集合，一个序列的大小定义为各元素大小之和，那么$SE{Q}_A$的$OGF$：

$SE{Q}_A(x)=1+A(x)+A^2(x)+...+A^n(x)=\frac{1}{1-A(x)}$ 。

$1.2$ 背包计数问题：有$k$种物品，每种物品有容量$v_i$和数量$n_i$，问组合出容量为$V$的方案数。

$F(x)={\prod }_{i=1}^k(1+x^{v_i}+x^{2v_i}+...+x^{n_i{v}_i})={\prod }_{i=1}^n\frac{x^{(n_i+1)v_i}-1}{x^{v_i}-1}$

假设背包有无穷种物品，每种物品的体积为$i$，个数也无限，把$n$的正整数拆分的方案数记作$p(n)$，$p$也叫分拆数。

不难得到$p(n)$的生成函数：$F(x)={\prod }_{i=1}^{\infty }\frac{1}{1-x^i}$

两边取对数，有$\ln F(x)=-{\sum }_{i=1}^{\infty }\ln (1-x^i)$

在$\mathrm{mod}{x}^{n+1}$意义下可以把无穷和变为有限的：$\ln F(x)=-{\sum }_{i=1}^n\ln (1-x^i)$

求右边的麦克劳林展式：

$\ln F(x)=-{\sum }_{i=1}^n\ln (1-x^i)={\sum }_{i=1}^n{\sum }_{j=1}^{\infty }\frac{x^{ij}}{j}={\sum }_{j=1}^{\infty }\frac{1}{j}{\sum }_{i=1}^n{x}^{ij}={\sum }_{j=1}^n\frac{1}{j}{\sum }_{i=1}^{\lfloor \frac{n}{j}\rfloor }{x}^{ij}$

右边和式可以处理出来，再对其求多项式$\exp$即可，复杂度$O(n\log n)$。

$1.3$ 指数生成函数 $EGF$：$F(x)={\sum }_{n=0}^{\infty }{f}_n\frac{x^n}{n!}$

一次积分相当于右移一项，一次求导相当于左移一项

$\int F(x)={\sum }_{n=1}^{\infty }{f}_{n-1}\frac{x^n}{n!}$，$F^{\prime }(x)={\sum }_{n=0}^{\infty }{f}_{n+1}\frac{x^n}{n!}$

两个函数的卷积：$h_n={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)f_k{g}_{n-k}$，也把序列$h$叫做序列$f$和$g$的二项卷积

$1.4$ 组合意义：$OGF$考虑的是多重集的组合问题，$EGF$考虑的是多重集的排列问题。

$1.5$ 有时我们需要考虑带标号的组合对象，如标号图。

定义$SE{T}_A$是$A$中元素任意拼接组成的集合（拼接时不考虑顺序），$SE{T}_A$的$EGF$：

$SE{T}_A(x)=1+A(x)+\frac{A^2(x)}{2}+...+\frac{A^n(x)}{n!}=\exp (A(x))$

一个带标号的简单无向图是若干个联通分量不考虑顺序拼接成的，$G$是简单无向图的$EGF$，$C$是简单连通图的$EGF$，那么：

$G(x)={\sum }_{n=0}^{\infty }{2}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\frac{x^n}{n!}$，$\exp (C(x))=G(x)$

所以$C(x)=\ln G(x)$

$1.6$ 集合划分问题：集合$S$的一个划分是把$S$分成两两不相交的非空子集，并且它们的并是$S$。

不难发现，划分的结果是由若干个子集无序拼接起来的。对于一个集合而言，不能选空集，而分出$1,2,...,n$个的方案数都只有一种，只有在拼接的时候指定编号。

故一个集合分出元素的$EGF$是$\exp (x)-1$，集合的划分的$EGF$是$\exp (\exp (x)-1)$。

$\text{bell}$数$B_n$是基数为$n$的集合划分数目，之前我们推导出了$B_n$的$EGF$是$\exp (\exp (x)-1)$，可以快速求前$n$个$\text{bell}$数。

$1.7$ 第二类$\text{Stirling}$数：$S(n,m)$表示将$n$个不同的元素划分称$m$个集合的方案数。

我们可以写出第二类$\text{Stirling}$数的$EGF$，假设$m$是一个定值，那么有

${\sum }_{n=0}^{\infty }{a}_n\frac{x^n}{n!}=\frac{(\exp (x)-1{)}^m}{m!}$，$a_n=S(n,m)$

不难求得$S(n,m)=\frac{1}{m!}{\sum }_{k=0}^m(-1{)}^{m-k}(\genfrac{}{}{0ex}{}{m}{k})k^n$

把$m!$放到和式里面：$S(n,m)={\sum }_{k=0}^m\frac{(-1{)}^{m-k}}{(m-k)!}\frac{k^n}{k!}$

这是一个卷积的形式，给定$n$，可以快速算出$S(n,m)(1\le m\le n)$

给定$m$，用${\sum }_{n=0}^{\infty }{a}_n\frac{x^n}{n!}=\frac{(\exp (x)-1{)}^m}{m!}$，$a_n=S(n,m)$可以快速算出前$n$个$S(n,m)$

复杂度$O(n\log n)$。这就是第二类斯特林数行/列

$1.8$ 第一类$\text{Sirling}$数：$\left[\begin{array}{c}n\\ m\end{array}\right]$表示将$n$个不同元素划分为$k$个互不区分的非空轮换的方案数。

递推式：$\left[\begin{array}{c}n\\ m\end{array}\right]=\left[\begin{array}{c}n-1\\ m-1\end{array}\right]+(n-1)\left[\begin{array}{c}n-1\\ m\end{array}\right]$

$\mathrm{1.8.1}$ 同一行第一类斯特林数计算

我们构造同行第一类斯特林数的生成函数，即$F_n(x)={\sum }_{i=0}^n\left[\begin{array}{c}n\\ m\end{array}\right]x^i$

根据递推公式，不难写出：$F_n(x)=(n-1)F_{n-1}(x)+x{F}_{n-1}(x)$

于是$F_n(x)={\prod }_{i=0}^{n-1}(x+i)$

这其实是$x$的$n$次上升阶乘幂，记作$x^{\overline{n}}$。用上升幂相关做法可以$O(n\log n)$求出。

$\mathrm{1.8.2}$ 同一列第一类斯特林数的计算

显然，单个轮换的指数型生成函数为$F(x)={\sum }_{i=1}^n\frac{(i-1)!x^i}{i!}$

它的$k$次幂就是$\left[\begin{array}{c}i\\ k\end{array}\right]$的指数型生成函数，$O(n\log n)$计算即可。

$1.9$ 上升幂的计算

考虑倍增，$x^{\overline{2n}}=x^{\overline{n}}(x+n{)}^{\overline{n}}$

于是现在我们有多项式$f(x)$，要求$f(x+c)$的值

不难得到$f(x+c)$可以二项式展开然后卷积求出。

复杂度$O(n\log n)$ 。

用上升幂求第二类斯特林数的列：

利用递推式$\left\{\begin{array}{c}n\\ m\end{array}\right\}=\left\{\begin{array}{c}n-1\\ m-1\end{array}\right\}+m\left\{\begin{array}{c}n-1\\ m\end{array}\right\}$

设$F_k(x)={\sum }_{i=0}^{\infty }\left\{\begin{array}{c}i\\ k\end{array}\right\}{x}^i$

不难发现$F_k(x)=x{F}_{k-1}(x)+kx{F}_k(x)$，那么$F_k(x)=\frac{x}{1-kx}{F}_{k-1}(x)$

那么$F_k(x)={\prod }_{i=1}^k\frac{x}{1-ix}=x^k({\prod }_{i=1}^k(1-ix){)}^{-1}$

考虑算${\prod }_{i=1}^k(1-ix)$。

${\prod }_{i=1}^k(1-ix)=x^k{\prod }_{i=1}^k(x^{-1}-i)$

注意到${\prod }_{i=1}^k(x-i)$翻转后就能得到$x^k{\prod }_{i=1}^k(x^{-1}-i)$

那么算${\prod }_{i=1}^k(x-i)=\frac{x^{\underline{k+1}}}{x}$ 即可。

复杂度$O(n\log n)$。