卡特兰数（Catalan）

Catalan数列（$C_n$）是一个非常常见的数列，OEIS编号为A000108，常被用于解决以下问题：

在圆上取$2n$个点，将这些点分成$n$对，将对应的点连起来得到的$n$条线段不相交的方案数。
从凸多边形的对角线中选取若干不相交的对角线，将其分成三角形的方案数。
$1, 2, \dots, n$进入一个无上限的栈，出栈序列的方案数。
$n$个点的二叉树的方案数。

这些问题都可以等价归结为括号序列问题：长度为$2n$的括号序列的方案数。

根据括号序列的定义，可以得出卡特兰数的递推式如下：

$$ C_0 = C_1 = 1 \\ C_n = \sum_{i=1}^n C_{i-1}C_{n-i} $$

考虑括号序列的特殊性质，取数列$\{ a_i \}$，满足：

$$ a_i = \begin{cases} 1 & s_i = "(" \\ -1 & s_i = ")" \end{cases} $$

对$a_i$取前缀和$S_i$，则$\forall 1 \leq i \leq 2n, S_i \geq 0, S_{2n} = 0$，如果将括号序列看作在平面直角坐标系上游走，左括号向右走，右括号向上走，则长度为$2n$的括号序列将从$(0,0)$走到$(n, n)$，且根据括号序列的性质，路径将不会超过直线$y=x$，即不会碰到直线$y=x+1$，只需要在统计这样的路径方案数即得到括号序列的方案数。

在直角坐标系上从$(0,0)$走到$(n,n)$的路径总方案数为$\binom{2n}{n}$，其中不合法的即碰到直线$y=x+1$的路径，这些路径可以将与直线$y=x+1$第一次触碰之前的路径关于直线对称后与从$(-1, 1)$到$(n,n)$的路径一一对应，方案数为$\binom{2n}{n+1}$，故：

$$ \begin{aligned} C_n &= \binom{2n}{n} - \binom{2n}{n+1} \\ &= \binom{2n}{n} - \frac{n}{n+1} \binom{2n}{n} \\ &= \frac{1}{n+1} \binom{2n}{n} \\ C_n &= \frac{4n-2}{n+1} C_{n-1} \end{aligned} $$

斯特林数（Stirling）

第一类斯特林数

第一类斯特林数$s(n, k)$，又称为有符号斯特林数，OEIS编号为A008275，可以定义为对应递降阶乘展开式的各项系数，即：