第一类斯特林数：
形如$left[egin{matrix}n\mend{matrix} ight]$，也写作 $s(n,k)$
组合意义：
$s(n,k)$ 表示吧$n$个数分成$k$组，每组是一个环，求分成的方案数。
也就是一个轮子，怎么转都是一样的，如：1,2,3,4 和 4,1,2,3 只算一种方案。
递推式：
$$s(n+1,2)=s(n,1)+s(n,2)cdot n$$
即要么自成一个环，要么加入其它$k$个环，可以插入$n-1$个位置。（每两个数之间）
当然边界条件$left[egin{matrix}0\0end{matrix} ight]=1$
性质：
1. $s(n,1)=(n-1)!$
2. $s(n,2)=(n-1)! imessum_{i=1}^{n-1}frac{1}{i}$
3. $sum_{i=0}^n s(n,k)=n!$
证明：
1. 显然，我们把$n$个元素排列起来，有$n!$种可能，首尾相接即可得到一个环。这里面每种情况重复了$n$次，因为可以旋转$n$次，所以除以$n$，得到$s(n,1)=(n-1)!$。
2. 通过数学归纳法可以证明。
egin{align*}s(n+1,2)&=s(n,1)+s(n,2)cdot n \&=(n-1)!+n(n-1)!sum _{i=1}^{n-1}frac{1}{i} \&=(n-1)!+n!sum _{i=1}^{n-1}frac{1}{i} \&=frac{n!}{n}+n!sum _{i=1}^{n-1}frac{1}{i} \&=n!sum _{i=1}^{n}frac{1}{i} \end{align*}
3. 这里有一个巧妙地“算两次”方法。
首先构造一个问题，求$n$个数的所有排列。
首先用乘法原理直接得出结论，$ans=n!$。
我们知道，对于一个排列对应一个置换，即：
egin{pmatrix}
1 & 2 & ... & n \ a_1 & a_2 & ... & a_n
end{pmatrix}
把这个置换中的上下对应位置连边，可以得到许多的环。由于排列和置换是一一对应的，所以我们要求排列的个数，就是求用$n$个元素组成环的方案数，所以我们枚举环的个数:
$$n!=sum_{k=1}^ns(n,k)$$
由于我们有$s(n,0)=0$，所以也可以写成：
$$sum_{k=0}^ns(n,k)=n!$$
第二类斯特林数：
形如$left{egin{matrix}n\kend{matrix} ight}$，也写作 $S(n,k)$
组合意义：
$S(n,k)$ 表示吧$n$个数分成$k$组，组内无序，每组没有区别。
递推式：
egin{align*}egin{Bmatrix}n\kend{Bmatrix}=egin{Bmatrix}n-1\k-1end{Bmatrix}+egin{Bmatrix}n-1\kend{Bmatrix}*k\end{align*}
即要么自成一个组，要么加入其它$k$个组，可以插入$k$个组。
当然边界条件$left{egin{matrix}0\0end{matrix} ight}=1$
性质：
没有什么特别常用的。
通项公式：
$$S(n,m)=frac{1}{m!} sum _{k=0}^m (-1)^kC_m^k(m-k)^n$$
大概就是容斥原理，$k$枚举有多少个集合是空的，每种情况有$C^k_m$种空集情况，$n$个元素可以放进非空的$m-k$个集合中。这样求出来的答案是有序的，所以我们除以$m!$使得其变为无序。
卷积形式：
它具有卷积的形式$egin{align*}left{egin{matrix}n\mend{matrix} ight}=sumlimits_{k=0}^mdfrac{(-1)^k}{k!}dfrac{(m-k)^n}{(m-k)!}end{align*}$
可以用FFT在$O(mlog_2m)$的时间内算出$left{egin{matrix}n\1end{matrix} ight}cdotsleft{egin{matrix}n\mend{matrix} ight}$
转化幂：
第二类斯特林数可以用于转化幂：$egin{align*}x^n=sumlimits_{k=1}^nleft{egin{matrix}n\kend{matrix} ight}x^underline kend{align*}$，可以用归纳法证明
egin{align*}x^n&=xsumlimits_{k=1}^{n-1}left{egin{matrix}n-1\kend{matrix} ight}x^underline k\&=sumlimits_{k=1}^{n-1}left{egin{matrix}n-1\kend{matrix} ight}(x^underline{k+1}+kx^underline k)\&=sumlimits_{k=1}^nleft{egin{matrix}n-1\k-1end{matrix} ight}x^underline k+sumlimits_{k=1}^nleft{egin{matrix}n-1\kend{matrix} ight}kx^underline k\&=sumlimits_{k=1}^nleft{egin{matrix}n\kend{matrix} ight}x^underline kend{align*}