斯特林数学习笔记
第二类斯特林数
为什么先说第二类斯特林数？ 因为 OIwiki 是先讲的第二类
定义 $\begin{Bmatrix}n\\k\end{Bmatrix}$ 表示将 $n$ 个两两不同的元素划分为 $k$ 个互不区分的非空子集的方案数。称 $\begin{Bmatrix}n\\k\end{Bmatrix}$ 为第二类斯特林数。
递推式
有个非常简单的递推式：
$$ \begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix} $$
边界是 $\begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]$。
考虑新加的第 $n$ 个元素。$\begin{Bmatrix}n-1\\k-1\end{Bmatrix}$ 表示将这个元素划分为一个新的集合，后面的则是把这个元素加入之前的一个集合。用加法原理加起来即可。
通项公式
可以用二项式反演套路地做。
考虑 $G(i)$ 表示将 $n$ 个元素划分到两两不同的 $i$ 个集合的方案数（可以为空），$F(i)$ 表示将 $n$ 个元素划分到 $i$ 个两两不同的非空集合的方案数。
显然有： $G(i)=i^n,G(i)=\sum_{j=0}^i\binom{i}{j}F(j)$，那么：
$$ \begin{aligned} F(i)&=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}G(j)\\ &=\sum_{j=0}^i\frac{(-1)^{i-j}i!j^n}{j!(i-j)!} \end{aligned} $$
然后第二类斯特林数是划分成 $k$ 个互不区分的集合，所以每种划分会被 $F(k)$ 算 $k!$ 遍，除去即可。
综上：
$$ \begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{j=0}^k\frac{(-1)^{k-j}j^n}{j!(k-j)!} $$
同一行第二类斯特林数的计算
留坑待补。
同一列第二类斯特林数的计算
留坑待补。
第一类斯特林数
定义 $\begin{bmatrix}n\\k\end{bmatrix}$ 表示将 $n$ 个两两不同的元素划分为 $k$ 个互不区分的非空轮换的方案数。
一个轮换就是一个首尾相接的环形序列，可以视作一串珠子。比如 $1,2,3,4$ 和 $2,3,4,1$ 是同一个轮换，但 $1,2,3,4$ 和 $4,3,2,1$ 不是同一个轮换。
递推式
$$ \begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix} $$
边界是 $\begin{bmatrix}n\\0\end{bmatrix}=[n=0]$。
证明和第二类类似，关于系数 $n-1$，因为插到前面每个数都后面是不同的。
通项公式
第一类斯特林数没有实用的通项公式。
同一行第一类斯特林数的计算
留坑待补。
同一列第一类斯特林数的计算
留坑待补。
应用
上升幂和下降幂转化为普通幂
记上升幂 $x^{\overline{n}}=\prod_{k=0}^{n-1}(x+k)$，则有：
$$ x^{\overline{n}}=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}x^k $$
证明
考虑数学归纳法。
首先对于 $n=0$，等号两边都等于 $1$。对于 $n=1$，左右两边都等于 $x$。
考虑 $n>1$，此时有：
$$ \begin{aligned} x^{\overline{n}}&=(x+n-1)x^{\overline{n-1}}\\ &=(x+n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^k\\ &=\left(x\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^k\right)+\left((n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^k\right)\\ &=\left(\sum_{k=1}^{n}\begin{bmatrix}n-1\\k-1\end{bmatrix}x^k\right)+\left(\sum_{k=1}^{n}(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}x^k\right)\\ &=\sum_{k=1}^n\left(\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}\right)x^k\\ &=\sum_{k=1}^n\begin{bmatrix}n\\k\end{bmatrix}x^k\\ &=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}x^k \end{aligned} $$
对于其中第四步两个 $\sum$ 下标改变的原因，第一个是将 $x$ 乘进去后改为枚举 $k+1$，第二个是因为 $k=0,k=n$ 时 $\begin{bmatrix}n-1\\k\end{bmatrix}$ 均为 $0$。最后一步也同理。
记下降幂 $x^{\underline{n}}=\prod_{k=0}^{n-1}(x-k)$，有：
$$ x^{\underline{n}}=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}x^k $$
证明类似，守序邪恶。
普通幂转化为上升幂和下降幂
普通幂转下降幂：
$$ \begin{aligned} x^n&=\sum_{k}\begin{Bmatrix}n\\k\end{Bmatrix}k!\binom{x}{k}\\ &=\sum_{k}\begin{Bmatrix}n\\k\end{Bmatrix}k!\frac{x!}{(x-k)!k!}\\ &=\sum_{k}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}} \end{aligned} $$
第一步考虑组合意义，$n$ 个球放进 $x$ 个互相区分的可空盒子里，那么先从 $x$ 个盒子里面选 $k$ 个，然后转化成 $n$ 个放到 $K$ 个互相区分的非空盒子里。后面的推导都很显然。
更板的推导是使用斯特林反演。
然后普通幂转上升幂：
$$ x^n=\sum_{k}(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\overline{k}} $$
证明还是斯特林反演。