基础定义

斯特林树分成两类，

• 第一类：将 $n$ 个元素划分成 $m$ 个圆排列的方案数量。计做 $\left[\begin{array}{l}
  n \\
  m
  \end{array}\right]$

  $$\left[\begin{array}{l} n \\ m \end{array}\right]=\left[\begin{array}{l} n-1 \\ m-1 \end{array}\right]+(n-1)\left[\begin{array}{c} n-1 \\ m \end{array}\right]$$

  递推式是由于，考虑我们加入第 $n$ 个元素的时候，可以新开一个圆排列，也可以加入到之前任何一个数的后面的位置。

• 第二类：将 $n$ 个元素划分成为 $m$ 个集合的方案数量。计做 $\left\{\begin{array}{l}n \\m\end{array}\right\}$

  $$\left\{\begin{array}{l} n \\ m \end{array}\right\}=\left\{\begin{array}{l} n-1 \\ m-1 \end{array}\right\}+m\left\{\begin{array}{c} n-1 \\ m \end{array}\right\}$$

  递推式是由于，考虑我们加入第 $n$ 个元素的时候，可以新开一个集合，也可以加入到之前任何一个集合。

  同时它可以写成展开式：

  $$\left\{\begin{array}{l}n \\m\end{array}\right\}=\frac{1}{m !} \sum_{k=0}^{m}(-1)^{k}\left(\begin{array}{l}m \\k\end{array}\right)(m-k)^{n}$$

  我们考虑一个容斥，由于最终目标是让 $n$ 个集合划分成 $m$ 个集合，显然不能有空的。我们可以枚举一下假设有 $k$ 个集合是空的，那么方案数量就是 $(m-k)^n$ ，我们想要选择集合的方案数量是 $m \choose k$ ，容斥系数是 $(-1)^k$ ，当然，这个是具有顺序的，实际上是没有顺序的方案个数，所以还需要去个顺序。

引理 & 推论

首先是正常幂转下降幂，用到的是第二类斯特林数：

$$n^{m}=\sum_{i=0}^{m}\left\{\begin{array}{l}m \\ i\end{array}\right\} n^{\underline i}$$

考虑 $n^m$ 的组合意义，就是选择 $m$ 轮，每轮选择一个 $1\sim n$ 的数，可以选择相同的数。我们考虑枚举不同数的个数，然后把 $m$ 个位置分配给不同数，接着再确定这些集合的标号（因为斯特林数集合是无标号的）。

然后是上升幂转正常幂

$$n^{\overline{m}}=\sum_{i=0}^{m}\left[\begin{array}{l}m \\i\end{array}\right] n^{i}$$

我也证不来。可以用数学归纳法证明。

扒过来 lsj 爷爷的证明

$$\begin{aligned}n^{\overline{m}} &=(n+m-1) n^{\overline{m-1}} \\&=(n+m-1) \sum_{i=0}^{m-1}\left[\begin{array}{c}m-1 \\i\end{array}\right] n^{i} \\&=\sum_{i=0}^{m-1}\left[\begin{array}{c}m-1 \\i\end{array}\right] n^{i+1}+\sum_{i=0}^{m-1}\left[\begin{array}{c}m-1 \\i\end{array}\right] n^{i}(m-1) \\&=\sum_{i=1}^{m}\left[\begin{array}{c}m-1 \\i-1\end{array}\right] n^{i}+\sum_{i=0}^{m-1}\left[\begin{array}{c}m-1 \\i\end{array}\right] n^{i}(m-1) \\&=\sum_{i=0}^{m}\left(\left[\begin{array}{c}m-1 \\i-1\end{array}\right]+(m-1)\left[\begin{array}{c}m-1 \\i\end{array}\right]\right) n^{i} \\&=\sum_{i=0}^{m}\left[\begin{array}{c}m \\i\end{array}\right] n^{i}\end{aligned}$$

然后是重要的俩反转公式

$$[n=m]=\sum_{k=m}^{n}(-1)^{n-k}\left[\begin{array}{l}n \\k\end{array}\right]\left\{\begin{array}{l}k \\m\end{array}\right\}$$ $$[n=m]=\sum_{k=m}^{n}(-1)^{n-k}\left\{\begin{array}{l}n \\k\end{array}\right\}\left[\begin{array}{l}k \\m\end{array}\right]$$

证明就用前面两个东西推一下大概就好了。。

斯特林反演

终于进入正题辣！

$$\begin{aligned}f(n) &=\sum_{k=0}^{n}\left\{\begin{array}{l}n \\k\end{array}\right\} g(k) \Leftrightarrow g(n)=\sum_{k=0}^{n}(-1)^{n-k}\left[\begin{array}{l}n \\k\end{array}\right] f(k) \\f(n)&=\sum_{k=0}^{n}\left[\begin{array}{l}n \\k\end{array}\right] g(k) \Leftrightarrow g(n)=\sum_{k=0}^{n}(-1)^{n-k}\left\{\begin{array}{l}n \\k\end{array}\right\} f(k) \\f(n)&=\sum_{k \geq n}\left\{\begin{array}{l}k \\n\end{array}\right\} g(k) \Leftrightarrow g(n)=\sum_{k \geq n}(-1)^{k-n}\left[\begin{array}{l}k \\n\end{array}\right] f(k)\\f(n)&=\sum_{k \geq n}\left[\begin{array}{l}k \\n\end{array}\right] g(k) \Leftrightarrow g(n)=\sum_{k \geq n}(-1)^{k-n}\left\{\begin{array}{l}k \\n\end{array}\right\} f(k)\end{aligned}$$

这看着很吓人的式子其实很好推的啦。。

随便挑一个来证，比如挑第二个，把 $g$ 写成

$$g(n) = \sum_{k=0}^n[n=k]g(k)$$

然后直接带入反转公式

$$\begin{aligned}g(n) &= \sum_{k=0}^n\left(\sum_{i=k}^n(-1)^{n-i} \left\{\begin{array}{l} n \\ i \end{array}\right\} \left[\begin{array}{l} i \\ m \end{array}\right] \right)g(k)\\g(n) &= \sum_{i=0}^n(-1)^{n-i} \left\{\begin{array}{l} n \\ i \end{array}\right\} \sum_{k=0}^i \left[\begin{array}{l} i \\ k \end{array}\right] g(k)\\g(n) &= \sum_{i=0}^n (-1)^{n-i} \left\{\begin{array}{l} n \\ i \end{array}\right\} f(i)\end{aligned}$$

其他三个变化的无非就是，选择哪一个反转公式，反转公式是 $[n=k]$ 还是 $[k=n]$ 的问题。。。

例题

其实是一个再放送

CF1278F Cards

我也不知道公式挂没有，还是建议在 luogu 博客或者下面的链接里面查看。

一道斯特林数的模版练手题。不会可以看 这里 。

我们考虑枚举出现了多少次王牌，出现 $i$ 次王牌的概率，可以从 $n$ 轮操作选择 $i$ 轮抽出王牌，写成式子：

$$\begin{aligned}& \sum_{i\ge 0} i^k{n\choose i}\frac 1 m^{i} \frac{m-1}{m}^{n-i}\\&= \frac{1}{m^n} \sum_{i= 0}^n i^k {n\choose i} (m-1)^{n-i}\\&= \frac 1 {m^n} \sum_{i=0}^n {n\choose i} (m-1)^{n-i} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} i^{\underline j}\\&= \frac 1 {m^n} \sum_{i=0}^n {n\choose i} (m-1)^{n-i} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} {i\choose j}j!\\&= \frac 1 {m^n} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} j! \sum_{i=0}^n {n\choose i} {i\choose j} (m-1)^{n-i}\\&= \frac 1 {m^n} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} j! {n\choose j}\sum_{i=0}^n {n-j\choose i-j} (m-1)^{n-i}\\\end{aligned}$$

最后一步用到了以前写过的那个组合恒等式，就是从 $n$ 个选 $i$ 个再选 $j$ 个，本质上等价于 $n$ 个先选择好 $j$ 个，再从剩下的 $n-j$ 个选择第一步应当选择的 $i-j$ 个。

然后可以看出最后面其实是个二项式定理！

$$= \frac 1 {m^n} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} j! {n\choose j}m^{n-j}\\$$

然后可以很简便地写 $O(k^2)$ 了，也可以预处理第二类斯特林数的行 $O(k\log k)$ 做。可以去看 这里 的题解。