斯特林数

Published: by Creative Commons Licence

  • Tags:

第一类斯特林数

第一类斯特林数 \(s(n,k)\) 定义为下面公式的系数:

\[x^{\underline{n}}=\sum_{k=0}^n s(n,k) x^k\]

定义无符号斯特林数为:

\[c(n,k)= \left[ \begin{array}{c} n\\ k \end{array} \right] =|s(n,k)|\]

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

\[s(n,k)=(-1)^{n-k}c(n,k)\]

无符号斯特林数满足:

\[x^{\overline{n}}=\sum_{k=0}^n c(n,k) x^k\]

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

\[\left[ \begin{array}{c} n+1\\ k \end{array} \right] = n \left[ \begin{array}{c} n\\ k \end{array} \right] + \left[ \begin{array}{c} n\\ k-1 \end{array} \right]\]

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

\[s(n+1,k)=-ns(n,k)+s(n,k-1)\]

无符号斯特林数的组合意义是:将$n$个元素分成$k$个环(都不空)的方案数为 \(\left[ \begin{array}{c} n\\ k \end{array} \right]\)

生成函数

对于给定的n,设$F^{(n)}$为第一类斯特林数的生成函数,即 \(F^{(n)}_i= \left[ \begin{array}{c} n\\ i \end{array} \right]\) 。由于无符号斯特林数满足:

\[x^{\overline{n}}=\sum_{k=0}^n c(n,k) x^k\]

因此可以直接得到:

\[F^{(n)}(x)=x^{\overline{n}}=\prod_{i=0}^{n-1}(x+i)\]

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

容易发现下面公式成立:

\[F^{(n)}(x)= \left\{ \begin{array}{ll} F^{(\frac{n}{2})}(x)F^{(\frac{n}{2})}(x+\frac{n}{2})&, 2|n\\ (x+n-1)F^{n-1}(x)&,else \end{array} \right.\]

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

\[F^{(n)}(x+n)\\ =\sum_{i=0}^nF^{(n)}_i(x+n)^i\\ =\sum_{i=0}^nx^i\sum_{j=i}^nF^{(n)}_jn^{j-i}{j\choose i}\\ =\sum_{i=0}^nx^i\sum_{j=i}^nF^{(n)}_jn^{j-i}\frac{j!}{i!(j-i)!}\\ =\sum_{i=0}^n\frac{1}{i!}x^i\sum_{j=i}^n[F^{(n)}_jj!][\frac{n^{j-i}}{(j-i)!}]\\\]

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

总的时间复杂度为

\[T(n)=T(\frac{n}{2})+O(n\log_2n)=O(n\log_2n)\]

第二类斯特林数

第二类斯特林数 \(\begin{Bmatrix} n\\ k \end{Bmatrix}\) 的定义为下面公式的系数:

\[x^n = \sum_{k=0}^n \begin{Bmatrix} n\\ k \end{Bmatrix} x^{\underline{k}}\]

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

\[\begin{Bmatrix} n+1\\ k \end{Bmatrix} = k \begin{Bmatrix} n\\ k \end{Bmatrix} + \begin{Bmatrix} n\\ k-1 \end{Bmatrix}\]

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

\[\begin{Bmatrix} n\\ k \end{Bmatrix} = \frac{1}{k!}\sum_{i=0}^k(-1)^i{k\choose i}(k-i)^n\]

第二类斯特林数 \(\begin{Bmatrix} n\\ k \end{Bmatrix}\) 的可以用来表示将n个元素拆分成k个非空子集的方法数。

生成函数

对于某个n,以及所有$0\leq k \leq n$计算 \(\begin{Bmatrix} n\\ k \end{Bmatrix}\) ,可以利用快速卷积在 \(O(n\log_2n)\) 的时间复杂度内实现。

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

\[\begin{Bmatrix} n\\ k \end{Bmatrix} = \frac{1}{k!}\sum_{i=0}^k(-1)^i{k\choose i}(k-i)^n\\ =\sum_{i=0}^k(-1)^i(k-i)^n\frac{1}{i!(k-i)!}\\ =\sum_{i=0}^k[(-1)^i\frac{1}{i!}][(k-i)^n\frac{1}{(k-i)!}]\]

记第二类斯特林数的生成函数为$F$, \(F_k=\begin{Bmatrix}n\\k\end{Bmatrix}\) 那么我们可以推出$F$是另外两个多项式的卷积:

\[F(x)=[\sum_{i=0}^n(-1)^i\frac{1}{i!}] \times [\sum_{i=0}^ni^n\frac{1}{i!}]\]

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

斯特林反演

反演内容:

\[f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k\end{Bmatrix} g(k) \Leftrightarrow g(n)= \sum_{k=0}^n s(n,k)f(k) = \sum_{k=0}^n (-1)^{n-k} \left[ \begin{array}{c} n\\ k \end{array} \right] f(k)\]

以及反转公式:

\[\sum_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]\\ \sum_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]\]