Bell 数是划分集合的方案数。

将一个 n 元集合划分为任意个非空子集的方案数，为 Bell 数 B_n。例如，三元集 \{a, b, c\} 有 5 中划分方法 \{ \{ a, b, c \} \}, \{ \{ a, b \}, \{ c \} \}, \{ \{ a \}, \{ b, c \} \}, \{ \{b\}, \{a, c\}\}, \{ \{ a \} , \{ b \}, \{ c \} \}，因此 B_3 = 5。

特别地，规定 B_0 = 1。

性质

递推公式

Bell 数适合如下的递推公式：

证明：对于一个 n + 1 元集，取出其中一个元 x。若 x 单独做一个子集，则剩下的 n 元有 B_n 种划分方法；若 x 与剩下 n 元之一做一个子集，则有 \binom{n}{1} B_{n - 1} = \binom{n}{n - 1} B_{n - 1} 中划分方法；若 x 与剩下 n 元之 2 做一个子集，则有 \binom{n}{2} B_{n - 2} = \binom{n}{n - 2} B_{n - 2} 种划分方法……以此分类下去，公式得证。

Bell 三角形

Bell 三角形是如下定义的一组数：

• 第 1 行 a_{1, 1} = 1
• 第 i 行有 i 个数，自第 2 行起，行首等于上一行的行尾，也就是 a_{i, 1} = a_{i - 1, i - 1}
• 从第 2 列起，这个数等于同行上一列和上一行上一列的数之和，也就是 a_{i, j} = a_{i, j - 1} + a_{i - 1, j - 1}。

这样构造后，第 i 行的行末就代表第 i 个 Bell 数 B_i。

组合解释

参考：Wikipedia

Bell 三角形中，a_{n, k} 表示的是将 n + 1 元集 \{ 1, 2, \dots, n + 1 \} 划分后，k + 1 落在一个单元素集中，且 k + 2, k + 3, \dots, n + 1 都落在非单元素集中的方法数。换句话说，k + 1 是某种划分中，下标最大的单元素集。

例如，将 \{ 1, 2, 3, 4 \} 划分，且 3 做最大下标单元素集的方法数，有以下 3 种方法：

这对应 a_{3, 2} = 3。

a_{i, 0} = a_{i - 1, i - 1} 可以解释为：