7.4 号爸 斯特林数笔记

· · 算法·理论

斯特林数

第一类斯特林数

表示将 $n$ 个不同元素构成 $m$ 个圆排列的数目。 ### 性质 $ \begin{bmatrix}n\\0\end{bmatrix} $ = 0; 将 0 个数放到 0 个圆排列中，方案数为 1  ---- $\begin{bmatrix}n\\n\end{bmatrix}$= 1 将$n$个数放到 $?$ 个圆排列中，每一个数占用一个圆，方案数为1 ---- $\begin{bmatrix}n\\1\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\\0 \end{Bmatrix}=0 \begin{Bmatrix}n\\1 \end{Bmatrix}=1 \begin{Bmatrix}n\\2 \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。

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

证毕 ——S08577