斯特林数 笔记

这篇文主要记录一些lizbaka在学习斯特林数时遇到的一些比较关键的点
此文条理较为混乱，不甚完善，主要以作为笔记为目的，仅供参考

第二类斯特林数

第二类斯特林数$\begin{Bmatrix}n\\k\end{Bmatrix}$表示$n$个元素划分成$k$个非空无标号集合的方案数

其递推方程为：

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\times\begin{Bmatrix}n-1\\k\end{Bmatrix}$$

$$\begin{Bmatrix}0\\0\end{Bmatrix}=1$$

其意义为，最后一个元素，单独组成一个集合，或加入已有的任意一个集合

第二类斯特林数$\begin{Bmatrix}n\\k\end{Bmatrix}$又称为“$n$子集$k$”

---

第二类斯特林数的展开式为：

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}(k-i)^n$$

考虑盒子有标号，且允许有空盒的情况

那么有$i$个盒子为空的方案数即为$\begin{pmatrix}k\\i\end{pmatrix}(k-i)^n$

容斥一下，再除以一个阶乘变成无标号的情况即可

进一步整理，式子化为

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^k\frac{(-1)^i}{i!}\times \frac{(k-i)^n}{(k-i)!}$$

这是一个卷积形式的式子，可以利用FFT/NTT求得

---

第一类斯特林数

第一类斯特林数$\begin{bmatrix}n\\k\end{bmatrix}$表示$n$个元素划分成$k$个圆排列的方案数

其递推方程为：

$$\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\times\begin{bmatrix}n-1\\k\end{bmatrix}$$

$$\begin{bmatrix}0\\0\end{bmatrix}=1$$

其意义为，最后一个元素，单独组成一个圆排列，或者插入到已有的任意一个元素的左侧

第一类斯特林数$\begin{bmatrix}n\\k\end{bmatrix}$又称为“$n$轮换$k$”

---

每一个排列都与一个轮换的集合等价*(《具体数学》$P217-P218$)*

于是有:

$$\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}=n!(n\ge0)$$

斯特林数与常幂/下降幂/上升幂

记下降幂：

$$x^{\underline n}=x\times(x-1)\times(x-2)\cdots\times(x-n+1)$$

记上升幂：

$$x^{\overline n}=x\times(x+1)\times(x+2)\cdots\times(x+n+1)$$

这常常出现在组合计数中

---

幂之间的转换公式*(《具体数学》$P219-P220$)*：

$$x^{\overline n}=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}x^k$$

$$x^{\underline n}=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k$$

$$x^n=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline k}=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{n-k}x^{\overline k}$$

事实上，我们可以建立常幂与组合数之间的关系：

$$x^n=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline k}=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\times k!\times \begin{pmatrix}x\\k\end{pmatrix}$$

从而转化到组合数进行求解