生成函数与组合计数初步
该文为（金策《生成函数的运算与组合计数问题》）学习笔记
幂级数
级数：一个有穷或无穷序列 $a_0, a_1, a_2, …$ 的形式和「即 $\sum\limits_{i = 0} a_i$」被称为级数，序列中的项称作级数的通项
敛散性：极限是无穷即为发散「如 $f(x) = x$」；极限不为无穷即为收敛「如 $f(x) = \frac{1}{x}$」
那么幂级数即为形如 $\sum\limits_{n = 0}^{\infty} a_n(x - c)^n$ 或者化简为 $\sum\limits_{n = 0}^{\infty} a_nx^n$ 的形式
形式幂级数
形式幂级数
$$
A(x) = \sum\limits_{n = 0}^{\infty} a_nx^n
$$
形式与幂级数很像，但这里 $x$ 作为一个符号而不用具体数值带进去算，也不研究敛散性什么的
形式幂级数的加减乘法与多项式的有着类似的定义
实际运算时一般在 $\bmod{x^n}$ 的意义下进行，即仅取次数不超过 $n - 1$ 的项
笛卡儿积「直积」
有集合 $A, B$，则 $A, B$ 的笛卡儿积记作 $A \times B$，是所有可能组成的有序对的集合，且分别为 $A, B$ 的成员，即 $A \times B = \{(a, b) | a \in A \land b \in B\}$
笛卡儿积一般不满足交换律与结合律
笛卡儿积对集合的并和交满足分配律
$$
A \times (B \cup C) = (A \times B) \cup (A \times C) \\
A \times (B \cap C) = (A \times B) \cap (A \times C) \\
(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)
$$
生成函数与组合计数
组合对象
在组合计数问题中，一般定义了一类组合对象，该对象可能是满足某一性质的树、图等的集合，且一类组合对象 $A$ 其中的对象 $a \in A$ 有大小 $size(a)$，那么通常的计数任务即为求出 $A_n = (size (a) = n)$ 的数值
组合对象分为有标号与无标号，就比如结点有标号的无向图个数与结点无标号的无向图个数
这一部分非常重要，对于题目必须先明确组合对象，才可以通过 OGF 或 EGF 的公式来进行求解
普通生成函数「OGF」
数列 $A_0, A_1, A_2, …$ 的 OGF 定义为形式幂级数
$$
A(x) = \sum\limits_{n = 0}^{\infty} A_nx^n
$$
其中，$A$ 是一类无标号对象，$A_n$ 表示满足 $size(a) = n$ 的对象 $a \in A$ 的数量
或者可以这么理解，对于集合 $A = \{A_0, A_1, A_2, …\}$，其中 $A_i$ 的出现集合为 $M_i$，那么 $A$ 的 OGF 即为 $\prod\limits_{n = 0}^{\infty} \left(\sum\limits_{m \in M_n} x^m\right)$
考虑集合 $A, B$ 的笛卡儿积 $D = A \times B$，并有 $size(d) = size(a) + size(b)$，那么显然
$$
D_k = \sum\limits_{i + j = k} A_iB_j
$$
则有
$$
D(x) = A(x)B(x)
$$
生成函数 $\frac{1}{(1 - x)^n}$
这是一个比较常见的生成函数，接下来证明它的原数列为
$$
\sum\limits_{k = 0}^{\infty} \dbinom{k + n - 1}{n - 1} x^k
$$
有两种方法
证明方法一
首先显然
$$
\frac{1}{(1 - x)^n} = \prod_{i = 1}^n\left(\sum\limits_{k = 0}^{\infty} x^k\right)
$$
那么使用隔板法就可以直接证明了
证明方法二
- 结论：若数列 $a_0, a_1, a_2, …$ 的 OGF 是 $A(x)$，令 $s_n = \sum\limits_{i = 0}^n a_i$，则 $s_0, s_1, s_2, …$ 的 OGF $B(x)$ 为 $\frac{A(x)}{1 - x}$
- 证明：显然 $B(x) = \sum\limits_{n = 0}^{\infty} x^nA(x)$，得证
那么对于 $\frac{1}{(1 - x)^n}$ 的系数来讲，假如按照括号顺序合并，那么第 $n$ 项的系数就是第 $n - 1$ 项的系数加上上一版的第 $n$ 项系数，又初始系数全部为 $1$，所以这就是杨辉三角的递推关系，得证
指数生成函数「EGF」
数列 $A_0, A_1, A_2, …$ 的 EGF 定义为形式幂级数
$$
A(x) = \sum\limits_{n = 0}^{\infty} A_n\frac{x^n}{n!}
$$
其中，$A$ 是一类有标号对象，$A_n$ 的意义同 OGF
OGF 表示的是序列，而 EGF 表示的是集合，而集合不同于序列的就是其没有顺序关系，故需除以 $n!$
换个层面理解，对于多重集 $A = \{\infty \times A_0, \infty \times A_1, \infty \times A_2, …\}$
首先多重集的排列数为 $\frac{n!}{n_0!n_1!n_2!…}$
又其中 $A_i$ 的出现集合为 $M_i$，那么 $A$ 的 EGF 即为 $\prod\limits_{n = 0}^{\infty} \left(\sum\limits_{m \in M_n} \frac{x^m}{m!}\right)$
这个式子和上面那个定义式是一样的
同样地，考虑有标号对象的拼接，从 $A, B$ 中各选 $n, m$ 件，因为是有标号的，所以需要令其保持顺序，故选择方法共有
$$
\dbinom{n + m}{n}
$$
种，那么
$$
\begin{aligned}
D_k &= \sum\limits_{i + j = k} a_ib_j\frac{k!}{i!j!} \\
\frac{D_k}{k!} &= \sum\limits_{i + j = k} \frac{a_i}{i!}\frac{b_j}{j!}
\end{aligned}
$$
说明
$$
\begin{aligned}
D(x) &= \sum\limits_{k = 0}^{\infty}\left(\sum\limits_{i = 0}^{\infty} \dbinom{k}{i} a_ib_{k - i}\right)\frac{x^k}{k!} \\
&= \sum\limits_{k = 0}^{\infty}\sum\limits_{i = 0}^{\infty} \frac{a_i}{i!}\frac{b_{k - i}}{(k - i)!} \\
&= A(x)B(x)
\end{aligned}
$$
多项式求逆
该部分见 多项式求逆
生成函数相关应用
OGF 求 $Fibonacci$ 数列通项
定义 $Fibonacci$ 数列的 OGF
$$
F(x) = \sum\limits_{n = 1}^{\infty} fibo_n x^n
$$
因为 $Fibonacci$ 数列与其右移一位的 $Fibonacci$ 数列的差是其右移两位，得
$$
\begin{aligned}
F(x) - xF(x) &= x + x^2 \times F(x) \\
F(x) &= \frac{x}{1 - x - x^2} \\
&= \frac{x}{(1 - \frac{1 - \sqrt5}{2}x)(1 - \frac{1 + \sqrt5}{2}x)}
\end{aligned}
$$
现在要将该式裂项，假定 $F(x) = \frac{x}{(x - x_1)(x - x_2)}$，则裂项结果为 $\frac{t_1}{x - x_1} + \frac{t_2}{x - x_2}$，通项，得
$$
F(x) = \frac{t_1x - t_1x_2 + t_2x - t_2x_1}{(1 - x_1)(1 - x_2)}
$$
现在求解 $t_ 1, t_2$，有方程组
$$
\begin{cases}
t_1 + t_2 = 1 \\
t_1x_1 + t_2x_2 = 0
\end{cases}
$$
解出 $t_1, t_2$ 即可裂项，得
$$
F(x) = -\frac{1}{\sqrt5}\frac{1}{1 - \frac{1 - \sqrt5}{2}x} + \frac{1}{\sqrt5}\frac{1}{1 - \frac{1 + \sqrt5}{2}x}
$$
注意式子 $\frac{1}{1 - \frac{1 - \sqrt5}{2}x}$ ，这和式子 $\sum\limits_{n = 0}^{\infty} x^n = \frac{1}{1 - x}$，是一样的，可以直接还原为数列，故
$$
fibo_n = - \frac{1}{\sqrt5}\left(\frac{1 - \sqrt5}{2}\right)^n + \frac{1}{\sqrt5}\left(\frac{1 + \sqrt5}{2}\right)^n
$$
生成函数求伯努利数
伯努利数
伯努利数分为两类：
$B_n^-$ 表示第一类伯努利数，$B_n^+$ 表示第二类伯努利数，它们的差别在于第一项，分别为 $B_1^- = - \frac{1}{2}, B_1^+ = + \frac{1}{2}$
并且对于所有大于 $1$ 的奇数 $n$，其伯努利数 $B_n = 0$
现在定义等幂和
$$
S_m(n) = \sum\limits_{k = 1}^n k^m
$$
该式成为伯努利多项式，变量为 $n$，次数为 $m$，又
$$
S_m(n) = \frac{1}{m + 1}\sum\limits_{k = 0}^n \dbinom{m + 1}{k} B_k^+ n^{m + 1 - k}
$$
这就是伯努利数与伯努利多项式的关系
伯努利数可以通过递推式计算
$$
\sum\limits_{j = 0}^m \dbinom{m + 1}{j} B_j = 0 (B_0 = 1)
$$
它还可以通过 EGF 表达「证明占坑」
$$
\frac{x}{e^x - 1} = \sum\limits_{n = 0}^{\infty} B_n\frac{x^n}{n!}
$$
乘法逆元求伯努利数
$$
\begin{aligned}
\sum\limits_{n = 0}^{\infty} B_n\frac{x^n}{n!} &= \frac{x}{e^x - 1} \\
&= \frac{x}{\sum\limits_{n = 1}^{\infty} \frac{x^n}{n!}} \\
&= \frac{1}{\left(\sum\limits_{n = 0}^{\infty} \frac{x^n}{(n + 1)!}\right)}
\end{aligned}
$$
那么求一次乘法逆元即可
生成函数优化 $DP$
先给出一道来自论文的例题
字符集大小为 $m$。给定一个长度为 $k$ 的字符串 $s$，求出所有长为 $n$ 的串中，不包含子串 $s$ 的有多少个。$(n, m, k \le 10^5)$
直接 $DP$ 很好想，令 $f_i$ 表示前 $i$ 个位置填字符，并且第一次满足 $substr[i - k + 1, i] = s$
$$
f_i = m^{i - k} - \sum\limits_{j = 1}^{i - k} f_jm^{i - j - k} - \sum\limits_{j \in Next} f_{i - j}
$$
注意，此处的 $Next$ 集合定义为 $\{j \ge 0 | s[1, k - j] = s[j + 1, k]\}$，不然下面不好进行优化
接下来对 $DP$ 进行优化
考虑生成函数 $f(x) = \sum\limits_{n = 0}^{\infty} f_nx^n, N(x) = \sum\limits_{j \in Next} x^j$，根据上面的 $DP$ 方程，可以得到
$$
f(x) = \frac{x^k}{1 - mx} + \frac{x^k}{1 - mx}f(x) + f(x)(N(x) - 1)
$$
其中，第一项直接等比数列求和即可得到，至于 $2, 3$ 项，会发现这实际上就是两个生成函数相乘每一项的系数变化，并且注意此时 $N(x)$ 需减 $1$，防止计算到 $f_i$，故得该表示
化简，得
$$
f(x) = \frac{x^k}{x^k + (1 - mx)N(x)}
$$
那么最终答案为 $g_n = m^n - \sum\limits_{j = 1}^n f_jm^{n - j}$，其 OGF $g(x)$ 为
$$
\begin{aligned}
g(x) &= \frac{1}{1 - mx} - \frac{1}{1 - mx}f(x) \\
&= \frac{N(x)}{x^k + (1 - mx)N(x)}
\end{aligned}
$$
然后把下面那东西乘出来化简一下就又可以得到一个新的多项式，然后就可直接解了
复杂度 $O (n \log n)$
对数与指数运算
形式幂级数的复合运算
设 $A(x) = \sum\limits_{i = 0}^{\infty} a_ix^i, B(x) = \sum\limits_{i = 1}^{\infty} b_ix^i$，那么它们的复合为
$$
C(x) = A(B(x)) = \sum\limits_{i = 0}^{\infty} a_i(B(x))^i
$$
显然最终 $C(x)$ 可以归纳成 $C(x) = \sum\limits_{i = 0}^{\infty} c_ix^i$ 的形式
注意因为 $B(x)$ 是没有常数项的，所以 $B(x)^i$ 是从 $x^i$ 起步的，故 $B(x)$ 与 $A(x)$ 的复合可以定义「猜测是这样，真正原因占坑」
形式导数
对于 $A(x) = \sum\limits_{n = 0} ^{\infty} a_nx^n$，定义其形式导数
$$
A’(x) = \sum\limits_{n = 1}^{\infty} na_nx^{n - 1}
$$
经过验证可知
$$
\begin{matrix}
&(cA(x))’ = cA’(x) \\
&(A(x) \pm B(x))’ = A’(x) \pm B’(x) \\
&(A(x)B(x))’ = A’(x)B(x) + A(x)B’(x) \\
&\left(\frac{1}{A(x)}\right) = - \frac{A’(x)}{A(x)^2} \\
&(A(B(x))’ = A’(B(x))B’(x)
\end{matrix}
$$
这些基本求导法则对形式导数仍然成立
可微函数
可微函数指那些在其定义域中所有点都存在导数的函数，因此，可微函数的图像不存在任何间断点、尖点或是有垂直切线的点
泰勒级数
对于一个在实数或复数 $a$ 邻域上，以实数或复数作为变量，并且是无穷且可微的函数，其泰勒级数定义为以下形式的幂级数
$$
\sum\limits_{n = 0}^{\infty} \frac{f^{(n)}(a)}{n!}(x - a)^n
$$
如果 $a = 0$，那么该级数亦称作麦克劳林级数
实际上该式也就是泰勒展开的式子，证明：泰勒展开证明
常用函数的麦克劳林序列
$$
\begin{matrix}
\frac{1} {1 - x} = \sum\limits_{n = 0}^{\infty} x^n ~ ~ ~ ~ \forall x \in (- 1, 1) \\\
e^x = \sum\limits_{n = 0}^{\infty} \frac{x^n} {n!} ~ ~ ~ ~ \forall x \\\
\ln (1 + x) = \sum\limits_{n = 1}^{\infty} \frac{(- 1)^{n + 1} } {n}x^n ~ ~ ~ ~ \forall x \in (- 1, 1) \\\
\ln (1 - x) = - \sum\limits_{n = 1}^{\infty} \frac{x^i} {i}
\end{matrix}
$$
对数函数的计算
给定 $A(x) = 1 + \sum\limits_{n = 1}^{\infty} a_nx^n$ 「此处 $+ 1$ 是为了保证多项式求逆有解」
$$
\begin{aligned}
B(x) &= ln (A(x)) \\\
B’(x) &= \frac{A(x)}{A’(x)} \\\
B(x) &= \int \frac{A(x)}{A’(x)} \mathrm{d}x
\end{aligned}
$$
时间复杂度 $O (n \log n)$
指数函数的计算
给定 $A(x) = \sum\limits_{i = 1}^{\infty} a_ix^i$，令
$$
B(x) = e^{A(x)}
$$
那么经过归纳之后可以表示为 $B(x) = \sum\limits_{i = 0}^{\infty} b_ix^i$
那么接下来的事情就是要计算系数 $b_i$
显然 $b_0 = 1$，那么扩展，得
$$
b_i = \frac{1}{i}\sum\limits_{k = 1}^i a_kb_{i - k}
$$
接下来证明这个结论
证明方法一
先从简单的开始看起
$$
\begin{aligned}
&b_1 = \frac{a_1}{1!} \\\
&b_2 = \frac{a_2}{1!} + \frac{a_1 \times a_1}{2!} \\\
&b_3 = \frac{a_3}{1!} + \frac{a_1 \times a_2 + a_2 \times a_1}{2!} + \frac{a_1 \times a_1 \times a_1}{3!}
\end{aligned}
$$
对于 $b_4$ 先只列举一个：
$$
b_4 = … + \frac{a_1 \times a_1 \times a_2 + a_1 \times a_2 \times a_1 + a_2 \times a_1 \times a_1}{3!} + …
$$
可以发现，相当于现在处理的问题是，令 $n = \sum\limits_{i = 1}^{total} m_ip_i$，那么可以得到一个集合 $\{m_1 \times p_1, m_2 \times p_2, …\}$，那么要如何通过集合 $\{\{m_1 \times p_1, …, (m_i - 1) \times p_i, …, m_{total} \times p_{total}\}(i = 1, 2, …, total)\}$ 转移到该集合
由于最终得到的 $a_{p_1}a_{p_2}a_{p_3}…$ 无关紧要，故只考虑其系数
先考虑最终需要的值
$$
\begin{aligned}
final &= \frac{\frac{m!}{m_1!m_2!m_3!…}}{m!} \\\
&= \frac{1}{m_1!m_2!m_3!…}
\end{aligned}
$$
对于每个 $i$，容易知道它的贡献为 $\frac{1}{m_1!…(m_i - 1)!…m_{total}!}$
现在只有 $n$ 关于 $m_i, p_i$，的公式，考虑将每个 $i$ 的贡献乘上 $p_i$，求和，则有
$$
\frac{\sum\limits_i m_ip_i}{m_1!m_2!m_3!…} = \frac{n}{m_1!m_2!m_3!…}
$$
上下同除一个 $n$ 即可得解
好像这个证明有点麻烦，那么还有一个
证明方法二
两边求导，得
$$
B’(x) = A’(x)B(x)
$$
那么展开一下就得到该式了
那么有了这个结论之后求 $b_i$ 直接分治 $FFT$ 解决即可
时间复杂度 $O (n \log^2 n)$
牛顿迭代法
给定 $g(x)$，求解 $f(x)$
$$
g(f(x)) = 0
$$
假设已经处理出 $f(x)$ 的前 $n$ 项 $f_0(x)$，则有
$$
\begin{aligned}
f(x) &\equiv f_0(x) &\pmod{x^n} \\\
f(x) - f_0(x) &\equiv 0 &\pmod{x^n} \\\
(f(x) - f_0(x))^2 &\equiv 0 &\pmod{x^{2n}}
\end{aligned}
$$
那么将 $g(f(x))$ 泰勒展开，得
$$
\begin{aligned}
0 &= g(f(x)) \\\
&= \sum\limits_{n = 0}^{\infty} \frac{g^{(n)}(f_0(x))}{n!}(f(x) - f_0(x))^n \\\
&\equiv g(f_0(x)) + g’(f_0(x))(f(x) - f_0(x)) \pmod{x^{2n}} \\\
f(x) &\equiv f_0(x) - \frac{g(f_0(x))}{g’(f_0(x))} \pmod{x^{2n}}
\end{aligned}
$$
那么就可以 $O (n \log n)$ 求解 $f(x)$ 了
牛顿迭代法计算指数函数
给定 $A(x) = \sum\limits_{i = 1}^{\infty} a_ix^i$，求解 $e^{A(x)}$
令 $g(x) = \ln (x) - A(x)$，则有
$$
\begin{aligned}
f(x) &= f_0(x) - \frac{\ln (f_0(x)) - A(x)}{\frac{1}{f_0(x)}} \\
&= f_0(x)\left(1 - \ln (f_0(x)) + A(x)\right)
\end{aligned}
$$
牛顿迭代法计算 $k$ 次幂
给定多项式 $A(x) = \sum\limits_{i = 0}^n a_ix^i$ 及正整数 $k$，求解 $A(x)^k$
直接快速幂复杂度 $O (n \log^2 n)$，复杂度较高
接下来讨论：
若 $A(x)$ 常数项为 $1$，则
$$
A(x)^k = e^{k \ln A(x)}
$$
若 $A(x)$ 常数项不为 $1$，则进行转化
设 $A(x)$ 得最低次项为 $a_tx^t$，转化为常数项为 $1$，即
$$
A(x)^k = a_t^kx^{kt}\left(\frac{A(x)}{a_tx^t}\right)^k
$$
同样牛顿迭代法即可
时间复杂度 $O (n \log n)$
组合计数
序列计数
有一类组合对象 $A$，$A$ 的元素可以组成序列「最简单的例子就是由 $\{n_1 \times l_1, n_2 \times l_2, …\}$ 这样的长度集合拼成长度为 $k (k = 1, 2, …)$ 的方案数所构成的序列」，则这些序列定义了新的一类组合对象 $B$，即
$$
B(x) = \sum\limits_{k = 0}^{\infty} A(x)^k = \frac{1}{1 - A(x)}
$$
该结论对有无标号都成立
集合计数
有标号的集合计数
集合与序列的区别在于元素没有顺序，故需去除重复的，则
$$
B(x) = \sum\limits_{n = 0}^{\infty} \frac{A(x)^n}{n!} = e^{A(x)}
$$
有标号的连通图计数
设 $G$ 是所有简单连通图，则其 EGF 为
$$
G(x) = \sum\limits_{n = 0}^{\infty} 2^{\frac{n(n - 1)}{2}}\frac{x^n}{n!}
$$
可以将所有简单连通图看作连通分量「其集合为 $C(x)$」的集合，故
$$
\begin{aligned}
G(x) &= e^{C(x)} \\
C(x) &= \ln G(x)
\end{aligned}
$$
时间复杂度 $O (n \log n)$
无标号的集合计数
完全背包计数
体积为 $i$ 的有 $a_i$ 种不同的物品，每种物品有无限个，那么最终装满体积为 $V$ 的背包的方案数
显然答案为
$$
\begin{aligned}
Ans &= \prod_{i = 1}^n\left(\sum\limits_{j = 0}x^{ij}\right)^{a_i} \\
&= \prod_{i = 1}^n\left(\frac{1}{1 - x^i}\right)^{a_i} \\
\end{aligned}
$$
接下来用对数函数化乘为加
$$
\begin{aligned}
Ans &= \exp (\sum\limits_{i = 1}^n \ln \left(\left(\frac{1}{1 - x^i}\right)^{a_i}\right)) \\
&= \exp (- \sum\limits_{i = 1}^n a_i\ln(1 - x^i)) \\
&= \exp (\sum\limits_{i = 1}^na_i\left(\sum\limits_{n = 1}^{\infty} \frac{x^{in}}{n}\right)) \\
\end{aligned}
$$
接下来令 $A(x) = \sum\limits_{i = 1}^{\infty} a_ix^i$，换为枚举 $n$，得
$$
Ans = \exp (\sum\limits_{n = 1}^{\infty} \frac{1}{n}A(x^n))
$$
那么时间复杂度的计算就是调和级数，总时间复杂度 $O (n \log n)$
环的计数
有标号的环的计数
圆排列问题
从 $n$ 个元素中不重复地取出 $m$ 个元素在一个圆周上，并且每个排列经过旋转后不会与其它任意一个排列相同，叫做这 $n$ 个元素的圆排列
显然 $n$ 个元素取 $m$ 个作圆排列的方案数为
$$
total = \frac{A_n^m}{m}
$$
那么，对于一类组合对象 $A$，其圆排列的生成函数为
$$
\sum\limits_{k = 1}^{\infty} \frac{A(x)^k}{k} = - \ln (1 - A(x))
$$
有标号的无向连通图中的基环树个数计数
考虑将基环树拆分为若干棵树的拼凑
注意此时需考虑的是有根树，即先将节点看作组合对象，根据 $Cayley$ 定理，$n$ 个节点的完全图有 $n^{n - 1}$ 棵有根树，则有根树的 EGF $T(x)$ 为
$$
T(x) = \sum\limits_{n = 1}^{\infty} n^{n - 1}\frac{x^n}{n!}
$$
那么此时将有根树看作组合对象，则将它们组成环，即基环树的 EGF $G(x)$ 为
$$
\begin{aligned}
G(x) &= \frac{1}{2}\sum\limits_{n = 3}^{\infty} \frac{T(x)^k}{k} \\
&= - \frac{1}{2}\ln (1 - T(x)) - \sum\limits_{k = 1}^2 \frac{T(x)^k}{k}
\end{aligned}
$$
无标号的环的计数
「由于需要群论知识，故留坑」
「以下留坑」