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\)，因为有：
大括号表示子集符号，这一符号雷同也颇具含义。
显然有初始状态 \(\begin{Bmatrix}n\\n\end{Bmatrix} = 1, \begin{Bmatrix}k\\0\end{Bmatrix} = 0(k>0)\)。
考虑递推。
考虑最后一个数字加入什么集合。
可以新开一个集合，也可以选择之前的集合加入。
那么
时间复杂度 \(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\)，因为有：
我们先来探讨特殊情况。
两个数的集合可以组成几个轮换？一个，因为 \([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] = [E,A,B,C,D]\)，因此末尾不能够插入数。这样，一共有 \(n-1\) 个位置可以插入数。
因此有
时间复杂度 \(O(nk)\)。
原文地址：http://www.cnblogs.com/Zeardoe/p/16859913.html
