大概是总结一下这几天正睿的组合数学

组合数学好玩（

就算写不出来题也好玩（

都2020年了不会还有组合数学博客从加法原理开始讲吧，不会吧不会吧

有一说一我完全不理解这种东西为什么所有博客 / 教程甚至ZR的课都要放在最前面讲一遍……

推荐阅读：【学习笔记】组合数学 第5章

插板法

经典小学奥数内容

把 $n$ 个相同的球放进 $m$ 个不同的盒子里，每个盒子里至少要有一个球，求方案数。

考虑在 $n-1$ 个空隙中插入 $m-1$ 块板子将 $n$ 个球分成 $m$ 分，显然方案数为 $\dbinom{n-1}{m-1}$。

我们现在考虑每个盒子里不一定要都有球的情况。

我们先给每个盒子钦定一个球，于是我们把球的总数加上 $m$，易得方案数为 $\dbinom{n+m-1}{m-1}$

Catalan 数

いっそ僕の全部、カトレア

我们定义 Catalan 数

$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

一个 Catalan 数的经典组合意义是一个长度为 $n$ 的序列的合法出栈序列个数。

我们定义出栈序列是一个 $01$ 序列，其中 $0$ 表示入栈，$1$ 表示出栈，$0$ 和 $1$ 各有 $n$ 个。

显而易见的，一个合法的出栈序列的每一个前缀中 $0$ 的个数总是不小于 $1$ 的个数——也就是说，对于每一个 $1 \le i \le n$，有 $\sum\limits_{j=1}^i [a_j=0] \ge \sum\limits_{j=1}^i [a_j=1]$（其实也可以把这个当作它的定义）

我们可以证明，每一个不合法的出栈序列与每一个由 $n+1$ 个 $0$，$n-1$ 个 $1$ 组成的长度为 $2n$ 的 $01$ 序列一一对应——通过把不合法出栈序列的第一个不合法的前缀进行 $01$ 反转得到。

举个例子： $001110$ 是一个不合法的出栈序列，$00111$$0$ 是它的第一个不合法的前缀（即 $1$ 的个数大于 $0$ 的个数），于是我们对其 $01$ 翻转，即将原序列变为 $11000$$0$。

关于证明……别问，问就是不会证

于是这个问题的答案就是 $\dbinom{2n}{n}-\dbinom{2n}{n-1}=\dfrac{1}{n+1} \dbinom{2n}{n}$

错排

定义 $D_n$ 为长度为 $n$ 的 $1\sim n$ 的排列 $p$ 的排列个数，使得对于所有 $1 \le i \le n$ 有 $p_i \ne i$。

$D_n = (n-1)(D_{n-1}+D_{n-2})$

这个蛮好理解的（

容斥原理

课件

题中给出 $n$ 个需要满足的条件

使用容斥，枚举不被满足的条件集合 $S$ 和对应的方案数，其系数为 $(-1)^{|S|}$。

设 $A$ 为条件集合，容斥原理大概是这个样子的

$\sum\limits_{S \in A} (-1)^{|S|} \cdot f(~\text{S中条件不被满足}~)$

是非常有用的东西，但是单就知识点的话没啥好讲的（

第二类斯特林数

我们定义第二类斯特林 (Stirling) 数为把 $n$ 个不同的球放进 $r$ 个相同的盒子里的方案数，记作 $S(n,r)$ 或 $\begin{Bmatrix} n \\ r \end{Bmatrix}$

有一个显然的递推式

$\begin{Bmatrix}n \\ r\end{Bmatrix} =r\begin{Bmatrix}n-1\\r\end{Bmatrix}+\begin{Bmatrix} n-1 \\ r-1 \end{Bmatrix},n>r\ge 1$

可以结合组合数的递推式理解。

同样有通项：

$\begin{Bmatrix}n \\ k\end{Bmatrix} = \frac{1}{k!} \sum\limits_{i=0}^k (-1)^i \binom k i (k-i)^n$

如果把 $\dfrac{1}{k!}$ 这一项去掉，意义即变为把 $n$ 个不同的球放进 $r$ 个不同的盒子里的方案数，剩下的部分是个容斥。

（感觉自己写的好随便 = =

以及两个比较重要的式子（渲染出现了一些问题，下降幂的下划线没有显示

$x^n = \sum\limits_{k=0}^n \begin{Bmatrix}n\\k\end{Bmatrix} x^{\underline k}$

其中 $x^{\underline k}$ 表示 $x$ 的 $k$ 次下降幂，$x^{\underline k} = \dfrac{x!}{(x-k)!}$

$\binom n i i^{\underline j}= \binom{n-j}{i-j} n^{\underline j}$

直接展开（（

总之就是看到不太好算的幂次就直接代换斯特林数，调换求和顺序之类的，和莫反一个套路（（

图的计数

以下 $n$ 均表示节点个数，$m$ 均表示边数。

01 带编号无向图

$2^{\binom n 2}$

是个人都会

02 带编号无向连通图

我们设 $g(n)$ 表示 $n$ 个点的无向图个数，由上可知 $g(n)=2^{\binom n 2}$，设 $f(n)$ 表示 $n$ 个点的无向连通图个数。

我们枚举在一个普通无向图中节点 $1$ 所在的连通块的大小，得到

$g(n) = \sum\limits_{i=1}^n \binom{n-1}{i-1} \cdot f(i) \cdot g(n-i)$

也就是说，我们在尝试使用 $f$ 来表示 $g$。

大概解释一下这个式子：$i$ 是枚举的 $1$ 所在的连通块大小。首先选择构成这个连通块的是哪些点，即 $\dbinom{n-1}{i-1}$。选择这个连通块的构成方式，即 $f(i)$。选择连通块之外的点的构成方式，即 $g(n-1)$。

于是我们可以根据这个式子算出 $f(n)$，即

$f(n) = g(n) - \sum\limits_{i=1}^{n-1} \binom{n-1}{i-1} \cdot f(i) \cdot g(n-i)$

03 带编号偶度点图

$2^{\binom{n-1}{2}}$

构造方法是对于前 $n-1$ 个点任意连边，第 $n$ 个点向所有奇度点连边（可以证明奇度点一定有偶数个）。

04 带编号偶度连通图

计算方法其实和带编号无向连通图没差，不写了（

无根树 / Prufer 序列

<课件>

01 无根树转 Prufer 序列

每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n-2$ 次后就只剩下两个结点，算法结束。

• Prufer 序列的长度为 $n-2$
• 每个点在 Prufer 序列中出现的次数为其度数-1

02 Prufer 序列转无根树

每次选择一个度数为 $1$ 的最小的编号节点，与当前枚举到的 Prufer 序列的点之间连上一条边，然后同时将两个点的度数-1。最后在剩下的两个度为 $1$ 的点间连一条边。
注意到，点数为 $n$ 的无根树与长度为 $n-2$ 的 Prufer 序列一一对应

</课件>

于是树的计数的一般思路就是对 Prufer 序列计数

03 完全图的生成树数量

注意到要求的实际上就是长度为 $n-2$，值域为 $1\sim n$ 的 Prufer 序列的数量，于是方案数即为 $n^{n-2}$

04 给定 $n$ 个节点的度数，求无根树的个数

已知度数，也就是说每个元素在 Prufer 序列中出现的次数是确定的，即 $i$ 在数列中出现了 $d_i -1$ 次，于是问题转化成为可重集的排列个数。答案即为

$\frac{(n-2)!}{\prod\limits_{i=1}^n (d_i - 1)!}$

05 计算完全二分图 $K(n,m)$ 的生成树个数

注意到生成树的 Prufer 序列中一定有 $n-1$ 个左侧的点，$m-1$ 个右侧的点，于是答案即为 $n^{m-1} \cdot m^{n-1}$