数数太难了，学不会数数。

[TOC]

基础知识

第一类斯特林数

$S_u(n, m)$ 表示 $n$ 个不同元素构成 $m$ 的圆排列的方案数。

$$S_u(n, m) = S_u(n - 1, m - 1) + (n - 1) \times S_u(n - 1, m)$$

有符号：$S_s(n, m) = (-1)^{n + m} S_u(n, m)$

有符号生成函数：$x^{ \underline n}$

第二类斯特林数

$S(n, m)$ 表示把 $n$ 个不同元素拆分成 $m$ 个非空集合的方案数。

$$S(n, m) = S(n - 1, m - 1) + m \times S(n - 1, m) \\ S(n, m) = \frac 1{m!} \sum{(-1)^k \binom mk (m - k)^n}$$

贝尔数为第二类斯特林数之和。

拆分数

$f_n$ 代表大小为 $n$ 的正整数拆分成若干个无序的正整数的和的方案数。

两种 dp，$f_{i, j}$ 表示拆分成若干个小于等于 $j$ 的数字的方案数，$f_{i, j} = f_{i - j, j} + f_{i, j - 1}$。$g_{i, j}$ 表示拆分成 $j$ 个数字的方案数，$g_{i, j} = g_{i - j, j} + g_{i - 1, j - 1}$。

单独用任何一个复杂度都是 $O(n^2)$。考虑大于 $\sqrt n$ 的数字只有 $\sqrt n$ 个，结合二者，复杂度 $O(n \sqrt n)$。

生成函数：$\displaystyle \frac 1{ \sum_{n = 0}^\infty{(-1)^k x^{k(3k \pm 1)}}}$

形式幂级数

形如 $\displaystyle \sum_{n = 0}^\infty{a_n x^n}$。

$$\sum_{n = 0}^\infty{a_n x^n} \pm \sum_{n = 0}^\infty{b_n x^n} = \sum_{n = 0}^\infty{(a_n \pm b_n) x^n} \\ \sum_{n = 0}^\infty{a_n x^n} \pm \sum_{n = 0}^\infty{b_n x^n} = \sum_{n = 0}^\infty{\left( \sum_{k = 0}^n{a_k b_{n - k}}\right) x^n}$$

闭形式

形式幂级数的表达形式是一个长度为无穷的多项式，但是对于部分的形式幂级数，存在长度有限的函数能够直接表示它，我们通常称之为闭形式。

考虑一个最简单的例子：$\displaystyle \sum_{n = 0}^\infty{x^n} = \frac 1{1 - x}$。

注意到闭形式其实存在收敛域的问题。但形式幂级数中，$x$ 仅仅是一个符号，我们忽略讨论收敛域。

一些例子

• $\displaystyle \sum_{n = 0}^\infty{x^n} = \frac 1{1 - x}$，这个可以等比数列求和公式（存在收敛域，不讨论）
• 显然能得到 $\displaystyle \sum_{n = 1}^\infty{x^n} = \frac x{1 - x}$
• 考虑 $\displaystyle \sum_{n = 1}^\infty{n x^n}$，这个怎么求呢？
  1. 对第一个式子两边求导：$\displaystyle \left( \sum_{n = 0}^\infty{x^n}\right)’ = \left( \dfrac 1{1 - x}\right)’ \Rightarrow \sum_{n = 0}^\infty{(n + 1) x^n} = \frac 1{(1 - x)^2}$。再两边乘 $x$ 即可得到 $\displaystyle \sum_{n = 1}^\infty{n x^n} = \dfrac x{(1 - x)^2}$。
  2. $\displaystyle \left( \sum_{n = 0}^\infty{x^n}\right) \ast \left( \sum_{n = 0}^\infty{x^n}\right) = \sum_{n = 0}^\infty{(n + 1) x^n} = \frac 1{(1 - x)^2}$，和上一种方法殊途同归。
• 我们还知道 $\displaystyle \sum_{n = 0}^\infty{ \frac 1{n!} x^n} = e^x$。
• 其实上面的几个就是各种生成函数。你已经上贼船了。

组合对象

组合计数是一类常见问题，通常给定我们若干组合条件，对于每个组合对象，有某个函数 size 衡量了它的大小，如图的节点数，序列的长度等。size 为 $n$ 的满足组合条件的组合对象个数为有限个，记为 $A_n$ ，题目要求某个 $A_n$。

组合对象分为是否有标号的两种，指的是是否考虑组合对象内部的元素有不同的区别，例如无标号的三个点的图只有 $4$ 种，而有标号的有 $8$ 种。

生成函数引入 - 二项式定理

怎么让文化课选手也能理解生成函数呢？我们从大家都会的二项式定理说起。

此处选用了所有亲高中生的写法，比如将组合数 $\displaystyle \binom nm$ 改用 $C_n^m$ 表示。

如果你学过了选修 2-3，你会知道

$$(1 + x)^n = C_n^0 + C_n^1 x + C_n^2 x^2 + \cdots + C_n^{n - 1} x^{n - 1} + C_n^n x^n$$

然后如果你做了（高中数学老师名字隐去）的作业，你会遇到让你求 $C_n^0 - C_n^1 + C_n^2 - C_n^3 + \cdots + (-1)^n C_n^n$ 的题目。作为一名文化课选手，你熟练地将 $x = -1$ 代了进去，并且发现等式左边是 $0$，于是你又做出了一道题，拿到了 5 分。

你没有局限于文化课固定的垃圾套路，发现了其中的奥秘。你发现，这种操作把一个数列（$C_n^i$）映射到了一个函数（$(x + 1)^n$）上。你开始思考，是不是其他的数列也可以这么操作呢？

恭喜你，你发现了生成函数。通过生成函数，我们可以把数列的运算转化为对函数的运算，借用多项式的运算，大量的毒瘤数数题就此诞生了。

普通生成函数（OGF）

数列 $A_0, A_1, \cdots$ 的普通生成函数为 $\displaystyle \sum_{n = 0}^\infty{A_n x^n}$。

普通生成函数通常考虑无标号问题（组合问题），它的加法操作和乘法操作分别对应了并和拼接两种操作。

• 并：无标号 $n$ 个点的图的个数，假如 $\displaystyle \sum_{n = 0}^\infty{a_n x^n}$ 是连通图的 OGF，$\displaystyle \sum_{n = 0}^\infty{b_n x^n}$ 是不连通图的 OGF，$\displaystyle \sum_{n = 0}^\infty{a_n x^n} + \sum_{n = 0}^\infty{b_n x^n}$ 就是所有图的 OGF。
• 拼接：有两类物品，拿 $n$ 个物品 A 的方案数为 $a_n$，OGF 为 $\displaystyle \sum_{n = 0}^\infty{a_n x^n}$；拿 $n$ 个物品 B 的方案数为 $b_n$，OGF 为 $\displaystyle \sum_{n = 0}^\infty{b_n x^n}$。那么拿 $n$ 个物品的 OGF 为 $\displaystyle \sum_{n = 0}^\infty{a_n x^n} \ast \sum_{n = 0}^\infty{b_n x^n}$。

常用的 OGF

↓这个表格某些单元格的对齐方式渲染有问题，有神仙知道原因或解决方案请务必告诉我，谢谢（

数列	形式幂级数	闭形式
$1, 1, 1, \cdots$	$\displaystyle \sum_{n = 0}^\infty{x^n}$	$\displaystyle \frac 1{1 - x}$
$\displaystyle \binom NN, \binom{N + 1}N, \binom{N + 2}N, \cdots$	$\displaystyle \sum_{n = 0}^\infty{\binom{N + n}N x^n}$	$\displaystyle \frac 1{(1 - x)^{N + 1}}$
$1, 1, 1, \cdots, 1$	$\displaystyle \sum_{n = 0}^N{x^n}$	$\displaystyle \frac{1 - x^{N + 1}}{1 - x}$
$1, 0, 0, 1, 0, 0, 1, \cdots \ (a = 3)$	$\displaystyle \sum_{n = 0}^\infty{x^{a n}}$	$\displaystyle \frac 1{1 - x^a}$

此外还有一些很 trivial 的东西，比如 OGF 乘以 $x$ 相当于数列右移一位。

把一个数列的 OGF 乘以 $\displaystyle \frac 1{1 - x}$ 相当于对其求前缀和，乘以 $1 - x$ 相当于对其求差分。详见P5488 差分与前缀和。

斐波那契数

令 $f_n$ 为斐波那契数列，$f_1 = f_2 = 1$，如何求出 $\displaystyle \sum_{n = 0}^\infty{f_n x^n}$ 的闭形式？

令 $\displaystyle F_n = \sum_{n = 0}^\infty{f_n x^n}$，由 $f_n = f_{n - 1} + f_{n - 2}$ 可以得到 $F(x) = x F(x) + x^2 F(x) + x$。解方程得 $\displaystyle F(x) = \frac x{1 - x - x^2}$。

$1 - x - x^2$ 怎么因式分解呢？

待定系数法，设 $(1 + ax)(1 + bx) = (1 - x - x^2)$，解得 $a, b$ 分别是 $\displaystyle \frac{-1 \pm \sqrt 5}2$。此时有

$$F(x) = \frac x{ \left(1 - \frac{1 + \sqrt 5}2 x \right) \left(1 - \frac{1 - \sqrt 5}2 x \right)}$$

考虑裂项和待定系数法，设 $\displaystyle \frac A{1 + ax} + \frac B{1 + bx} = F(x)$。取 $\displaystyle a = \frac{-1 + \sqrt 5}2$，解得 $\displaystyle A = \frac 1{ \sqrt 5}, B = - \frac 1{ \sqrt 5}$。

这样，我们就得到了

$$F(x) = \frac 1{ \sqrt 5} \left( \frac 1{1 - \frac{1 + \sqrt 5}2 x} - \frac 1{1 - \frac{1 - \sqrt 5}2 x} \right)$$

因为 $\displaystyle \sum_{n = 0}^\infty{a x^n} = \frac 1{1 - ax}$，代入得

$$f_n = [x^n] F(x) = \frac 1{ \sqrt 5} \left( \left( \frac{1 + \sqrt 5}2 \right)^n - \left( \frac{1 - \sqrt 5}2 \right)^n \right)$$

卡特兰数

如何求节点数为 $n$ 的二叉树的个数？

直接大力推式是可以的，但是太麻烦了完全看不懂。

注意到生成函数本身是具有组合性质的。令 $F(x)$ 表示该问题的生成函数，考虑一棵二叉树可以划分成根节点和左右两个子树，得到 $F(x) = x F^2(x) + 1$。解方程得 $\displaystyle F(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$。

$\displaystyle F(x) = \sum_{n = 0}^\infty{ \frac{(2n)!}{n! (n + 1)!} x^n}$，证明从略。

指数型生成函数（EGF）

数列 $A_0, A_1, \cdots$ 的指数型生成函数为 $\displaystyle \sum_{n = 0}^\infty{A_n \frac{x^n}{n!}}$。

在处理有标号问题（排列问题）的时候，我们通常使用指数型生成函数。在这样的定义下，加法和乘法依然保持了性质。

常用的 EGF

数列	形式幂级数	闭形式
$1, 1, 1, \cdots$	$\displaystyle \sum_{n = 0}^\infty{ \frac{x^n}{n!}}$	$e^x$
$1, 0, 1, \cdots$	$\displaystyle \sum_{n = 0}^\infty{ \frac{x^{2n}}{(2n)!}}$	$\displaystyle \frac{e^x + e^{-x}}{2}$
$0, 1, 0, \cdots$	$\displaystyle \sum_{n = 0}^\infty{ \frac{x^{2n + 1}}{(2n + 1)!}}$	$\displaystyle \frac{e^x - e^{-x}}{2}$

群论相关

这里推荐一篇博客，讲的是比我下面抄的课件要清楚的。

群的定义

定义集合 $G$ 和作用于 $G$ 中的元素的二元运算 $\oplus$，若其满足以下性质，则称其为一个群，记作 $(G, \oplus)$。

1. 封闭性
   对于任意 $a \in G, b \in G$，都有 $a \oplus b \in G$。
2. 结合律
   对于任意 $a, b, c$，有 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$。
3. 单位元
   存在唯一的 $e \in G$，满足对于任意 $a \in G$ 有 $a \oplus e = e \oplus a = a$。
4. 逆元
   对于任意 $a \in G$，存在唯一的 $a’ \in G$ 满足 $a \oplus a’ = a’ \oplus a = e$。

置换群

置换就是对元素进行重排列。

置换群指的是一个置换的集合，满足任意两个置换不能复合出一个新的不在集合内的置换。

Burnside 引理

令 $X$ 表示某个集合，令 $G$ 表示作用在 $X$ 上的某个置换群。对于任意 $G$ 内的元素 $g$，定义 $f(g)$ 为 $X$ 内经过置换 $g$ 后不变的元素的数量。我们要求的是 $X$ 内本质不同的元素的个数，本质不同指不能通过 $G$ 获得彼此，记为 $|X / G|$。

$$|X / G| = \frac 1{|G|} \sum_{g \in G}{f(g)}$$

Polya 定理

令 $G$ 是 $X$ 的一个置换群，$|X| = n$，用 $m$ 种颜色染色，本质不同的染色方案是

$$|X / G| = \frac 1{|G|} \sum_{g \in G}{m^{c(g)}}$$

其中 $c(g)$ 表示 $g$ 的循环节数。

通常我们并不需要枚举所有的 $g$ 计算 $c(g)$，而是枚举 $c(g)$ 快速计算多少 $g$ 满足条件。

线性代数相关

行列式

一个方阵 $A$ 的行列式表示为 $|A|$ 或 $\det(A)$。

$$\det(A) = \sum_{p}{(-1)^{ \sigma(p)}}{ \prod_{i = 1}^n{a_{i, p_i}}}$$

其中 $p$ 表示一个排列，$\sigma(p)$ 表示 $p$ 的逆序对数。使用高斯消元快速计算行列式的值。

行列式的性质：

• 对角矩阵 / 上三角矩阵 / 下三角矩阵的行列式是主对角线上元素的乘积。
• 交换矩阵的两行，行列式的值取相反数。
• 将矩阵的一行的所有元素乘上一个相同的常数 $k$，行列式的值也乘上 $k$。
• 将矩阵的一行加到另外一行上去，行列式的值不变。
• 由于转置的存在，行列式所有对行成立的性质对列也成立。

Matrix-Tree 定理

对于无向图 $G$，定义 $G$ 的度数矩阵 $D$：

$$D_{i, j} = \begin{cases} \deg_i &, i = j \\ 0 &, i \ne j \end{cases}$$

定义 $G$ 的基尔霍夫矩阵 $L = D - C$，其中 $C$ 代表 $G$ 的邻接矩阵，则图 $G$ 的生成树数量是 $L$ 的任意一个代数余子式。

简单拓展

带权图的生成树：

定义一棵树的权值是树上所有边的总权值。

我们将度数矩阵中的度数改为与它相连的所有边的边权和，邻接矩阵的连通性改为边权，就可以求出所有生成树的权值和。

有向图的生成树形图计数：

我们将度数矩阵中的度数改为入度，邻接矩阵改为有向图的邻接矩阵，那么以 $x$ 为根的树形图个数即为 $L_{x, x}$。

Best theorem

一个有向图 $G$ 的欧拉回路的数量是

$$t_1(G) \prod_{i = 1}^n{(\deg(i) - 1)!}$$

其中 $t_1(G)$ 表示图 $G$ 的以 $1$ 为根的树形图的数量。

几道例题

连通图计数 - [集训队作业2013]城市规划

这篇题解是刚学多项式求逆的时候写的，学完 OGF 和 EGF 之后重看题解学会了很多东西，并且有了个新方法（待补）

洛谷模板题

problem

一个 $n$ 个点 $n$ 条边的环，给点任意染色，求有多少种本质不同的染色方案，对 $10^9 + 7$ 取模。

两种染色方案本质不同，当且仅当其任意旋转后不能重合。

solution

有 $n$ 种置换，分别为顺时针旋转 $0 \sim n - 1$ 格。其中对于顺时针旋转 $i$ 格的置换，每个循环节的长度为 $\displaystyle \frac n{ \gcd(i, n)}$，循环节个数为 $\gcd(i, n)$。

设答案为 $L$，朴素 Polya 定理的式子是 $\displaystyle L = \frac 1n \sum_{i = 1}^n{n^{ \gcd(i, n)}}$，这个显然是要超时的。

枚举 $\gcd$ 稍微推一下式子得到 $\displaystyle L = \sum_{d | n}{n^{d - 1} \varphi \left(\frac nd\right)}$。

设 $n$ 的唯一分解 $\displaystyle n = \prod_{i = 1}^m{p_i^{c_i}}$，对所有 $1 \le i \le m$ 预处理 $\varphi(p_i), \varphi(p_i^2), \cdots, \varphi(p_i^{c_i})$。通过枚举 $p_i$ 的指数枚举 $d$ 即可在 $O(1)$ 求 $\displaystyle \varphi\left(\frac nd\right)$。

code