斯特林数学习笔记

1.定义

第二类斯特林数：

定义 $S(n,m)$ 或 $\left\{\dfrac{n}{m}\right\}$ 表示斯特林数，表示n个不同的小球放在m个相同盒子的方案数。

有递推式：

S(n,m)=S(n-1,m-1)+m\times S(n-1,m)

枚举最后一个球放在了之前的格子还是新的盒子。

通项公式：

S(n,m)=\frac 1{m!} \sum_{k=0}^m(-1)^kC(m,k)(m-k)^n

证明：枚举空集合的个数k，那么剩下m-k的里面就都是有球的，方案数为 $C(m,k)(m-k)^n$ 。

容斥原理，因为是无序的，要除以m的阶乘。

~~其实和斯特林数基本没关系~~

看到 $x^k$ ，我们可以首先想到降幂，即

x^k=\sum_{i=0}^k\left\{\dfrac{k}{i}\right\}\binom x ii!

这个式子其实挺好理解的， $x^k$ 是有 $k$ 个标号球放在 $x$ 个有标号盒子里面。

枚举选出了哪几个盒子，再把 $k$ 个球放进去的方案数是斯特林数。

最后的 $i!$ 是因为盒子是有标号的，但是斯特林数是没有标号的……

那么这个题就是

f(x)^k=\sum_{i=0}^k\left\{\dfrac{k}{i}\right\}i!\binom{f(x)}{i}

发现前面的部分可以直接做，只有后面的 $\binom {f(x)}i$ 是不知道的。

我们再考虑一波组合意义： $\binom {f(x)}i$ 表示从 $f(x)$ 这个边集中选出 $i$ 条边的方案数，其中 $x$ 是点集。

这启发我们进行树形dp。

但我们又发现边集也是不确定的，那么我们可以dp虚树的形态，在虚树的根统计答案。

这样，我们有 $f[u][i]$ 表示在以 $u$ 为根的所有虚树中，选出了 $i$ 条边的方案数。

注意：我们只是考虑选了 $i$ 条边，并不用考虑选法是否联通，这是由上面的式子所决定的。

我们可以在两棵子树合并的时候统计答案。

题解里面没有说为什么只有在合并时才能统计答案，这里说一下我的见解。

还是回顾一下我们的目的：统计在一个点集中最小连边形成的边集中选出 $i$ 条的方案数。

我们的 $f[u][i]$ 就是 $u$ 和 $u$ 的子树所有点集的答案，而这个贡献我们已经在合并之前统计完了。

也就是说，只有当点集改变时，我们才可能加入新的答案，这便是子树的合并。

在合并结束后，我们把合并的这两棵子树看成一棵子树，再更新它们的 $f$ 。这是经典 trick了。

注意：合并后的 $f[u][i]$ 和之前的已经不一样了，因为点集扩大了，所以我们要更新 $f$ ，保证后面转移所用的 $f$ 是正确的。

合并的过程类似树形背包搞一搞就好了。

这里的复杂度是 $O(nk)$ 的，证明可以参考i207M学长的博客，讲得非常好，我这里就不赘述了。