斯特林数
stripe_python
·
2026-08-23 22:08:07
·
学习·文化课
14.1 第二类斯特林数
第二类斯特林数 \left\{\begin{matrix}
n \\
m
\end{matrix}\right\} 表示将 n 个有标号 元素划分为 m 个无标号 非空子集的方案数。
我们可以用递推的思想来求解。考虑加入一个新元素的贡献:
将新元素单开一个子集,方案数 \left\{\begin{matrix}
n-1 \\
m-1
\end{matrix}\right\} 。
将新元素插入一个现有子集,方案数 m\left\{\begin{matrix}
n-1 \\
m
\end{matrix}\right\} 。
由加法原理合并得到递推式:
\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-1 \\
m-1
\end{bmatrix} 。
插入一个现有轮换,方案数 (n-1)\begin{bmatrix}
n-1 \\
m
\end{bmatrix} 。
加法原理合并就得到递推公式
\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) 。考虑精细实现:
用线性倒推法求解阶乘逆元。
用线性筛预处理 i^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}}=x(x+1)(x+2)\cdots (x+n-1)=\prod\limits_{i=0}^{n-1} (x+i) 。
下降幂 x^{\underline n}=x(x-1)(x-2)\cdots (x-n+1)=\prod \limits_{i=0}^{n-1} (x-i)=A_x^n 。
斯特林数可以实现上升幂 / 下降幂 / 普通幂之间的相互转化。
上升幂和普通幂的转化:
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!
这个公式非常重要,称为拆幂公式 。见到与普通幂有关的题目时,都可以尝试用下降幂转化。