斯特林数和贝尔数

版权说明：抄写了hypoc的博客

第一类斯特林数

符号： \(\begin{bmatrix}n\\m\end{bmatrix}\) 或 \(s(n,m)\)

意义： \(n\) 个不同球穿成 \(m\) 条项链的方案数。

第 \(n\) 个球接在前面 \(n-1\) 个小球中某一个的后面或新开一条项链。

递推式：

复杂度 \(O(nm)\)

考虑生成函数优化。

第 \(i\) 次选择时，有 \(i-1\) 中选择不创造新的项链，\(1\) 种选择创造新项链。写成生成函数就是

使用分治来解决，每层再用 \(FFT\) 将左右两边的多项式相乘， \(x^m\) 的系数是 \(s(n,m)\) 。时间复杂度 \(O(n\log^2 n)\) 。

有些题存在 \(O(n\log n )\) 做法。

第二类斯特林数

符号： \(\begin{Bmatrix}n\\m\end{Bmatrix}\) 或 \(S(n,m)\)

意义： \(n\) 个不同小球放入 \(m\) 个相同盒子的方案数。

要么和前面的放一个盒子里要么新开一个。

时间复杂度 \(O(nm)\)

生成函数无法加速了。考虑容斥加速。

不妨先假设每个盒子都不一样，最后再除以 \(m!\) 。

容斥需要计算不合理方案。空盒子即不合理。

时间复杂度 \(O(n\log n)\)

据说是 \(FFT\) 搞一搞。

斯特林数与下降幂

一般幂转下降幂

考虑 \(x^n\) 的组合意义， \(n\) 个不同的球放入 \(x\) 个不同的盒子的方案数。

枚举有多少非空的盒子：

下降幂转一般幂

第一类斯特林数的生成函数是上升幂，即：

如果将 \((x+i)\) 替换为 \((x-i)\) 那么就会求出下降幂。

贝尔数

\(n\) 个不同小球放在若干个相同的盒子里，问方案数。

递推公式：

枚举 \(i\) 表示 \(n-i\) 个球和 \(n+1\) 个球在同一个盒子里，剩下的 \(i\) 个又有 \(B_i\) 种。选球花 \(n\choose i\)

快速求 \(B_i\) :

\(O(n\log n)\) 处理 \(\frac {(n-i)^n} {(n-i)!}\) 后缀和，\(O(n)\) 求出 \(B_n\) 即可。

斯特林数和贝尔数

原文：https://www.cnblogs.com/zdsrs060330/p/14619391.html