喝美了~
生成函数求常系数齐次线性递推
若 $\sum\limits_{i=0}^k C_iF_{n-i}=0$，求 $F$ 的生成函数。
构造 $F_t(x)=C_tx^t(F(x)-\sum\limits_{i=0}^{k-t-1}F_ix^i)$，提取 $x^n$ 项系数：$[x^n]F_t(x)=[n\ge k]C_tF_{n-t}$。
再对 $F_t$ 关于 $t$ 求和：
$$ \begin{aligned} \sum\limits_{t=0}^kF_t(x)&=\sum\limits_{t=0}^k\sum\limits_{n=0}[n\ge k]C_tF_{n-t}x^n\\ &=\sum\limits_{n=0}[n\ge k]x^n\sum\limits_{t=0}^k C_tF_{n-t} \end{aligned} $$
而 $\sum\limits_{i=0}^kC_iF_{n-i}=0$，因此 $\sum\limits_{t=0}^kF_t(x)=0$，即
$$ \sum\limits_{t=0}^k C_tx^t(F(x)-\sum\limits_{i=0}^{k-t-1}F_ix^i)=0\\ F(x)\cdot \sum\limits_{t=0}^tC_tx^t=\sum\limits_{t=0}^{k-1}C_tx^t\sum\limits_{i=0}^{k-t-1}F_ix^i $$
是关于 $C$ 的生成函数，以及右边的余项 $P(x)$，于是 $F(x)=\dfrac{P(x)}{C(x)}$。
特征根法
矩阵乘法
Bostan-Mori
常用于有标号
斯特林数
第一类斯特林数
$\begin{bmatrix}n\\m\end{bmatrix}$：$n$ 个元素组成 $m$ 组轮换的方案数。考虑当前数增环还是接在某个元素之后，有 $\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}$。
不存在实用的通项公式。
恒等式：
-
$\sum\limits_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}=n!$。轮换与排列一一对应。
-
$x^{\overline n}=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i$。考虑归纳：对于 $n=0,n=1$ 显然成立。
$$ \begin{aligned} x^{\overline{n+1}}&=(x+n)x^{\overline n}\\ &=(x+n)\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum\limits_{i=1}^{n+1}\begin{bmatrix}n\\{i-1}\end{bmatrix}x^{i}+n\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum\limits_{i=1}^n\left(\begin{bmatrix}n\\i-1\end{bmatrix}+n\begin{bmatrix}n\\i\end{bmatrix}\right)x^i+x^{n+1}+[n=0]\\ &=\sum\limits_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}x^i \end{aligned} $$
- $x^{\underline n}=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i$。
考虑 $x^{\underline n}=(-1)^n(-x)^{\overline n}=(-1)^n\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-x)^i=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i$。
二元生成函数
$$\sum\limits_{i\ge0}\sum\limits_{j\ge0}\begin{bmatrix}i\\j\end{bmatrix}\dfrac{x^iy^j}{i!}=(1-x)^{-y}$$
第一类斯特林数行的生成函数，由于总元素固定，因此我们希望求 OGF：$\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i=x^{\overline n}$。
第一类斯特林数列的生成函数，总元素并不固定，我们希望求 EGF。对于一个圆排列的生成函数为 $C(x)=\sum\limits_{i\ge1}\dfrac{(i-1)!x^i}{i!}=\sum\limits_{i\ge1}\dfrac{x^i}{i}=\ln\dfrac{1}{1-x}$。于是 $k$ 个圆排列的生成函数就是 $\dfrac{(C(x))^k}{k!}$，即 $\dfrac{1}{k!}\left(\ln\dfrac{1}{1-x}\right)^k$。
第二类斯特林数
$\begin{Bmatrix}n\\m\end{Bmatrix}$：$n$ 个元素划分成 $m$ 个非空集合的方案数。考虑当前新元素是开新集合还是放在已有集合，有 $\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$。
恒等式
-
$m^n=\sum\limits_{i=0}^m\begin{Bmatrix}n\\i\end{Bmatrix}i!\dbinom{m}{i}$。考虑组合意义，左式是 $n$ 个有标号球塞到 $m$ 个有标号盒且可空的方案数。右式枚举塞到多少个非空盒子里，再枚举把 $n$ 划分到 $i$ 个球的方案，最后再乘上盒子的相对顺序 $i!$。
-
$\begin{Bmatrix}n\\m\end{Bmatrix}=\dfrac{1}{m!}\sum\limits_{i=0}^m(-1)^{m-i}\dbinom mii^n$。考虑对上式二项式反演。这也是第二类斯特林数的通项公式。
-
$\sum\limits_{i=0}^ni^k=\sum\limits_{j=0}^i\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n+1}{j+1}$。这是第一个式子的推论，考虑杨辉三角一列和。
二元生成函数
$$\sum\limits_{i\ge 0}\sum\limits_{j\ge 0}\begin{Bmatrix}i\\j\end{Bmatrix}\dfrac{x^ny^j}{i!}=\exp(y(e^x-1))$$
行的生成函数： $[x^m]F(x)=\dfrac{1}{m!}\sum\limits_{i=0}^m(-1)^{m-i}\dfrac{m!}{i!(m-i)!}i^n=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\dfrac{i^n}{i!}$，实际上就是 $e^{-x}$ 与 $A(x)=\sum\limits_{i\ge0}\dfrac{i^n}{i!}x^i$ 的卷积形式，直接卷就完了。
列的生成函数。考虑一个非空集合的生成函数，显然是 $\sum\limits_{i\ge1}\dfrac{x^i}{i!}=e^x-1$。于是 $k$ 个非空集合的生成函数就是去掉集合相对顺序后的，即 $\dfrac{1}{k!}(e^x-1)^k$。
相互关系
上升幂、下降幂、普通幂的相互转换
上升幂转普通幂：$x^{\overline n}=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i$。
普通幂转上升幂：$x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}x^{\overline i}$。可以从第四个式子中推来，即 $(-x)^n=(-1)^n(x)^n$，另 $x^{\underline i}=(-1)^i(-x)^{\overline i}$。
下降幂转普通幂：$x^{\underline n}=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i$。
普通幂转下降幂：$x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}$。
斯特林反演
$$F_n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}G_i\iff G_n=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}F_i$$
$$F_n=\sum\limits_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}G_i\iff G_n=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}F_i$$
$$F_n=\sum\limits_{i=n}\begin{Bmatrix}i\\n\end{Bmatrix}G_i\iff G_n=\sum\limits_{i=n}(-1)^{i-n}\begin{bmatrix}i\\n\end{bmatrix}F_i$$
$$F_n=\sum\limits_{i=n}(-1)^{i-n}\begin{Bmatrix}i\\n\end{Bmatrix}G_i\iff G_n=\sum\limits_{i=n}\begin{bmatrix}i\\n\end{bmatrix}F_i$$
求生成函数的碎碎念
除了第一类的行，其他都是极其好求的，卷积或者快速幂即可。对于 $x^{\overline n}$，注意到 $x^{\overline {2n}}=x^n(x+n)^{\overline{n}}$。然后
$$ \begin{aligned} (x+n)^{\overline n}&=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(x+n)^i\\ &=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}\sum\limits_{j=0}^i\dbinom ijx^jn^{i-j}\\ &=\sum\limits_{j=0}^n\dfrac{x^j}{j!}\sum\limits_{i=0}^{n-j}(i+j)!\begin{bmatrix}n\\i+j\end{bmatrix}\dfrac{n^{i}}{(i)!} \end{aligned} $$
后面的系数很像卷积形式，考虑 $F(x)=\sum\limits_{i\ge 0}i!\begin{bmatrix}n\\i\end{bmatrix}x^{n-i}$，$G(x)=\sum\limits_{i\ge 0}\dfrac{n^i}{i!}x^i$。这个技巧叫翻转多项式，然后就是 $\dfrac{1}{j!}[x^{n-j}]F\cdot G$。
一些题目
P4451 [国家集训队] 整数的lqp拆分
设答案的生成函数为 $G(x)$，容易发现 $[x^n]G(x)=\sum\limits_{i=0}^n f_ig_{n-i}$，其中 $g_0=1$。于是有 $G=F\cdot G+1$。
$$ \begin{aligned} G&=\dfrac{1}{1-F}\\ &=\dfrac{1-x-x^2}{1-2x-x^2}\\ &=1+\dfrac{x}{1-2x-x^2} \\ \end{aligned} $$
设 $\dfrac{x}{1-2x-x^2}=\dfrac{a}{x-c}+\dfrac{b}{x-d}$，解方程，有
P4841 [集训队作业2013] 城市规划
求有标号无向连通图个数。
设 $f_n$ 为点数为 $n$ 的有标号无向连通图个数，$g_n$ 为点数为 $n$ 的有标号无向图个数。考虑边是否存在，有 $g_n=2^{\binom n2}$，考虑固定 $1$ 所在连通块大小，有 $g_n=\sum\limits_{i=1}^n\dbinom{n-1}{i-1}f_{i}g_{n-i}$。这就是二者卷积的结果，设 $g$ 的 EGF 为 $G(x)$，$f$ 的 EGF 为 $F(x)$。
上式可化作 $\dfrac{g_n}{(n-1)!}=\sum\limits_{i=1}^n\dfrac{f_i}{(i-1)!}\cdot\dfrac{g_{n-i}}{(n-i)!}$，即 $G’(x)=F’(x)\cdot G(x)$。
$$ \begin{aligned} \int \dfrac{G’(x)}{G(x)}\mathrm dx&=\int F’(x)\mathrm dx \\ \int \dfrac{\mathrm d G(x)}{G(x)}&=F(x)+C \\ \ln G(x)&=F(x)+C \end{aligned} $$
考虑这个常数是多少，考虑求 $x^0$ 项，$[x^0]G(x)=[x^0]F(x)=1$，因此这个 $C=0$。于是 $F(x)=\ln G(x)$。
P4389 付公主的背包
给出 $n$ 种商品，有无限个。求填满 $m$ 的方案数。
答案的生成函数就是 $F(x)=\prod\limits_{i=1}^n\dfrac{1}{1-x^{v_i}}$，但是直接算是 $\mathcal O(nm\log m)$ 的，不行。
考虑乘转加，$\ln \dfrac{1}{(1-x^V)}=-\ln (1-x^V)=\sum\limits_{i\ge1}\dfrac{x^{Vi}}{i}$。答案就是 $\sum\limits_{V\in v}\sum\limits_{i\ge 1}\dfrac{x^{i\cdot V}}{i}$，也就是对于一个出现 $k$ 次的 $v$，在对应位置上加 $k$ 次即可，复杂度变成调和级数，求 $\ln$ 求 $\exp$ 是线性对数的，总复杂度就是线性对数。
这个做法好像是叫欧拉变换。
P5320 [BJOI2019] 勘破神机
设 $g(i)$ 表示用 $1\times 2$ 填满 $3\times i$ 的格子的方案数，$f(i)$ 表示用 $1\times 2$ 填满 $2\times i$ 的方案数。给出 $l,r,k,m$，当 $m=2$ 时令 $F=f$，反之令 $F=g$。求 $\dfrac{1}{r-l+1}\sum\limits_{i=l}^r\dbinom{F(i)}{k}$ 在模 $998244353$ 下的结果。
$f$ 显然是 Fibonacci，有：
$$f_{n}=\dfrac{1}{\sqrt 5}\left(\dfrac{\sqrt 5-1}{2}\right)^n-\dfrac{1}{\sqrt 5}\left(\dfrac{\sqrt 5+1}{2}\right)^n$$
呃，左移一位才对。
显然 $i$ 为偶数时有解，设 $g_i$ 表示铺满 $3\times 2i$ 网格的方案数。观察一下有 $g_n=4g_{n-1}-g_{n-2}$，解得两个根为 $x_1=2+\sqrt 3,x_2=2-\sqrt 3$。设 $g_n=Ax_1^n+Bx_2^n$，于是
$$g_n=\dfrac{3-\sqrt 3}{6}(2+\sqrt 3)^n+\dfrac{3+\sqrt 3}{6}(2-\sqrt 3)^n$$
$ans_1$ 是 $\dfrac{1}{r-l+1}\sum\limits_{i=l}^r\dbinom{f(i)}{k}$，$ans_2$ 是类似的。考虑怎么求这个东西。
$$ \begin{aligned} \sum\limits_{n=l}^r\dbinom{f_n}{k}&=\dfrac{1}{k!}\sum\limits_{n=l}^rf_n^{\underline{k+1}}\\ &=\dfrac{1}{k!}\sum\limits_{n=l}^r\sum\limits_{i=0}^k\begin{bmatrix}k\\i\end{bmatrix}(-1)^{k-i}(A\alpha^n+B\beta^n)^i \\ &=\dfrac{1}{k!}\sum\limits_{n=l}^r\sum\limits_{i=0}^k\begin{bmatrix}k\\i\end{bmatrix}(-1)^{k-i}\sum\limits_{p=0}^i\dbinom{i}{p}A^pB^{i-p}(\alpha^p\beta^{i-p})^n\\ &=\dfrac{1}{k!}\sum\limits_{i=0}^k\begin{bmatrix}k\\i\end{bmatrix}(-1)^{k-i}\sum\limits_{p=0}^i\dbinom{i}{p}A^pB^{i-p}\sum\limits_{n=l}^r(\alpha^p\beta^{i-p})^n \\ &=\dfrac{1}{k!}\sum\limits_{i=0}^k\begin{bmatrix}k\\i\end{bmatrix}(-1)^{k-i}\sum\limits_{p=0}^i\dbinom{i}{p}A^pB^{i-p}\dfrac{(\alpha^p\beta^{i-p})^{r+1}-(\alpha^p\beta^{i-p})^{l}}{\alpha^p\beta^{i-p}-1} \end{aligned} $$
你发现最后是一个等比数列求和的式子，可以很快算出来。而前面两个求和可以 $\mathcal O(k^2)$ 地求出，且 $k\le 501$，于是就做完了。
不过这题中的 $\sqrt 5$ 与 $\sqrt 3$ 在模 $998244353$ 的意义下并不存在，怎么办呢。考虑扩域，即表示为 $a+b\sqrt 3$，反正最后根号也会消掉，于是就可以了。
P4931 [MtOI2018] 情侣？给我烧了！（加强版）
设 $f_i$ 表示钦定有 $i$ 对情侣和睦的方案数，$g_i$ 表示恰好有 $i$ 对情侣和睦的方案数。二项式反演有 $g_k=\sum\limits_{i=k}^n(-1)^{k+i}\dbinom ikf_i$。
而 $f_i$ 也是好算的，考虑钦定 $i$ 对之后再选位置，有 $f_i=\dbinom ni\dbinom nii!2^i(2n-2i)!$，于是答案就是
$$ \begin{aligned} \sum\limits_{i=k}^n{(-1)}^{k+i}\dbinom ik\dbinom ni\dbinom nii!2^i(2n-2i)!&=\dfrac{(n!)^2}{k!}\sum\limits_{i=k}^n\dfrac{(-1)^{k-i}}{(i-k)!}\cdot\dfrac{(2n-2i)!}{((n-i)!)^2}\cdot 2^i\\ &=\dfrac{(n!)^22^k}{k!}\sum\limits_{i=0}^{n-k}\dfrac{(-2)^i}{i!}\cdot\dbinom{2(n-k)-i}{(n-k)-i} \end{aligned} $$
设 $t=n-k$，则
$$ \begin{aligned} \dfrac{(n!)^22^k}{k!}\sum\limits_{i=0}^{n-k}\dfrac{(-2)^i}{i!}\cdot\dbinom{2(n-k)-i}{(n-k)-i}&=\dfrac{(n!)^22^k}{k!}\sum\limits_{i=0}^{t}\dfrac{(-2)^i}{i!}\cdot\dbinom{2t-i}{t-i} \end{aligned} $$
设 $F(x)=\sum\limits_{i\ge0}\dfrac{(-2)^i}{i!}x^i$，$G(x)=\sum\limits_{i\ge0}\dbinom{2i}{i}x^i$，答案就是
$$\dfrac{(n!)^22^k}{k!}[x^{n-k}]F(x)\cdot G(x)$$
容易注意到 $F(x)=e^{-2x}$，而 $G$ 和卡特兰的生成函数比较类似，平移后求导。设 Catalan 数的生成函数为 $C(x)$，于是 $G(x)=(xC(x))’$，即 $G(x)=\dfrac{1-\sqrt{1-4x}}{2}$。所求即为：
$$\dfrac{(n!)^22^k}{k!}[x^{n-k}]\dfrac{e^{-2x}}{\sqrt{1-4x}}$$
设 $F(x)=\dfrac{e^{-2x}}{\sqrt{1-4x}}$，平方，把分母乘上去。
$$ \begin{aligned} (1-4x)F^2&=e^{-4x}\\ -4F^2+2F\cdot F’(1-4x)&=-4e^{-4x}\\ -4F^2+2F\cdot F’(1-4x)&=-4(1-4x)F^2\\ 16xF&=(2-8x)F’\\ 8xF&=F’-4xF’ \end{aligned} $$
于是 $F_{i+1}\times (i+1)=4i\cdot F_i+8F_{i-1}$，其中 $F_0=1,F_1=0$。对一组 $(n,k)$，答案就是 $F_{n-k}\times\dfrac{(n!)^22^k}{k!}$。
EGF
P5219 无聊的水题 I
有标号树计数，最大度数恰好为 $m$。
恰好先转成 $[\le m]-[\le m-1]$。
考虑 Prüfer 序列，每个点在序列上出现次数为度数 $-1$。考虑每个点的生成函数，即 $F(x)=\sum\limits_{i=0}^{m}\dfrac{x^i}{i!}$，于是答案的 EGF 就是 $F^n(x)$。
然后多项式快速幂一下就好，由于首位一直为 $1$ 所以可以 $\exp$ 再 $\ln$。
P5162 WD与积木
给出 $n$ 个数，往 $n$ 组里随机分配（区分编号，区分第几组），求非空组数的期望。
选一组的 EGF 为 $F(x)=\sum\limits_{i=0}\dfrac{x^i}{i!}-1=e^x-1$。
选 $k$ 组的 EGF 即 $F(x)^k$，于是所有方案的 EGF 就是 $\sum\limits_{k=0} F(x)^k=\dfrac{1}{1-F(x)}=\dfrac{1}{2-e^x}$。
以上是只看方案的答案，考虑加权（即统计集合数）后的 EGF。
$$ \begin{aligned} \sum\limits_{k=0}kF(x)^k&=\dfrac{F(x)}{(1-F(x))^2}\ &=\dfrac{e^x-1}{(2-e^x)^2} \end{aligned} $$
于是答案就是 $\dfrac{[x^n]\dfrac{e^x-1}{(2-e^x)^2}}{[x^n]\dfrac{1}{2-e^x}}$，然后随便做啦。
P5824 十二重计数法
$\text{I}$：每个球选一遍，$m^n$。
$\text{II}$：若 $m>n$ 答案为 $0$。反之，$m^{\underline n}$。
$\text{III}$：把 $n$ 个元素放到 $m$ 个集合中，就是将 $n$ 个元素塞到 $m$ 个集合中的方案，然后再乘上集合的相对顺序。$m!\begin{Bmatrix}n\\m\end{Bmatrix}$。
$\text{IV}$：考虑塞到几个盒子里，于是答案就是 $\sum\limits_{i=1}^m\begin{Bmatrix}n\\i\end{Bmatrix}$。
$\text{V}$：$[n\le m]$。
$\text{VI}$：$\begin{Bmatrix}n\\m\end{Bmatrix}$。
$\text{VII}$：插板法，$\dbinom{n+m-1}{m-1}$。
$\text{VIII}$：$\dbinom mn$。
$\text{IX}$：还是插板法，$\dbinom{n-1}{m-1}$。
$\text{X}$：分拆。分别考虑每个大小的有几个，大小为 $i$ 的生成函数为 $\sum\limits_{j\ge0}x^{ji}=\dfrac{1}{1-x^i}$，答案就是 $[x^n]\prod\limits_{i=1}^m\dfrac{1}{1-x^i}$。先 $\ln$ 再 $\exp$ 回去就做完了。特别的，你也许会疑惑这个限制是最大数不超过 $m$，但是根据分拆优秀的对偶性质（详见 Ferrers Diagram），这实际上是对称的。
$\text{XI}$：$[n\le m]$。
$\text{XII}$：和 $\text X$ 问题等价，令 $n\gets n-m$。