斯特林数

之前好多次听说过,但是因为没有碰到过对应的题所以就咕咕咕了。现在才好好学了这个东西。

它的定义是将 $n$ 个不同的小球划分为 $m$ 个不相区分的圆排列的方案数。以下用 $S(n,m)$ 表示第一类斯特林数。

有递推式 $S(n,m)=S(n-1,m-1)+(n-1)*S(n-1,m)$
组合意义是考虑最后一个元素的划分情况,他可以自成一个圆排列,也可以插到之前的圆排列中。

如果给定 $n$ 要对于所有 $i$ 求 $S(n,i)$ 还有 $O(nlog^2n)$ 和 $O(nlogn)$ 的NTT求法,需要证明一些东西,先咕着

它的定义是将 $n$ 个不同的小球放入 $m$ 个相同的盒子,每个盒子不能为空的方案数。以下用 $S(n,m)$ 表示第二类斯特林数。

有递推式 $S(n,m)=S(n-1,m-1)+m*S(n-1,m)$

组合意义是考虑最后一个小球的放入情况,他可以单独放入一个盒子,也可以放入到之前的m个盒子之中。
看到这递推式这么像就能知道它们有一些妙不可言的关系2333

对于这个组合问题,我们还可以从容斥的角度计算,从而得到第二类斯特林数的另一个计算方法。
考虑先把盒子都编上号,最后除以 $m!$ ,这样简化问题。那么就只有盒子不能为空的条件了。这个可以直接容斥。

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

这个式子把组合数拆开之后可以化简成

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

这是一个卷积的形式,可以直接用NTT计算。复杂度 $O(nlogn)$

如果只用求一项 $S(n,m)$ 的话，直接用容斥的式子计算就可以了，不用写NTT。

关于斯特林数还有一些反演等更牛逼的东西,先咕着2333

下面用 ${n\brack k}$ 表示第一类斯特林数， ${n\brace k}$ 表示第二类斯特林数。

首先有这两个式子:

x^n=\sum_k{n\brace k}x^{\underline k}

x^{\overline n}=\sum_k{n\brack k}x^k

注意到

x*x^{\underline k}=x^{\underline{k+1}}+kx^{\underline k}

(x+n-1)x^k=x^{k+1}+(n-1)x^k

即可归纳证明。（这长得本来就很像它们的递推式。）

我们还可以注意到 $x^{\overline n}=(-1)^n(-x)^{\underline n}$ （对称也成立）
稍加推导即可得出

x^n=\sum_k{n\brace k}(-1)^{n-k}x^{\overline k}

x^{\underline n}=\sum_k{n\brack k}(-1)^{n-k}x^k

看起来很容易混淆？没关系，具体数学中的巧记法：
我们对于这些幂有一个很自然的排序:

x^{\overline n}>x^n>x^{\underline n}

于是当我们用“小的”幂去展开“大的”幂时不需添加负号，反之则添加负号。
接下来我们把这些公式互相代一代就会得出一个这样的式子：

x^n=\sum_{k,m}{n\brack k}{k\brace m}(-1)^{n-k}x^m

如果两边看成关于 $x$ 的多项式的话则左边只有 $n$ 次项系数为 $1$ ，右边也应同样。故以下恒等式成立。

\sum_k{n\brack k}{k\brace m}(-1)^{n-k}=[m=n]

其中 $-1$ 的指数也可写成 $k-m$ 。这个公式叫做翻转公式。我们有了一个判断的式子，接下来就可以开始喜闻乐见的反演了。
斯特林反演:

f(n)=\sum_k{n\brace k}g(k)\Leftrightarrow g(n)=\sum_k{n\brack k}(-1)^{n-k}f(k)

先正着推一下

g(n)=\sum_m[m=n]g(m)=\sum_{m,k}{n\brack k}{k\brace m}(-1)^{n-k}g(m)=\sum_k{n\brack k}(-1)^{n-k}f(k)

真的好推啊。。倒着推同理。注意这里 $-1$ 的指数是不能变的。

还要提一句的是翻转公式和斯特林反演中的第一类和第二类斯特林数都是可以互换的。然后就没了。

注意第二类斯特林数的生成函数

\sum_{n=0}^{\infty}{n\brace k}\frac{z^n}{n!}=\frac{(e^z-1)^k}{k!}

第一类斯特林数的生成函数

\sum_{n=0}^{\infty}{n\brack k}\frac{z^n}{n!}=\frac{(\ln\frac{1}{1-z})^k}{k!}

（然后第二类斯特林数的生成函数二项式定理展开一下就得到了容斥计算）
斯特林反演还可以用生成函数推。
当两个数列满足关系

b_n=\sum_{k=0}^n{n\brace k}a_k

时，我们称其为 Stirling 变换，其 EGF 对应的有

g(z)=f(e^z-1)

因此我们换元可以得到

f(z)=g(\ln(1+z))

故得到斯特林反演公式

a_n=\sum_{k=0}^n(-1)^{n-k}{n\brack k}b_k

Prutekoi's blog