贝尔数 Bn 是将一个含有 n 个不同元素的集合划分为若干非空、两两不交的块的方法数。块之间的顺序以及每个块内部元素的顺序都不计。贝尔数是组合数学中的基本数列,出现在等价关系、生成函数、概率以及分类问题的研究中。该数列的前几项为
B0,B1,B2,…=1,1,2,5,15,52,203,877,4140,21147,115975,….
定义与示例
有限集合 S 的一个集合划分是一族非空子集,这些子集称为块,且 S 的每个元素恰好属于其中一个块。这种划分的方法数只取决于 S 的元素个数,与元素本身是什么无关。
对于 S={a,b,c},五种划分为
{{a,b,c}},{{a,b},{c}},{{a,c},{b}},{{b,c},{a}},{{a},{b},{c}}.
因此 B3=5。
约定 B0=1:空集恰好有一种划分,即不含任何块的空集族。这与包含一个空块的集族不同,后者不是有效的划分。
每个划分都确定一个等价关系:两个元素等价,当且仅当它们位于同一个块中。反过来,一个等价关系的各个等价类构成一个划分。因此,Bn 也表示含有 n 个元素的集合上的等价关系数。
不应将贝尔数与整数分拆的计数混淆。在集合划分中,元素是可区分的;而在整数分拆中,只考虑各部分的大小。
递推关系
贝尔数满足递推关系
Bn+1=k=0∑n(kn)Bk,B0=1,
其中 (kn) 是二项式系数。
为证明这个恒等式,在含有 n+1 个元素的集合中指定一个元素。选出不属于该元素所在块的 k 个元素。选法共有 (kn) 种,而这些元素的划分方法共有 Bk 种。其余所有元素都属于指定元素所在的块。对所有 k 求和,每种划分恰好被计算一次。
例如,
B4=(03)B0+(13)B1+(23)B2+(33)B3=1+3+6+5=15.
贝尔三角形
计算该数列的一种初等方法是使用贝尔三角形,也称艾特肯三角形:
1125155223720675102787153711452151203
每行的首项等于上一行的末项。此后每一项都等于其左侧相邻项与左上方项之和。若行号从零开始,则第 n 行的首项为 Bn,末项为 Bn+1。
利用这个三角形,可以通过 O(n2) 次加法计算出直至 Bn 的所有贝尔数;若只保留当前行,则只需存储 O(n) 个整数。这些界限统计的是算术运算次数和所存整数的个数,并未考虑各项的位数会不断增加。
与斯特林数的联系
第二类斯特林数 S(n,k) 表示将含有 n 个元素的集合划分为恰好 k 个非空块的方法数。因此,
Bn=k=0∑nS(n,k).
斯特林数满足
S(n+1,k)=kS(n,k)+S(n,k−1).
新增的元素要么加入已有的 k 个块之一,要么单独构成一个单元素块。
一个相关恒等式可以用下降阶乘表示普通幂:
xn=k=0∑nS(n,k)xk,
其中
xk=x(x−1)⋯(x−k+1),x0=1.
图沙尔多项式
Tn(x)=k=0∑nS(n,k)xk
用变量的幂次记录块的个数。贝尔数是该多项式在 x=1 处的值:
Tn(1)=Bn.
指数生成函数
贝尔数的指数生成函数为
F(x)=n=0∑∞Bnn!xn=exp(ex−1),
其中 n! 表示 n 的阶乘。
内层表达式
ex−1=m=1∑∞m!xm
表示一个由带标号元素组成的非空块。外层的指数函数则对应于由这些块组成的无序集合。
求导可得
F′(x)=exF(x).
比较系数便可得到贝尔数的递推关系。这个恒等式可以视为形式幂级数的恒等式;从分析的角度看,该级数对任意复数 x 都收敛。
更一般地,图沙尔多项式的生成函数为
n=0∑∞Tn(t)n!xn=exp(t(ex−1)).
多宾斯基公式与概率
多宾斯基公式将每个贝尔数表示为一个无穷和:
Bn=e1k=0∑∞k!kn.
这里 e 是自然常数e。当 n=0 时,将其中的 00 解释为 1。
展开生成函数,得到
exp(ex−1)=e1k=0∑∞k!ekx
再比较 xn/n! 的系数,即可得到该公式。
它也有直接的概率解释。若 X 服从参数为 1 的泊松分布,则
Pr(X=k)=k!e−1,
所以
E[Xn]=Bn.
因此,贝尔数是均值为 1 的泊松随机变量的各阶原点矩,其中 E 表示期望值。更一般地,若 X 服从参数为 λ 的泊松分布,则
E[Xn]=Tn(λ).
虽然多宾斯基公式是精确的,但由于它涉及无穷求和,且中间计算量并非整数,因此在进行精确的整数计算时,基于递推的方法通常更方便。
增长与同余
贝尔数的增长速度快于任何固定底数的指数函数 cn,但慢于 n!。一个有用的对数估计为
logBn=nlogn−nloglogn−n+O(lognnloglogn),n→∞.
这里 log 表示自然对数,误差项使用大O记号。该估计描述的是对数尺度上的增长;它本身并不能给出 Bn 的相对误差近似。
贝尔数在模算术中也满足一些恒等式。图沙尔同余式指出,对于任意素数 p 和任意整数 n≥0,都有
Bn+p≡Bn+Bn+1(modp).
当 p=2 时,这变为
Bn+2≡Bn+Bn+1(mod2).
从 B0≡B1≡1 出发,模 2 的余数按 1,1,0 循环。因此,Bn 为偶数,当且仅当 n≡2(mod3)。
应用与相关计数
当对象可区分、但组不带标号时,贝尔数给出了所有可能的分组方法数。
- **聚类:**如果允许任意数量的非空簇,那么 n 个观测对象共有 Bn 种可能的划分。这是聚类分析中不加约束的组合搜索空间的大小,而不是某个特定聚类算法的输出数量。
- **关系与分类:**有限集合上的等价关系与该集合的划分一一对应。
- **图论:**在图论中,Bn 表示具有 n 个带标号顶点、且每个连通分量都是完全图的简单图的数量。每个块确定一个完全连通分量。
- **概率:**贝尔数既作为泊松分布的矩出现,也出现在按集合划分组织随机变量乘积的公式中。
不同的约定会产生不同的计数。如果要求恰好有 k 个不带标号的非空组,则方法数为 S(n,k)。如果再为这 k 个组赋予各不相同的标号,则方法数变为 k!S(n,k)。如果要求每个组都恰好包含两个元素,那么计数的就只有配对划分,而不是贝尔数所涵盖的全部划分。
历史背景
这个数列以埃里克·坦普尔·贝尔的名字命名,他在20世纪30年代以“指数数”之名研究了这些数。不过,这个用于计算划分数量的数列及其若干公式,在他的工作之前就已出现。多宾斯基的无穷级数公式可追溯至1877年。