第一类斯特林数

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

定义第一类斯特林数 $\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 $$

最后修改:2021 年 02 月 07 日 08 : 30 AM