S(n,k) · Bell Bₙ

Stirling 第二类数与 Bell 数

组合数 $C(n, k)$ 回答的是「选出哪一部分」，划分数回答的是「切成哪几块」。后者不给块贴标号：把 $n$ 个可辨的球分成恰 $k$ 个非空且互不可辨的组，方式数记作 Stirling 第二类数（Stirling numbers of the second kind） $S(n, k)$ ，也就是 $n$ 元集合分成 $k$ 块的划分数。对块数求和得到 Bell 数 $B_n = \sum_k S(n, k)$ ，即一个 $n$ 元集合全部划分的个数。

1 · 分块与选取的差别

S(n, k) · n 元集合分成恰 k 个非空块

选取产出的是一个子集，它与自己的补集身份不同；划分产出的是一族块，块之间既无先后也无名字，写成 $\{1, 3\}\ \{2\}$ 还是 $\{2\}\ \{1, 3\}$ 都是同一个划分。四元集合分成两块共 $S(4, 2) = 7$ 种，与 $C(4, 2) = 6$ 只差一个数值上的巧合，两者问的不是同一件事。

$S(4, 2)$ 有一条快捷的核对路线：给两块临时贴上标号 $A$ 与 $B$ ，等价于为每个元素挑一个标号，共 $2^4$ 种，扣掉两种让某一块落空的挑法得 $14$ ；标号是临时加的，撕掉它即除以 $2!$ ，回到 $7$ 。

图 1-1 · 按块数分档列出

n

元集合的全部划分，列内条数即

S(n, k)

。可拖动

n

观察各档的增长，点击某一列查看它收纳的划分。

2 · 三角上的递推

S(n, k) = k · S(n−1, k) + S(n−1, k−1)

盯住第 $n$ 个球，它只有两种去处。并入前 $n-1$ 个球已经分好的 $k$ 块中的某一块：前 $n-1$ 个球须已占满 $k$ 块，有 $S(n-1, k)$ 种分法，而第 $n$ 个球有 $k$ 个块可挑。或者自己单独成块：前 $n-1$ 个球只分成 $k-1$ 块，有 $S(n-1, k-1)$ 种分法。两类互斥且穷尽，

S(n, k) = k\, S(n-1, k) + S(n-1, k-1)

边界取 $S(0, 0) = 1$ （空集只有一个划分，即不含任何块）、 $S(n, 0) = 0$ ，以及 $k > n$ 时为 $0$ 。

这条递推与 Pascal 三角与二项式定理的 $C(n, k) = C(n-1, k) + C(n-1, k-1)$ 结构相同，差别只在左项多出的系数 $k$ 。系数的来历在于两种「不动」的做法数不一样：Pascal 里「第 $n$ 个元素不选」只有一种做法，而划分里「第 $n$ 个球并入已有的块」有 $k$ 种——块虽不带标号，却由各自的成员互相区别开，是 $k$ 个不同的去处。

图 2-1 · Stirling 三角，行末标出该行之和

B_n

。可拖动行数

N

，点击任一格看它由上一行哪两格按

k \cdot a + b

生成。

3 · Bell 数与 Bell 三角

固定 $n$ 把各块数的方案数相加，得到不限块数的划分总数 $B_n = \sum_{k=0}^{n} S(n, k)$ ，序列开头是 $1, 1, 2, 5, 15, 52, 203, 877$ 。它另有一条不经过 $S(n, k)$ 的算法：Bell 三角首行写 $1$ ，此后每行以上一行的末项开头，其余每项等于它的左邻加上一行的同列项，每行首项即 $B_n$ 。第 4 行 $15, 20, 27, 37, 52$ 的首尾两数是 $B_4$ 与 $B_5$ 。

按第 $n$ 个元素所在的块有多大来分类，还能得到 $B_n = \sum_{j} C(n-1, j)\, B_j$ ：与它同块的 $j$ 个同伴从其余 $n-1$ 个元素里选，剩下的 $n-1-j$ 个元素任意划分。

警示 · Bell 数越出双精度安全整数的位置比预想的早。本页的 bell() 走 Bell 三角的加法递推，在 $n = 23$ 上首次给出错值：算得 44152005855084344，精确值是 44152005855084346，差 2。 $B_{22} = 4506715738447323$ 尚在 Number.MAX_SAFE_INTEGER 之内， $B_{23}$ 已经越过。加法递推本身不制造额外误差，失真全部来自结果放不进 53 位尾数。

枚举侧的规模涨得更凶。setPartitions(12) 材料化 4213597 个划分，在 node 26.6.0 上实测约 2.1 秒； $n = 13$ 的 27644437 个划分在默认 4 GB 堆上跑了 73 秒后以 heap out of memory 中止。计数走递推是 $O(n^2)$ 次加法，枚举走递归是 $O(B_n)$ 次输出，两条路的分野在个位数的 $n$ 上还看不出来。

4 · 满射与贴标号

给 $k$ 个块重新贴上标号，一个划分就分裂成 $k!$ 个不同的对象，而这些对象恰好是 $n$ 元集合到 $k$ 元集合的满射：满射把定义域切成 $k$ 个非空的原像，再把这 $k$ 块与 $k$ 个目标元素配对。于是满射数为 $k!\, S(n, k)$ 。同一个数也能由容斥算出——从全部 $k^n$ 个映射里减去漏掉某个像的，加回漏掉两个像的，逐层交替：

\sum_{j=0}^{k} (-1)^j C(k,\, j)\, (k-j)^n = k!\, S(n, k)

见容斥原理。两侧互不依赖，一侧走递推、一侧走带符号求和，对照起来便是一组现成的测试断言。

注 · 这组断言在 $n = 14$ 、 $k = 13$ 处分家：容斥式给出 566658892802，而 $13!\, S(14, 13) = 566658892800$ 。结果本身只有约 $5.7 \times 10^{11}$ ，远在安全整数之内，坏掉的是中间项—— $j = 2$ 那一项 $C(13, 2) \cdot 11^{14} = 29620487019492800$ 已是 Number.MAX_SAFE_INTEGER 的 3.3 倍，各项量级约为结果的五万倍，交错相消把有效位一并消去，残差落在末位。核算这类交错和须换 BigInt，或者干脆改走递推那一侧。测试里的等价断言也据此只覆盖 $n \le 12$ 。

集合论那一侧关心的是怎样不重不漏地把这 $B_n$ 个划分列出来，三种生成算法见枚举全部划分：三种算法。 $S(n, k)$ 与 $B_n$ 在球盒模型里各占若干格，全表见十二重计数法。

5 · 参考文献

Stirling numbers of the second kind. Wikipedia. $S(n, k)$ 的递推、闭式与满射解释。https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
Bell number. Wikipedia. Bell 数、Bell 三角与几条等价递推。https://en.wikipedia.org/wiki/Bell_number
Twelvefold way. Wikipedia. 球盒模型的十二格总表。https://en.wikipedia.org/wiki/Twelvefold_way
Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley. 第 6 章给出两类 Stirling 数的记号与恒等式表。