ベル数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ベル数（-すう、英:Bell number）は自然数で、n個のものを分割（もしくはグループ化）する方法の総数にあたる数である。n番目のベル数をB_nとし、B₀=B₁=1 と定義する。Eric Temple Bellによって名付けられた。例えば5は3個のものをグループ化する方法の総数（後述）であるので5は3番目のベル数B₃である。

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

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, …

[編集] 計算例と性質

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は以下の漸化式で表わされる。

<math>B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}</math>

<math>{n \choose k}</math> は二項係数で、組み合わせの記号を使えば <math>_{n}C_{k}</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>

[編集] 外部リンク

• Diagrams of Bell numbers
• Using the Bell Triangle to calculate Bell numbers
• Bell Number MathWorld

[編集] 関連項目

• パーティション