贝尔数

贝尔数 $B_{n}$ 是含有 $n$ 个不同元素的集合划分成非空、不相交的块的方法数。每个元素恰好属于一个块，块的排列顺序不计入结果。空集合有一个空划分，因此约定 $B_{0} = 1$ 。

例如，把三个人分成若干个非空小组，可以全部分开，也可以只让一对同组，或者让三人同组。五种可能为 $\begin{matrix} {1} {2} {3}, \\ {1, 2} {3}, {1, 3} {2}, {2, 3} {1}, \\ {1, 2, 3} . \end{matrix}$ 由此 $B_{3} = 5$ 。交换一组中的元素，或交换组的先后，都不会改变划分。

三个标记为一、二、三的点，依次展示全分开、三种两点成组和全部成组，共五种集合划分。 — 框表示一个非空块。三个元素的划分按块数分成一种三块、三种两块和一种一块。

递推关系

对 $n \geq 0$ ，贝尔数满足 $B_{n + 1} = \sum_{k = 0}^{n} (\binom{n}{k}) B_{k} .$ 这个递推通过观察含指定元素的块，把一个划分拆成可独立选择的两部分。^[1]

证明。 从集合 ${1, \dots, n, n + 1}$ 开始，先确定没有与 $n + 1$ 同块的元素，假设它们有 $k$ 个。可以从前 $n$ 个元素中以 $(\binom{n}{k})$ 种方式选出它们，再以 $B_{k}$ 种方式划分这 $k$ 个元素。剩下的前 $n$ 个元素全部与 $n + 1$ 构成一个块。每个原划分只对应一个这样的 $k$ 和一次选择，按 $k = 0, \dots, n$ 相加便得递推式。

从 $B_{0} = 1$ 依次得到 $B_{1} = 1$ 、 $B_{2} = 2$ 、 $B_{3} = 5$ 。例如 $\begin{matrix} B_{4} & = (\binom{3}{0}) B_{0} + (\binom{3}{1}) B_{1} \\ + (\binom{3}{2}) B_{2} + (\binom{3}{3}) B_{3} \\ = 1 + 3 + 6 + 5 = 15. \end{matrix}$

四个元素的直接核对

四个元素的划分可按块的大小分组。四个单元素块有一种；一个二元素块与两个单元素块有 $(\binom{4}{2}) = 6$ 种；两个二元素块有 $3$ 种；一个三元素块与一个单元素块有四种；一个四元素块有一种。总数为 $1 + 6 + 3 + 4 + 1 = 15$ 。

两个二元素块的三种方法可直接写为 ${1, 2} {3, 4}$ 、 ${1, 3} {2, 4}$ 和 ${1, 4} {2, 3}$ 。如果先选出任意两个元素作为第一块，则每个划分会按两块的选择顺序被计算两次，因此 $(\binom{4}{2}) / 2 = 3$ 。

固定块数与生成函数

记 $S (n, k)$ 为 $n$ 个元素划分为恰好 $k$ 个非空块的方法数，也称第二类斯特林数。每个划分有唯一确定的块数，故 $B_{n} = \sum_{k = 0}^{n} S (n, k) .$ 对于非空集合， $S (n, 0) = 0$ 。在空集合上取 $S (0, 0) = 1$ ，与空划分约定一致。

令指数型生成函数为 $F (x) = \sum_{n \geq 0} B_{n} x^{n} / n!$ 。把递推两边乘以 $x^{n} / n!$ 并求和，可得 $F^{'} (x) = e^{x} F (x), F (0) = 1.$ 这里右侧中 $x^{n} / n!$ 的系数正好是 $\sum_{k} (\binom{n}{k}) B_{k}$ 。解这个初值问题得到 $F (x) = \exp (e^{x} - 1) .$ 普通整数分拆数与贝尔数计算不同的对象。前者划分一个整数，后者把有区别的元素分成无标签的块。

参考资料

↑ Alexander Postnikov，Algebraic Combinatorics, Lecture 6，集合划分与贝尔数。访问于2026年11月7日。

[1] Alexander Postnikov，Algebraic Combinatorics, Lecture 6，集合划分与贝尔数。访问于2026年11月7日。

[1]