第二类斯特林数

第二类斯特林数

$S(n,m): n$个点分成$m$个相同集合

带入定义，递推式为$S(n,m)=S(n-1,m-1)+m\cdot S(n-1,m)$

转化$x^n$

$x^n$的组合意义是把$n$个点随意放到$x$个不同位置里，枚举那些位置放了点，则

$$x^n=\sum_0^x C(x,i)i!S(n,i)$$

有一些涉及到$x^n\rightarrow (x+1)^n$可以展开之后带入递推式快速转移

容斥/二项式反演得到

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

即$S(n,m)$的通项公式

下降幂多项式卷积

$x^{\underline n}=\frac{x!} {(x-n)!}$

下降幂多项式$F(x)$的$EGF$是

$EGF(F(x))=\sum_{i=0}^{\infty}\frac{x^i} {i!}\sum_{j=0}^{n} \frac{i!} {(i-j)!}\cdot F_j$

$EGF(F(x))=\sum_{i=0}^{\infty}x^i \sum_{j=0}^{n} \frac{1} {(i-j)!}\cdot F_j$

换一下顺序

$EGF(F(x))=\sum_{i=0}^{n} F_i \sum_{j=i}^{\infty}\frac{1} {(j-i)!} x^j$

$EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^i \sum_{j=0}^{\infty}\frac{1} {j!} x^j$

$EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^i e^x$

那么直接卷积就可以得到$F(x)$的$EGF$，然后点值对应相乘

卷回来的时候

$EGF(F(x))=\sum_{i=0}^{n} F_i \cdot x^ie^x$

$F_i=\frac{EGF(F(x))} {x^ie^x}$

那么就直接卷上$e^{-x}$就可以了

普通多项式转下降幂多项式

带入$x^n$的第二类斯特林数展开式，$x^n=\sum C(x,i)i!S(n,i)=\sum x^{\underline i}S(n,i)$

$G(x)=\sum [x^i]F(x)\sum x^{\underline j}S(i,j)$

$G(x)=\sum [x^i]F(x)\sum x^{\underline j}\sum \frac{(-1)^{j-k} C(j,k) k^i} {j!}$

$G(x)=\sum [x^i]F(x)\sum x^{\underline j}\sum \frac{(-1)^{j-k} k^i} {k!(j-k)!}$

是一个三元的卷积优化，比较复杂

$i\rightarrow j,[x^{\underline j}]G(x)=\frac{(-1)^{j-k}[x^i]F(x) k^i} {(j-k)!k!}$

考虑分步优化

Part1 $i\rightarrow k$

先计算出$H(k)=\sum [x^i]F(x) k^i$

发现$[x^i]H(x)=F(i)$，多项式多点求值得到

Part2 $k\rightarrow j$

对于已经得到的$H(x)$

$[x^{\underline j}]G(x)=\sum \frac{(-1)^{j-k}[x^k]H(x)} {k!(j-k)!}$

可以直接卷积得到

下降幂多项式转普通多项式

求出$F(x)$的$EGF$，然后带入前$n$项的值，快速插值回来即可