包括组合数、卡特兰数、第一二类斯特林数等。
组合数
\[ \begin{align} \binom{n}{m}&=\frac{n!}{(n-m)!m!}\\ \binom{n}{m}&=\binom{n-1}{m}+\binom{n-1}{m-1} \end{align} \]
插板法
将 \(n\) 个相同物品分为 \(k\) 组（非空）的方案数。
对于 \(n\) 个点，相邻两个有一个槽，插入 \(k-1\) 个板，也就分成了 \(k\) 组。
所以答案为 \(\displaystyle \binom{n-1}{k-1}\)。
多重集的组合数
从 \(n\) 个数中选出 \(k\) 个数组成多重集的方案数。
等价于解 \(x_1+x_2+x_3+\cdots +x_n=k\) 的非负整数解个数。
答案： \[ \binom{n+k-1}{k-1} \] 插板法：在原来的 \(n-1\) 个槽基础上再加 \(k\) 个槽，被选则表示该组为空。
卡特兰数
| \(H_0\) | \(H_1\) | \(H_2\) | \(H_3\) | \(H_4\) | \(H_5\) | \(H_6\) | ... |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 14 | 42 | 132 | ... |
常用公式：
\[ \begin{align} H_n&=\frac{1}{n+1}\dbinom{2n}{n} \\ H_n&=\dbinom{2n}{n}-\dbinom{2n}{n-1} \\ H_n&=\begin{cases} \sum_{i=1}^{n}H_{i-1}H_{n-i} &n\ge2,n\in\mathbb{N_{+}}\\ 1 &n=0,1 \end{cases} \\ H_n&=\frac{4n-2}{n+1}H_{n-1}\\ \end{align} \]
应用
\(H_n\)：
表示由 \(n\) 个节点组成不同构二叉树的方案数。
表示有 \(2n+1\) 个节点组成不同构满二叉树的方案数。
表示通过连接顶点将 \((n+2)\) 边的凸多边形分成三角形的方法个数。
表示在 \(n\times n\) 的网格图中不越过对角线的路径条数。
表示长度为 \(2n\) 的 \(\texttt{dyck word}\) 个数(有 \(n\) 个"X"与 \(n\) 个"Y"组成的字符串，满足前缀“X”的个数大于等于前缀“Y”的个数)。
第一类斯特林数
表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个非空圆排列的方案数。 \[ \begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix} \] 边界 \(\displaystyle \begin{bmatrix}n\\0\end{bmatrix}=[n=0]\)。
第二类斯特林数
表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个非空子集的方案数。 \[ \begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix} \] 边界 \(\displaystyle \begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]\)。