[学习笔记]浅析 第二类斯特林（Stirling）数 的妙用

斯特林（Stirling）数 的妙用"/>

[学习笔记]浅析 第二类斯特林（Stirling）数 的妙用

一、概念及递推

第二类斯特林数：把 n n $n$ 个元素分成 m'>mm$m$ 个非空无序集合的方案数，记作

{nm} { n m } $$\begin{Bmatrix}n\\m\end{Bmatrix}$$
递推式：考察第 n n $n$ 个元素是否单独属于一个集合。
如果单独属于一个集合，那么剩下的 n−1'>n−1n−1$n-1$ 个元素有 {n−1m−1} { n − 1 m − 1 } $\begin{Bmatrix}n-1\\m-1\end{Bmatrix}$ 中划分方法。
如果不单独属于一个集合，那么剩下的 n−1 n − 1 $n-1$ 个元素有 {n−1m} { n − 1 m } $\begin{Bmatrix}n-1\\m\end{Bmatrix}$ 种划分方法，第 n n $n$ 个元素可以插入这 m'>mm$m$ 个集合中的任一。
所以得出第二类斯特林数的递推式：
{nm}={n−1m−1}+m×{n−1m} { n m } = { n − 1 m − 1 } + m × { n − 1 m } $$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\times\begin{Bmatrix}n-1\\m\end{Bmatrix}$$
边界 {00}=1 { 0 0 } = 1 $\begin{Bmatrix}0\\0\end{Bmatrix}=1$ 。

二、通项公式

可以用容斥的方法求第二类斯特林数。
先考虑无序转有序，设 T(n,m) T ( n , m ) $T(n,m)$ 表示把 n n $n$ 个元素划分成 m'>mm$m$ 个非空有序集合的方案数。
注意这里「有序」的概念：集合的顺序有序，而集合内的元素无序。
如 {1,3}{2,4,5} { 1 , 3 } { 2 , 4 , 5 } $\{1,3\}\{2,4,5\}$ 和 {3,1}{5,4,2} { 3 , 1 } { 5 , 4 , 2 } $\{3,1\}\{5,4,2\}$ 是同一种方案，
而 {1,3}{2,4,5} { 1 , 3 } { 2 , 4 , 5 } $\{1,3\}\{2,4,5\}$ 和 {2,4,5}{1,3} { 2 , 4 , 5 } { 1 , 3 } $\{2,4,5\}\{1,3\}$ 不是同一方案。
这时候有：

{nm}=T(n,m)m! { n m } = T ( n , m ) m ! $$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{T(n,m)}{m!}$$
还是不 太好求，考虑能否去掉「非空」这个条件。
如果不要求「非空」，那么可以把问题成对于每个元素，都为这个元素选取一个它所属的集合。方案数为：
mn m n $$m^n$$
再加上「非空」这一条件，可以考虑容斥，枚举 {1,2,...,m} { 1 , 2 , . . . , m } $\{1,2,...,m\}$ 的一个子集 S S $S$ ，强制 S'>SS$S$ 内所有元素对应的集合全部为空。根据容斥原理，
T(n,m)=∑S⊂{1,2,...m}(−1)|S|×(m−|S|)n T ( n , m ) = ∑ S ⊂ { 1 , 2 , . . . m } ( − 1 ) | S | × ( m − | S | ) n $$T(n,m)=\sum_{S\subset\{1,2,...m\}}(-1)^{|S|}\times (m-|S|)^n$$
利用上组合数，把枚举 S S $S$ 改为枚举 |S|'>|S||S|$|S|$ ：
T(n,m)=∑i=0m(−1)i×(m−i)n×(mi) T ( n , m ) = ∑ i = 0 m ( − 1 ) i × ( m − i ) n × ( m i ) $$T(n,m)=\sum_{i=0}^m(-1)^i\times (m-i)^n\times\binom m i$$
故
{nm}=1m!∑i=0m(−1)i×(m−i)n×(mi) { n m } = 1 m ! ∑ i = 0 m ( − 1 ) i × ( m − i ) n × ( m i ) $$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac 1{m!}\sum_{i=0}^m(-1)^i\times (m-i)^n\times\binom m i$$

三、形如 nm n m $n^m$ 的式子的分解

先给出公式：

nm=∑i=0∞{mi}×(ni)×i! n m = ∑ i = 0 ∞ { m i } × ( n i ) × i ! $$n^m=\sum_{i=0}^{\infty}\begin{Bmatrix}m\\i\end{Bmatrix}\times\binom n i\times i!$$
可以从组合数学的角度分析。
首先， {mi}×i!=T(m,i) { m i } × i ! = T ( m , i ) $\begin{Bmatrix}m\\i\end{Bmatrix}\times i!=T(m,i)$ ：
nm=∑i=0∞T(m,i)×(ni) n m = ∑ i = 0 ∞ T ( m , i ) × ( n i ) $$n^m=\sum_{i=0}^{\infty}T(m,i)\times\binom n i$$
这就是在 n n $n$ 个集合中选出一些集合，用 m'>mm$m$ 个元素填充选出的集合， 使得被选出的集合不得为空。换一种想法，是在 n n $n$ 个集合中，先指定一部分集合必须为空，剩下的集合必须非空，并用 m'>mm$m$ 个元素填充 指定非空的集合。
进一步进行转化——用 m m $m$ 个元素填充 n'>nn$n$ 个集合， 集合空或非空都行的方案数。
因此方案数为 nm n m $n^m$ ！

四、应用

给定一个 n n $n$ 个点 m'>mm$m$ 条边的 DAG 和参数 k k $k$ ， 定义一条经过 l'>ll$l$ 条边的路径的权值为 lk l k $l^k$ 。 对于 1≤i≤n 1 ≤ i ≤ n $1\le i\le n$ ， 求出所有 1 1 $1$ 到 i'>ii$i$ 的路径的权值之和，对 998244353 998244353 $998244353$ 取模。 1≤n≤105 1 ≤ n ≤ 10 5 $1\le n\le 10^5$ 。 1≤m≤2×105 1 ≤ m ≤ 2 × 10 5 $1\le m\le 2\times 10^5$ 。 0≤k≤500 0 ≤ k ≤ 500 $0\le k\le 500$ 。
显然拓扑排序，但直接求解有些困难，不妨转化下 lk l k $l^k$ ：

lk=∑i=0k{ki}×(li)×i! l k = ∑ i = 0 k { k i } × ( l i ) × i ! $$l^k=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}\times\binom l i\times i!$$
看到 0≤k≤500 0 ≤ k ≤ 500 $0\le k\le 500$ 的范围，将每个 i i $i$ 分开考虑。
定义 f[u][i]'>f[u][i]f[u][i]$f[u][i]$ 表示从 1 1 $1$ 到 u'>uu$u$ 的所有路径的 (路径长度i) ( 路 径 长 度 i ) $\binom{路径长度}i$ 之和。
根据组合数的递推公式，可以得出转移：对于一条边 <u,v> < u , v > <script id="MathJax-Element-4681" type="math/tex"> </script> ，
f[v][i]+=f[u][i]+f[u][i−1] f [ v ] [ i ] + = f [ u ] [ i ] + f [ u ] [ i − 1 ] $$f[v][i]+=f[u][i]+f[u][i-1]$$
1 1 $1$ 到 u'>uu$u$ 的路径权值和就是：
∑i=0k{ki}×i!×f[u][i] ∑ i = 0 k { k i } × i ! × f [ u ] [ i ] $$\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}\times i!\times f[u][i]$$

五、In A Word

第二类斯特林数的妙用就是转换形如 nm n m $n^m$ 的式子。