斯特林数

Published: July 21, 2020 by Daltao

• Categories:
• algorithm 101

• 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)$的方法：

$$\begin{aligned} &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)!}]\\ \end{aligned}$$

可以看出后面项是等差卷积，可以用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个非空子集的方法数。

根据定义可以发现下面公式的成立：

$$\sum_{m=0}^n{n\choose m}\begin{Bmatrix} m\\ k \end{Bmatrix}=(k+1)\begin{Bmatrix} n\\ k+1 \end{Bmatrix}+\begin{Bmatrix} n\\ k \end{Bmatrix}$$

生成函数

对于某个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]$$