组合数

错排列

前 $7$ 项：

$D_0$	$D_1$	$D_2$	$D_3$	$D_4$	$D_5$	$D_6$	$D_7$
$0$	$0$	$1$	$2$	$9$	$44$	$265$	$1854$	$\cdots$

公式： $D_n=(n-1)(D_{n-1}+D_{n-2})=nD_{n-1}+(-1)^n$

公式： $(n-1)!$

前 $6$ 项：

$H_0$	$H_1$	$H_2$	$H_3$	$H_4$	$H_5$	$H_6$	$H_7$
$1$	$1$	$2$	$5$	$14$	$42$	$132$	$429$	$\cdots$

公式：

应用：

$n$ 对括号有多少种匹配方式。
记 $f_{2i}$ 表示前 $2i$ 个位置的方案数。枚举与位置 $2i$ 上放置的右括号匹配的左括号的位置，有 $f_{2i}=f_0\times f_{2i-2}+f_2\times f_{2i-4}+\cdots+f_{2i-2}\times f_0$ 。可知 $f_{2i}=H_i$ 。
一个无穷大的栈，进栈序列为 $1,2,\cdots,n$ ，有多少个不同的出栈序列。
将进栈看作左括号，将出栈看作右括号，同 1。
在圆上选择 $2n$ 个点，将这些点成对相连使得所得到的 $n$ 条线段不相交的方法数。
同 1。
$2n$ 个人排队买票问题，票价 $50$ 元， $n$ 个人拿 $50$ 元， $n$ 个人拿 $100$ 元，售票处无零钱，能顺利卖票的排队方式数。
将 $50$ 元看作进栈， $100$ 元看作出栈，同 1。
对角线不相交的情况下，将一个 $n+2$ 个顶点的凸多边形区域分成三角形区域的方法数。
以凸多边形的一边为基，设这条边的顶点为 $A$ 和 $B$ 。从剩余顶点中选一点 $C$ ，可以将凸多边形分成三个部分。中间是一个三角形 $ABC$ ，左右两边分别是两个凸多边形，然后求解左右两个凸多边形。
由 $n$ 个结点构成的不同的二叉树的个数。
根占用一个结点，那么剩余的 $n-1$ 个结点分配给左 / 右儿子。

例子：

只往上 / 右走，从 $(0,0)$ 走到 $(n,m)$ （ $n\ge m$ ）且不越过 $y=x$ 的方案数。
不合法方案等价于到沿 $y=x+1$ 翻折后的 $(n,m)$ 的方案数。

$\begin{bmatrix}n\\m\end{bmatrix}$ （ $s(n,m)$ ）表示把 $n$ 个数的序列划分为 $m$ 个圆排列的方案数。

公式： $\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\cdot\begin{bmatrix}n-1\\m\end{bmatrix}$

性质： $n!=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}$

第 $i$ 次选择时，有 $1$ 种选择创建新的圆排列，有 $i-1$ 种选择加入旧的原排列，写出生成函数为 $\prod_{i=1}^n(x+i-1)=\prod_{i=0}^{n-1}(x+i)=x^{\overline{n}}$ 。

分治 NTT 时间复杂度 $O(n\log^2n)$ 。存在 $O(n\log n)$ 的算法，待填。

$\begin{Bmatrix}n\\m\end{Bmatrix}$ （ $S(n,m)$ ）表示把 $n$ 个不同的小球放在 $m$ 个相同的盒子里方案数。

公式：

$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\cdot\begin{Bmatrix}n-1\\m\end{Bmatrix}$
$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m\frac{(-1)^{m-i}\cdot i^n}{i!\cdot(m-i)!}$