「OI」斯特林数 Stirling

斯特林数是 \(n^p\) 与 \(n^{ \underline{0}, \underline{1}, \cdots, \underline{ p } }\)(\( n \) 的下降幂)之间联系的纽带。

未完待续。

为了更符合人类认知过程,我决定先介绍第二类斯特林数。

第二类斯特林数

定义

我们从 「OI」差分表 Difference Table 开始。

我们不妨对 \( \{ a _ n \} , a _ n = n^p, n \in \mathbb{N} \) 进行差分,不难得到差分表。

我们暂时不考虑差分表上的具体数据,那么我们有
\[ n^p = c _ 0 \binom {n} {0} + c _ 1 \binom {n} {1} + \cdots + c _ n \binom {n} {p} \]

展开组合数
\[ n^p = \frac {c _ 0 n^{ \underline {0} } } { 0! } + \frac { c _ 1 n^{ \underline {1} } } {1!} + \cdots + \frac{ c _ p n^{ \underline {p} } } {p!} \]

不难发现 \( \dfrac {c _ i} {i!} \) 具有特殊意义,我们不妨给他一个更加简洁的表达方式 \( \begin{Bmatrix} p \\i \end{Bmatrix}\)。

也就是说,第二类斯特林数 \( \begin{Bmatrix} p \\ i \end{Bmatrix} \) 是满足
\[ n ^ p = \sum^p _ { i = 0 } \begin{Bmatrix} p \\ i \end{Bmatrix} n^{ \underline{i} } \]
的一类数。

数值

考虑之前我们事实上是用差分表来定义第二类斯特林数的,那么我们应该用差分表来求值。

考虑定义式
\[ n ^ p = \sum ^ p _ { i = 0 } \begin {Bmatrix} p \\ i \end{Bmatrix} n ^ { \underline {i} } \]

如果把 \( p = 0 \) 代入,我们有
\[ n ^ 0 = \begin {Bmatrix} 0 \\ 0 \end {Bmatrix} \]

因为 \( n \in \mathbb {N} \),所以 \( n ^ 0 = 1 \)(此处定义 \( 0 ^ 0 = 1 \)),继而
\[ \begin {Bmatrix} 0 \\ 0 \end{Bmatrix} = 1 \]

此外,因为第二类斯特林数其实是差分表记法的转化,所以我们有
\[ \begin {Bmatrix} p \\ 0 \end {Bmatrix} = \frac {c _ 0} {0!} = c _ 0 \]

考虑到 \( p \geq 1\) 时 \( c _ 0 = 0 ^ p = 0 \),所以有
\[
\begin {Bmatrix} p \\ 0 \end {Bmatrix} =
\begin {cases}
1 , & p = 0 \\
0 , & p \geq 1
\end {cases}
\]

此外,我们不难得到 \( \begin {Bmatrix} p \\ p \end {Bmatrix} = 1 \),这个式子与上面的式子一样,都是我们递推的起点(边界条件)

递推式

第二类斯特林数满足递推公式
\[ \begin {Bmatrix} p \\ k \end {Bmatrix} = k \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} + \begin {Bmatrix} p – 1 \\ k – 1 \end{Bmatrix} \]

证明

根据定义,我们有
\[ n ^ p = \sum ^ p _ { k = 0 } \begin {Bmatrix} p \\ k \end {Bmatrix} n ^ { \underline {k} } \]
\[ n ^ { p – 1 } = \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } \]

那么我们有
\[
\begin {aligned}
n ^ p & = n \times n ^ { p – 1 } \\
& = n \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } \\
& = \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } n \\
& = \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } ( n – k + k ) \\
& = \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } ( n – k ) + \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } k \\
& = \sum ^ { p – 1 } _ { k = 0 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline { k + 1 } } + \sum ^ { p – 1 } _ { k = 1 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } k \\
& = \sum ^p _ { k = 1 } \begin {Bmatrix} p – 1 \\ k – 1 \end {Bmatrix} n ^ { \underline {k} } + \sum ^ { p – 1 } _ { k = 1} \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } k \\
& = \begin {Bmatrix} p – 1 \\ p – 1 \end {Bmatrix} n ^ { \underline {p} } + \sum ^ { p – 1 } _ { k = 1 } \begin {Bmatrix} p – 1 \\ k – 1 \end {Bmatrix} n ^ { \underline {k} } + \sum ^ { p – 1 } _ { k = 1 } \begin {Bmatrix} p – 1 \\ k \end {Bmatrix} n ^ { \underline {k} } k \\
& = n ^ { \underline {p} } + \sum ^ { p – 1 } _ { k = 1 } \left ( \begin {Bmatrix}p – 1 \\ k – 1 \end {Bmatrix} n ^ { \underline{k}}+\begin{Bmatrix}p-1\\k\end{Bmatrix}n^{\underline{k}}k\right)\\
&=n^{\underline{p}}+\sum^{p-1} _ {k=1}n^{\underline{k}}\left(\begin{Bmatrix}p-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}p-1\\k\end{Bmatrix}\right)\\
\end{aligned}
\]

将最后的式子与
\[
\begin{aligned}
n^p&=\sum^p _ {k=0}\begin{Bmatrix}p\\k\end{Bmatrix}n^{\underline{k}}\\
&=n^{\underline{p}}+\sum^{p-1} _ {k=0}\begin{Bmatrix}p\\k\end{Bmatrix}n^{\underline{k}}\\
&=n^{\underline{p}}+\sum^{p-1} _ {k=1}\begin{Bmatrix}p\\k\end{Bmatrix}n^{\underline{k}}
\end{aligned}
\]
比较可得
\[\begin{Bmatrix}p\\k\end{Bmatrix}=k\begin{Bmatrix}p-1\\k\end{Bmatrix}+\begin{Bmatrix}p-1\\k-1\end{Bmatrix}\]

组合意义

第二类斯特林数 \(\begin{Bmatrix}p\\k\end{Bmatrix}\) 的组合意义是将 \(p\) 元素集合划分到 \(k\) 个集合且没有空集的方案数

不难发现划分的边界条件与之前相同,即
\[
\begin{cases}
\begin{Bmatrix}p\\p\end{Bmatrix}=1,&p\geq 0\\
\begin{Bmatrix}p\\0\end{Bmatrix}=[p=0]
\end{cases}
\]

所以重点是理解递推公式
\[\begin{Bmatrix}p\\k\end{Bmatrix}=k\begin{Bmatrix}p-1\\k\end{Bmatrix}+\begin{Bmatrix}p-1\\k-1\end{Bmatrix}\]

其实就是分类讨论:

  • 单独划分,对应 \(\begin{Bmatrix}p-1\\k-1\end{Bmatrix}\);
  • 与前面形成的 \(k\) 个集合分在一起,对应 \(k\begin{Bmatrix}p-1\\k\end{Bmatrix}\)。

这就是它的组合意义。

其他求法

求一行

考虑容斥原理。枚举空着的盒子数量,那么
\[
\begin{aligned}
\begin{Bmatrix}n\\m\end{Bmatrix}&=\frac{1}{m!}\sum^m _ {i=0}(-1)^i\binom{m}{i}(m-i)^n\\
&=\frac{1}{m!}\sum^m _ {i=0}(-1)^i\frac{m!}{i!(m-i)!}(m-i)^n\\
&=\sum^m _ {i=0}\frac{(-1)^i}{i!(m-i)!}(m-i)^n\\
&=\sum^m _ {i=0}\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}\\
\end{aligned}
\]

不妨设 \(f(x)=\frac{(-1)^x}{x!}\),\(g(x)=\frac{x^n}{x!}\),用快速数论变换 \(\texttt{NTT}\) 即可以 \(n\log _ 2n\) 的时间复杂度求得 \(\begin{Bmatrix}n\\0,1,\cdots,n\end{Bmatrix}\)。

求一列

考虑生成函数
\[
\begin{aligned}
H _ k(x)&=\sum \begin{Bmatrix}i\\k\end{Bmatrix}x^i\\
&=\sum x^i\begin{Bmatrix}i\\k\end{Bmatrix}\\
&=\sum x^i\left(\begin{Bmatrix}i-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}i-1\\k\end{Bmatrix}\right)\\
&=\sum x^i\begin{Bmatrix}i-1\\k-1\end{Bmatrix}+k\sum x^i\begin{Bmatrix}i-1\\k\end{Bmatrix}\\
&=x\sum x^{i-1}\begin{Bmatrix}i-1\\k-1\end{Bmatrix}+k\sum x^i\begin{Bmatrix}i-1\\k\end{Bmatrix}\\
&=xH _ {k-1}(x)+kxH _ k(x)
\end{aligned}
\]

所以我们可以得出
\[H _ k(x)=\frac{x}{1-kx}H _ {k-1}(x)\]

继而
\[H _ k(x)=H _ 0(x)\prod^k _ {i=1}\frac{x}{1-ix}\]

其中 \(H _ 0(x)=\begin{Bmatrix}0\\0\end{Bmatrix}+\begin{Bmatrix}1\\0\end{Bmatrix}x+\cdots=1\)。

所以
\[H _ k(x)=x^k\prod^k _ {i=1}\frac{1}{1-ix}\]

我们可以通过上面的式子用 分治 \(\texttt{NTT}\) 求出一列的第二类斯特林数。

更多性质

  • \[\begin{Bmatrix}p\\1\end{Bmatrix}=1,p\geq 1\]
    考虑组合意义(只选择 \(1\) 个集合)即可证明。
  • \[\begin{Bmatrix}p\\2\end{Bmatrix}=2^{p-1}-1,p\geq 2\]
    选择两个集合,那么每个数只有两种选择,方案数为 \(2^p\),又因为集合不能为空,所以答案要减去 \(2^{p-1}+1\),最后得到 \(2^{p-1}-1\)。
  • \[\begin{Bmatrix}p\\p-1\end{Bmatrix}=\binom{p}{2},p\geq 1\]
    考虑组合意义即可。

应用

第一类斯特林数

定义

我们尝试用 \(n^0,n^1,\cdots,n^p\) 表示出 \(n^{\underline{p}}\)。

我们先展开 \(n^{\underline{0}},n^{\underline{1}},n^{\underline{p}}\)。
\[
\begin{cases}
n^{\underline{0}}&=1\\
n^{\underline{1}}&=n\\
n^{\underline{2}}&=n(n-1)=n^2-n\\
n^{\underline{3}}&=n(n-1)(n-2)=n^3-3n^2+2n\\
\vdots\\
n^{\underline{p}}&=\prod^{p-1} _ {i=0}(n-i)。
\end{cases}
\]

不难看出,\(n^{\underline{p}}\) 的展开式为一个多项式,其中多项式的系数正负相间。我们不妨写成一个式子
\[n^{\underline{p}}=c _ pn^p-c _ {p-1}n^{p-1}+\cdots+(-1)^{p-1}c _ 1n^1+(-1)^pc _ 0n^0\]

不难发现 \(c _ i\) 具有特殊意义,我们给它一个更简洁的表达方式 \(\begin{bmatrix}p\\i\end{bmatrix}\)。

也就是说,第一类斯特林数 \(\begin{bmatrix}p\\i\end{bmatrix}\) 是满足
\[n^{\underline{p}}=\sum^p _ {i=0}(-1)^{p-i}\begin{bmatrix}p\\i\end{bmatrix}n^i\]
的一类数。

数值

考虑到我们之前事实上是用下降幂的展开式来定义第一类斯特林数的,那么我们应该用下降幂来求值。

考虑定义式
\[n^{\underline{p}}=\sum^p _ {i=0}(-1)^{p-i}\begin{bmatrix}p\\i\end{bmatrix}n^i\]

如果把 \(p=0\) 代入,我们有
\[n^{\underline{0}}=\begin{bmatrix}0\\0\end{bmatrix}n^0\]

因为 \(n\in\mathbb{N}\),所以 \(n^0=1\)(此处定义 \(0^0=1\)),又 \(n^{\underline{0}}=1\),继而
\[\begin{bmatrix}0\\0\end{bmatrix}=1\]

此外,因为第一类斯特林数其实是下降幂记法的转化,而下降幂最高项系数为 \(1\),所以我们有
\[\begin{bmatrix}p\\p\end{bmatrix}=1\]

参考资料

  1. Stirling Number of the First Kind – Wolfram MathWorld
  2. Stirling Number of the Second Kind – Wolfram MathWorld