斯特林数有两类，分为第一类斯特林数和第二类斯特林数。

其中第一类斯特林数又有无符号版本和有符号的版本。这里主要介绍无符号版本。

第一类斯特林数

定义

将$1-n$划分为$k$个圆排列的方案数，这$k$个圆排列相互之间没有顺序。记作$s(n,k)$或$\left[\begin{array}{c}n\\ k\end{array}\right]$。

求法

$\left[\begin{array}{c}n\\ k\end{array}\right]=\left[\begin{array}{c}n-1\\ k-1\end{array}\right]+(n-1)\left[\begin{array}{c}n-1\\ k\end{array}\right]$

推导的思路：
假设我们现在正在放第$n$个数，我们目前有两种选择：

1. 将$n$放到新的圆当中
2. 将$n$放到已有的圆中

对于第一种选择，对于$n$来说，放到新圆当中，只有一种放法。因此我们主要考虑前$n-1$个数的放法即可。我们发现前$n-1$个数的放法其实就是一个斯特林数$\left[\begin{array}{c}n-1\\ k-1\end{array}\right]$，也就是将$n-1$个数划分为$k-1$个圆排列的方案数。

对于第二种选择，对于$n$来说，放到之前的圆排列中的方案数，我们可以根据下面的例子得出：

对于这个含有4个数的圆排列，现在我想往里面插入一个数，总共有几种方案？
可以发现，我们可以把新的数插入到$1$的后面，或者到$2$的后面，或者$3$的后面，或者$4$的后面，也就是图中的$a,b,c,d$四个位置。总共有4种方案。

因此我们现在想将$n$插入到之前已存在的圆排列当中，就相当于选择插入到哪个前$n-1$个数的后面。因此，有$n-1$种方案。

考虑了$n$的插入放法，基于之前$n-1$个数已经分成了$k$个圆排列。因此最终第二种选择的方案数就是：$(n-1)\ast \left[\begin{array}{c}n-1\\ k\end{array}\right]$。

两种选择的方案数相加即可推出上式。

性质

1. $\left[\begin{array}{c}0\\ 0\end{array}\right]=1$
2. $\left[\begin{array}{c}n\\ n\end{array}\right]=1$
3. $\left[\begin{array}{c}n\\ 0\end{array}\right]=0$
4. $\left[\begin{array}{c}n\\ 1\end{array}\right]=(n-1)!$
   推导：
   这就相当于$n$个数的圆排列。$n$个数组成一个圆的方案数总共有$n!$种，不过，对于每种方案，都有$n$个圆排列通过旋转可以与其相同，因此，不同的圆排列方案数有$\frac{n!}{n}=(n-1)!$
5. $\left[\begin{array}{c}n\\ n-1\end{array}\right]=C_n^2$
6. $\left[\begin{array}{c}n\\ 2\end{array}\right]=\frac{1}{2}{\sum }_{i=1}^{n-1}{C}_n^i(i-1)!(n-i-1)!=(n-1)!{\sum }_{i=1}^{n-1}\frac{1}{i}$
   推导过程如下：
   $\frac{1}{2}{\sum }_{i=1}^{n-1}{C}_n^i(i-1)!(n-i-1)!=\frac{1}{2}{\sum }_{i=1}^{n-1}\frac{n!}{i(n-i)}=\frac{1}{2}{\sum }_{i=1}^{n-1}(n-1)!\frac{n}{i(n-i)}=\frac{1}{2}{\sum }_{i=1}^{n-1}(n-1)!(\frac{1}{i}+\frac{1}{n-i})=\frac{1}{2}\ast 2{\sum }_{i=1}^{n-1}(n-1)!\frac{1}{i}=(n-1)!{\sum }_{i=1}^{n-1}\frac{1}{i}$
   倒数第二步的推导，是由于$\frac{1}{i}$和$\frac{1}{n-i}$在取值范围内的值域相同，因此可以直接2倍。
7. $\left[\begin{array}{c}n\\ n-2\end{array}\right]=2C_n^3+3C_n^4$
8. ${\sum }_{k=0}^{n}s(n,k)=n!$
   可以通过升阶函数证明。

第二类斯特林数

定义

将$1-n$划分成$k$个子集的方案数，记作$S(n,k)$或$\left\{\begin{array}{c}n\\ k\end{array}\right\}$。

求法

$S(n,k)=S(n-1,k-1)+kS(n-1,k)$

递推方式与第一类相同。

性质

1. $S(n,0)=0^n$
2. $S(n,1)=1$
3. $S(n,n)=1$
4. $S(n,2)=2^{n-1}-1$
   假设两个集合有序，那么$n$个数插入两个集合的总方案数是$2^n$，由于两个集合都不能为空，因此方案数是$2^n-2$。最后因为两个集合不考虑相互位置，因此，总方案数是$(2^n-2)/2=2^{n-1}-1$。
5. $S(n,n-1)=C_n^2$
6. $S(n,n-2)=C_n^3+3C_n^4$
7. $S(n,n-3)=C(n,4)+10C(n,5)+15C(n,6)$
8. ${\sum }_{k=0}^{n}S(n,k)=B_n,B_n是贝尔数$

通项公式

$S(n,m)=\frac{1}{m!}{\sum }_{k=0}^m(-1{)}^{k}C(m,k)(m-k{)}^n$

两类斯特林数的关系

${\sum }_{k=0}^n\left[\begin{array}{c}n\\ k\end{array}\right]\left\{\begin{array}{c}k\\ m\end{array}\right\}={\sum }_{k=0}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}\left[\begin{array}{c}k\\ m\end{array}\right]$

斯特林数：stirling

概念：

1、第一类斯特林数：把1~n排列成k个非空循环的方案数，用小写s(n,k)或[n k]表示

2、第二类斯特林数：将1~n排成k个非空集合的方案数，用大写S(n,k)或{n,k}表示

第一类斯特林数：

递推：

边界s(0,0)=1,s(n,k)=0 (n<k)

组合意义：考虑加入n时，可以自己构成环，后者插入一个之前已有的数的后面，复杂度O(nk)

- 与上升幂、下降幂的关系:

上升幂定义：

$$
\ x^ \bar n=x \times (x+1) \times.....\times(x+n-1)
$$

是一个多项式，有

$$
x^ \bar n=\sum_{k=1}^{n}s(n,k)\times x^k
$$

组合意义：考虑把1~n排成k个非空循环序列，然后将每个环染成[1,x]中的某种颜色，等式右边就是枚举环的数量，然后每个环任意染色，等式左边相当与考虑每次加入一个新点n，若构成一个新环，则有x种染色方法，否则插入1个之前已有的数的后面继承其颜色，那么n个点的总方案数就是上升幂

下降幂定义：

$$
x^\bar n=x(x-1)....(x-n+1)
$$

是一个多项式，有：

$$
\ x^\bar n=\sum_{k=1}^{n} \left(-1\right)^ \left(n-k\right)\times s(n,k)\times x^k
$$

• 性质：

  $$
  s(n,1)=(n-1)!
  $$

   

  $$
  s(n,2)=(n-1)!\times\sum_{i=1}^{n-1}\frac{1}{i}
  $$

   

  $$
  n!=\sum_{k=0}^{n}s(n,k)
  $$

   

  最后一条的组合意义：任意1个排列可以看成一个置换，那么枚举置换中环的数量然后求和就是全排列

第二类斯特林数：S(n,k)

递推：

$$
S(n,k)=S(n-1,k-1)+k\times S(n-1,k)
$$

边界S(0,0)=1,S(n,k) = 0(n<k)

组合意义：考虑加入n时，可以自己构成一个集合，或者插入一个1之前已有的集合，复杂度O(nk)。第二类斯特林数也可以用小球模型来描述，其对应：n个不同的球，放进k个相同的盒子，不能有空盒子的方案数

• 与下降幂之间的关系：

  $$
  x^n=\sum_{k=0}^{n}\times x^\underline k
  $$

   

  组合意义：给1~n每个数染[1,x]中的某种颜色，方案数为左边x^n右边枚举一共有k种不同的颜色，把1~n分成k个集合（S(n,k)）然后每个集合一次染色

• 通项公式（容斥）：

  $$
  S(n.k)=\frac{1}{k!}\sum_{i=0}^{k}\times s(n,i)\times\left(n-k\right)^n
  $$

   

  组合意义：考虑“n个不同的球，放进k个不同的盒子，可以有空盒子的方案数”，其显然等于k^n。若不能有空盒子，则枚举空盒子的数量i然后容斥，即“n个不同的球，放进k个不同盒子，有至少i个空盒子”的方案数=s(n,i)*(k-i)^n,容斥系数为(-1)^i，最后再除以k！时把盒子不同转化为盒子相同，利用这个容斥可以实现O(nlogn)计算一个S(n,k)

  • 与自然数幂和的关系

    定义：

    $$
    F(n)=\sum_{i=1}^{n}i^k
    $$

     

    暴力计算时间复杂度O(nlogk)

  • 使用第二类stiring数转化为下降幂：

    $$
    F(n)=\sum_{i=1}^{n}\sum_{j=0}^{k}S\{k,j\}=\sum_{i=1}^{n}\sum_{j=0}^{k}S\{k,j\}j!s(i,j)
    $$

     

    $$
    F(n)=\sum_{j=0}^{k}j!\sum_{i=j}^{n}s(i,j)
    $$

     

    这个式子和n相关的杨辉三角上一列求和，等于右下角

    $$
    F(n)=\sum_{j=0}^{k}S\{k,j\}j!s(n+1,j+1)
    $$

     

    这个式子仅枚举k如果O(k^2)预处理S(k,j)那么可以在O(klogk)时间求解上F(n)

联合省选的D1T2放出了一道裸的斯特林数，幸亏之前推过第二类斯特林数求自然数幂和，所以很幸运地切了。
这次比赛之后dyp和gmh77疯狂学斯特林数，从此免疫。
惊得我也系统地学一下斯特林数做做样子。

概念

第一类斯特林数：记为$s(m,n)$（也可以用中括号表示），组合意义为$m$个数形成$n$个圆排列的方案数。
有个比较系统的定义：$s(m,n)=[x^n]{\prod }_{i=0}^{m-1}(x+i)$
性质：
$s(m,n)=(m-1)\ast s(m-1,n)+s(m-1,n-1)$
组合意义可证。
${\sum }_{k=0}^{n}s(n,k)=n!$
每一种排列，对应着一种轮换。意思记排列为$p$，$i$向$p_i$连边，这样就会形成若干个环。

第二类斯特林数：记为$S(m,n)$（也可以用大括号表示），组合意义为$m$个数形成$n$个集合的方案数。
性质：
$S(m,n)=n\ast S(m-1,n)+S(m-1,n-1)$
组合意义可证。
$S(m,n)=\frac{1}{n!}{\sum }_{k=0}^n(-1{)}^{k}C(n,k)(n-k{)}^m$
反演得到（下面有提及）。
${\sum }_{k=0}^{n}S(n,k)=B_n$
$B$表示贝尔数。

有符号斯特林数：顾名思义就是有符号的斯特林数。
$s_s(m,n)=-(m-1)\ast s_s(m-1,n)+s_s(m-1,n-1)$
$S_s(m,n)=-n\ast S_s(m-1,n)+S_s(m-1,n-1)$

下标$s$意思为“signed”

打个表出来可以发现
$s_s(m,n)=(-1{)}^{m-n}s(m,n)$
$S_s(m,n)=(-1{)}^{m-n}S(m,n)$

性质

$s(m,n)\ge S(m,n)$
排列数大于等于集合数。

普通幂、上升幂、下降幂相关：（这个在推式子的时候经常能够用到！）
$x^n={\sum }_{k=0}^{n}S(n,k)x^{\underline{k}}$
$x^n={\sum }_{k=0}^{n}S(n,k)(-1{)}^{n-k}{x}^{\overline{k}}={\sum }_{k=0}^n{S}_s(n,k)x^{\overline{k}}$
$x^{\overline{n}}={\sum }_{k=0}^{n}s(n,k)x^k$
$x^{\underline{n}}={\sum }_{k=0}^{n}s(n,k)(-1{)}^{n-k}{x}^k={\sum }_{k=0}^n{s}_s(n,k)x^k$
具体证明嘛，各种归纳，各种组合意义。

快速求斯特林数

第一类斯特林数：
把定义式搬下来：$s(m,n)=[x^n]{\prod }_{i=0}^{m-1}(x+i)$
记$s_m(x)={\prod }_{i=0}^{m-1}(x+i)$
考虑倍增求这个东西。从$s_m(x)$推到$s_{2m}(x)$时：
$s_{2m}(x)=s_m(x)s_m(x+m)$
快速求出$s_m(x+m)$。设$s_m(x)={\sum }_{i=0}^m{s}_{m,i}{x}^i$。之前已经求出$s_{m,i}$。
$s_m(x+m)={\sum }_{i=0}^m{s}_{m,i}(x+m{)}^i$
二项式展开一下，推一波式子，就可以发现一个卷积。
于是计算$s_m(x+m)$的时间复杂度是$O(m\lg m)$的。
由于$m$是两倍两倍地扩大，所以总的时间复杂度也是$O(m\lg m)$。

第二类斯特林数：
把上面那个普通幂转下降幂的式子搬下来，简单反演一下，得到：
$n!S(m,n)={\sum }_{k=0}^n(-1{)}^{k}C(n,k)(n-k{)}^m$
把后面的那个组合数拆开，可以发现这是个很明显的卷积形式。
时间复杂度$O(n\lg n)$

斯特林反演

$f(n)={\sum }_{k=0}^{n}S(n,k)g(k)⟺g(n)={\sum }_{k=0}^n(-1{)}^{n-k}s(n,k)f(k)$
有个叫反转公式的东西：
${\sum }_{k}s(n,k)S(k,m)(-1{)}^{n-k}=[m=n]$
${\sum }_{k}S(n,k)s(k,m)(-1{)}^{n-k}=[m=n]$
关于这个怎么证明……最严谨的方法应该是归纳。

写公式太麻烦，直接口胡一下证明的思路（挺好推的）。
比如上面这条式子：${\sum }_{k}s(n,k)S(k,m)(-1{)}^{n-k}=[m=n]$
先将$s(n,k)$用递推式拆开，展开一下。
再将$S(k,m)$用递推式拆开，展开一下。
照着这么做就可以很自然地归纳证明出来了。
另一条式子也可以类似地推出来。
看了一些博客，有些博客里面写了一种不是很严谨的证明方法：
具体就是取一个普通幂$n^m$，将它先用第二类斯特林数表示成下降幂多项式，然后将这个下降幂用第一类斯特林数表示成普通幂。
推推式子就会得到这样：$n^m={\sum }_{j=0}^m{n}^j{\sum }_{k=j}^{m}S(m,k)s(k,j)(-1{)}^{j-k}$
然后谁告诉我，这怎么就能直接得到${\sum }_{k=j}^{m}S(m,k)s(k,j)(-1{)}^{j-k}=[j=m]$了？？？
这种方法只能解释假设反转公式成立，这个东西也成立；但不能反过来推啊……

如果设矩阵$F_{i,j}=S(i,j)$，$G_{i,j}=(-1{)}^{i-j}s(i,j)$
（或者$F_{i,j}=s(i,j)$，$G_{i,j}=(-1{)}^{i-j}S(i,j)$）
不难发现$F\ast G=E$，即$F$和$G$互逆。

拉赫数（第三类斯特林数？）

似乎只有维基上略有提及，所以不够详细请见谅。
有错误请指出。

无符号拉赫数：
上升幂和下降幂定义：
$x^{\overline{n}}={\sum }_{k=0}^{n}L(n,k)x^{\underline{n}}$
$x^{\underline{n}}={\sum }_{k=0}^n(-1{)}^{n-k}L(n,k)x^{\overline{n}}$
递推式定义：$L(m,n)=L(m-1,n-1)+(n-1+m)L(m,n-1)$
矩阵乘法定义：$L(m,n)={\sum }_{k}s(m,k)S(k,n)$

有符号拉赫数：
上升幂和下降幂定义：
$x^{\overline{n}}=(-1{)}^n{\sum }_{k=0}^n{L}_s(n,k)x^{\underline{n}}$
$x^{\underline{n}}=(-1{)}^k{\sum }_{k=0}^n{L}_s(n,k)x^{\overline{n}}$
$L_s(m,n)=(-1{)}^{m}L(m,n)$

性质：
$L(m,n)=C(m-1,n-1)\frac{m!}{n!}$
归纳可证：
${\sum }_k{L}_s(m,k)L_s(k,n)={\sum }_k(-1{)}^{m-k}L(m,k)L(k,n)=[m=n]$
$L(n,k)=n![x^n]\frac{1}{k!}(\frac{x}{1-x}{)}^k$

参考资料

https://www.cnblogs.com/Wuweizheng/p/8638858.html
https://www.cnblogs.com/hchhch233/p/10016543.html
https://www.cnblogs.com/owenyu/p/6724661.html
https://www.cnblogs.com/gzy-cjoier/p/8426987.html
百度百科
维基百科