ベルナンバー - Hieの日記

今年，D通大のC学科の夜間一年生は離散数学の試験が大変だったようですね．
問題文を聞く機会があったのですが，どうやら「ベルナンバー」が出題されたようです．

ベルナンバーとは何か

ベルナンバー(Bell Number)というのは，有限集合 $X$ を分割する方法はいくつあるかという問題です．
たとえば， $X = \{x_1,x_2,x_3\}$ なら， $\{\{x_1\},\{x_2\},\{x_3\}\}, \{\{x_1,x_2\},\{x_3\}\},\{\{x_1\},\{x_2,x_3\}\},\{\{x_1,x_3\},\{x_2\}\},\{\{x_1,x_2,x_3\}\}$ のように，分割するパターンは5つあります*1．
$X$ の要素数を $n$ としたとき，次のようになります．

$n$	パターン数	$n$	パターン数
1	1	11	678570
2	2	12	4213597
3	5	13	27644437
4	15	14	190899322
5	52	15	1382958545
6	203	16	10480142147
7	877	17	82864869804
8	4140	18	682076806159
9	21147	19	5832742205057
10	115975	20	51724158235372

この表を式で表現するとどうなるのか？という問題なのです．

ちょっと嘘ついた

上で，一年生にベルナンバーが出題されたと書きました．ちょっと嘘です．
正確には，有限集合 $X$ 上の同値関係の総数を示せというもの．
同値関係 $R$ をとった場合，その商集合 $X/R$ は $X$ の直和分割になっています．つまり，同値関係は何パターンとれるかという質問はベルナンバーそのものになっています．
一年生諸君はそもそも，このことに気づいたのでしょうか．

導出は結構難しい

一般式があれば，それが成立することを証明することは簡単です．
しかし，一般式を求めよ，というのは結構難しいものです．
私も同じ先生に同じ問題を出題されたことがあるので，導出したことがありますが，かなりキツかったです．試験で出すなよ，かわいそうでしょ！って感じです．
ちなみに，私が解いたときはベルナンバーという名前はしりませんで，4年のとき，研究室のBugさんに教えてもらいました．

で，答えは？

全射の総数を使って解いた記憶があります．答えは
$\displaystyle{\sum_{k=1}^n \frac{F(n,k)}{k!}}\qquad,\qquad\qquad \displaystyle{F(n, k) = \sum_{i=1}^k (-1)^{k-i} {k \choose i}i^n}$
だと思います． $F(n,k)$ は全射の総数です．

*1:最後のやつは分割しないというパターン