ベル数

ベル数（ベルすう、英: Bell number）とは、 $n$ 個のものを分割（もしくはグループ化）する場合の数のことである。 $n$ 番目のベル数を $B n$ とし、 $B 0 = B 1 = 1$ と定義する。名前は数学者エリック・テンプル・ベルに因む。

例えば 3個のものをグループ化する場合の総数は5通り（後述）であるので 3番目のベル数 $B 3$ は5である。

ベル数の列の小さい方は次の通りである：

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通りである。よって $B 3 = 5$ となる。a, b の2つの要素なら

{a}, {b}
{a, b}

の2通りであり、 $B 2 = 2$ 。同様に $B 1 = 1$ であり、 $B 0$ は空集合（0個の要素）をグループ化すると考えて $B 0 = 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 3 = 5$ に対応している。

$n$ 番目のベル数 $B n$ は以下の漸化式で与えられる。

B_{n+1}=\textstyle \sum \limits _{k=0}^{n}\displaystyle {n \choose k}B_{k}

{n \choose k}

は二項係数で、組み合わせの記号を使えば

{}_{n}{\text{C}}_{k}

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

B_{n}={\frac {1}{e}}\textstyle \sum \limits _{k=0}^{\infty }{\dfrac {k^{n}}{k!}}

また素数 $p$ に対して次式が成り立つ。

B_{p+n}\equiv B_{n}+B_{n+1}\ {\pmod {p}}

上の漸化式より、ベル数の指数型母関数 B(x) > 0 は微分方程式 B ′(x) = e^xB(x), B(0) = 1 を満たすので、変数分離法より

B(x)=\textstyle \sum \limits _{n=0}^{\infty }B_{n}{\dfrac {x^{n}}{n!}}=e^{e^{x}-1}

となることも導ける。

ベル数の三角形

ベル三角形の計算過程。三角形の斜辺にベル数が小さい順に並ぶ

ベル数はパスカルの三角形と類似の方法で計算ができる。まず最初のベル数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.wolfram.com (英語).

ベル数

目次

計算例と性質

ベル数の三角形

関連項目

外部リンク