ベル数

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

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

ベル数を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通りである。よって 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}=\sum_{k=0}^{n}{{n \choose k}B_k}
{n \choose k} は二項係数で、組み合わせの記号を使えば nCk に等しい。ここから以下の式が導かれる。
B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}

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

B_{p+n}\equiv B_n+B_{n+1}\ (\operatorname{mod}\ p)

[編集] 外部リンク

[編集] 関連項目

"http://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E6%95%B0" より作成