本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-04 20:42:27

斯特林数

第一类斯特林数

$ \begin{bmatrix}n\\m\end{bmatrix} $（或 $s(n,m)$ ）

表示将 $n$ 个不同元素构成 $m$ 个圆排列的数目。

性质

$ \begin{bmatrix}n\\end{bmatrix} $ = 0;

将 0 个数放到 0 个圆排列中，方案数为 1 

$\begin{bmatrix}n\n\end{bmatrix}$= 1

将$n$个数放到 $?$ 个圆排列中，每一个数占用一个圆，方案数为1

$\begin{bmatrix}n\
\end{bmatrix}$= $(n-1)!$

将 $?$ 个数放到 1 个圆排列中，就是 1 \~ $?$ 的圆排列的方案数，$(?−1)!$。

$\begin{bmatrix} n\n-2 \end{bmatrix} = C^2_n$

将n个数放到 $?−1$ 个圆排列中的方案数。即有一个圆排列是两个数，其余均为 1 个数的方案数，也就是从 $?$ 个数里选择两个数，剩余的 $?−2$ 个数自动每一个数归为一个圆排列，所以总方案数为 $C_?^2$。

我们考虑如何求解第一类斯特林数，一般首先考虑递推。

考虑这样一个问题：将 1 \~ $?$ 的一个排列，划分为 $k$ 个圆排列，一共有多少种方案。

我们使用DP的分析方法，分析第 $?$ 个数 $?$，有哪些放置方法。

发现一共有两种放置方法：$?$ 放到一个新的圆中，或者 ? 放到已有的圆中。

• $?$ 放到一个新的圆中

此时就意味着前 $?−1$ 个数放到 $?−1$ 个圆中，$?$ 放到自己的圆中，也就是第 $?$ 个圆，此时的方案数等于 $\begin{bmatrix} ?−1\?−1 \end{bmatrix}$。

• $?$ 放到已有的圆中

即前 $?−1$ 个数放到 $?$ 个圆里，第 $?$ 个数放到前面 $?$ 个圆里，那么对于每一个圆中，一共有 $?−1$ 个数所以对于 ? 来说，一共有 ?−1 中放置方案。故此时的方案数等于 $(?−1) × $ $\begin{bmatrix} ?−1\? \end{bmatrix}$。

根据加法原理，我们可以得到递推式：

 $\begin{bmatrix} ?\? \end{bmatrix}$ $=$ $\begin{bmatrix} ?−1\?−1 \end{bmatrix}$ $+$ $(?−1)$ $×$ $\begin{bmatrix} ?−1\? \end{bmatrix}$

第二类斯特林数

第二类斯特林数实际上是集合的一个拆分，表示将 ? 个不同的元素拆分成 $?$ 个集合间有序（可以理解为集合上有编号且集合不能为空）的方案数，记为  $\begin{Bmatrix}n\\m \end{Bmatrix}$ (或$?(?,?)$ ）。

性质

$\begin{Bmatrix}n\ \end{Bmatrix}=0$

$\begin{Bmatrix}n\
\end{Bmatrix}=1$

$\begin{Bmatrix}n\ \end{Bmatrix}=2^{n-1}-1$

$\begin{Bmatrix}n\{n-1} \end{Bmatrix}=C^2_n$

$\begin{Bmatrix}n\n \end{Bmatrix}=1$

第二类Stirling数要求盒子是无区别的，所以可以得到其方案数公式：

假设要把 ? 个元素分成 ? 个集合，我们来分析第 $?$ 个数 $?$，有哪些放置方法。

发现还是一共有两种放置方法：$?$ 放到一个新的集合中，或者 $?$ 放到已有的集合中。

• $?$ 放到一个新的集合中

此时就意味着前 ?−1 个数放到 ?−1 个集合中，? 放到自己的集合中，也就是第 ? 个集合，此时的方案数等于 $\begin{Bmatrix}n-1\\k-1 \end{Bmatrix}=1$。

• $?$ 放到已有的集合中

即前 ?−1 个数放到 ? 个集合里，第 ? 个数放到前面 ? 个集合里，那么对于每一个集合中，由于内部是无序的，而集合间是有序的，所以相当于将 ? 放到 ? 个箱子里，有 ? 种选择。故此时的方案数等于 $?×\begin{Bmatrix}n-1\\k \end{Bmatrix}=1$。

故可以得到第二类斯特林数的递推公式：

$\begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1 \end{Bmatrix}+ ? ×\begin{Bmatrix}n-1\\k \end{Bmatrix}=1$`

证毕

——S08577