斯特林反演

引入

关于斯特林数的定义可以上百度搜…这部分很简单就没写了。

本文中，$s_1(n,k)$表示第一类斯特林数，$s_2(n,k)$表示第二类。

这里不加说明的给出递推式：

$$\begin{align}s_1(n,k)&=(n-1)\cdot s_1(n-1,k)+s_1(n-1,k-1)\\ s_2(n,k)&=k\cdot s_2(n-1,k)+s_2(n-1,k-1)\end{align}$$

卷积求第二类斯特林数

首先有一个组合意义很明显的式子：

$$n^k=\sum_{i=0}^{k}s_2(k,i)\binom{n}{i}i!$$

就是说$k$个位置填$n$种颜色，我们可以分成若干组，每组颜色不同。

我们可以把后面的值为$0$的项补全：

$$n^k=\sum_{i=0}^{n}s_2(k,i)\binom{n}{i}i!$$

对其进行二项式反演：

$$s_2(k,n)n!=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}i^k$$

这个可以写成卷积形式，顺便把变量换下：

$$s_2(n,k)=\sum_{i=0}^k\frac{(-1)^{k-i}}{(k-i)!}\cdot \frac{i^n}{i!}$$

阶乘幂

阶乘幂的定义是这样的：

上升幂：$x^{\overline n}=\prod_{i=1}^{n}(x+i-1)$。

下降幂：$x^{\underline n}=\prod_{i=1}^{n}(x-i+1)$。

显然可以根据组合数的定义得到：

$$x^{\underline n}=\binom{x}{n}n!$$

还有两个这样的式子：

$$x^{\overline n}=(-1)^n(-x)^{\underline n}\\ x^{\underline n}=(-1)^n(-x)^{\overline n}$$

把右边拆开就能证明了。

阶乘幂与斯特林数的转化

所以上面卷积的第一个式子可以写成这样：

$$n^k=\sum_{i=0}^{k}s_2(k,i)\binom{n}{i}i!=\sum_{i=0}^{k}s_2(k,i)n^{\underline i}$$

还有一个第一类斯特林数和上升幂的关系：

$$x^{\overline n}=\sum_{i=0}^{n}s_1(n,i)x^i$$

可以通过数学归纳来证明：

$$\begin{align} x^{\overline {n}}&=(x+n-1)\sum_{i=0}^{n-1}s_1(n-1,i)x^i\\ &=\sum_{i=0}^{n-1}s_1(n-1,i)x^{i+1}+\sum_{i=0}^{n-1}(n-1)\cdot s_1(n-1,i)x^i\\ &=\sum_{i=1}^{n}s_1(n-1,i-1)x^{i}+\sum_{i=1}^{n-1}(n-1)\cdot s_1(n-1,i)x^i\\ &=\sum_{i=1}^{n}\big(s_1(n-1,i-1)+(n-1)s_1(n-1,i)\big)x^{i}\\ &=\sum_{i=0}^{n}s_1(n,i)x^i \end{align}$$

注意由于$s_1(n,0)=s_1(n,n+1)=0$，所以中间边界条件其实不需要在意。

我们把这个式子变一下可以得到一个第一类斯特林数和下降幂的关系：

$$x^{\overline n}=\sum_{i=0}^{n}s_1(n,i)x^i$$ $$(-1)^n(-x)^{\overline n}=(-1)^n\sum_{i=0}^{n}s_1(n,i)x^i(-1)^i$$ $$x^{\underline n}=\sum_{i=0}^{n}(-1)^{n-i}s_1(n,i)x^i$$

最上面那个普通幂转第二类斯特林数和上升幂的式子也可以类似的变一下：

$$x^n=\sum_{i=0}^{n}s_2(n,i)x^{\underline i}$$ $$\begin{align}(-1)^n(-x)^n&=(-1)^n\sum_{i=0}^{n}s_2(n,i)(-x)^{\underline i}\\ (-1)^n(-x)^n&=(-1)^n\sum_{i=0}^{n}s_2(n,i)x^{\overline i}(-1)^i\\ x^n&=\sum_{i=0}^{n}(-1)^{n-i}s_2(n,i)x^{\overline i} \end{align}$$

总结一下一共四个转化的式子：

$$\begin{align} x^n&=\sum_{i=0}^{n}s_2(n,i)x^{\underline i}\\ x^n&=\sum_{i=0}^{n}(-1)^{n-i}s_2(n,i)x^{\overline i}\\ x^{\underline n}&=\sum_{i=0}^{n}(-1)^{n-i}s_1(n,i)x^i\\ x^{\overline n}&=\sum_{i=0}^{n}s_1(n,i)x^i \end{align}$$

反转公式

首先搬出下降幂的公式：

$$x^n=\sum_{i=0}^{n}s_2(n,i)x^{\underline i}$$

套上面的公式变成上升幂：

$$x^n=\sum_{i=0}^{n}s_2(n,i)(-1)^i(-x)^{\overline i}$$

套上升幂转第一类斯特林数的公式：

$$x^n=\sum_{i=0}^{n}s_2(n,i)(-1)^i\sum_{j=0}^{i}s_1(i,j)(-x)^j$$

把$x$的幂提前，换一下求和符号：

$$x^n=\sum_{j=0}^{n}x^j\sum_{i=j}^ns_2(n,i)s_1(i,j)(-1)^{i-j}$$

由于这里我们把$x$看成未知量，其他的都是已知量，所以我们可以把左右当作多项式，那么对比系数可得：

$$\sum_{i=m}^{n}s_2(n,i)s_1(i,m)(-1)^{i-m}=[m=n]$$

这个叫做反转公式。

同理我们可以类似的得出第二个反转公式：

$$\sum_{i=m}^{n}s_1(n,i)s_2(i,m)(-1)^{i-m}=[m=n]$$

注意：反转公式$-1$的指数也可以写成$n-i$，稍加分析可以发现$m=n$时成立，$m\ne n$时有两种情况，一种不变，另一种会将答案取相反数，但是由于结果为$0$所以不影响。

斯特林反演

这里先给出反演的式子在加以证明：

$$f(n)=\sum_{i=0}^{n}s_2(n,i)g(i)\Longleftrightarrow g(n)=\sum_{i=0}^{n}(-1)^{n-i}s_1(n,i)f(i)$$

考虑一般反演的套路，先写出一个$[i=n]$的形式：

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

在把和斯特林数以及$[m=n]$的式子套进去，也就是上面的反转公式（注意$-1$的指数）：

$$\begin{align} g(n)&=\sum_{i=0}^{n}g(i)\sum_{j=i}^{n}(-1)^{n-j}s_1(n,j)s_2(j,i)\\ &=\sum_{j=0}^{n}(-1)^{n-j}s_1(n,j)\sum_{i=0}^{j}s_2(j,i)g(i)\\ &=\sum_{i=0}^{n}(-1)^{n-i}s_1(n,i)f(i) \end{align}$$

证毕。

当然由于反转公式的对称性，所以互换$s_1,s_2$依然成立。