ベル数
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}}
ベル数はパスカルの三角形と類似の方法で計算ができる。 まず最初のベル数1を縦に並べて書く。
ここで x の値は x の一つ左の数と、その上にある数との和とする。
ここでは y の値は 一つ上の段の右端の数と同じ数を書くものとする。
z は x の場合と同様に左隣の数と斜め左上の数との和である。一番左端の数以外は以下同様に計算する。左端の数は y と同様に三角形の斜辺上の数を写してくる。
上からn段目にn個の数が並ぶように順次計算をして数を書き込んでいくと上記のようになる。n段目の右端の数がn番目のベル数である。