关于斯特林数
bluewindde
·
·
算法·理论
Copyright (c) 2025 bluewindde
采用 CC BY-NC-SA 4.0 International 协议 发布。
前情提要：https://www.luogu.com.cn/article/wofybi22
摘要：本文通过代数方法给出第二类斯特林数的定义。
modfish 好闪，拜谢 modfish！
规定 0^0 = 1。
考虑函数
\def\dd{\mathrm d}
\def\dx{\mathrm dx}
\def\d#1{\mathrm d#1}
\begin{align*}
f_k(n) = &\sum\limits_{i = 0}^n \binom n i i^k p^i \\
= &\left( p \frac \dd {\d p} \right)^k \sum\limits_{i = 0}^n \binom n i p^i \\
= &\left( p \frac \dd {\d p} \right) f_{k-1}(n) \\
\end{align*}
特别地
f_0(n) = \sum\limits_{i = 0}^n \binom n i p^i = (1 + p)^n
因此
\def\dd{\mathrm d}
\def\dx{\mathrm dx}
\def\d#1{\mathrm d#1}
\begin{align*}
f_1(n) &= \left( p \frac \dd {\d p} \right) (1 + p)^n = np(1+p)^{n-1} \\
f_2(n) &= np(1+p)^{n-1} + n(n-1)p^2(1+p)^{n-2} \\
f_3(n) &= np(1+p)^{n-1} + 3n(n-1)p^2(1+p)^{n-2} + n(n-1)(n-2)p^3(1+p)^{n-3} \\
f_4(n) &= np(1+p)^{n-1} + 7n(n-1)p^2(1+p)^{n-2} + 6n(n-1)(n-2)p^3(1+p)^{n-3} + n(n-1)(n-2)(n-3)p^4(1+p)^{n-4} \\
&\cdots \\
\end{align*}
关注每次求导带来的系数变化，设第 t 项 p^t(1+p)^{n-t} 的系数为 g_k(t)，有递推
g_k(t) = t \cdot g_{k-1}(t) + g_{k-1}(t-1)
特别地
g_k(1) = g_{k-1}(1) = 1
g_k(k) = g_{k-1}(k - 1) = 1
$${k \brace t} = g_k(t), 1 \leqslant t \leqslant k$$
该定义通常采用的组合意义定义等价。
第二类斯特林数组合意义：$n$ 个两两不同的物体，划分为 $k$ 个互不区分非空子集的方案数。
因此
$$f_k(n) = \sum\limits_{i = 1}^k {k \brace i} \frac {n!} {(n-i)!} p^i(1+p)^{n-i}$$
---
多么波澜壮阔的冒险！
英雄之旅抵达终点，「再创世」的真相也呼之欲出——
可是，当真如此吗？
---
当 $k = n$ 时，$(1+p)^{n-k} = (1+p)^0 = 1$，但在上面的递推中它的导数被认为是 $(1+p)^{-1}$。
临界情况
$$
\begin{align*}
f_n(n) &= \sum\limits_{i = 1}^{n-1} {n \brace i} \frac {n!} {(n-i)!} p^i(1+p)^{n-i} + {n \brace n} \frac {n!} {(n-n)!} p^n(1+p)^{n-n} \\
&= \sum\limits_{i = 1}^{n-1} {n \brace i} \frac {n!} {(n-i)!} p^i(1+p)^{n-i} + n! p^n \\
\end{align*}
$$
然后
$$
\begin{align*}
f_{n+1}(n) &= \sum\limits_{i = 1}^{n-1} {n+1 \brace i} \frac {n!} {(n-i)!} p^i(1+p)^{n-i} + {n \brace n-1} n! p^n + n! n p^n \\
f_{n+2}(n) &= \sum\limits_{i = 1}^{n-1} {n+2 \brace i} \frac {n!} {(n-i)!} p^i(1+p)^{n-i} + {n+1 \brace n-1} n! p^n + {n \brace n-1} n! n p^n + n! n^2 p^n \\
&\cdots \\
\end{align*}
$$
当 $k > n$ 时
$$f_k(n) = \sum\limits_{i = 1}^{n-1} {k \brace i} \frac {n!} {(n-i)!} p^i (1+p)^{n-i} + \sum\limits_{i = n}^k {i-1 \brace n-1} n!n^{k-i}p^n$$
根据 ${k \brace n} = n {k-1 \brace n} + {k-1 \brace n-1}$，有
$$
\begin{align*}
{k \brace n} &= n {k-1 \brace n} + {k-1 \brace n-1} \\
&= n \left( n {k-2 \brace n} + {k-2 \brace n-1} \right) + {k-1 \brace n-1} \\
&= n \left( n \left( n {k-3 \brace n} + {k-3 \brace n-1} \right) + {k-2 \brace n-1} \right) + {k-1 \brace n-1} \\
&= \cdots \\
&= \sum\limits_{i = n}^k {i-1 \brace n-1} n^{k-i} \\
\end{align*}
$$
因此
$$
\begin{align*}
f_k(n) &= \sum\limits_{i = 1}^{n-1} {k \brace i} \frac {n!} {(n-i)!} p^i (1+p)^{n-i} + \sum\limits_{i = n}^k {i-1 \brace n-1} n!n^{k-i}p^n \\
&= \sum\limits_{i = 1}^{n-1} {k \brace i} \frac {n!} {(n-i)!} p^i (1+p)^{n-i} + {k \brace n} n!p^n \\
&= \sum\limits_{i = 1}^n {k \brace i} \frac {n!} {(n-i)!} p^i (1+p)^{n-i} \\
\end{align*}
$$
综上所述，$n \in \mathbf N, k \in \mathbf N*$ 时
$$f_k(n) = \sum\limits_{i = 0}^n \binom n i i^k p^i = \sum\limits_{i = 1}^{\min(n, k)} {k \brace i} \frac {n!} {(n-i)!} p^i (1+p)^{n-i}$$
注意为了使第二类斯特林数有定义，最终式子不包含 $k = 0$ 的情况。
---
当 $p = -1$ 时
$$
f_k(n) = \sum\limits_{i = 0}^n \binom n i i^k (-1)^i =
\begin{cases}
0, &k < n, \\
(-1)^n {k \brace n} n!, &k \geqslant n. \\
\end{cases}
$$
[modfish_](https://www.luogu.com.cn/user/605226) 给上面的式子赋予了组合意义：长为 $k$，值域为 $[1, n]$ 的整数数列，值域中的每个数都在数列中出现至少一次的方案数。$f_k(n)$ 就是在容斥计算该问题的答案。
令 $k = N, n = M$，导出第二类斯特林数通项公式
$$
\begin{align*}
{n \brace m} &= (-1)^m \frac 1 {m!} \sum\limits_{i = 0}^m \binom m i i^n (-1)^i \\
&= (-1)^m \frac 1 {m!} \sum\limits_{i = 0}^m \frac {m!} {i! (m-i)!} i^n (-1)^i \\
&= (-1)^m \sum\limits_{i = 0}^m \frac {(-1)^i i^n} {i! (m-i)!} \\
\end{align*}
$$
---
当 $p = 1$ 时
$$f_k(n) = \sum\limits_{i = 0}^n \binom n i i^k = \sum\limits_{i = 1}^{\min(n, k)} {k \brace i} \frac {n!} {(n-i)!} 2^{n-i}$$
导出组合恒等式
$$
\begin{align*}
f_1(n) &= \sum\limits_{i = 0}^n \binom n i i = n2^{n-1} \\
f_2(n) &= \sum\limits_{i = 0}^n \binom n i i^2 \\
&= n 2^{n-1} + n(n-1) 2^{n-2} = n(n+1)2^{n-2} \qquad (n \geqslant 2) \\
f_3(n) &= \sum\limits_{i = 0}^n \binom n i i^3 \\
&= n2^{n-1} + 3n(n-1)2^{n-2} + n(n-1)(n-2)2^{n-3} \\
&= (n+3)n^22^{n-3} \qquad (n \geqslant 3) \\
\end{align*}
$$