ベル数
是非お友達にも!
■暇つぶし何某■

[Wikipedia|▼Menu]
香の図 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)


目次

1 計算例と性質

2 ベル数の三角形

3 外部リンク

4 関連項目


計算例と性質

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}=\sum _{k=0}^{n}{{n \choose k}B_{k}}} ( n k ) {\displaystyle {n \choose k}} は二項係数で、組み合わせの記号を使えば n C k {\displaystyle {}_{n}C_{k}\quad } に等しい。ここから以下の式が導かれる。 B n = 1 e ∑ k = 0 ∞ k n k ! {\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}

また素数を p とおくと次式が成り立つ。 B p + n ≡ B n + B n + 1   ( mod ⁡   p ) {\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}\ (\operatorname {mod} \ p)}
ベル数の三角形ベル三角形の計算過程。三角形の斜辺にベル数が小さい順に並ぶ

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

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

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

z は x の場合と同様に左隣の数と斜め左上の数との和である。一番左端の数以外は以下同様に計算する。左端の数は y と同様に三角形の斜辺上の数を写してくる。 1 1 2 2 3 5 5 7 10 1515 20 27 37 52

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

Diagrams of Bell numbers

Using the Bell Triangle to calculate Bell numbers

Weisstein, Eric W. ⇒"Bell Number". MathWorld(英語). CS1 maint: Multiple names: authors list

関連項目

集合の分割

スターリング数


更新日時:2016年6月18日(土)05:09
取得日時:2018/04/22 02:18


是非お友達にも!
■暇つぶし何某■

記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:6951 Bytes
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:FIRTREE