スターリング数とは？
すたーりんぐすう
スターリング数とは、集合の分割や順列の組合せ論的な数え方に使われる2種類の整数の組のことで、第1種と第2種に分かれます。
スターリング数（Stirling numbers）は組合せ数学の基本的な数列で、第1種スターリング数と第2種スターリング数の2種類があります。18世紀のスコットランドの数学者ジェームズ・スターリングにちなんで命名されました。
第2種スターリング数 S(n, k) は、n 個の区別できる要素を k 個の空でない区別しないグループ（部分集合）に分割する方法の数を表します。たとえば S(4, 2) = 7 は、4つの要素を2つの空でないグループに分ける方法が7通りあることを意味します。
第1種スターリング数 s(n, k) は、n 個の要素を k 個の巡回置換（サイクル）の積として表す符号付き整数です。符号なし第1種スターリング数は、n 個の要素の置換のうち、ちょうど k 個のサイクルを持つものの数を数えます。
スターリング数は次のような場面で活躍します。
- ベル数（集合の全分割数）の計算
- 多項式をべき乗の積で表す変換
- 確率論における分布の計算
- アルゴリズムの計算量解析
組合せ論の教科書では、二項係数と並んで重要な数表として扱われ、数え上げ問題の基礎となっています。
使い方・例文
4人の学生を2つのグループに分ける方法を数える問題で第2種スターリング数が使われます。データ構造の分析やランダム置換の理論でも頻繁に登場します。
この用語をシェア
最終更新: