首页 📚学习笔记

第二类斯特林数·行

我们定义 $\begin{Bmatrix} n\\m \end{Bmatrix}$ 表示把 $n$ 个不同元素划分成 $m$ 个相同的集合中(不能有空集)的方案数。

让我们用另一种形式表达这个东西

$$ \begin{align} x^n&=\sum_{i=0}^n \binom xi \begin{Bmatrix} n\\i \end{Bmatrix}i!\\ &=\sum_{i=0}^n\begin{Bmatrix} n\\i \end{Bmatrix}x^{\underline{i}} \end{align} $$

用组合意义解释一下就是:把 $n$ 物品放进 $m$ 个集合里,有 $m^n$ 种方法(允许不放)

那我们枚举哪些是非空集合,也就有$\dbinom mi$种选法,然后划分方案是$\begin{Bmatrix} n\\i \end{Bmatrix}$ ,最后再排列一下即可

那么怎么快速求第二类斯特林数呢。你看这个式子就像二项式反演,所以设:

$$ f(m)=m^n\quad\quad g(m)=\begin{Bmatrix} n\\m \end{Bmatrix}m! $$

代入原式

$$ \begin{align} m^n&=\sum_{i=0}^n \binom mi \begin{Bmatrix} n\\i \end{Bmatrix}i!\\ f(m)&=\sum_{i=0}^m \binom mi g(i)\\ g(m)&=\sum_{i=0}^m \binom mi (-1)^{m-i}f(i) \end{align} $$

再代换回来

$$ \begin{align} \begin{Bmatrix} n\\m \end{Bmatrix}m!&=\sum_{i=0}^n \binom mi (-1)^{m-i}i^n\\\\ \begin{Bmatrix} n\\m \end{Bmatrix}&=\sum_{i=0}^n\frac{\binom mi (-1)^{m-i}i^n}{m!}\\ \begin{Bmatrix} n\\m \end{Bmatrix}&=\sum_{i=0}^n\frac{i^n}{i!}\ \frac{(-1)^{m-i}}{(m-i)!}\\ \end{align}\\ $$

一看,这个东西就像卷积,卷一卷就好了,$NTT$乱搞

这个东西还可以转把普通多项式转成下降幂多项式

$$ \begin{align} \sum_{i=0}^na_ix^i&=\sum_{i=0}^na_i\sum_{j=0}^i\begin{Bmatrix} i\\j \end{Bmatrix}x^{\underline{j}}\\ &=\sum_{j=0}^nx^{\underline{j}}\sum_{i=j}^{n}\begin{Bmatrix} i\\j \end{Bmatrix}a_i\\ b_i&=\sum_{j=i}^{n}\begin{Bmatrix} j\\i \end{Bmatrix}a_j \end{align} $$




文章评论

目录