ベル数

出典: フリー百科事典『ウィキペディア（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は以下の漸化式で表わされる。

$B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}$

${n \choose k}$ は二項係数で、組み合わせの記号を使えば

n C k

に等しい。ここから以下の式が導かれる。

$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)$

[編集] 外部リンク

[編集] 関連項目

パーティション

カテゴリ: 数論 | 整数の類 | 数学に関する記事

See also ebooksgratis.com: no banners, no cookies, totally FREE.

ベル数

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

[編集] 計算例と性質

[編集] 外部リンク

[編集] 関連項目

Views

ナビゲーション

ヘルプ

検索

他の言語