组合与计数

错排问题

递推：

$D(n)=(n-1)[D(n-2)+D(n-1)]$

容斥：

$$D(n)=n![\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{(-1)^n}{n!}]$$

容斥的式子可以由二项式反演简单的推出来：不考虑 $i \neq a_i$ 这个条件，那么方案数即为 $n!$。这些排列中包含了所有恰由 $k(k=0,1,2,\cdots,n)$ 个位置不变的排列，因此有

$$n!=\sum_{i=0}^n\binom{n}{i}f_i$$

使用二项式反演即可得到

$$f_n=n!\sum_{i=0}^n \frac{(-1)^i}{i!}$$

第一类 Stirling 数

第一类 Stirling 数表示 n 个不同元素构成 m 个圆排列的数目。有无符号 Stirling 数也表示升阶函数和降阶函数的系数：

$$x^{n\downarrow}=x(x-1)(x-2)\cdots(x-n+1)=\sum_{k=0}^n s_s(n,k)x^k$$ $$x^{n\uparrow}=x(x+1)(x+2)\cdots(x+n-1)=\sum_{k=0}^n s_u(n,k)x^k$$

有无符号 Stirling 数之间的关系为 $s_s(n,m)=(-1)^{n-m}s_u(n,m)$

递推形式：$s(n,r)=(n-1)s(n-1,r)+s(n-1,r-1)$

有符号的第一类 Stirling 数可以简单推导如下：

$$\sum_{k=0}^{n+1}s(n+1,k)\cdot x^k=x^{n\downarrow} (x-n)=\sum_{k=0}^ns(n,k)\cdot x^{k+1}-n\sum_{k=0}^ns(n,k)\cdot x^k$$

即

$$s_s(n,m)=s_s(n-1,m-1)-(n-1)\cdot s_s(n-1,m)$$

性质：

• $s(n,0)=[n=0]$
• $s(n,1)=(n-1)!$
• $s(n,2)=(n-1)!\sum_{i=1}^{n-1}\frac{1}{i}$
• $s(n,n-1)=\binom{n}{2}$
• $\sum_{k=0}^ns_u(n,k)=n!$
• $\sum_{k=0}^ns_s(n,k)=[n=0]$

第二类 Stirling 数

第二类 Stirling 数可以表示把 $n$ 个球放进 $r$ 个相同的盒子里的方案数（没有空盒）。

递推形式： $S(n,r)=rS(n-1,r)+S(n-1,r-1)$

第二类 Stirling 数也可用下降阶乘幂定义：

$$\begin{aligned} x^n&=\sum_{k=0}^nS(n,k)(x)_k\\ &=\sum_{k=0}^nS(n,k)x(x-1)\cdots (x-k+1) \end{aligned}$$

通项公式为

$$S(n,m)=\frac{1}{m!}\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n$$

可以用容斥理解。$k$ 为有多少集合是空的，每个 $k$ 有 $\binom{m}{k}$ 种空集，$n$ 个元素可以放进非空的 $m-k$ 个集合中。最后再除以 $m!$ 使其变为无序的情况。

性质：

• $S(n,1)=S(n,n)=1$
• $S(n,0)=[n=0]$
• $S(n,2)=2^{n-1}-1$
• $S(n,3)=\frac{1}{6}(3^n-3\cdot 2^n+3)$
• $S(n,n-1)=\binom{n}{2}$

Catalan 数

Catalan数从 $0$ 开始的前几项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845

Catalan 数常见公式

$$H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}$$ $$H_n = \frac{ (4n-2)}{n+1} H_{n-1}$$ $$H_n = \binom{2n}{n} - \binom{2n}{n-1} =\frac{1}{n+1}\binom{2n}{n}$$

Catalan 数应用

路径计数问题：只能往右或往上走一个单位长度，问有多少种不同的路径可以从左下角 $(1,1)$ 走到右上角 $(n,n)$，并且要求路径不能经过直线 $y=x$ 上方的点。

对于一种不合法的方案，它的路径一定与 $y=x+1$ 有交。将第一个交点后面的路径关于 $y=x+1$ 做个对称，新的路径就会到达 $(n-1,n+1)$。合法的方案总数就是

$$C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}$$

括号序列计数：有多少种不同的长度为 $n$ 的括号序列。长度为 $2n$ 的括号序列的方案数就是 $C_n$

出栈顺序：有多少种可能的操作序列。

二叉树计数：有多少种不同的 $n$ 个结点的二叉树

$$f_n=\sum_{i=1}^n f_{i-1}f_{n-i}$$

对这棵树进行遍历，遍历顺序即是一个括号序列。

在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数。

对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数。