这篇是 [生成函数基础](https://lx-2003.blog.luogu.org/generating-function) 和 [简单的图计数](https://www.luogu.com.cn/blog/lx-2003/generating-function-advanced) 的重写。
由于时间跨度稍长，本文的文风或有变化（变得更像数学人了？）。
由于想写的内容较多，我决定将其拆为多篇文章。
本文的面向读者是：略有生成函数（幂级数）知识，但是或许不能熟练运用以进行组合计数的读者。若您完全不了解，可以先阅读 [生成函数基础](https://lx-2003.blog.luogu.org/generating-function)。
若您有修改意见（包括但不限于修订错误、章节编排、有趣的例子/习题提供），烦请联系 [
[email protected]](mailto:
[email protected])。
*2022年7月30日更新：添加了一些例子和粗体。*
# 0. 符号及约定
$x^0=1$ 对所有数成立，包括 $0$。
我们仍采取艾弗森括号约定，
即如果 $P$ 是一个命题，
则 $[P] = \begin{cases} 1 & P \\ 0 & \lnot P\end{cases}$。
$\mathbb{N}$ 表示自然数集合，即非负整数集合。
我们用“形式幂级数”代替“生成函数”，
即任意形如 $\sum_{n \geq 0} f_n x^n$ 的和式都是一个形式幂级数。
各种运算规则不变。
这样代替的原因是，我们只把数列的生成函数称为生成函数，
例如斐波那契数列的生成函数是 $\frac{1}{1 - x - x^2}$。
而这样的生成函数本身是一个幂级数。
（就好比说 $2$ 的倒数是 $0.5$。但是我们不会说“$0.5$ 是一个倒数”，
只会说“$0.5$ 是一个小数/有理数/分数”。
这里“生成函数”类比“倒数”，“形式幂级数”类比“有理数”）
# 1. 计数类
要计数，首先就要知道我们是要对什么东西计数。
## 1.1. 计数类
我们定义**计数类**如下 _（注记：这并非是标准术语，只是我对此物件的称呼。下同）_：
**定义 (计数类).**
**计数类**是带有“权值”的集合：即有一个集合 $\mathcal{A}$，以及一个**权值**映射 $\mathcal{A} \to \mathbb{N}$。
此外，我们采取如下记号：
- 对一个元素 $x \in \mathcal{A}$，用 $\lvert x \rvert$ 表示 $x$ 的权值。
- 对于非负整数 $n$，用 $\mathcal{A}_n$ 表示 $\mathcal{A}$ 中所有权值为 $x$ 的元素。
- 用 $A_n$ 表示权值为 $n$ 的元素个数，也就是 $\mathcal{A}_n$ 的大小。我们将非负整数序列 $\{A_0, A_1, \dots\}$ 称为 $\mathcal{A}$ 的**计数序列**。
为了可以正常计数，我们还加以如下限制：
- 对于非负整数 $n$，$A_n < \infty$。也就是说 $\mathcal{A}$ 中每种权值的元素只有有限个。
不然的话我们就数不出个数了。
---
由于我们只关心计数，不关心计数类里面具体有什么，因此我们定义计数类的同构如下：
**定义 (同构).**
如果两个计数类 $\mathcal{A}$ 和 $\mathcal{B}$ 的**计数序列相同**，即 $A_n = B_n$，
就说它们**同构**，记作 $\mathcal{A} \cong \mathcal{B}$.
等价地，如果我们可以把 $\mathcal{A}$ 和 $\mathcal{B}$ 中的元素一一对应起来，
使得每个元素和其对应的元素权值相同，就说这两个计数类同构。
---
**例.**
- 设 $\mathcal{W}$ 是**所有二进制字符串**（由 $0$ 和 $1$ 组成的串，包括空串）**的集合**，其中一个串的权值就是其长度。那么 $\mathcal{W}_n$ 就是所有长为 $n$ 的二进制串的集合，因此 $W_n = 2^n$。
- 设 $\mathcal{F}$ 是上面 $\mathcal{W}$ 的子集，要求二进制串中不能有相邻的两个 $1$。那么 $\mathcal{F}_n$ 就是所有长为 $n$、不包含相邻的 $1$ 的二进制串。我们将会看到，其计数序列 $F_n$ 正是斐波那契数列（习题 2）。
- 设 $\mathcal{B}$ 是无穷大的满二叉树（也就是，从一个根结点出发，每个点都有恰好两个子结点，无穷延伸下去）上**所有结点构成的集合**，其中每个点的权值是它的深度（根节点深度为 $1$）。不难发现，$B_n = 2^n$，因此 $\mathcal{B} \cong \mathcal{W}$。
- 设 $\mathcal{E} = \{ \epsilon \}$ 是只包含一个权值为 $0$ 的元素的集合（计数类）。因此 $E_0 = 1, E_n = 0 \quad (n \geq 1)$。
- 设 $\mathcal{T}$ 是**所有有根树的计数类**（这里是无标号的，也就是说两个无根树看作相同当且仅当他们同构），其中每棵树的权值是它的结点个数。则 $T_n$ 就是 $n$ 个点的有根树的个数。我们暂时不知道怎么计算 $T_n$。不过可以列举前几项：$T_0 = 0, T_1 = 1, T_2 = 1, T_3 = 2, T_4 = 4, T_5 = 9$。
- 设 $\mathcal{N}$ 是**所有“涂了两种色的项链“的计数类**：把黑色和白色的两种珠子串成环（可以只用一个珠子），翻转和旋转下一样的项链视作同一个。一条项链的权值就是其中珠子的个数。例如说，不超过四个点的项链共有如下几个。我们列举其计数序列的前几项：$N_1 = 2, N_2 = 3, N_3 = 4, N_4 = 6, N_5 = 8, N_6 = 14, N_7 = 20$。
**注记.** 我们永远使用 $\epsilon$ 表示一个权值为 $0$ 的元素；也表示空字符串、空序列等。
## 1.2 计数构造
我们当然需要一些“运算”，例如两个计数类可以相并，可以取乘积等。
**定义 (计数类的构造).**
如果我们有若干个计数类，我们可以用他们“组合”出一些新的计数类：若这种“组合”的方式是可以推广的，就称之为一种**构造**。
例如说，如果一种二元操作 $\mathtt{S}$，只要任取两个计数类 $\mathcal{A}, \mathcal{B}$，
它都能产出一个新的计数类 $\mathcal{C} = \mathtt{S}(\mathcal{A}, \mathcal{B})$,
$\mathtt{S}$ 就是一种构造。
（当然，构造也不一定是二元的。它可以是一元的，或者三元的等）。
由于我们只关心计数，因此对构造加以如下要求：
- 构造得到的类的计数序列只取决于被构造类的计数序列。
例如说，如果还是二元操作 $\mathtt{S}$，
就要求我们必须可以从 $\{ A_n \}, \{ B_n \}$ 算出 $\{ C_n \}$，
而不能具体取决于 $\mathcal{A}$ 或者 $\mathcal{B}$ 中具体有什么东西。
---
**例.**
- 对两个计数类 $\mathcal{A}, \mathcal{B}$，定义 $\mathcal{A} + \mathcal{B}$ 为这两个类的不交并（即把它们两个里的元素强行视为不相同的，然后取并）。一个元素在这个新计数集里的权值就和在原来的（$\mathcal{A}$ 或者 $\mathcal{B}$）里一样。
- 对两个计数类 $\mathcal{A}, \mathcal{B}$，定义 $\mathcal{A} \times \mathcal{B}$ 为这两个类的乘积。也就是说，这个新类里的元素就是一个两元组（pair）$(a, b)$，其中 $a \in \mathcal{A}, b \in \mathcal{B}$。权值定义为 $\lvert(a, b)\rvert = \lvert a \rvert + \lvert b \rvert$。
- 对一个计数类 $\mathcal{A}$，定义 $\mathtt{SEQ}(\mathcal{A})$ 为以 $\mathcal{A}$ 中元素组成的序列形成的计数类。也就是说 $\mathtt{SEQ}(\mathcal{A})$ 里一个元素就是一个任意长（可以为空）的序列（数组）$(a_1, a_2, \dots, a_n)$，其中每个 $a_i \in \mathcal{A}$。其权值定义为 $\lvert (a_1, a_2, \dots, a_n) \rvert = \lvert a_1 \rvert + \lvert a_2 \rvert + \dots + \lvert a_n \rvert$。
- 对一个计数类 $\mathcal{A}$，定义 $\mathtt{SET}(\mathcal{A})$ 为 $\mathcal{A}$ 的有限子集形成的计数类。也就是说 $\mathtt{SET}(\mathcal{A})$ 里一个元素就是一个子集 $\{a_1, a_2, \dots, a_n\}$，其中每个 $a_i \in \mathcal{A}$。其权值定义为 $\lvert \{a_1, a_2, \dots, a_n\} \rvert = \lvert a_1 \rvert + \lvert a_2 \rvert + \dots + \lvert a_n \rvert$。 _这与上一条的区别是，子集中的元素没有顺序，也就是说 $\{ a_1, a_2 \}$ 和 $\{ a_2, a_1 \}$ 视为同一个子集；且子集中每个元素只能出现一次。_
- 对一个计数类 $\mathcal{A}$，定义 $\mathtt{MSET}(\mathcal{A})$ 为 $\mathcal{A}$ 的有限多重子集形成的计数类。也就是说 $\mathtt{MSET}(\mathcal{A})$ 里一个元素就是一个多重子集 $\{a_1, a_2, \dots, a_n\}$，其中每个 $a_i \in \mathcal{A}$。其权值定义为 $\lvert \{a_1, a_2, \dots, a_n\} \rvert = \lvert a_1 \rvert + \lvert a_2 \rvert + \dots + \lvert a_n \rvert$。 _和上一条基本上相同，除了每个元素可以出现多次。_
**注记.** 在 $\mathtt{SEQ}, \mathtt{SET}, \mathtt{MSET}$ 三个构造中，我们都要求 $\mathcal{A}$ 不包含权值为 $0$ 的元素。不然的话，例如在 $\mathtt{SEQ}$ 中，任意长的只包含权值为 $0$ 元素的序列的权值都为 $0$。这样的话，就不满足“每种权值的元素只有有限个”的条件。
虽然 $\mathtt{SET}$ 没有这种担忧，但是一般来说我们还是做这样的要求，以简化讨论。
---
**例.**
1. 设 $\{ \bullet \}$ 为一个点构成的构造类，这个点的权值为 $1$。我们把这个构造类本身也记作 $\bullet$。那么：
- $\mathtt{SEQ}(\bullet)$ 中，每种权值的元素恰有一个：权值为 $n$ 的元素就是 $n$ 个 $\bullet$ 组成的序列。我们可以把这个东西看作所有链（图论中的链）的计数类（由于无标号，所以相同点数的链就是同一个）
- $\mathtt{SET}(\bullet)$ 中只有两个元素。一个元素权值为 $0$（空集），另一个元素权值为 $1$（$\{ \bullet \}$）。
- $\mathtt{MSET}(\bullet)$ 和 $\mathtt{SEQ}(\bullet)$ 类似。
2. 设 $\{ \bullet, \circ \}$ 两个点构成的构造类，他们的权值都是 $1$。那么：
- $\mathtt{SEQ}(\{ \bullet, \circ \})$ 中，权值为 $n$ 的元素有 $2^n$ 个。因为权值为 $n$ 的元素就是长为 $n$、每一项或黑或白的序列个数。这个东西显然与二进制串的计数类 $\mathcal{W}$ 等价。
- $\mathtt{SET}(\{ \bullet, \circ \})$ 里共有四个元素，权值分别为 $0, 1, 1, 2$。
- $\mathtt{MSET}(\{ \bullet, \circ \})$ 中权值为 $n$ 的元素有 $n+1$ 个：对每个 $0 \leq i \leq n$，由 $i$ 个黑点和 $n - i$ 个白点构成的多重集的权值都是 $n$。
3. 仍取 1.1 节中的计数类 $\mathcal{W}$。可以把 $\mathcal{W}$ 拆成三部分：空串、以 `0` 开头的二进制串、以 `1` 开头的二进制串。第一部分对应计数类 $\{ \epsilon \}$，第二部分对应计数类 $\{ \mathtt{0} \} \times \mathcal{W}$，第三部分对应计数类 $\{ \mathtt{1} \} \times \mathcal{W}$。其中 $\mathtt{0}, \mathtt{1}$ 的权值都为 $1$。因此我们有“组合恒等式”
$
\mathcal{W} \cong \{ \epsilon \} + (\{ \mathtt{0} \} \times \mathcal{W}) + (\{ \mathtt{1} \} \times \mathcal{W})
$。
4. 类似地，我们考虑 1.1 节中的 $\mathcal{F}$。可以把 $\mathcal{F}$ 也拆成三部分：空串、`0` 开头的串、`01` 开头的串。因此类似的我们有
$
\mathcal{F} \cong \{ \epsilon \} + (\{ \mathtt{0} \} \times \mathcal{F}) + (\{ \mathtt{01} \} \times \mathcal{F})
$。
## 1.3 生成函数
之后，我们就要引入生成函数。
**定义 (一般型生成函数).**
计数类 $\mathcal{A}$ 的一般型生成函数就是幂级数
$$
A(x) = \sum_{n = 0}^{\infty} A_n x^n.
$$
等价地说，这就是
$$
A(x) = \sum_{a \in \mathcal{A}} x^{\lvert a \rvert}.
$$
因为在下面这个式子里，$x^n$ 出现的次数也恰好是权值为 $n$ 的元素个数，即 $A_n$。
---
**注记 (幂级数).**
在这里，我们不详细讲述何为“幂级数”。
读者需要记住的是，幂级数虽然像是某种函数，但是其并不是真正的函数。
也就是说，你并不能将其“代入值”：
除了唯一的例外，即 $A(0) = A_0 + A_1 0 + A_2 0^2 + \dots = A_0$。
有关幂级数的定义，参看 [前篇](https://www.luogu.com.cn/blog/lx-2003/generating-function)。
---
由于在构造的定义中，我们要求构造出的计数序列只取决于原本的计数序列；
而计数序列和生成函数之间是可以互相转换的，因此我们可以从原本计数类的生成函数，计算出构造出的计数类的生成函数。
接下来，我们就要给出构造与生成函数之间的关系——也就是我们要引入生成函数的原因。
_定理 1 (无标号构造与生成函数). 第 1.2 节“例”中的构造对应的生成函数可以构造如下：_
$$\begin{aligned}
\mathcal{C} &= \mathcal{A} + \mathcal{B} &&\implies& C(x) &= A(x) + B(x), \\
\mathcal{C} &= \mathcal{A} \times \mathcal{B} &&\implies& C(x) &= A(x) \cdot B(x), \\
\mathcal{C} &= \mathtt{SEQ}(\mathcal{A}) &&\implies& C(x) &= \frac{1}{1-A(x)}, \\
\mathcal{C} &= \mathtt{SET}(\mathcal{A}) &&\implies& C(x) &= \prod_{n=1}^\infty (1+x^n)^{A_n} = \exp\Bigl(\sum_{k = 1}^\infty \frac{(-1)^{k - 1}}{k} A(x^k)\Bigr), \\
\mathcal{C} &= \mathtt{MSET}(\mathcal{A}) &&\implies& C(x) &= \prod_{n=1}^\infty \frac{1}{(1-x^n)^{A_n}} = \exp\Bigl(\sum_{k = 1}^\infty \frac{1}{k} A(x^k)\Bigr).
\end{aligned}$$
_证明._ 第一条是平凡的。
**对第二条**，我们考虑如何枚举 $\mathcal{C} = \mathcal{A} \times \mathcal{B}$ 的元素。
由于这样的元素都是二元组，可以分别枚举它的两个分量，即
$$
C(x) = \sum_{(a, b) \in \mathcal{C}} x^{\lvert (a, b) \rvert}
= \sum_{a \in \mathcal{A}} \sum_{b \in \mathcal{B}} x^{\lvert a \rvert + \lvert b \rvert}
= \sum_{a \in \mathcal{A}} x^{\lvert a \rvert} \sum_{b \in \mathcal{B}} x^{\lvert b \rvert}
= A(x)B(x).
$$
**对第三条**，我们给出这样的“组合恒等式”：
$$
\mathtt{SEQ}(\mathcal{A}) \cong \{ \epsilon \} + (\mathcal{A}) + (\mathcal{A} \times \mathcal{A}) + (\mathcal{A} \times \mathcal{A} \times \mathcal{A}) + \dots
$$
也就是，先枚举序列的长度；然后我们发现长为 $2$ 的序列其实就是数对，也就是 $\mathcal{A} \times \mathcal{A}$；同理，长为 $n$ 的序列其实就是 $\underbrace{\mathcal{A} \times \mathcal{A} \times \dots \times \mathcal{A}}_{n \text{个} \mathcal{A}}$。把他们“加起来”，就得到了所有序列。
而根据第二条，我们知道 $n$ 个 $\mathcal{A}$ 的乘积的生成函数就是 $A(x)^n$。因此
$$
C(x) = 1 + A(x) + A(x)^2 + \dots = \frac{1}{1 - A(x)}.
$$
**第四条和第五条**的证明将会留在后续章节给出。
$\square$
---
**例.** 取 1.1 节中的计数类 $\mathcal{W}$，按照 1.2 节的组合恒等式 $\mathcal{W} \cong \{ \epsilon \} + (\{ \mathtt{0} \} \times \mathcal{W}) + (\{ \mathtt{1} \} \times \mathcal{W})$，取两边的生成函数，我们得到
$$
W(x) = 1 + x \cdot W(x) + x \cdot W(x)
$$
解方程，可以得到 $W(x) = \frac{1}{1 - 2x}$.
## 1.4 习题
1. 给出 1.1 节中，$\mathcal{W}$ 和 $\mathcal{B}$ 之间的一一对应，使得每个元素的权值和它对应的元素的权值相等。
2. 利用 1.2 节中关于 $\mathcal{F}$ 的“组合恒等式”，证明其计数序列 $\{ F_n \}$ 确实是斐波那契数列。
3. 结合 1.2 节中关于 $\mathcal{F}$ 的组合恒等式以及定理 1 的内容，证明其生成函数是 $\frac{1}{1 - x - x^2}$。
4. 用与最后一个“例”或者习题 3 相同的方法，用另一种方式证明 $\mathtt{SEQ}$ 对应的生成函数.（提示：$\mathtt{SEQ}(\mathcal{A}) = \{ \epsilon \} + \mathcal{A} \times \mathtt{SEQ}(\mathcal{A})$）
5. (\*) 定理 1 证明中，关于 $\mathtt{SEQ}$ 的部分，我们将无穷多个计数类进行了相加。为什么可以这么做？（提示：有限性）
6. 取 1.1 节中的计数类 $\mathcal{T}$，说明 $\mathcal{T} = \{ \bullet \} \times \mathtt{MSET}(\mathcal{T})$。$\bullet$ 是一个权值为 $1$ 的元素，可以看作树的一个结点。（提示：考虑子树）
7. (\*) 证明定理 1 中 $\mathtt{SET}$ 和 $\mathtt{MSET}$ 的等式的后一部分（提示：考虑 $\ln$ 和 $\exp$ 的互逆性质）：
$$
\prod_{n=1}^\infty (1+x^n)^{A_n} = \exp\Bigl(\sum_{k = 1}^\infty \frac{(-1)^{k - 1}}{k} A(x^k)\Bigr), \quad \prod_{n=1}^\infty \frac{1}{(1-x^n)^{A_n}} = \exp\Bigl(\sum_{k = 1}^\infty \frac{1}{k} A(x^k)\Bigr).
$$
8. (\*\*) 给出关于 $\mathtt{SET}$ 和 $\mathtt{MSET}$ 的生成函数的等式的证明。（提示： 01 背包和无穷背包）
## 1.5 后记
本文某种意义上乃是心血来潮之作，会视反馈如何决定是否续写。若您有修改意见（包括但不限于修订错误、章节编排、有趣的例子/习题提供），烦请联系 [
[email protected]](mailto:
[email protected])。
欲知后事如何，且听下回分解。