斯特林数

Published: by Creative Commons Licence

  • Tags:

第一类斯特林数

第一类斯特林数 定义为下面公式的系数:

定义无符号斯特林数为:

可以利用下面公式通过无符号斯特林数计算有符号斯特林数:

无符号斯特林数满足:

无符号斯特林数的递推关系为:

有符号斯特林数的递推公式为:

无符号斯特林数的组合意义是:将$n$个元素分成$k$个环(都不空)的方案数为

生成函数

对于给定的n,设$F^{(n)}$为第一类斯特林数的生成函数,即 。由于无符号斯特林数满足:

因此可以直接得到:

乘积符号内是n个多项式,我们可以用分治+FFT在$O(n(\log_2n)^2)$时间复杂度内计算得到。下面介绍用倍增+FFT在$O(n\log_2n)$的算法。

容易发现下面公式成立:

我们可以用倍增算法来解决。下面给出计算$F^{(n)}(x+n)$的方法:

可以看出后面项是等差卷积,可以用FFT直接得到。

总的时间复杂度为

第二类斯特林数

第二类斯特林数 的定义为下面公式的系数:

第二类斯特林数的递推公式为:

第二类斯特林数的直接计算公式为:

第二类斯特林数 的可以用来表示将n个元素拆分成k个非空子集的方法数。

生成函数

对于某个n,以及所有$0\leq k \leq n$计算 ,可以利用快速卷积在 的时间复杂度内实现。

观察下面第二类斯特林数的直接计算公式:

记第二类斯特林数的生成函数为$F$, 那么我们可以推出$F$是另外两个多项式的卷积:

因此利用快速卷积算法就可以得到第二类斯特林数的生成函数。

斯特林反演

反演内容:

以及反转公式: