斯特林数

· · 学习·文化课

14.1 第二类斯特林数

第二类斯特林数 \left\{\begin{matrix} n \\ m \end{matrix}\right\} 表示将 n 个有标号元素划分为 m 个无标号非空子集的方案数。

我们可以用递推的思想来求解。考虑加入一个新元素的贡献:

由加法原理合并得到递推式:

\left\{\begin{matrix} n \\ m \end{matrix}\right\}=\left\{\begin{matrix} n-1 \\ m-1 \end{matrix}\right\}+m\left\{\begin{matrix} n-1 \\ m \end{matrix}\right\}

可以做到 O(n^2) 求解。

14.1.1 通项公式

上面的式子复杂度还是太高了,我们考虑直接用组合数学方法求 \left\{\begin{matrix} n \\ m \end{matrix}\right\}。记:

根据球盒模型我们知道 g(m)=m^n,又根据消序原理 \left\{\begin{matrix} n \\ m \end{matrix}\right\}=\dfrac{f(m)}{m!},所以只需配上容斥系数实现 g \to f 的转化。

考虑枚举空集的数目,可以实现 f \to g 的转化:

g(m)=\sum_{i=0}^m \binom{m}{i} f(i)

由二项式反演形式一,容斥系数 (-1)^{m-i} \dbinom{m}{i}。也即

\begin{aligned} f(m)&=\sum_{i=0}^m (-1)^{m-i} \binom{m}{i} g(i)\\ &=\sum_{i=0}^m (-1)^{m-i} \dfrac{m!}{i!(m-i)!} i^n\\ &=\sum_{i=0}^m \dfrac{(-1)^{m-i}i^n m!}{i!(m-i)!} \end{aligned}

消序后就得到通项公式

\left\{\begin{matrix} n \\ m \end{matrix}\right\} = \sum_{i=0}^m \dfrac{(-1)^{m-i} i^n}{i!(m-i)!}

这是一个卷积的形式:记 f_i=\dfrac{i^n}{i!},g_i=\dfrac{(-1)^i}{i!},则有 \left\{\begin{matrix} n \\ m \end{matrix}\right\}=[x^m] FG。容易在 O(n \log n) 内求解同行第二类斯特林数。

14.2 第一类斯特林数

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

在 OI 中,可以认为第一类斯特林数没有通项公式。

根据第一类斯特林数的组合意义,有一个组合恒等式:

\sum_{i=0}^n\begin{bmatrix} n \\ i \end{bmatrix}=n!

14.3 贝尔数

贝尔数 B_n 表示将 n 个有标号元素不重不漏地划分为若干非空集合的方案数。

根据第二类斯特林数的组合意义,贝尔数就是同行第二类斯特林数的和:

B_n=\sum_{i=0}^m\left\{\begin{matrix} n \\ i \end{matrix}\right\}

贝尔数还满足一个递推式:

B_{n+1}=\sum_{i=0}^m \binom{n}{i} B_i

原理是枚举第 n+1 个元素所在集合的大小。上面的两种方法都能做到 O(n^2) 计算贝尔数。

14.3.1 求法

P5748 集合划分计数:

$T =10^3$,$n \le 10^5$,1 秒,125 MB。

我们介绍两种做法。第一种做法可以 O(n) 计算单个 B_n,第二种做法可以 O(n \log n) 求出 B_1 \sim B_n。

:::::success[单个贝尔数的求法]

代入第二类斯特林数的通项公式:

\begin{aligned} B_n&=\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} \\ &=\sum_{k=0}^{n} \sum_{i=0}^{k} \dfrac{(-1)^{k-i}i^n}{i!(k-i)!}\\ &=\sum_{i=0}^n \sum_{k=i}^n \dfrac{(-1)^{k-i}i^n}{i!(k-i)!}\\ &=\sum_{i=0}^n\dfrac{i^n}{i!} \sum_{k=i}^n \dfrac{(-1)^{k-i}}{(k-i)!}\\ &=\sum_{i=0}^n\dfrac{i^n}{i!} \sum_{j=0}^{n-i} \dfrac{(-1)^j}{j!}\\ \end{aligned}

预处理 \dfrac{(-1)^j}{j!} 的前缀和即可做到 O(n \log n)。考虑精细实现:

预处理后复杂度 O(n)。

:::::

:::::success[多个贝尔数的求法]

记贝尔数的 EGF 为 F,代入递推公式:

\begin{aligned} F(x)&=\sum_{n \ge 0} B_n \dfrac{x^n}{n!}\\ F'(x)&=\sum_{n \ge 0}B_{n+1} \dfrac{x^n}{n!}\\ &= \sum_{n \ge 0} \dfrac{x^n}{n!} \sum_{k=0}^n \binom{n}{k} B_k\\ &= \sum_{k \ge 0} B_k \sum_{n \ge k} \binom{n}{k} \dfrac{x^n}{n!}\\ &= \sum_{k \ge 0} B_k \sum_{n \ge k} \dfrac{x^n}{k!(n-k)!} \\ &= \sum_{k \ge 0} B_k \dfrac{x^k}{k!} \sum _{i \ge 0} \dfrac{x^i}{i!}\\ F'(x)&=F(x) \times e^x \end{aligned}

由微分方程 F'=Fe^x 得 \ln F=e^x+C。代入 F(0)=1 知 C=-1,因此我们得到了贝尔数的 EGF

F(x)=\exp (e^x-1)

两次多项式 \exp 即可,复杂度 O(n \log n)。

:::::

14.3.2 性质

在第二种方法中,我们求得了贝尔数的 EGF。据此还可以得到 Dobinski 公式

B_n=\dfrac{1}{e} \sum_{k \ge 0} \dfrac{k^n}{k!}

贝尔数对质数 p 有如下同余式

B_{n+p} \equiv B_n+B_{n+1} \pmod p

称为 Touchard 同余。另外还有扩展 Touchard 同余

B_{n+p^k}=kB_n+B_{n+1} \pmod p

这两个定理我们不证。

14.4 应用

先给出两个定义:

斯特林数可以实现上升幂 / 下降幂 / 普通幂之间的相互转化。

上升幂和普通幂的转化:

x^{\overline n}=\sum_{k=0}^n\begin{bmatrix} n \\ k \end{bmatrix}x^k \iff x^n=\sum_{k=0}^n (-1)^{n-k}\left\{\begin{matrix} n \\ k \end{matrix}\right\} x^{\overline k}

下降幂和普通幂的转化:

x^n=\sum_{k=0}^n\left\{\begin{matrix} n \\ k \end{matrix}\right\} x^{\underline k} \iff x^{\underline n} =\sum_{k=0}^n (-1)^{n-k}\begin{bmatrix} n \\ k \end{bmatrix}x^k

同组内的两个等式由斯特林反演得到。

其中普通幂转下降幂的式子又可以写作

x^n=\sum_{k=0}^n\left\{\begin{matrix} n \\ k \end{matrix}\right\} \binom{n}{k} k!

这个公式非常重要,称为拆幂公式。见到与普通幂有关的题目时,都可以尝试用下降幂转化。