斯特林数

标签：begin end Bmatrix 斯特林 轮换 bmatrix

source：《具体数学》第六章
记号：
\(\begin{Bmatrix}n\\k\end{Bmatrix}\)：第二类斯特林数，读作“\(n\) 子集 \(k\)”。
\(\begin{bmatrix}n\\k\end{bmatrix}\)：第一类斯特林数，读作“\(n\) 轮换 \(k\)”。

基本思想：
一一对应；递推。

---

第二类斯特林数

\(n\) 个元素划分成 \(k\) 个无标号的集合，有几种方案？
如 \(\begin{Bmatrix}4\\2\end{Bmatrix} = 7\)，因为有：

\[\{1\},\{2,3,4\} \\ \{2\},\{1,3,4\} \\ \{3\},\{1,2,4\} \\ \{1,2\},\{3,4\} \\ \{1,3\},\{2,4\} \\ \{2,3\},\{1,4\} \\ \{1,2,3\},\{4\} \\ \]

大括号表示子集符号，这一符号雷同也颇具含义。

显然有初始状态 \(\begin{Bmatrix}n\\n\end{Bmatrix} = 1, \begin{Bmatrix}k\\0\end{Bmatrix} = 0(k>0)\)。

考虑递推。
考虑最后一个数字加入什么集合。
可以新开一个集合，也可以选择之前的集合加入。
那么

\[\begin{Bmatrix}n\\k\end{Bmatrix} = \begin{Bmatrix}n-1\\k-1\end{Bmatrix} + k\begin{Bmatrix}n-1\\k\end{Bmatrix}\]

时间复杂度 \(O(nk)\)。

有标号？乘以 \(k!\) 即可。

https://codeforces.com/gym/100342/problem/D

第一类斯特林数

\(n\) 个元素划分成 \(k\) 个无标号的轮换，有几种方案？

注意轮换指的是若干个数字组成的一个环。比如 \([1,2,3,4] = [3,4,1,2]\)，但是 \([1,2,3,4] \neq [4,3,2,1]\)。

如 \(\begin{bmatrix}4\\2\end{bmatrix} = 11\)，因为有：

\[[1,2,3],[4] \\ [1,3,2],[4] \\ （剩下六组轮换） \\ [1,2],[3,4] \\ [1,3],[2,4] \\ [2,3],[1,4] \\ \]

我们先来探讨特殊情况。

两个数的集合可以组成几个轮换？一个，因为 \([A,B]=[B,A]\)。三个数的集合可以组成两个轮换：\([A,B,C],[A,C,B]\)。

\(n\) 个数的集合 \(\{1,...,n\}\) 可以组成几个轮换？考虑钦定 \(1\) 放在最前面，那么剩下 \(n-1\) 个数的排列与 \(n\) 个数的轮换一一对应，也就是 \(\begin{bmatrix}n\\1\end{bmatrix} = (n-1)!\)。

注意到 \(\begin{bmatrix}n\\k\end{bmatrix} \geq \begin{Bmatrix}n\\k\end{Bmatrix}\) 恒成立。因为一个子集可以有若干个轮换。

考虑递推。最后一个数怎么插？可以单独成为一个轮换。不单独成为轮换的情况有几种呢？考虑钦定所有轮换的第一个数，那么每一个数之前都可以插入最后一个数形成一个新的轮换：

\[[A,B,C,D] + E \\ \rightarrow \\ [E,A,B,C,D] \\ [A,E,B,C,D] \\ [A,B,E,C,D] \\ [A,B,C,E,D] \\ \]

注意，\([A,B,C,D,E] = [E,A,B,C,D]\)，因此末尾不能够插入数。这样，一共有 \(n-1\) 个位置可以插入数。

因此有

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

时间复杂度 \(O(nk)\)。

标签：begin,end,Bmatrix,斯特林,轮换,bmatrix
From： https://www.cnblogs.com/Zeardoe/p/16859913.html