スターリング数の漸化式と応用を完全解説！高校数学から一歩踏み出す
スターリング数は、組合せ論や確率論、そして離散数学で非常に重要な概念です。高校数学の枠を超えた内容ですが、丁寧に理解すれば高校生でも十分に学べます。ここでは、スターリング数の定義、漸化式、例題、そして応用まで徹底的に解説します。
目次
スターリング数とは？
スターリング数には2種類あります：
- 第1種スターリング数：順列の分解に関係し、符号付きの数で表される。
- 第2種スターリング数：ある個数の区別できない玉を、区別できる箱に区別なく分ける方法の数（空箱不可）を表す。
この解説では、特に第2種スターリング数（以下、単にスターリング数と呼びます）に焦点を当てます。
スターリング数 \( S(n, k) \) は、n個の区別できる要素を、k個の区別しない非空集合に分ける方法の数です。
たとえば、3人を2つのグループに分ける方法の数 \( S(3,2) \) は次のように考えられます：
- \(\{\{1,2\},\{3\}\}\)
- \(\{\{1,3\},\{2\}\}\)
- \(\{\{2,3\},\{1\}\}\)
よって、\( S(3,2) = 3 \) です。
スターリング数の漸化式
スターリング数 \( S(n, k) \) は次の漸化式を満たします：
\[ S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1) \]この漸化式は次のように解釈できます：
- 新しく加える要素（n番目）を、すでにあるk個のグループのいずれかに入れる場合（その方法はk通り）
- 新しいグループを1つ作って、そこにn番目の要素を単独で入れる場合（その場合は、残りn−1個をk−1個のグループに分ける必要あり）
境界条件として、次のような性質があります：
- \( S(0, 0) = 1 \)
- \( S(n, 0) = 0 \) （n > 0）
- \( S(0, k) = 0 \) （k > 0）
- \( S(n, k) = 0 \) （k > n）
- \( S(n, 1) = 1 \) （すべて一つのグループに入れる）
- \( S(n, n) = 1 \) （各要素を別のグループにする）
スターリング数を使った例題
例題1：S(4,2)の計算
漸化式を使って、次のように計算できます：
\[ S(4, 2) = 2 \cdot S(3, 2) + S(3, 1) \]すでに以下が分かっているとします：
- \( S(3,2) = 3 \)
- \( S(3,1) = 1 \)
実際に列挙しても以下の7通りがあります（省略せずにすべて書くと膨大なので漸化式のありがたさが実感できます）。
例題2：漸化式を使ってスターリング数の三角形を作る
下のように三角形の形で整理すると、パスカルの三角形のように各要素を再帰的に求められます：
| n \ k | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | |||
| 2 | 1 | 1 | ||
| 3 | 1 | 3 | 1 | |
| 4 | 1 | 7 | 6 | 1 |
このような三角形は「スターリング数の三角形」とも呼ばれ、再帰的計算の視覚化に便利です。
応用：スターリング数の現実的な使い道
スターリング数は実用的な場面にも現れます。
応用1：タスクのグルーピング
ある企業で10人の社員を3つのプロジェクトに分ける方法の数を知りたい場合、スターリング数 \( S(10,3) \) が使えます。
応用2：確率論との関連
スターリング数は、確率論のモーメント母関数や、ボゾン統計などの物理モデルでも使われます。
応用3：コンピュータ科学
関数型プログラミングや、データベースの分割、クラスタリングアルゴリズムなど、様々な計算理論の中でスターリング数が登場します。
応用4：漸化式の演習としての重要性
スターリング数の漸化式を理解することで、他の数列（フィボナッチ数列やカタラン数など）に応用できる漸化式のテクニックが身につきます。
スターリング数の概念は少し難しく感じるかもしれませんが、漸化式を使うことで計算がしやすくなり、具体例を通じて理解が深まります。数学オリンピックや情報科学、物理学など多くの分野で活用されるこの知識を、ぜひ自分のものにしましょう。
