ベル数 - 暇つぶしWikipedia

ベル数

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

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

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

{a}, {b}

{a, b}

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

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

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

a を一つの箱に、b と c を別の一つの箱に入れる。

b を一つの箱に、a と c を別の一つの箱に入れる。

c を一つの箱に、a と b を別の一つの箱に入れる。

a, b, c の3つとも一つの箱に入れる。

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

n 番目のベル数 Bn は以下の漸化式で与えられる。 B n + 1 = ∑ k = 0 n ( n k ) B k {\displaystyle B_{n+1}=\textstyle \sum \limits _{k=0}^{n}\displaystyle {n \choose k}B_{k}} ( n k ) {\displaystyle {n \choose k}} は二項係数で、組み合わせの記号を使えば n C k {\displaystyle {}_{n}{\text{C}}_{k}} に等しい。ここから以下の式が導かれる。 B n = 1 e ∑ k = 0 ∞ k n k ! {\displaystyle B_{n}={\frac {1}{e}}\textstyle \sum \limits _{k=0}^{\infty }{\dfrac {k^{n}}{k!}}}

また素数 p に対して次式が成り立つ。 B p + n ≡ B n + B n + 1 ( mod p ) {\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}\ {\pmod {p}}}

上の漸化式より、ベル数の指数型母関数 B(x) > 0 は微分方程式 B ′(x) = exB(x), B(0) = 1 を満たすので、変数分離法より B ( x ) = ∑ n = 0 ∞ B n x n n ! = e e x − 1 {\displaystyle 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 1515 20 27 37 52

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

Size:9890 Bytes
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef