斯特林数

在数学中，斯特林数（Stirling）用于解决各种数学分析和组合数学问题，斯特林数是两组不同的数，均是 18 世纪由詹姆斯·斯特林引入并以其命名，以第一类斯特林数和第二类斯特林数的称呼区分。此外，有时候也将拉赫数称为第三类斯特林数。^[1]

1. 第一类斯特林数

定义第一类斯特林数是将 $n$ 个不同元素分成 $k$ 个不同的环的方案数，记作 $s(n,\,k)$ 或 $\begin{bmatrix}n \\ k\end{bmatrix}$ 。其中两个环不相同当且仅当这两个环不能通过旋转得到。表示方法为

\begin{bmatrix} n \\ k \end{bmatrix}

考虑递推，把 $n$ 个不同元素分成 $k$ 个不同的环有两种转移。

第一种，有可能是 $n−1$ 个不同元素分成 $k−1$ 个不同的环，当前的第 $n$ 个独立成一个元素。

第二种可能是 $n−1$ 个不同元素已经分好了 $k$ 个不同的环，当前这个可以加进去。加在每个已有元素的逆时针方向（或顺时针方向，方向没有关系，只要统一即可）就不会出现重复，共有 $n−1$ 种方法，所以：

\begin{bmatrix} 0 \\ 0 \end{bmatrix} = 1

\begin{bmatrix} n \\ k \end{bmatrix} = \begin{bmatrix} n - 1 \\ k - 1 \end{bmatrix} + \begin{bmatrix} n - 1 \\ k \end{bmatrix} \cdot (n-1)

这就是第一类斯特林数的递推式，也可以写成：

s(n,\,k)=s(n−1,\,k−1)+s(n−1,\,k) \cdot (n−1)

性质：