斯特林数什么的

定义

第一类strling数

$\begin{bmatrix} n \\ m \end{bmatrix}$表示把$n$个数划分成$m$个环排列的方案数

递推式1

$$\begin{bmatrix} n \\ m \end{bmatrix} = \begin{bmatrix} n - 1 \\ m - 1 \end{bmatrix} + \begin{bmatrix} n - 1 \\ m \end{bmatrix} \ast (n - 1)$$

枚举最后一个点的位置

递推式2

$$\begin{bmatrix} n \\ m \end{bmatrix} = \sum_{i = 1} ^ n\begin{bmatrix} n - i \\ m - 1 \end{bmatrix} \ast (i - 1)! \ast \binom{n - 1}{i - 1}$$

枚举最后一个环排列的大小

第二类斯特林数

$\begin{Bmatrix} n \\ m \end{Bmatrix}$表示把$n$个数划分成$m$个无序集合的方案数

递推式1

$$\begin{Bmatrix} n \\ m \end{Bmatrix} = \begin{Bmatrix} n - 1 \\ m - 1 \end{Bmatrix}+\begin{Bmatrix} n - 1\\ m \end{Bmatrix} \ast m$$

枚举最后一个点的位置

递推式2

$$\begin{Bmatrix} n \\ m \end{Bmatrix} = \sum_{i = 1}^n \begin{Bmatrix} n - i\\ m - 1 \end{Bmatrix}\ast \binom{n - 1}{i - 1}$$

枚举最后一个集合的大小

特殊表达形式

$$\begin{Bmatrix} n \\ m \end{Bmatrix}=\frac{1}{m!}\sum_{k = 0} ^ m (-1)^k \binom{m}{k}(m - k) ^n$$

性质

公式1（下降幂转次幂）

$$x^{\underline{n}} = \sum_{k = 0} ^ n (-1)^{n - k}\begin{bmatrix} n \\ k \end{bmatrix}x^k$$

证明如下：

比较简单，直接考虑怎么算出$x^k$项的系数就可以了，省略

公式2（次幂转下降幂）

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

也可以转换成组合数和阶乘的形式

$$x^n = \sum_{k = 0} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix} \binom{x}{k}k!$$

公式3

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

证明如下：

将公式2代入公式1

得到：

$$x^{\underline{n}} = \sum_{k = 0} ^ n (-1)^{n - k}\begin{bmatrix} n \\ k \end{bmatrix}\sum_{m = 0} ^ k \begin{Bmatrix} k \\ m \end{Bmatrix} x ^ \underline{m}$$

交换和号得：

$$x^{\underline{n}} = \sum_{m = 0} ^ n x^{\underline{m}}\sum_{k = m} ^ n (-1)^{n - k}\begin{bmatrix} n \\ k \end{bmatrix} \begin{Bmatrix} k \\ m \end{Bmatrix}$$

显然当$n = m$的时候$\sum_{k = m} ^ n (-1)^{n - k}\begin{bmatrix} n \\ k \end{bmatrix} \begin{Bmatrix} k \\ m \end{Bmatrix}$是1

所以有：

$$0 = \sum_{m = 0} ^ {n - 1} x^{\underline{m}}\sum_{k = m} ^ n (-1)^{n - k}\begin{bmatrix} n \\ k \end{bmatrix} \begin{Bmatrix} k \\ m \end{Bmatrix}$$

因为对于任意的x上面的式子都成立，所以可以得到当$n\not= m$的时候$\sum_{k = m} ^ n (-1)^{n - k}\begin{bmatrix} n \\ k \end{bmatrix} \begin{Bmatrix} k \\ m \end{Bmatrix}$是0

公式4

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

证明如下：

将公式1代入公式2

得到：

$$x^{n} = \sum_{k = 0} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix} \sum_{m = 0} ^ k (-1)^{k - m}\begin{bmatrix} k \\ m \end{bmatrix}x^m$$

交换和号得：

$$x^{n} = \sum_{m = 0} ^ n x^m\sum_{k = m} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix}\begin{bmatrix} k \\ m \end{bmatrix} (-1)^{k - m}$$

显然当$n = m​$的时候$\sum_{k = m} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix}\begin{bmatrix} k \\ m \end{bmatrix} (-1)^{k - m}​$是1

所以有：

$$0 = \sum_{m = 0} ^ {n - 1} x^m\sum_{k = m} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix}\begin{bmatrix} k \\ m \end{bmatrix} (-1)^{k - m}$$

因为对于任意的x上面的式子都成立，所以可以得到当$n\not= m​$的时候$\sum_{k = m} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix}\begin{bmatrix} k \\ m \end{bmatrix} (-1)^{k - m}​$是0

ps:

当然$(-1)^{k - m}$和$(-1)^{n - k}$没有任何区别

因为$n - m$是偶数的时候，没有影响

$n - m$是奇数的时候，相当于全体取负，不影响结论

公式5

$$\begin{bmatrix} n +1 \\ m + 1 \end{bmatrix} = \sum_{k = m} ^ n \begin{bmatrix} n \\ k \end{bmatrix}\binom{k}{m}$$

证明如下：

因为一个环排列对应着一个置换，然后一个置换又可以差分成很多的环排列，所以假设前$n$个数分成了$k$个环排列，并且这k个环排列中有$m$个不变，剩下的$k - m$个和新的环排列组合起来变成一个完整的环排列，也就是第$m+1$个环排列

公式6

$$\begin{Bmatrix} n +1 \\ m + 1 \end{Bmatrix} = \sum_{k = m} ^ n \binom{n}{k}\begin{Bmatrix} k \\ m \end{Bmatrix}$$

证明如下：

假设不和当前数在同一个集合里面的数是k个，所以这k个数会分成m个集合，然后再用组合数算一算和当前数在一个集合的数的方案数

公式7

$$\begin{bmatrix} n + 1\\ m + 1 \end{bmatrix} = \sum_{k = m} ^ n\begin{bmatrix} k\\ m \end{bmatrix}(\frac{n!}{k!}或n^{\underline{n - k}})$$

其实就是第一类斯特林数的递推式2的化简版本，组合意义一模一样

公式8

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

证明如下：

考虑第k+1个数是第一个被放进第m+1个集合中的数

所以前k个数会被放进m个集合中，并且还有$(m+1)^{n - k}$个数可以随便放

公式9（斯特林反演）

对于：

$$g(n) = \sum_{k = 0} ^ n(-1)^{n - k}\begin{bmatrix} n\\ k \end{bmatrix}f(k)$$

有：

$$f(n) = \sum_{k = 0} ^ n \begin{Bmatrix} n \\ k \end{Bmatrix} g(k)$$

反之亦然

证明可以直接带入然后用公式3和公式4进行理解

简单运用

第一类斯特林数求行方法

假设需要求第一类斯特林数第n行

首先有：

$$x^{\overline{n}} = \sum_{i = 0} ^ n \begin{bmatrix}n \\ i\end{bmatrix}x^i$$

就是下降幂换成上升幂，过程不变是是没有符号了，和公式1同理

那么也就是说$x^{\overline{n}}$是第n行斯特林数的生成函数

然后可以用$O(n\log^2 n)$的时间分治fft来算

也可以用$O(n\log n)$的倍增算法

$$f_{2n}(x) = x^{\overline{2n}} = f_n(x)f_n(x + n)$$

然后$f_n(x+n)$实际上就是把$f_n(x)$的各项$x^k$换成$(x+n)^k$

可以用二项式系数展开并且用$O(n\log n)$时间卷积求出

第二类斯特林数求行方法

实际上就是第二类斯特林数的特殊表达形式

发现没有其实这是一个卷积：

$$\begin{Bmatrix} n \\ m \end{Bmatrix}=\frac{1}{m!}\sum_{k = 0} ^ m (-1)^k \binom{m}{k}(m - k) ^n$$

然后可以直接卷积算出来了