第二类 Stirling 数学习小结

发表于 2020-07-28 更新于 2022-09-17

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

第二类 Stirling 数

定义

球盒模型

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

下降幂

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

$\begin{matrix} (1) & x^{\underset{―}{n}} \equiv [x]_{n} \equiv x (x - 1) (x - 2) \dots (x - n + 1) \end{matrix}$

边界值 $[x]_{0} = 1$ 。

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

$\begin{matrix} (2) & \begin{aligned} x^{n} & = S (n, 0) [x]_{0} + S (n, 1) [x]_{1} + \dots + S (n, n) [x]_{n} \\ = \sum_{k = 0}^{n} S (n, k) [x]_{k} \end{aligned} \end{matrix}$

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

$\begin{matrix} (3) & [x]_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} s (n, k) x^{k} \end{matrix}$

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

递推式

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

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

球盒模型

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

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

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

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

于是可得：

$\begin{matrix} (4) & S (n, m) = m S (n - 1, m) + S (n - 1, m - 1) \end{matrix}$

下降幂

考察定义式 $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 (n > 0)$
$S (n, n) = 1 (n \geq 0)$

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

$\begin{matrix} (5) & \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} x S (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} k S (n - 1, k) [x]_{k} \\ = \sum_{k = 0}^{n - 1} S (n - 1, k) [x]_{k + 1} + \sum_{k = 0}^{n - 1} k S (n - 1, k) [x]_{k} \\ = \sum_{k = 1}^{n} S (n - 1, k - 1) [x]_{k} + \sum_{k = 1}^{n - 1} k S (n - 1, k) [x]_{k} \\ = \sum_{k = 1}^{n} (S (n - 1, k - 1) + k S (n - 1, k)) [x]_{k} \end{aligned} \end{matrix}$

最后一步利用了 $S (n - 1, n) = 0$ 。对比上式和定义式，即得到 $S (n, k) = k S (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 - δ)$ 的边界值可以通过讨论放球最多的盒子放了多少球得出。以 $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 数的通项公式，当然由于其中使用了求和符号所以并不是解析式。这个通项是：

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

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

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

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

$\begin{matrix} (7) & \begin{aligned} G_{e} (x) & = {(x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \dots)}^{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} \end{matrix}$

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

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

单峰性

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

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

$\begin{matrix} (8) & S (n, 0) \leq S (n, 1) \leq \dots \leq S (n, K - 1) \leq S (n, K) \geq S (n, K + 1) \geq \dots \geq S (n, n - 1) \geq S (n, n) \end{matrix}$

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

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

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

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

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

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

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

另一个递推式

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

$\begin{matrix} (9) & S (n, m) = m S (n - 1, m) + S (n - 1, m - 1) \end{matrix}$

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

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

这个公式很容易理解：首先把 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 {K (n), K (n) + 1}$ ，从而完成整个归纳步骤。下面我们分别证明两个子命题。

递增部分

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

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

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

因此有 $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, \dots, n - 1$ 时，利用递推式 $(2)$ 和第二类数学归纳法的归纳假设可得

$\begin{matrix} (12) & \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}) (S (k, r) - S (k, r + 1)) \\ \geq (\binom{n}{r - 1}) + \sum_{k = r}^{n} (\binom{n}{k}) \times 0 \\ > 0 \end{aligned} \end{matrix}$

因此有 $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$ 成立。综上，序列 ${S (n, k) | k = 0, 1, 2, \dots, n}$ 是单峰的。