把球放進箱子的問題 - 貝爾數

美國數學家 貝爾 (Eric Temple Bell 1883-1960)

印度數學家拉瑪努江 (Srinivasa Aaiyabgar Ramanujan 1887-1920)

(照片均取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

 

箱子與球的問題

問題:把 3 個有編號的球於進任意多個箱子中 (空箱不作計算),有多少不同的組合 (Combination)?

研究不同組合的問題,我們稱之為組合數學 (Combinatorics),如圖論 (Graph Theory)、幻方 (Magic Square)等也屬這門學科。這是數學中一門更新的分支,當中尚有很多疑團。

返回我們的問題,我們可以一一數算。

我們只用一個箱,把所有球於進一個箱中,有一個組合;

我們只用二個箱,把一球於進其中一個箱中,另外兩個一組放進另一個箱中,這樣有三個組合;

我們用上三個箱,每一個箱放一個球,這樣有一個組合;

合共有五個組合。

 

那麼四個球又如何呢?

我們只用一個箱,把所有球於進一個箱中,有一個組合;

我們只用二個箱,把一球於進其中一個箱中,另外三個一組放進另一個箱中,這樣有四個組合;

每個箱放兩個球,這樣有 3 個組合;

我們用上三個箱,其中一個放兩個球,另外兩個箱各放一個球,這樣有六個組合;

我們用上四個箱,每一個箱放一個球,這樣有一個組合;

合共有十五個組合。

 

我們可以看看下圖,圖中的三角形或正方形的每一隻角表示一個球,有直線相連的角,表示那兒的球放進同一個箱中,圖點則表示那個球單獨地放進一個箱子內。

 

 

把 n 個有編號的球於進任意多個箱子中的組合數目,我們稱為貝爾數 (Bell Number),記作 Bn, 定義 B0 = B1 = 1。

最初數個貝爾數為 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ... (OEIS A000110)

 

 

貝爾數

這是紀念美國數學家及數學史家貝爾 (Eric Temple Bell 1883-1960),他的其中一本著作 "Men of Mathematics: The Lives and Achievements of the Great Mathematicians from Zeno to Poincare" (中譯本為「數學大師:從芝諾到龐加萊, 徐源譯, 上海:上海科技教育出版社, 2004),相信亦有不少朋友看過。貝爾在 1934年發表的論文曾言及此數,但其實最先對此數作詳細研究的為印度數學家拉瑪努江 (Srinivasa Aaiyabgar Ramanujan 1887-1920)。

我們亦可以從另一個角度來看貝爾數。一個含有 n 個不同元素 (Element) 的集合 (Set) S,把它的元素分配於不同的非空子集 (Non - empty Subset) 中,使它們之間的交集 (Intersection) 為空,且所有子集的聯集 (Union) 為 S。貝爾數  Bn 正是那不同分割方法的數目。

 

我們計算貝爾數可以一個名為貝爾三角形 (Bell Triangle),亦有人稱此為阿特金陣列 (Atiken's Array):

1          
1 2        
2 3 5      
5 7 10 15    
15 20 27 37 52  
52 67 87 114 151 203

首先第一行開始為 1,第二行的第一個數也為 1。

接下自第二行的第二個起,該數等同該行的前一個數和前一行的前一個數的和,如 2 = 1 + 1。

每一行的第一個數為前一行的最尾的一個數,如第三行第一個數便是第二行最尾的那個 2。

如此類推。

 

讓我們試試為貝爾三角形多添一行吧:

第七行的第一個數源於第六行尾的 203,下一個數為 203 + 52 = 255,下一個數為 255 + 67 = 322,接下來是 322 + 87 = 409 和 409 + 114 = 523,再接下來是 523 + 151 = 674 和 674 + 203 = 877。即 B7 = 877。

1            
1 2          
2 3 5        
5 7 10 15      
15 20 27 37 52    
52 67 87 114 151 203  
203 255 322 409 523 674 877

 

此外我們還有一些算式可以計算貝爾數的值的:

式中的括號為二項式系數 (Binomial Coefficient)。

另外我們亦有一道與貝爾數相關的同餘式 (Congruence):

若特取 k = 0,便有下式:

 

貝爾數當中的素數 (Prime Number),我們便稱為貝爾素數 (Bell Prime),如 2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 等。(OEIS A051131)

 

參考文獻及網址

Weisstein, E. W. "Bell Number." From MathWorld. http://mathworld.wolfram.com/BellNumber.html.

Wikipedia. "Bell Number." From Wikipedia. http://en.wikipedia.org/wiki/Bell_number.