Bell number

ウィキペディア

ベル数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/30 21:39 UTC 版)

「ペル数」とは異なります。

香の図。5本の縦線を横線でつないでグループ化する方法の総数は5番目のベル数 B₅ = 52通りである。

ベル数（ベルすう、英: Bell number）とは、n個のものを分割（もしくはグループ化）する場合の数のことである。n番目のベル数を B_n とし、B₀ = B₁ = 1 と定義する。名前は数学者エリック・テンプル・ベルに因む。

例えば 3個のものをグループ化する場合の総数は5通り（後述）であるので 3番目のベル数 B₃ は5である。

ベル数の列の小さい方は次の通りである：

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, …（オンライン整数列大辞典の数列 A110）

計算例と性質

a, b, c の3つの要素を各要素の順番を問わずグループ化する方法は

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

の5通りである。よって B₃ = 5 となる。a, b の2つの要素なら

• {a}, {b}
• {a, b}

の2通りであり、B₂ = 2。同様に B₁ = 1 であり、B₀ は空集合（0個の要素）をグループ化すると考えて B₀ = 1 とする。

要素の分割の方法とベル数の関係を考える。例えば3個のボール a, b, c を箱に入れる方法は次の通りである。

• a, b, c の3つとも別々の箱に入れる。
• a を一つの箱に、b と c を別の一つの箱に入れる。
• b を一つの箱に、a と c を別の一つの箱に入れる。
• c を一つの箱に、a と b を別の一つの箱に入れる。
• a, b, c の3つとも一つの箱に入れる。

要素が3つのときは5通りの分割の方法があり、これは B₃ = 5 に対応している。

n 番目のベル数 B_n は以下の漸化式で与えられる。

${\displaystyle B_{n+1}=\textstyle \sum \limits _{k=0}^{n}\displaystyle {n \choose k}B_{k}}$

ベル三角形の計算過程。三角形の斜辺にベル数が小さい順に並ぶ

ベル数はパスカルの三角形と類似の方法で計算ができる。 まず最初のベル数1を縦に並べて書く。

 1
 1 (x)

ここで x の値は x の一つ左の数と、その上にある数との和とする。

 1
 1  2
(y)

ここでは y の値は 一つ上の段の右端の数と同じ数を書くものとする。

 1
 1  2
 2 (z)

z は x の場合と同様に左隣の数と斜め左上の数との和である。一番左端の数以外は以下同様に計算する。左端の数は y と同様に三角形の斜辺上の数を写してくる。

 1
 1  2
 2  3  5
 5  7 10 15
15 20 27 37 52

上からn段目にn個の数が並ぶように順次計算をして数を書き込んでいくと上記のようになる。n段目の右端の数がn番目のベル数である。

歴史

ベル数の名は1934年にベル多項式、1938年にベル数について記述した^[1][2]エリック・テンプル・ベルに因む。ベル自身は論文で、自らがベル数を発見したとは主張しておらず、数を exponential numbers と呼び、"頻繁に研究されてきた"（have been frequently investigated）、"何度も再発見されてきた"（have been rediscovered many times）と書いている。ベルはドビンスキの公式（英語版）を発表したドビンスキの論文 (Dobiński 1877) など早期の文献の引用も行っている。「ベル数」（Bell numbers）という名とB_nという記法は Becker & Riordan 1948 によって与えられた^{[注釈 1]}。

集合の分割の個数の、完全な数え上げが最初に見られたのは、中世日本である。当時の人気作品である源氏物語に刺激されて源氏香という遊びが生まれた。与えられた5つの香木を、同じ香りのするものに分ける。香木の分け方は52（=B₅）通りあることが香の図によって記録されている。章の表題の上部に香の図が印刷された源氏物語の版もある^{[3][注釈 2]}。

シュリニヴァーサ・ラマヌジャンは2つ目の Notebook にてベル数とベル多項式の両方を研究している^[4]。左右の辺にベル数を持つ数の三角形であるベル三角形（英語版）に関する早期の論文には Peirce 1880 や Aitken 1933 がある。

脚注

注釈

1. ^ Rota 1964は誤ってこの1948年の論文を1934年と記述している。
2. ^ Gardner 1978 と Berndt 2011 にはベル数と源氏物語の関係について、あまり詳細ではないが言及がある。

出典

1. ^ Bell 1934.
2. ^ Bell 1938.
3. ^ Knuth 2013.
4. ^ Berndt 2011.

参考文献

• Asai, Nobuhiro; Kubo, Izumi; Kuo, Hui-Hsiung (2000). “Bell numbers, log-concavity, and log-convexity”. Acta Applicandae Mathematicae 63 (1–3): 79–87. arXiv:math/0104137. doi:10.1023/A:1010738827855. MR1831247. 
• Aitken, A. C. (1933). “A problem in combinations”. Mathematical Notes 28: 18–23. doi:10.1017/S1757748900002334. 
• Becker, H. W.; Riordan, John (1948). “The arithmetic of Bell and Stirling numbers”. American Journal of Mathematics 70 (2): 385–394. doi:10.2307/2372336. JSTOR 2372336. .
• Bell, E. T. (1934). “Exponential polynomials”. Annals of Mathematics 35 (2): 258–277. doi:10.2307/1968431. JSTOR 1968431. .
• Bell, E. T. (1938). “The iterated exponential integers”. Annals of Mathematics 39 (3): 539–557. doi:10.2307/1968633. JSTOR 1968633. .
• Bender, Edward A.; Williamson, S. Gill (2006). “Example 11.7, Set Partitions”. Foundations of Combinatorics with Applications. Dover. pp. 319–320. ISBN 0-486-44603-4. http://www.math.ucsd.edu/~ebender/CombText/ch-11.pdf 
• Berend, Daniel; Tassa, Tamir (2010). “Improved bounds on Bell numbers and on moments of sums of random variables”. Probability and Mathematical Statistics 30 (2): 185–205. https://www.math.uni.wroc.pl/~pms/files/30.2/Article/30.2.1.pdf. 
• Berndt, Bruce C. (2011). “Ramanujan Reaches His Hand From His Grave To Snatch Your Theorems From You”. Asia Pacific Mathematics Newsletter 1 (2): 8–13. http://www.asiapacific-mathnews.com/01/0102/0008_0013.pdf. 
• de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108 
• Callan, David (2006). “A combinatorial interpretation of the eigensequence for composition”. Journal of Integer Sequences 9 (1): 06.1.4. arXiv:math/0507169. Bibcode: 2005math......7169C. MR2193154. https://eudml.org/doc/52955. 
• Canfield, E. Rodney (1995). “Engel's inequality for Bell numbers”. Journal of Combinatorial Theory. Series A 72 (1): 184–187. doi:10.1016/0097-3165(95)90033-0. MR1354972. 
• Claesson, Anders (2001). “Generalized pattern avoidance”. European Journal of Combinatorics 22 (7): 961–971. arXiv:math/0011235. doi:10.1006/eujc.2001.0515. MR1857258. 
• Conway, John Horton; Guy, Richard K. (1996). “Famous Families of Numbers: Bell Numbers and Stirling Numbers”. The Book of Numbers. Copernicus Series. Springer. pp. 91–94. ISBN 9780387979939. https://archive.org/details/bookofnumbers0000conw/page/91 
• Dobiński, G. (1877). “Summirung der Reihe ${\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}}$ Portal:数・プロジェクト:数