第二类 Stirling 数学习小结

发表于 更新于

学习《组合数学》慕课课程的时候学到第二类 Stirling 数，慕课中讲得比较浅尝辄止；网上查了一圈，感觉没有对它的性质描述特别全面的资料。权当是写一份考试复习资料，写篇文章整理一下。

第二类 Stirling 数

定义

球盒模型

球盒模型可能是最简单朴素的定义方式之一，网上找到的也大多是这个定义。按此定义，第二类 Stirling 数 $S(n, m)$ 表示将 $n$ 个有区别的小球放入 $m$ 个无区别的盒子（不允许空盒）的方案数。

下降幂

另外一种比较具有组合意义的定义方式是利用下降幂（Falling Factorial）。$x$ 的 $n$ 次下降幂记作 $x^{\underline n}$ 或 $[x]_n$，定义为

$$x^{\underline n} \equiv [x]_n \equiv x(x-1)(x-2)\cdots(x-n+1)$$

边界值 $[x]_0 = 1$。

第二类 Stirling 数指出如何用一系列 $[x]_k$ 表出 $x^n$，即：

$$
\begin{aligned}
x^n &= S(n,0)[x]_0 + S(n,1)[x]_1 + \cdots + S(n,n)[x]_n \\
&= \sum _{k=0}^n S(n,k)[x]_k
\end{aligned}
$$

相对而言，使用下降幂的定义才是真正的第二类 Stirling 数的定义。从它的名字就可以看出，由于有第二类 Stirling 数，就必然有第一类 Stirling 数，而这两类 Stirling 数一正一反地揭示了下降幂和普通代数幂之间的关系。事实上，$\left\{x^0, x^1, x^2, \cdots, x^n\right\}$ 和 $\left\{[x]_0, [x]_1, [x]_2, \cdots, [x]_n\right\}$ 分别是至多 $n$ 次的多项式构成的 $n + 1$ 维线性空间的一组基，而 Stirling 数告诉我们如何用其中一组基表示另外一组基。第二类 Stirling 数 $S(n, m)$ 是用后一组基表示前一组，而第一类 Stirling 数 $s(n, m)$ 则反之：

$$[x]_n = \sum _{k=0}^n (-1)^{n-k}s(n,k)x^k$$

关于第一类 Stirling 数的讨论是题外话，我们不在此做过多展开。

递推式

一个非常重要的问题是，上述两种方式都定义了第二类 Stirling 数，然而它们是否等价？答案显然是等价，否则它们也不会都叫做第二类 Stirling 数。虽然很难优雅地将其中一个定义通过某些手段变换为另一个，但我们可以证明它们满足同样的递推关系，从而证明二者定义的是同一个东西。

为了方便起见，我们规定当 $m > n$ 时 $S(n, m) = 0$。上面提到的两个定义都可以方便地解释这个规定：球盒模型定义中，如果盒子比球还多，那么必然会出现空盒，也就没有合法方案；下降幂定义中，$[x]_m$ 是比 $x^n$ 更高次的多项式，因此它前面的系数必然是 0。

球盒模型

我们需要规定，如果没有小球也没有盒子，那么视为仅有一种放球方案（即，什么都不做）。这样一来，根据定义立即得到：

  • $S(n, 0) = 0 \quad (n > 0)$
  • $S(n, n) = 1 \quad (n \geq 0)$

现在计算 $S(n, m)$：将 $n$ 个有区别小球放入 $m$ 个无区别盒子中，然后拿走 1 号小球。如果这时

  • 出现了一个空盒：相当于把其余的小球放入 $m - 1$ 个盒子中，方案数为 $S(n - 1, m - 1)$；
  • 没有出现空盒：相当于把其余的小球放入 $m$ 个盒子中，再将 1 号小球放入任意一个盒子中，方案数为 $mS(n - 1, m)$。

于是可得：

$$S(n, m) = mS(n - 1, m) + S(n - 1, m - 1)$$

下降幂

考察定义式 $x^n = \sum_{k=0}^n S(n,k)[x]_k$：当 $n \geq 1$ 时，$[x]_n$ 的展开中不含常数项，又由于 $[x]_0 = 1$，因此 $[x]_0$ 项的系数必定为 0。此外，等式右边 $x^n$ 的系数是 $S(n, n)$，它应该等于 1。综上可得：

  • $S(n, 0) = 0 \quad (n > 0)$
  • $S(n, n) = 1 \quad (n \geq 0)$

注意到 $x^n = x \cdot x^{n-1}$，代入定义式：

$$
\begin{aligned}
x^n = x \cdot x^{n-1}
&= x \sum _{k=0}^{n-1} S(n-1,k)[x]_k \\
&= \sum _{k=0}^{n-1} xS(n-1,k)[x]_k \\
&= \sum _{k=0}^{n-1} (x-k+k)S(n-1,k)[x]_k \\
&= \sum _{k=0}^{n-1} S(n-1,k)(x-k)[x]_k + \sum _{k=0}^{n-1} kS(n-1,k)[x]_k \\
&= \sum _{k=0}^{n-1} S(n-1,k)[x] _{k+1} + \sum _{k=0}^{n-1} kS(n-1,k)[x]_k \\
&= \sum _{k=1}^{n} S(n-1,k-1)[x]_k + \sum _{k=1}^{n-1} kS(n-1,k)[x]_k \\
&= \sum _{k=1}^{n} \left(S(n-1,k-1)+kS(n-1,k)\right)[x]_k
\end{aligned}
$$

最后一步利用了 $S(n - 1, n) = 0$。对比上式和定义式，即得到 $S(n, k) = kS(n - 1, k) + S(n - 1, k - 1)$。

因此，上面两种定义得到的结果满足相同的递推关系、有相同的递推初值和边界值；从而，这两种定义是等价的。

一些边界值

除了上面得到的递推关系初值之外，我们还可以用球盒模型推导一些其他的边界值，用来方便一些情况下的计算：

  • $S(n, 2) = 2^{n-1} - 1$

这是将 $n$ 个有区别小球放入 2 个无区别盒子的方案数。除了 1 号小球之外的每个小球都可以选择和 1 号小球是否位于同一个盒子中，一共有 $2^{n-1}$ 种情况；但是要排除它们都跟 1 号小球在同一个盒子中的情况（这时另一个盒子是空盒），所以要再减去 1。

  • $S(n, n - 1) = \binom{n}{2}$
  • $S(n, n - 2) = \binom{n}{3} + 3\binom{n}{4}$
  • $S(n, n - 3) = \binom{n}{4} + 10\binom{n}{5} + 15\binom{n}{6}$

这些形如 $S(n, n - \delta)$ 的边界值可以通过讨论放球最多的盒子放了多少球得出。以 $S(n, n - 2)$ 为例，装了最多球的盒子里面可能有 3 个或 2 个球。如果是 3 个，那么相当于是 $n - 3$ 个盒子中各装一个球，剩下一个盒子装 3 个球，方案数就是 $\binom{n}{3}$；如果是 2 个，那么相当于 $n - 4$ 个盒子中各装一个球，剩下 2 个盒子各装 2 个球，方案数就是 $\frac{1}{2}\binom{4}{2}\binom{n}{4} = 3\binom{n}{4}$。

通过上面三个边界值可以找到规律 $S(n, n - k) = \sum_{j = 1}^{k} T(k, j)\binom{n}{j + k}$ ，其中 $T(k, j)$ 是由 $k$ 和 $j$ 决定的常系数。$T(k, j)$ 被称作 Ward Numbers，它构成的序列可以在 OEIS 上找到。对于不同的 $k$ 和 $j$，$T(k, j)$ 实际上构成了一个数字三角形，OEIS 上的这个序列是它展平后的结果。

组合等式

慕课上讲到的唯一一个等式是第二类 Stirling 数的通项公式，当然由于其中使用了求和符号所以并不是解析式。这个通项是：

$$S(n, m) = \frac{1}{m!}\sum_{k=0}^m \binom{m}{k}(-1)^k(m-k)^n$$

要求出这个式子有很多方法，我简单查找了一下就得到了二项式反演、容斥原理和生成函数三种方案。此处因为算是复习上课内容，所以就用生成函数来得到这个式子。

以球盒模型来考虑这个问题，为了方便，先讨论 $m$ 个有区别盒子时的情况 $S^\sharp(n, m)$。由于每两个盒子都是不相同的，因此显然有 $S^\sharp(n, m) = m!S(n, m)$。这时，我们就可以把问题转变为从 $m$ 类元素中取 $n$ 个做可重排列（每一类元素都至少选取 1 个）。新问题的解与原问题的解一一对应：假如新问题得到的可重排列中下标 $i$ 处是第 $j$ 类元素，那么原问题中就把 $i$ 号球放进 $j$ 号盒子。

将问题转化为排列计数之后，我们就可以利用指数型生成函数处理它：

$$
\begin{aligned}
G_e(x) &= \left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^m = (e^x - 1)^m \\
&= \sum _{k=0}^m\binom{m}{k} (-1)^k e^{(m-k)x} \\
&= \sum _{k=0}^m\binom{m}{k} (-1)^k \sum _{n=0}^{\infty} \frac{(m-k)^n}{n!}x^n \\
&= \sum _{n=0}^{\infty} \frac{x^n}{n!} \sum _{k=0}^{m}\binom{m}{k} (-1)^k (m-k)^n
\end{aligned}
$$

因此 $S^\sharp(n,m) = \sum_{k=0}^m \binom{m}{k}(-1)^k(m-k)^n$，再除以 $m!$ 后即得到上述通项公式。

Upd：慕课后面又讲了使用容斥原理的计算方法，相比之下要直观许多。思路仍然是先计算 $S^\sharp(n, m)$：由于它要求每个盒子非空，因此我们令 $A_i$ 表示第 $i$ 个盒子为空的放球方法，于是就有 $S^\sharp(n, m) = \left|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_m}\right|$。注意到 $\left\{A_i\right\}$ 中任意 $k$ 个集合的交集大小均为 $(m-k)^n$，利用容斥原理就直接得到上述等式。

单峰性

慕课上留了一道很有意思的思考题：证明第二类 Stirling 数 $S(n, m)$ 关于 $m$ 是单峰（unimodal）的。

所谓单峰，是指序列 $\left\{S(n,k)|k = 0,1,2,\cdots,n\right\}$ 先单调递增再单调递减。形式地，对于任意 $n \geq 0$，都存在一个 $K$ 使得

$$S(n,0) \leq S(n,1) \leq \cdots \leq S(n,K-1) \leq S(n,K) \geq S(n,K+1) \geq \cdots \geq S(n,n-1)\geq S(n,n)$$

然而，作为特殊计数序列的第二类 Stirling 数实际上具有比这更强的性质。下面我们详细定义第二类 Stirling 数所具有的单峰性：

对任意 $n \geq 0$，存在唯一的非负整数 $K(n)$ 满足：

  • $S(n,0) < S(n,1) < \cdots < S(n,K(n)) \geq S(n,K(n)+1) > \cdots > S(n,n-1) > S(n,n)$
  • $K(n) = K(n - 1)$ 或者 $K(n) = K(n-1) + 1$

这也就是说，序列 $\left\{S(n,k)|k = 0,1,2,\cdots,n\right\}$ 恰好拥有 1 个或者 2 个相邻的最大值点；在最大值点左侧，序列严格递增；在最大值点右侧，序列严格递减。此外，当 $n$ 增加 1 时，最大值点或者不发生改变，或者也增加 1。

这个结论我并不会证明，在网上找了很久也没有找到好的参考资料。所幸在一顿中英日语混合搜索过后，发现一篇证了此结论的论文；论文十分牛逼，摘要就一句话：

For fixed n , Stirling numbers of the second kind, S(n,r) have a single maximum.

接下来，我们复现这篇论文中的证明，但是有一点不同：论文中讨论了最值点的位置，但事实上，仅需证明单峰性的话是无需做这一讨论的。

另一个递推式

回顾一开始得到的递推式：

$$\begin{equation} S(n, m) = mS(n - 1, m) + S(n - 1, m - 1) \end{equation}$$

为了证明 $S(n, m)$，我们还需要利用球盒模型给出第二类 Stirling 数的另一个递推式：

$$\begin{equation} S(n, m) = \sum_{k=m-1}^{n-1} \binom{n-1}{k} S(k,m-1) \end{equation}$$

这个公式很容易理解：首先把 1 号小球放入一个盒子中，剩下 $n - 1$ 个小球和 $m - 1$ 个盒子。我们枚举剩下的小球中有多少个放在了这 $m - 1$ 个盒子中：如果在这些盒子中放了 $k$ 个小球，那么选出这些小球有 $\binom{n-1}{k}$ 种方案，把它们放入这些盒子又有 $S(k, m-1)$ 种方案；至于其余的 $n - k - 1$ 个小球则只能和 1 号小球放到同一个盒子中。根据乘法原理和加法原理，就可以得到上述递推式。

完整证明

对 $n$ 施加归纳。当 $n = 0, 1, 2, 3$ 时有 $K(n) = 0, 1, 1, 2$，结论显然成立。

当 $n > 3$ 时，待证的命题实际上可以分为两项：

  • 递增部分：证明对 $1 \leq r \leq K(n)$ 有 $S(n + 1, r) > S(n + 1, r - 1)$ 成立
  • 递减部分：证明对 $K(n) + 1 \leq r \leq n$ 有 $S(n + 1, r) > S(n + 1, r + 1)$ 成立

一旦二者都成立，讨论 $S(n + 1, K(n))$ 和 $S(n + 1, K(n) + 1)$ 的大小关系，自然就有 $K(n + 1) \in \left\{K(n), K(n) + 1\right\}$，从而完成整个归纳步骤。下面我们分别证明两个子命题。

递增部分

当 $r = 1$ 时，$1 = S(n + 1, r) > S(n + 1, r - 1) = 0$ 显然成立。

当 $r = 2, 3, \cdots, K(n)$ 时，利用递推式 $(1)$ 和第一类数学归纳法的归纳假设可得

$$
\begin{aligned}
S(n + 1, r) - S(n + 1, r - 1) &= rS(n, r) + S(n, r - 1) - (r - 1)S(n, r - 1) - S(n, r - 2) \\
&= r\left(S(n, r) - S(n, r - 1)\right) + \left(S(n, r - 1) - S(n, r - 2)\right) + S(n, r - 1) \\
&> r\times 0 + 0 + 0 = 0
\end{aligned}$$

因此有 $S(n + 1, r) > S(n + 1, r - 1)$ 成立。

递减部分

当 $r = n$ 时，$\binom{n + 1}{2} = S(n + 1, r) > S(n + 1, r + 1) = 1$ 显然成立。

当 $r = K(n)+1, K(n)+2, \cdots, n-1$ 时，利用递推式 $(2)$ 和第二类数学归纳法的归纳假设可得

$$
\begin{aligned}
& S(n + 1, r) - S(n + 1, r + 1) \\
&= \sum_{k=r-1}^{n} \binom{n}{k} S(k,r-1) - \sum_{k=r}^{n} \binom{n}{k} S(k,r) \\
&= \binom{n}{r-1}S(r-1,r-1) + \sum_{k=r}^{n}\binom{n}{k}\left(S(k,r) - S(k,r+1)\right) \\
&\geq \binom{n}{r-1} + \sum_{k=r}^{n}\binom{n}{k}\times 0 \\
&> 0
\end{aligned}
$$

因此有 $S(n + 1, r) > S(n + 1, r + 1)$ 成立。注意在第三步中我们利用了 $S(k,r) - S(k,r+1) \geq 0$，实际上隐含地使用了一个结论，即 $K(n) \geq K(k)$ 对 $r \leq k \leq n$ 成立。根据归纳假设，这是显然的。

由于两个子命题均已得证，因此归纳步骤也得证。根据第一类和第二类数学归纳法，原命题对全部非负整数 $n$ 成立。综上，序列 $\left\{S(n,k)|k = 0,1,2,\cdots,n\right\}$ 是单峰的。