Skip to main content
  1. Posts/

贝尔数(集合的划分数目)

·2 mins
Table of Contents
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

http://baike.baidu.com/link?url=kw5Kxe3nSvRJR0TpJUpMrORcQL8fyZFpJlT9_o0RlGYOy0bKFobabPPSj3LxGfy7o1qGVycrYK4Iags3hMFq0a

在组合数合里,贝尔数给出了集合划分的数目,以数学家埃里克·坦普尔·贝尔(Eric Temple Bell)命名,是组合数学中的一组整数数列。[1]

以B0= B1=1为始, 首几项的贝尔数为:1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …(OEIS的A000110数列

_B__n_是基数为_n_的集合划分数目。集合S_的一个划分是定义为_S_的两两不相交的非空子集的族,它们的并是_S。例如_B_3 = 5因为3个元素的集合{abc}有5种不同的划分方法:

1  *

{{a}, {b}, {c}}

1  *

{{a}, {bc}}

1  *

{{b}, {ac}}

1  *

{{c}, {ab}}

1  *

{{a, b, c}}

_B_0是1因为空集

正好有1种划分方法。划分的定义要求空集的划分中的每个成员都是非空集合,而它们的并是

本身。所以

是它自身的唯一划分。(这是定义所允许的因为

2公式编辑
#

贝尔数适合递推公式:

它们也适合“Dobinski公式”:

期望值为1的泊松分布的’’n’‘次

它们也适合“Touchard同余”:若p是任意质数,那么

每个贝尔数都是"第二类Stirling数"的和

Stirling数S(n, k)是把基数为n的集划分为正好k个非空集的方法的数目。

把任一概率分布的n次矩以首n个累积量表示的多项式,其系数和正是第n个贝尔数。这种数划分的方法不像用Stirling数那个方法粗糙。

贝尔数的指数母函数

3贝尔三角形编辑
#

用以下方法建构一个三角矩阵(形式类似杨辉三角形):

(1) 第一行第一项是1(a_{1,1} = 1)

(2) 对于_n_>1,第n行第一项等同第n-1行最后一项。(

(3) 对于_m_,n>1,第n行第m项等于它左边和左上方的两个数之和。(

结果如下:(OEIS的A011971数列[2] )

每行首项是贝尔数。每行之和是第二类Stirling数

这个三角形称为贝尔三角形、Aitken阵列或Peirce三角形(Bell triangle, Aitken’s array, Peirce triangle)。

Related

codeforces 570 D. Tree Requests (dfs序)

·1 min
因为字母的排列顺序是任意的,所以判断能否形成回文串的条件就成了出现次数为奇数的字母的个数是否大于1个,如果是,那么一定不能形成回文串,否则一定可以.

cf 570 C. Replacement (暴力)

·2 mins
C. Replacement time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Daniel has a string s, consisting of lowercase English letters and period signs (characters ‘.’). Let’s define the operation of replacement as the following sequence of steps: find a substring “..” (two consecutive periods) in string s, of all occurrences of the substring let’s choose the first one, and replace this substring with string “.”. In other words, during the replacement operation, the first two consecutive periods are replaced by one. If string s contains no two consecutive periods, then nothing happens.