定义与递推式

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

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

\[S(n,k)=S(n-1,k-1)+S(n-1,k)\cdot k \]

方幂转下降幂

\[n^m=\sum_{k=0}^{min(n,m)}S(m,k)\binom {n}{k}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,…\)。

\[ \begin{aligned} f_{u,k}&=\sum_i\sum_j (L_i+R_j)^k\\ &=\sum_i\sum_j\sum_{t=0}^k\binom {k}{t}{L_i}^t{R_i}^{k-t}\\ &=\sum_{t=0}^k \binom {k}{t} (\sum_i{L_i}^t)(\sum_j{R_j}^{k-t})\\ &=\sum_{t=0}^k \binom {k}{t} f_{v1,t}\cdot f_{v2,k-t} \end{aligned} \]

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

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

\[\begin{aligned} g_{u,k}&=\sum_i\sum_j\binom{L_i+R_j}{k}\\ &=\sum_i\sum_j\sum_{t=0}^k\binom{L_i}{t}\binom{R_j}{k-t}\\ &=\sum_{t=0}^k(\sum_i\binom{L_i}{t})(\sum_j\binom{R_j}{k-t})\\ &=\sum_{t=0}^kg_{v1,t}\cdot g_{v2,k-t} \end{aligned} \]

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

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

显式公式

\[S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}i^n \]

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

生成函数

固定 \(k\) 的EGF：

\[\sum_{n=k}^\infty \frac{x^n}{n!}S(n,k)=\frac{(e^x-1)^k}{k!} \]

固定 \(k\) 的OGF：

\[\sum_{n=k}^\infty x^nS(n,k)=\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}\frac{1}{1-ix}\\ \sum_{n=k}^\infty x^nS(n,k)=\frac{x^k}{\prod_{i=0}^{k}1-ix} \]