「ベル数」の版間の差分
提供: miniwiki
(数字のあとにカンマを追加。) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:39時点における最新版
ベル数(ベルすう、英: 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]
ベル数の三角形
ベル数はパスカルの三角形と類似の方法で計算ができる。 まず最初のベル数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 15 15 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(英語). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。