斯特林数及其相关知识和应用

在组合数学，Stirling数可指两类数，第一类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。 Stirling数有两种，第一类Stirling数和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根（Copenhagen）大学的尼尔森（Niels Nielsen，1865-1931）提出了"Stirlingschen Zahlen erster Art" (第一类Stirling数)和"Stirlingschen Zahlen zweiter Art" (第二类Stirling数)，首次把这两类数冠以「Stirling数」之名 。因为苏格兰数学家斯特林（J. Stirling, 1692-1770）首次发现这些数并说明了它们的重要性。 ——来自于百度百科

此外，由于拉赫数与斯特林数关系密切，有时候也将拉赫数（Lah number）称为第三类斯特林数。

注：第二类斯特林数却在斯特林的相关著作和具体数学中被首先描述，同时也比第一类斯特林数常用得多。

在介绍斯特林数之前，我先介绍一下自然幂，上升幂和下降幂，因为斯特林数的性质和这三种幂紧密相关。

其实自然幂和上升幂，自然幂和下降幂之间是可以相互转换的，在之后的前两类斯特林数的性质中会讲述。

第一类斯特林数（斯特林轮换数）\(\begin{bmatrix} n\\ m\end{bmatrix}\)，表示将 \(n\) 个两两不同的元素，划分成 \(m\) 个互不区分的非空置换的方案数。

注：一个轮换是一个收尾相接的环形排列。两个可以通过旋转而互相得到的轮换是等价的（我们不认为两个可以通过翻转而相互得到的轮换等价）。

边界为：\(\begin{bmatrix} n\\0\end{bmatrix}=[n=0]\) 。

运用组合意义证明：

新加入的元素独立作为一个置换，方案数为 \(\begin{bmatrix} n-1\\ m-1\end{bmatrix}\) 。

新加入的元素加入现有的置换当中，因为对任意长度为 \(l\) 的置换插入该置换的方案数为 \(l\) ，当前置换总长为 \(n-1\) ，所以方案数为 \((n-1)\begin{bmatrix} n-1\\ m\end{bmatrix}\) 。

根据加法原理，将两式相加即可得到递推式。

理解：对于一个排列 \(P\) 我们可以将所有的 \((p_i, i)\) 连边，一个环则为一组轮换，每种排列一一每种置换。

证明：数学归纳法，请读者自行证明。

证明：

即 \(m^{\overline{k+1}}=\sum_{i=0}^{k+1}\begin{bmatrix} k+1\\ i \end{bmatrix}m^i\)

改命题由此得证。

证明：

第一类斯特林数目前没有实用的通项公式。

由于 \(O(n\log^2n)\) 的分治FFT的做法已经烂大街。

所以我们讲讲时间复杂度为 \(O(n\log n)\) 的做法（虽然还是逃不过多项式）。

考虑构造生成函数 \(F(x)^n=\prod\limits_{i=0}^{n-1}(x+i)=\prod\limits_{i=0}^{n}a_ix^i\) ，可以根据 \(m^{\overline{n}}=\sum\limits_{i=0}^n\begin{bmatrix} n\\ i \end{bmatrix}m^i\) 得到其中的 \(a_i=\begin{bmatrix}n\\ i\end{bmatrix}\) 。

显然 \(F(x)^{2n}=F(x)^nF(x+n)^n\) 。

我们可以通过左半部分系数得到右半部分系数由此得到全部的系数。

时间复杂度: \(T(n)=T(\frac n 2)+O(n\log n)=O(n\log n)\) 。