首先我们先来了解什么叫做斯特林数。
第一类斯特林数
$\left[n\atop m \right]$ 或者 $s(n,m)$ 表示从 $n$ 个元素中选出 $m$ 个圆排列的方案数。
什么是圆排列，对于两个排列，如果循环相同，那么这两个排列就被视为相同的圆排列，不难发现，$n$ 个元素的圆排列个数为 $(n-1)!$。
递推式
考虑递推斯特林数。我们考虑第 $n$ 个元素放在哪个圆排列中，首先是考虑新放一个圆排列，这样的方案数为 $s(n-1,m-1)$，考虑把第 $n$ 个元素放进之前的某个圆排列中，不难发现，把一个元素放入一个 $4$ 个元素的圆排列中有 $4$ 种放法，所以我们把第 $n$ 个元素放在之前的某个圆排列中一共有 $n-1$ 中放法，由此可以得到这样一个式子：
$$
\begin{bmatrix}n\m\end{bmatrix}=\begin{bmatrix}n-1\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\m\end{bmatrix}
$$
这就是第一类斯特林数的递推式。
递推边界：$s(n,n)=1(n\ge 0),s(n,0)=0(n\ge 1)$
性质
- $s(n,1)=(n-1)!$
由 $n$ 个元素的圆排列个数为 $(n-1)!$ 可以得到。
- $s(n,n-1)=\binom{n}{2}$
让 $n$ 个元素组成 $n-1$ 个圆排列，实际上是从这 $n$ 个元素里面选出来两个组成一个大小为 $2$ 的圆排列，其余元素单独组成员排列。由此可知，性质成立。
- $s(n,2)=(n-1)!\sum_{i=1}^{n-1}\frac{1}{i}$
首先我们考虑设第一个圆排列的元素个数为 $i$ ，第二个圆排列的元素个数为 $n-i$，那么根据 $s(n,1)=(n-1)!$ 我们可以得到 $\binom{n}{i}(i-1)!(n-i-1)!$，同时我们需要注意到，因为在第一类斯特林数的定义中圆排列相互之间是没有顺序的，但是我们在计数的过程中却区分了第一个圆排列，第二个圆排列，所以我们算重了 $2$ 遍，由此我们可以得到：
$$
\begin{aligned}
s(n,2)&=\sum\limits_{i=1}^{n-1}\frac{\binom{n}{i}(i-1)!(n-i-1)!}{2}\
&=\sum\limits_{i=1}^{n-1}\frac 12 \frac{n!}{i!(n-i)!}\times (i-1)!\times (n-i-1)!\
&=\sum\limits_{i=1}^{n-1}\frac 12 \frac{n!}{i(n-i)}=(n-1)!\sum\limits_{i=1}^{n-1}\frac{1}{2}(\frac{1}{i}+ \frac{1}{n-i})
\end{aligned}
$$
容易发现 $\frac{1}{i}$ 与 $\frac{1}{n-i}$ 的贡献相同，所以原式得证。
- $s(n,n-2)=2\times \binom{n}{3}+3\times \binom{n}{4}$
我们分两种情况讨论：第一种情况，我们把 $n-3$ 个元素分给 $n-3$ 个圆排列，其余 $3$ 个元素自成一个排列，这样的方案数为 $2\times \binom{n}{3}$，前者是 $3$ 元素圆排列个数，后者是从 $n$ 个元素中选出三个当圆排列。
第二种情况，我们把 $n-4$ 个元素分给 $n-4$ 个圆排列，然后剩下两个圆排列每个圆排列两个元素，首先 $\binom{n}{4}$ 选出 $4$ 个元素，然后再 $\binom{4}{2}$ 选出两个元素给第一个圆排列，考虑到我们又给排列定了顺序，所以乘上 $\frac 12$ 。由此可以得到原式。
- $\sum_{k=0}^ns(n,k)n^k=n!$
通过下文中的第一类斯特林数的生成函数可以得到这个性质。
符号
第一类斯特林数分为有符号斯特林数和无符号斯特林数，有符号斯特林数通常表示为 $s_s$，无符号斯特林数通常表示为 $s_u$，我们有 $s_s(n,k)=(-1)^{n-k}s_u(n,k)$，在本文中，若无特殊说明，第一类斯特林数通常都指的是无符号斯特林数。
第二类斯特林数
$\left{n\atop m\right}$ 或 $S(n,m)$ 表示把 $n$ 个元素划分成 $m$ 个非空集合的方案数，其中 $m$ 个集合两两相同。
通项公式
我们考虑容斥来计算第二类斯特林数的通项公式，首先不管两个限制：非空和集合两两相同。
我们钦定有 $i$ 个集合是空的，然后把所有的球随意的放进剩下的盒子，这里盒子两两不同，这样的方案数应该为 $\binom{n}{i}(m-i)^n$，然后我们容斥一下，就可以得到非空的方案数，再乘上 $\frac{1}{m!}$ 就可以得到盒子两两相同的方案数。由此，我们可以得到：
$$
\begin{Bmatrix}n\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n
$$
递推式
我们一样考虑第 $n$ 个元素怎么放。
第一种情况，把第 $n$ 个元素放在最后一个盒子里，其余的元素放在其他的盒子里，这样的方案数为 $S(n-1,m-1)$。第二种情况，把第 $n$ 个元素和其他元素放在一起，注意这里元素两两不同而盒子两两相同，所以说我们关注的是元素的组合情况，对于每一种方案，我们把第 $n$ 个元素加入一个新的组合都会产生一种情况，所以方案数为 $mS(n-1,m)$，由此，我们可以得到 $S(n,m)=S(n-1,m-1)+mS(n-1,m)$。
边界条件：$S(n,n)=1(n\ge 0),S(n,0)=0(n>1)$。
性质
- $S(n,1)=1$
根据第二类斯特林数的定义不难的出这个结论。
$S(n,2)=2^{n-1}-1$
两个集合我们考虑第一个集合放哪些数，这样的计数结果为 $\sum_{i=1}^{n-1}\binom ni$，考虑到我们给集合定顺序但集合间并没有顺序，所以我们算重了两边，最终结果为：
$$
\frac 12\sum\limits_{i=1}^{n-1}\binom ni=\frac 12(2^n-2)=2^{n-1}-1
$$
- $S(n,n-1)=\binom n2$
不难想到这个东西实际上是从 $n$ 个元素中选出 $2$ 个放到一个集合里去，由此可以得到上面这个式子。
- $\left{ n\atop m \right}\equiv 0\bmod n$ 当 $n$ 是质数且 $1<m<n$ 时成立。
证明：
当 $n$ 是质数且 $1<m<n$ 时，我们可以得到：
$$
\begin{aligned}
\left{ n\atop m \right}&= \frac{1}{m!}\sum\limits_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n\
&=\sum\limits_{i=0}^m(-1)^i \frac{(m-i)^n}{i!(m-i)!}\
&\equiv \sum\limits_{i=0}^m(-1)^i\frac{m-i}{i!(m-i)!}
\end{aligned}
$$
我们对上面这个东西建立生成函数：
$$
F(x)=\sum\limits_{m\ge0}(\sum\limits_{i=0}^m(-1)^i\frac{m-i}{i!(m-i)!})x^m
$$
发现这个东西是由两个生成函数卷积得到：
$$
F(x)=(\sum\limits_{i\ge0}\frac{(-1)^i}{i!}x^i) \times (\sum\limits_{i\ge0}\frac{i}{i!}x^i)
$$
发现这个是因为关注到 $F(x)$ 的系数本身就是一个卷积形式。
发现前面这个东西的封闭形式是 $e^{-x}$，证明可以通过写出 $e^ {-x}$ 在原点处的泰勒展开得到。
而后面那个式子，不难发现 $i=0$ 时式子值为 $0$，所以能够得到：
$$
\begin{aligned}
\sum\limits_{i\ge0}\frac{i}{i!}x^i&=\sum\limits_{i\ge 1}\frac{i}{i!}x^i\
&=\sum\limits_{i\ge 1} \frac{1}{(i-1)!}x^i=\sum\limits_{i\ge 0} \frac{x^{i+1}}{i!}\
&=x\sum\limits_{i\ge0}\frac{x^i}{i!}=xe^x
\end{aligned}
$$
由此我们可以得到 $F(x)$ 的封闭形式 $F(x)=x$。
注意到 $F(x)$ 的第 $m$ 次项为 $0$ ，而第 $m$ 项的系数为 $\left{ n\atop m \right}$，由此可知原式成立。
- $n^k=\sum_{i=0}^kS(k,i)i!\binom ni$
第三类斯特林数
第三类斯特林数也称作拉赫数，因为和第一二类斯特林数比较类似，所以有这两个名字。
拉赫数可以通过上升幂与下降幂之间的转化来定义，即：
$$
\begin{aligned}
x^{\overline{n}}&=\sum\limits_{k=0}^nL(n,k)x^{\underline{k}}\
x^{\underline{n}}&=\sum\limits_{k=0}^n(-1)^{n-k}L(n,k)x^{\overline{k}}
\end{aligned}
$$
由此我们可以得到 $L(n,k)$ 的通项公式：
$$
L(n,k)=\binom{n-1}{k-1}\frac{n!}{k!}
$$
有这个通项公式可以知道第三类斯特林数的递推公式：
$$
L(n,k)=(n+k-1)L(n-1,k)+L(n-1,k-1)
$$
这个定西可以简单的通过代入来证明。
各种幂之间的转换
这里先给出上升幂与下降幂的公式：
$$
\begin{aligned}
x^{\overline{n}}=x(x+1)…(x+n-1)\
x^{\underline{n}}=x(x-1)…(x-n+1)
\end{aligned}
$$
上升幂与下降幂之间的转换关系：
$$
(-x)^{\underline{n}}=(-1)^nx^{\overline{n}}\
(-x)^{\overline{n}}=(-1)^nx^{\underline{n}}
$$
二项式系数与下降幂之间的关系：
$$
\binom nk=\frac{n^{\underline{k}}}{k!}
$$
证明比较显然，这里不再赘述。
- 上升幂与通常幂之间的转换：
$$
\begin{aligned}
x^{\overline{n}}&=\sum\limits_{i=0}^ns(n,i)x^i\
x^n&=\sum\limits_{i=0}^n(-1)^{n-i}S(n,i)x^{\overline{i}}\
\end{aligned}
$$
证明：
- 通常幂与下降幂之间的转换：
$$
\begin{aligned}
x^{\underline n}&=\sum\limits_{i=0}^n(-1)^{n-i}s(n,i)x^i\
x^n&=\sum\limits_{i=0}^nS(n,i)x^{\underline{i}}\
\end{aligned}
$$
- 上升幂与下降幂之间的转换：
$$
\begin{aligned}
x^{\overline{n}}&=\sum\limits_{k=0}^nL(n,k)x^{\underline{k}}\
x^{\underline{n}}&=\sum\limits_{k=0}^n(-1)^{n-k}L(n,k)x^{\overline{k}}
\end{aligned}
$$
以上性质可以通过归纳以及上升幂与下降幂之间的转换来证明，这里不再赘述。
记忆上面的实际只需要注意什么时候添加 $-1$，给定序列 $x^{\underline{n}},x^n,x^{\overline{n}}$，从左往右转换时需要加，从右往左转换时不需要加，然后注意从上升下降幂转换到通常幂用第一类斯特林数，从通常幂转换到上升下降幂用第二类斯特林数。
通过以上式子，我们通过把上升幂用第三类斯特林数直接转化成下降幂，和先用第一类斯特林数转化成通常幂，再用第二类斯特林数转化成下降幂两种方式，通过比较下降幂系数，我们可以得到第三类斯特林数和两个斯特林数之间的关系：
$$
L(n,k)=\sum\limits_{k=0}^ns(n,k)S(k,i)
$$
生成函数
第一类斯特林数的生成函数就是上升幂。
设 $B_k(x)=\sum_{i\ge k} S(i,k)x^i$，通过观察，我们可以知道：
$$
B_k(x)=xB_{k-1}(x)+kxB_{k}(x)
$$
由此我们可以得到：
$$
\begin{aligned}
B_k(x)&=\frac{xB_{k-1}(x)}{1-kx}\
&=\frac{x^2B_{k-2}(x)}{(1-kx)(1-(k-1)x)}\
&=\frac{x^k}{\prod_{r=1}^k(1-rx)}
\end{aligned}
$$
设 $F_k(x)=\sum_{i\ge k}S(i,k)\frac{x^i}{i!}$ 则我们可以得到：
$$
\begin{aligned}
F_k(x)&=\sum\limits_{i\ge 0}\frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\binom kj j^i\frac{x^i}{i!}\
&=\frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\binom kj\sum\limits_{i\ge 0}j^i\frac{x^i}{i!}\
&=\frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\binom kje^{jx}\
&=\frac{(e^x-1)^k}{k!}
\end{aligned}
$$
斯特林反演
斯特林反演公式：
$$
f(n)=\sum\limits_{i=0}^nS(n,i)g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}s(n,i)f(i)
$$
要证明上面这个式子，我们首先引入一个反转公式：
$$
\begin{aligned}
x^n&=\sum\limits_{i=0}^nS(n,i)x^{\underline{i}}\
&=\sum\limits_{i=0}^nS(n,i)(-1)^i(-x)^{\overline{i}}\
&=\sum\limits_{i=0}^nS(n,i)(-1)^i\sum\limits_{j=0}^is(i,j)(-x)^j\
&=\sum\limits_{j=0}^nx^j\sum\limits_{i=j}^nS(n,i)s(i,j)(-1)^{i-j}\
\end{aligned}
$$
比较两边系数你就可以得到：
$$
\sum\limits_{i=m}^nS(n,i)s(i,m)(-1)^{i-m}=[n=m]
$$
注意这里 $-1$ 的系数也可以是 $n-i$，容易发现当 $n-m=0$ 时这两个数奇偶性相同，当奇偶性不同的时候这两个数绝对不相等，也就是说是 $0$，这并不影响我们这个式子的恒等。
用同样的方法，我们可以得到另一个反转公式：
$$
\sum\limits_{i=m}^ns(n,i)S(i,m)(-1)^{i-m}=[n=m]
$$
现在我们来证明斯特林反演。
$$
\begin{aligned}
g(n)&=\sum\limits_{i=0}^n[i=n]g(i)\
&=\sum\limits_{i=0}^ng(i)\sum\limits_{j=i}^n s(n,j)S(j,i)(-1)^{n-j}\
&=\sum\limits_{j=0}^ns(n,j)(-1)^{n-j}\sum\limits_{i=0}^jS(j,i)g(i)\
&=\sum\limits_{j=0}^ns(n,j)(-1)^{n-j}f(j)
\end{aligned}
$$
同理，从右往左也可以证明，于是原式得证。
和二项式反演一样，这个式子也有许多变式。由反转公式对称性可以知道，我们交换等号两边的斯特林数仍然成立。我们让和式从 $n$ 开始枚举，枚举的量变成第一个数，式子仍然成立。只需要注意证明的时候不用 $n-j$ 而是用 $j-m$。这里不再赘述其他的几种斯特林反演。