ベル数

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

例えば 3個のものをグループ化する場合の総数は5通り（後述）であるので 3番目のベル数 $B 3$ は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 3 = 5$ となる。a, b の2つの要素なら

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

の2通りであり、 $B 2 = 2$ 。同様に $B 1 = 1$ であり、 $B 0$ は空集合（0個の要素）をグループ化すると考えて $B 0 = 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 3 = 5$ に対応している。

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

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

{n \choose k}

は二項係数で、組み合わせの記号を使えば

{}_{n}{\text{C}}_{k}

に等しい。ここから以下の式が導かれる。

B_{n}={\frac {1}{e}}\textstyle \sum \limits _{k=0}^{\infty }{\dfrac {k^{n}}{k!}}

また素数 $p$ に対して次式が成り立つ。

B_{p+n}\equiv B_{n}+B_{n+1}\ {\pmod {p}}

上の漸化式より、ベル数の指数型母関数 B(x) > 0 は微分方程式 B ′(x) = e^xB(x), B(0) = 1 を満たすので、変数分離法より

B(x)=\textstyle \sum \limits _{n=0}^{\infty }B_{n}{\dfrac {x^{n}}{n!}}=e^{e^{x}-1}

となることも導ける。

ベル数の三角形

ベル数はパスカルの三角形と類似の方法で計算ができる。まず最初のベル数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 5$ ）通りあることが香の図によって記録されている。章の表題の上部に香の図が印刷された源氏物語の版もある^[3]^{[注釈 2]}。

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

脚注

注釈

^ Rota 1964は誤ってこの1948年の論文を1934年と記述している。
^ Gardner 1978 と 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. MR 1831247.
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
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.
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.
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
Dobiński, G. (1877). “Summirung der Reihe $\textstyle \sum {\frac {n^{m}}{n!}}$ für m = 1, 2, 3, 4, 5, …”. Grunert's Archiv 61: 333–336.
Engel, Konrad (1994). “On the average rank of an element in a filter of the partition lattice”. Journal of Combinatorial Theory. Series A 65 (1): 67–78. doi:10.1016/0097-3165(94)90038-8. MR1255264.
Flajolet, Philippe; Sedgewick, Robert (2009). “II.3 Surjections, set partitions, and words”. Analytic Combinatorics. Cambridge University Press. pp. 106–119
Gardner, Martin (1978). “The Bells: versatile numbers that can count partitions of a set, primes and even rhymes”. Scientific American 238 (5): 24–30. Bibcode: 1978SciAm.238e..24G. doi:10.1038/scientificamerican0578-24. , W. H. Freeman, 1992, pp. 24–38.第二章に補遺の付いた再販版。
Hazewinkel, Michiel, ed. (2001), “Bell numbers”, Encyclopaedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://eom.springer.de/p/b110240.htm
Hurst, Greg; Schultz, Andrew (2009). "An elementary (number theory) proof of Touchard's congruence". arXiv:0906.0696 [math.CO]。
Knuth, Donald E. (2013). “Two thousand years of combinatorics”. In Wilson, Robin; Watkins, John J.. Combinatorics: Ancient and Modern. Oxford University Press. pp. 7–37
Lovász, L. (1993). “Section 1.14, Problem 9”. Combinatorial Problems and Exercises (2nd ed.). Amsterdam, Netherlands: North-Holland. p. 17. ISBN 9780821869475. Zbl 0785.05001
Moser, Leo; Wyman, Max (1955). “An asymptotic formula for the Bell numbers”. Transactions of the Royal Society of Canada, Section III 49: 49–54. MR0078489.
Peirce, C. S. (1880). “On the algebra of logic”. American Journal of Mathematics 3 (1): 15–57. doi:10.2307/2369442. JSTOR 2369442. .
Rota, Gian-Carlo (1964). “The number of partitions of a set”. American Mathematical Monthly 71 (5): 498–504. doi:10.2307/2312585. JSTOR 2312585. MR0161805.
Spivey, Michael Z. (2008). “A generalized recurrence for Bell numbers”. Journal of Integer Sequences 11 (2): Article 08.2.5, 3. Bibcode: 2008JIntS..11...25S. MR2420912.
Wagstaff, Samuel S. (1996). “Aurifeuillian factorizations and the period of the Bell numbers modulo a prime”. Mathematics of Computation 65 (213): 383–391. Bibcode: 1996MaCom..65..383W. doi:10.1090/S0025-5718-96-00683-7. MR1325876.
Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001
Williams, G. T. (1945). “Numbers generated by the function e^{e^x − 1}”. American Mathematical Monthly 52: 323–327. doi:10.2307/2305292. JSTOR 2305292. MR0012612.

外部リンク

『全射の個数の証明とベル数』 - 高校数学の美しい物語
Diagrams of Bell numbers
Weisstein, Eric W. "Bell Number". mathworld.wolfram.com (英語).

[3] Rota 1964は誤ってこの1948年の論文を1934年と記述している。

[5] Gardner 1978 と Berndt 2011 にはベル数と源氏物語の関係について、あまり詳細ではないが言及がある。

[FOOTNOTEBell1934-1] Bell 1934.

[FOOTNOTEBell1938-2] Bell 1938.

[FOOTNOTEKnuth2013-4] Knuth 2013.

[FOOTNOTEBerndt2011-6] Berndt 2011.

[1]

[2]

[注釈 1]

[3]

[注釈 2]

[4]

計算例と性質

ベル数の三角形

歴史

脚注

注釈

出典

参考文献

関連項目

外部リンク