第二类斯特林数学习笔记

定义与递推式

\(\left\{ \begin{matrix} n \\ k \end{matrix} \right\}\) ，也可记作 \(S(n,k)\) ，表示将 \(n\) 个有标号的数分成 \(k\) 个互不区分的组的方案数。

根据组合意义，能推出递推式为：

方幂转下降幂

左式组合意义是从 \(n\) 个数中选 \(m\) 个数，可重且有标号的方案数。右式是枚举本质不同的点的个数 \(k\)，再将 \(m\) 个数 划分到 \(k\) 组 ，且组之间区分带上 \(k!\) 的系数，最后乘上 \(n\) 个点中选 \(k\) 个点的方案数。

观察式子两边与 \(n\) 关联的项，左边是方幂形式，右边是组合数，也就是下降幂形式。下降幂的形式能够保证与 \(n\) 有关的次数不会超过 \(n\) ，有时会起到优化作用。

应用

给定一棵树，且树有一个代价 \(cost(S)\),且 \(cost(S)\le|S|\) ，且 \(f\) 可以同子树合并得到，现在要求对于所有非空节点集合 \(S\) 的生成最小连通块的 \(cost(S)^M\) 之和。

一个平凡的思路是直接记录 \(f_{u,i}\) 表示以 \(u\) 为根的子树的所有方案中，\(cost(S)^i\) 的代价和。合并用二项式定理展开，假设两部分所有方案中的 \(cost\) 的序列分别是 \(L_0,L_1,…\) 与 \(R_0,R_1,…\)。

这样做的时间复杂度是 \(O(nM^2)\)。

考虑优化，记录 \(g_{u,i}\) 表示以 \(u\) 为根的子树的所有方案中，\(\binom {cost(S)}{i}\) 的代价和，通过方幂转下降幂的公式能够在 \(O(nM)\) 的时间复杂度复原答案。通过范德蒙德恒等式合并，有：

这样看似还是平方的，但是 \(g\) 的第二维不会超过子树大小，所以时间复杂度就是 \(O(nM)\)。

本质上就是从维护 \(n^k\) 变成 \(\binom{n}{k}\) 枚举量就从 \(m\) 变成 \(min(n,m)\)，最后通过公式将 \(\binom{n}{k}\) 复原成 \(n^k\)。

显式公式

考虑组合意义，可以先求出区分组的方案数，最后再带上 \(\frac{1}{k!}\) 。区分组的方案本质就是将 \(n\) 个数染色，出现颜色数为 \(k\) 的方案数，这个可以通过将 \(n\) 个数染成 \(1\) 到 \(k\) 的颜色二项式反演得到。

生成函数

固定 \(k\) 的EGF：

固定 \(k\) 的OGF：