この間分割数の記事についての記事を書いたときに続けてスターリング数も次回書くつもりですっかり忘れていたので書こうと思い立ちました。

数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。前回は分割数を、今回はスターリング数を勉強しました。

なお、スターリング数 (の考え方) が使える問題として以下があります (他にもあったら大募集なのん):

0. 写像12相 (再掲)

n 個の玉を k 個の箱に入れる場合の数を数える問題を考えます。

によって12パターンの問題設定が考えられるので写像12相と呼ばれています。以下の記事にとてもよくまとまっています。

ちょっと問題設定がなかなかピンと来ない感じですが、今回は「箱を区別しない」部分をメインに考えます。「箱を区別しない」というのはつまり n 個の玉を k 個のグループに分ける問題を考えるということです。

2. スターリング数

考察の対象は以下の場合です:

つまり n 個の互いに区別できる玉を k 個のグループに分ける場合の数を求める問題です。この場合の数を $S(n, k)$ と置くことにします。

ベル数もよく聞く名前ですが、それは以下の場合です:

つまり n 個の互いに区別できる玉を k 個以下のグループに分ける場合の数を求める問題です。この場合の数を $B(n, k)$ と置くことにします。自明にわかることとして、

${ \displaystyle B(n, k) = \sum_{i=1}^{k} S(n, i) }$

が成立します。そしてなんとベル数 B(n, n) は O(n) で求められるようです！

包除原理を用いて直接求めるバージョンと、漸化式で求めるバージョンがあります。

${ \displaystyle S(n, k) = S(n-1, k-1) + k S(n-1, k) }$

${ \displaystyle S(n, k) = \frac{1}{k!} \sum_{i=1}^{k} (-1)^{k-i} C(k, i) i^{n} }$

(これから書く)