ベル数 ベル数の概要

ウィキペディア

ベル数

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

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

例えば 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番目のベル数である。