ベル数

提供: miniwiki
2018/8/19/ (日) 17:39時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索
ファイル:Genjikonozu.PNG
香の図 5本の縦線を横線でつないでグループ化する方法の総数は5番目のベル数 B5 = 52 通りである

ベル数(ベルすう、: Bell number)は、n個のものを分割(もしくはグループ化)する方法の総数にあたる数である。n番目のベル数を Bn とし、B0 = B1 = 1 と定義する。Eric Temple Bell にちなんで名付けられた。例えば 3個のものをグループ化する方法の総数は5通り(後述)であるので 3番目のベル数 B3は5である。

ベル数を1から小さい順に列記すると

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 は以下の漸化式で与えられる。

[math]B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}[/math]
[math]{n \choose k}[/math]二項係数で、組み合わせの記号を使えば [math]{}_{n}C_{k}\quad[/math] に等しい。ここから以下の式が導かれる。
[math]B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}[/math]

また素数p とおくと次式が成り立つ。

[math]B_{p+n}\equiv B_n+B_{n+1}\ (\operatorname{mod}\ p)[/math]

ベル数の三角形

ファイル:BellNumberAnimated.gif
ベル三角形の計算過程。三角形の斜辺にベル数が小さい順に並ぶ

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

 1
 1 (x)

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

 1
 1  2
(y)

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

 1
 1  2
 2 (z)

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

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

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

外部リンク

関連項目