スターリング数とベル数
前回、高校で習う代表的な順列・組合せを見てきました。
今回はより難しい問題について、スターリング数やベル数と呼ばれるものを使って考えていきます。
[補足(2021/02/21)] ちなみにスターリング数の「スターリング」は、階乗の近似式であるスターリングの公式と同じようです。
第2種スターリング数
次のような問題を考えてみましょう。
n 人を k 個のグループに分ける方法は何通りあるか？
ただし、各グループの人数は異なってよいが 0 人のグループは認めない。
似たような問題は前回見ました。「n 人を k 個の部屋に入れる方法は何通りあるか？ただし 0 人の部屋があってもよい。」です。これは重複順列の考え方で n^k 通りと答えることが出来ました。
しかし今回は各グループが必ず 1 人以上であり、しかもグループの区別がされていません。これを既習の内容を使って求めるのは難しそうです。
そこで、求める場合の数を次のように表すことにします。
二項係数の ( ) が { } になったものです。
そして、(i), (ii) の２つに場合分けをします。
(i) (n-1) 人が k-1 個のグループに分かれている場合
この場合、残りの１人は１人でグループを作らなければなりません。0 人のグループはグループと認められないからです。
つまり、このとき n 人を k 個のグループに分ける方法は、(n-1) 人を (k-1) 個のグループに分ける方法と同じだけあります。
(ii) (n-1) 人が k 個のグループに分かれている場合
この場合、残りの一人は k 個グループのどれかに属することになります。つまり、このとき n 人を k 個のグループに分ける方法は、(n-1) 人を k 個のグループに分ける方法の６倍だけあります。
さて、(i), (ii) のことから次の (3) の式を求めることが出来ます。
(1) については n 人を n 個のグループに分ける方法は、明らかに 1 人のグループを n 個つくるという一通りしかありません。(2) については 1 人以上を 0 個のグループに分けることはできないので、0 通りとなります。
これらによって、計算した結果は次のようになります。
このような数を第2種スターリング数といいます。これは本来次の等式を満たすものとして定義されています。
これが何故、上で挙げたような漸化式で表せるのかは、証明がやや難しそうだったので省略することにします。しかし、k=3 を例に計算すると次のようになり、確かに成り立ちそうなことが確認できます。
ベル数
次は条件を少し変えて、このような問題を考えます。
n 人をグループ分けする方法は何通りあるか？
各グループの人数は異なってよい。
今回も次のように文字をおくことにしましょう。
この問題は、先ほどのものの''k 個のグループに''が消えたものになっています。つまり、1 個のグループに分ける方法から n 個のグループに分ける方法まで、すべて足したものを求めるということです。つまり、次のような式が成り立ちます。
これにより計算すると次のようになります。B₀ は 0 人を 0 個のグループに分ける方法は 1 通りと解釈します。
しかし、これを計算するには第２種スターリング数を n+1 個も求めなければならず、面倒です。なんとかベル数だけで漸化式を立てることはできないでしょうか？
やや難しいのですが、実は可能です。簡単のため、今回は n=4 のときを考えてみましょう。今回は次の (i) から (iv) に場合分けします。
(i) 4 人目が属するグループが 1 人の場合
この場合、他のグループの 3 人のグループの分け方を考えればよいです。つまり B₃ 通りです。
(ii) 4 人目が属するグループが 2 人の場合
この場合、まず 4 人目と同じグループの人が誰かで ₃C₁ 通りあります。そして、他のグループの 2 人の別れ方が B₂ 通りとなります。
(iii) 4 人目が属するグループが 3 人の場合
この場合、まず 4 人目と同じグループの人が誰かで ₃C₂ 通りあります。そして、残された 1 人は 1 人でグループを作るので 1 通りです。
(iii) 4 人目が属するグループが 4 人の場合
この場合、明らかに 1 通りです。
以上のことから、次の式を求めることが出来ます。
このような数のことをベル数といいます。
第1種スターリング数
最後に次のような問題を考えます。
n 人を k 個のグループに分け、円卓に座る方法は何通りあるか？
ただし、各グループの人数は異なってよいが 0 人のグループは認めない。
また、円卓の区別はしないとする。
今回は求める場合の数を次のように置くことにします。
そして、また (i), (ii) に場合分けします。
(i) (n-1) 人が k-1 個のグループに分かれている場合
この場合、n 人目は 1 人のグループを作らなければならないので、n 人が k 個のグループに分かれて円卓に座る方法は (n-1) 人が (k-1) 個のグループに分かれて円卓に座る方法の数に一致します。
(ii) (n-1) 人が k 個のグループに分かれている場合
この場合、n 人目は k 個のグループのどれかに属して円卓に座ることになります。属するグループごとに座れる場所の数はことなりますが、3 人が座る円卓であれば座れる場所は 3 通りあり、4 人が座る円卓であれば座れる場所は 4 通りあることを考えると、 (n-1) 人が k 個のグループに分かれて円卓に座る方法の数の n-1 倍になることが分かります。つまり、次の (3) の式が成り立ちます。
(1) は n 人が n 個のグループに分かれて円卓に座る方法は、1 人ずつのグループに分かれて円卓に座るしかないので 1 通りです。(2) は 1 人以上が 0 個のグループに分かれて円卓に座る方法は存在しないので 0 通りです。
この式を使って計算することで、具体的な値は次のようになることが分かります。
このような数を第１種スターリング数といいます。これも元々は次のような等式を満たすようなものとして定義されています。
左辺は上昇階乗冪ですね。下降階乗冪は？と思われるかもしれませんが、こちらも第１種スターリング数を用いることで、次のように簡単に表すことができます。
また、第２種スターリング数は和をとるとベル数になりましたが、第１種スターリング数は和をとると階乗になります。
二項係数（おまけ）
ところで、スターリング数の漸化式ってなんか既視感があると感じたんですが、やはり二項係数の漸化式とほぼ同じなんですよね。また、和をとると 2 の冪になります。
スターリング数だなんて初めて聞くようなものが二項係数と似た漸化式を持つと知ると、少し親しみが湧きますね。せっかくなので、全部並べてみます。
冪は重複順列、階乗は順列、二項係数は組合せと考えると、この繋がりは少しすごいように感じます。
今回参考にしたサイトは次の通りです。
ではまた～。
