第一类斯特林数

下面只讨论无符号第一类斯特林数。

定义第一类斯特林数 $\begin{bmatrix}n \\ m\end{bmatrix}$ 为 $n$ 个不同元素划分为 $m$ 个互不区分的圆排列的方案数。

递推式

由定义不难得到一个递推式
$$
\begin{bmatrix}n \\ m\end{bmatrix} = \begin{bmatrix} n - 1 \\ m - 1 \end{bmatrix} + (n - 1) \begin{bmatrix} n - 1 \\ m\end{bmatrix}
$$
边界是 $\begin{bmatrix} n \\ 0 \end{bmatrix} = [n = 0]$。

这个递推式的含义是：讨论 $n$ 号元素放在哪里，可以单独作为一个圆排列，也可以插入到之前任意一个元素后方。

计算一行

考虑写出第一类斯特林数第 $n$ 行的 OGF $F_n(x)$。我们有
$$
F_n(x) = (n - 1) F_{n-1}(x) + xF_{n - 1}(x) = (n - 1 + x) F_{n - 1}(x)
$$
又 $F_1 = x$，于是有
$$
F_n(x) = x^{\overline{n}} \tag{1} \label{1}
$$
可以分治计算，复杂度 $\mathcal{O}(n\log ^2 n)$；但是实际上可以做到 $\mathcal{O}(n\log n)$。

考虑倍增求 $x^{\overline{n}}$。$n$ 为奇数时只需要计算 $x^{\overline{n - 1}}$ 然后暴力乘上 $(x + n - 1)$ 即可，下面只考虑 $n$ 为偶数的情况。

设 $m = \frac{n}{2}$，则有
$$
x^{\overline{n}} = x^{\overline{m}} \times (x + m)^{\overline{m}}
$$
考虑递归求出 $x^{\overline{m}}$，然后求出 $(x+m)^{\overline{m}}$。这个问题相当于已知 $F(x)$，求 $F(x + m)$。
$$
\begin{align}
F(x + m) & = \sum_{i \geq 0} f_i (x + m) ^ i \\
& = \sum_{i\geq 0} f_i \sum_{j = 0}^i {i \choose j} x^j m^{i - j} \\
& = \sum_{j \geq 0} \frac{x^j}{j!} \sum_{i \geq j} f_i i! \times \frac{m^{i - j}}{(i - j)!}
\end{align}
$$
后面是一个差卷积的形式，于是可以在 $\mathcal{O}(n\log n)$ 的复杂度内求出 $F(x + m)$，从而解决了原问题。

总时间复杂度 $\mathcal{T}(n) = \mathcal{T}(\frac{n}{2}) + \mathcal{O}(n\log n) = \mathcal{O}(n\log n)$。

计算一列

考虑仅有一个圆排列时的 EGF $F(x)$，显然有
$$
F(x) = \sum_{i\geq 1} \frac{(i - 1) !x^i}{i!} = \sum_{i\geq 1}\frac{x^i}{i}
$$
那么 $m$ 个圆排列的 EGF 即为
$$
\frac{F(x)^m}{m!}
$$
这里除以 $m!$ 是因为圆排列是互不区分的。

这样子就可以直接多项式快速幂计算了。需要注意的是 $F(x)$ 常数项为 $0$，所以需要先左移一位，快速幂后再右移 $k$ 位。

第二类斯特林数

第二类斯特林数 $\begin{Bmatrix}n \\ m\end{Bmatrix}$ 定义为 $n$ 个不同元素划分为 $m$ 个互不区分的非空集合的方案数。

递推式

由定义不难得到一个递推式
$$
\begin{Bmatrix} n \\ m \end{Bmatrix} = \begin{Bmatrix} n - 1\\ m - 1\end{Bmatrix} + m \begin{Bmatrix} n - 1\\ m \end{Bmatrix}
$$
边界是 $\begin{Bmatrix} n \\ 0 \end{Bmatrix} = [n = 0]$。

这个递推式的含义是：考虑 $n$ 号元素放在哪里，可以单独作为一个集合，也可以放到之前的任意一个集合内。

通项公式

由容斥原理，我们可以得到一个通项公式
$$
\begin{Bmatrix} n \\ m \end{Bmatrix} = \frac{1}{m!} \sum_{i = 0}^m (-1)^{m - i} {m\choose i} i^n
$$
其中 $i$ 的含义为非空集合的数量。

我们也可以将其化简
$$
\begin{Bmatrix} n \\ m \end{Bmatrix} = \sum_{i = 0}^m (-1)^{m - i} \frac{i^n}{i!(m - i)!} \tag{2} \label{2}
$$

计算一行

$\eqref{2}$ 显然为卷积的形式，直接计算即可。

计算一列

考虑仅有一个集合时的 EGF $F(x)$，显然有
$$
F(x) = \sum_{i\geq 1}\frac{x^i}{i!}
$$
那么 $m$ 个集合时的 EGF 即为
$$
\frac{F(x)^m}{m!}
$$
这里除以 $m!$ 是因为集合是互不区分的。

这样子同样可以多项式快速幂计算。同样需要注意的是$F(x)$ 常数项为 $0$，按照第一类斯特林数计算一列时的方法处理即可。

一些应用

斯特林反演

$$
f_n = \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} g_i \Leftrightarrow g_n = \sum_{i = 1}^n (-1)^{n - i} \begin{bmatrix}n \\ i\end{bmatrix} f_i \tag{3} \label{3}
$$

证明先咕着，可以先看 gzy 的博客。

事实上反过来也是成立的
$$
f_n = \sum_{i = 1}^n \begin{bmatrix} n \\ i \end{bmatrix} g_i \Leftrightarrow g_n = \sum_{i = 1}^n (-1)^{n - i} \begin{Bmatrix}n \\ i\end{Bmatrix} f_i \tag{4} \label{4}
$$

上升幂与普通幂的相互转化

根据 $\eqref{1}$，我们可以得到
$$
x^{\overline{n}} = \sum_{i\geq 0} \begin{bmatrix} n \\ i \end{bmatrix} x^i
$$
由 $\eqref{4}$ 可得
$$
x^n = \sum_{i\geq 0} \begin{Bmatrix} n \\ i \end{Bmatrix} (-1)^{n - i} x^{\overline{i}}
$$

下降幂与普通幂的相互转化

有
$$
x^n = \sum_{i\geq 0} \begin{Bmatrix} n \\ i \end{Bmatrix} x^{\underline{i}}
$$
这可以通过组合意义证明：

• 左边为 $n$ 个有标号的球放到 $x$ 个有标号盒子中的方案数；
• 右边的含义为：枚举非空的盒子数 $i$，在 $x$ 个盒子中有顺序地选出 $i$ 个，然后把 $n$ 个球放在 $i$ 个盒子中。

显然左右两边是等价的。

由 $\eqref{3}$ 可得
$$
x^{\underline{n}} = \sum_{i\geq 0} (-1)^{n - i} \begin{bmatrix} n \\ i \end{bmatrix} x^i
$$