aiwiki.page
中文

贝尔数

贝尔数表示将有限集合划分为若干非空、无序块的方法数,是组合数学中的基本数列。

19 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
组合数学集合划分空集等价关系递推关系二项式系数生成函数阶乘贝尔数

贝尔数 BnB_n 是将一个含有 nn 个不同元素的集合划分为若干非空、两两不交的块的方法数。块之间的顺序以及每个块内部元素的顺序都不计。贝尔数是组合数学中的基本数列,出现在等价关系、生成函数、概率以及分类问题的研究中。该数列的前几项为

B0,B1,B2,…=1,1,2,5,15,52,203,877,4140,21147,115975,….B_0,B_1,B_2,\ldots = 1,1,2,5,15,52,203,877,4140,21147,115975,\ldots.

定义与示例

有限集合 SS 的一个集合划分是一族非空子集,这些子集称为块,且 SS 的每个元素恰好属于其中一个块。这种划分的方法数只取决于 SS 的元素个数,与元素本身是什么无关。

对于 S={a,b,c}S=\{a,b,c\},五种划分为

{{a,b,c}},{{a,b},{c}},{{a,c},{b}},{{b,c},{a}},{{a},{b},{c}}.\begin{aligned} &\{\{a,b,c\}\},\\ &\{\{a,b\},\{c\}\},\\ &\{\{a,c\},\{b\}\},\\ &\{\{b,c\},\{a\}\},\\ &\{\{a\},\{b\},\{c\}\}. \end{aligned}

因此 B3=5B_3=5。

约定 B0=1B_0=1:空集恰好有一种划分,即不含任何块的空集族。这与包含一个空块的集族不同,后者不是有效的划分。

每个划分都确定一个等价关系:两个元素等价,当且仅当它们位于同一个块中。反过来,一个等价关系的各个等价类构成一个划分。因此,BnB_n 也表示含有 nn 个元素的集合上的等价关系数。

不应将贝尔数与整数分拆的计数混淆。在集合划分中,元素是可区分的;而在整数分拆中,只考虑各部分的大小。

递推关系

贝尔数满足递推关系

Bn+1=∑k=0n(nk)Bk,B0=1,B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k, \qquad B_0=1,

其中 (nk)\binom{n}{k} 是二项式系数。

为证明这个恒等式,在含有 n+1n+1 个元素的集合中指定一个元素。选出不属于该元素所在块的 kk 个元素。选法共有 (nk)\binom{n}{k} 种,而这些元素的划分方法共有 BkB_k 种。其余所有元素都属于指定元素所在的块。对所有 kk 求和,每种划分恰好被计算一次。

例如,

B4=(30)B0+(31)B1+(32)B2+(33)B3=1+3+6+5=15.B_4 =\binom30B_0+\binom31B_1+\binom32B_2+\binom33B_3 =1+3+6+5=15.

贝尔三角形

计算该数列的一种初等方法是使用贝尔三角形,也称艾特肯三角形:

1122355710151520273752526787114151203\begin{array}{rrrrrr} 1\\ 1&2\\ 2&3&5\\ 5&7&10&15\\ 15&20&27&37&52\\ 52&67&87&114&151&203 \end{array}

每行的首项等于上一行的末项。此后每一项都等于其左侧相邻项与左上方项之和。若行号从零开始,则第 nn 行的首项为 BnB_n,末项为 Bn+1B_{n+1}。

利用这个三角形,可以通过 O(n2)O(n^2) 次加法计算出直至 BnB_n 的所有贝尔数;若只保留当前行,则只需存储 O(n)O(n) 个整数。这些界限统计的是算术运算次数和所存整数的个数,并未考虑各项的位数会不断增加。

与斯特林数的联系

第二类斯特林数 S(n,k)S(n,k) 表示将含有 nn 个元素的集合划分为恰好 kk 个非空块的方法数。因此,

Bn=∑k=0nS(n,k).B_n=\sum_{k=0}^{n}S(n,k).

斯特林数满足

S(n+1,k)=kS(n,k)+S(n,k−1).S(n+1,k)=kS(n,k)+S(n,k-1).

新增的元素要么加入已有的 kk 个块之一,要么单独构成一个单元素块。

一个相关恒等式可以用下降阶乘表示普通幂:

xn=∑k=0nS(n,k)xk‾,x^n=\sum_{k=0}^{n}S(n,k)x^{\underline{k}},

其中

xk‾=x(x−1)⋯(x−k+1),x0‾=1.x^{\underline{k}}=x(x-1)\cdots(x-k+1), \qquad x^{\underline0}=1.

图沙尔多项式

Tn(x)=∑k=0nS(n,k)xkT_n(x)=\sum_{k=0}^{n}S(n,k)x^k

用变量的幂次记录块的个数。贝尔数是该多项式在 x=1x=1 处的值:

Tn(1)=Bn.T_n(1)=B_n.

指数生成函数

贝尔数的指数生成函数为

F(x)=∑n=0∞Bnxnn!=exp⁡(ex−1),F(x)=\sum_{n=0}^{\infty}B_n\frac{x^n}{n!} =\exp(e^x-1),

其中 n!n! 表示 nn 的阶乘。

内层表达式

ex−1=∑m=1∞xmm!e^x-1=\sum_{m=1}^{\infty}\frac{x^m}{m!}

表示一个由带标号元素组成的非空块。外层的指数函数则对应于由这些块组成的无序集合。

求导可得

F′(x)=exF(x).F'(x)=e^xF(x).

比较系数便可得到贝尔数的递推关系。这个恒等式可以视为形式幂级数的恒等式;从分析的角度看,该级数对任意复数 xx 都收敛。

更一般地,图沙尔多项式的生成函数为

∑n=0∞Tn(t)xnn!=exp⁡ ⁣(t(ex−1)).\sum_{n=0}^{\infty}T_n(t)\frac{x^n}{n!} =\exp\!\bigl(t(e^x-1)\bigr).

多宾斯基公式与概率

多宾斯基公式将每个贝尔数表示为一个无穷和:

Bn=1e∑k=0∞knk!.B_n=\frac1e\sum_{k=0}^{\infty}\frac{k^n}{k!}.

这里 ee 是自然常数e。当 n=0n=0 时,将其中的 000^0 解释为 11。

展开生成函数,得到

exp⁡(ex−1)=1e∑k=0∞ekxk!\exp(e^x-1) =\frac1e\sum_{k=0}^{\infty}\frac{e^{kx}}{k!}

再比较 xn/n!x^n/n! 的系数,即可得到该公式。

它也有直接的概率解释。若 XX 服从参数为 11 的泊松分布,则

Pr⁡(X=k)=e−1k!,\Pr(X=k)=\frac{e^{-1}}{k!},

所以

E[Xn]=Bn.\mathbb E[X^n]=B_n.

因此,贝尔数是均值为 11 的泊松随机变量的各阶原点矩,其中 E\mathbb E 表示期望值。更一般地,若 XX 服从参数为 λ\lambda 的泊松分布,则

E[Xn]=Tn(λ).\mathbb E[X^n]=T_n(\lambda).

虽然多宾斯基公式是精确的,但由于它涉及无穷求和,且中间计算量并非整数,因此在进行精确的整数计算时,基于递推的方法通常更方便。

增长与同余

贝尔数的增长速度快于任何固定底数的指数函数 cnc^n,但慢于 n!n!。一个有用的对数估计为

log⁡Bn=nlog⁡n−nlog⁡log⁡n−n+O ⁣(nlog⁡log⁡nlog⁡n),n→∞.\log B_n = n\log n-n\log\log n-n + O\!\left(\frac{n\log\log n}{\log n}\right), \qquad n\to\infty.

这里 log⁡\log 表示自然对数,误差项使用大O记号。该估计描述的是对数尺度上的增长;它本身并不能给出 BnB_n 的相对误差近似。

贝尔数在模算术中也满足一些恒等式。图沙尔同余式指出,对于任意素数 pp 和任意整数 n≥0n\geq0,都有

Bn+p≡Bn+Bn+1(modp).B_{n+p}\equiv B_n+B_{n+1}\pmod p.

当 p=2p=2 时,这变为

Bn+2≡Bn+Bn+1(mod2).B_{n+2}\equiv B_n+B_{n+1}\pmod2.

从 B0≡B1≡1B_0\equiv B_1\equiv1 出发,模 22 的余数按 1,1,01,1,0 循环。因此,BnB_n 为偶数,当且仅当 n≡2(mod3)n\equiv2\pmod3。

应用与相关计数

当对象可区分、但组不带标号时,贝尔数给出了所有可能的分组方法数。

  • **聚类:**如果允许任意数量的非空簇,那么 nn 个观测对象共有 BnB_n 种可能的划分。这是聚类分析中不加约束的组合搜索空间的大小,而不是某个特定聚类算法的输出数量。
  • **关系与分类:**有限集合上的等价关系与该集合的划分一一对应。
  • **图论:**在图论中,BnB_n 表示具有 nn 个带标号顶点、且每个连通分量都是完全图的简单图的数量。每个块确定一个完全连通分量。
  • **概率:**贝尔数既作为泊松分布的矩出现,也出现在按集合划分组织随机变量乘积的公式中。

不同的约定会产生不同的计数。如果要求恰好有 kk 个不带标号的非空组,则方法数为 S(n,k)S(n,k)。如果再为这 kk 个组赋予各不相同的标号,则方法数变为 k!S(n,k)k!S(n,k)。如果要求每个组都恰好包含两个元素,那么计数的就只有配对划分,而不是贝尔数所涵盖的全部划分。

历史背景

这个数列以埃里克·坦普尔·贝尔的名字命名,他在20世纪30年代以“指数数”之名研究了这些数。不过,这个用于计算划分数量的数列及其若干公式,在他的工作之前就已出现。多宾斯基的无穷级数公式可追溯至1877年。