スターリング数電卓

スターリング数電卓へようこそ。このツールは、第1種（符号なし — サイクルへの置換）および第2種（空でない部分集合への集合の分割）のスターリング数を計算するための包括的な組合せ論ツールです。インタラクティブな三角形の可視化、ステップバイステップの漸化式導出、棒グラフ分布、深い組合せ論的解釈を備えたこの電卓は、教育的背景とともに高速で正確な結果を必要とする学生、教育者、研究者、および競技プログラマー向けに設計されています。

スターリング数とは？

スターリング数は、組合せ論、代数学、および解析学において自然に発生する2つの数列の族です。スコットランドの数学者ジェームス・スターリング（1692–1770）にちなんで名付けられ、階乗、二項係数、および多項式恒等式の間の架け橋となります。パスカルの三角形ほど知られてはいませんが、同様に基本的であり、離散数学の至る所に現れます。

第1種スターリング数

符号なし第1種スターリング数は、\(|s(n,k)|\) または \(\left[{n \atop k}\right]\) と表記され、\(n\)個の要素をちょうど\(k\)個の互いに素なサイクルに分解する置換の数を数えます。

直感的解釈: 要素\(n\)がどこに行くかを考えます。既存のサイクルのいずれかに挿入される場合（他の\(n-1\)個の要素それぞれの前に1つずつ、合計\(n-1\)個の挿入箇所があります）、\((n-1)\cdot|s(n-1,k)|\) の項に寄与します。あるいは、それ自体で新しい1-サイクルを形成し、\(|s(n-1,k-1)|\) に寄与します。

主な事実:

• \(|s(n,1)| = (n-1)!\) — 円順列（1つの大きなサイクル）
• \(|s(n,n)| = 1\) — 恒等置換（すべて不動点）
• \(|s(n,n-1)| = \binom{n}{2}\) — 1つの互換
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — 置換の総数

第2種スターリング数

第2種スターリング数は、\(S(n,k)\) または \(\left\{{n \atop k}\right\}\) と表記され、\(n\)個の要素の集合をちょうど\(k\)個の空でない部分集合に分割する方法の数を数えます。

直感的解釈: 要素\(n\)がどこに行くかを考えます。既存の\(k\)個の部分集合のいずれかに加わる場合（\(k\)通りの選択肢があります）、\(k \cdot S(n-1,k)\) の項に寄与します。あるいは、それ自体で新しい単集合の部分集合を形成し、\(S(n-1,k-1)\) に寄与します。

主な事実:

• \(S(n,1) = 1\) — 1通り：すべての要素が1つの集合に入る
• \(S(n,n) = 1\) — 1通り：すべての要素が単集合になる
• \(S(n,2) = 2^{n-1} - 1\) — 2つの空でない部分集合に分割する方法
• \(S(n,n-1) = \binom{n}{2}\) — どのペアが同じ部分集合を共有するかを選択
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — \(n\)番目のベル数

明示的な公式 (第2種)

この電卓の使い方

1. nを入力: 全要素数（0〜200）。
2. kを入力: サイクル数（第1種）または部分集合数（第2種）。0 ≤ k ≤ n である必要があります。
3. 種類を選択: 第1種、第2種、または比較のために「両方」を選択します。
4. 計算: 「スターリング数を計算」をクリックすると、導出ステップ、三角形の可視化、分布チャートが表示されます。

比較: 第1種 vs 第2種

スターリング数の応用

多項式変換

スターリング数は、異なる多項式の基底を接続します：

• 昇階乗: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• 通常の累乗: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (降階乗)

確率と統計

スターリング数は、確率分布のモーメントの計算、特に通常のモーメントと階乗モーメントの間の変換に現れます。これらは、ランダム置換や占有問題の解析において不可欠です。

コンピュータサイエンス

アルゴリズム解析において、スターリング数はオブジェクトをコンテナに分配する方法の数、ハッシュテーブルの解析、およびランダム置換の研究に現れます。第2種は、全射関数の数え上げに直接関係しています：n個の要素の集合からk個の要素の集合への全射関数の数は \(k!\, S(n,k)\) です。

数論

スターリング数は、ベルヌーイ数、調和数、および様々な和の恒等式に関連しています。有限差分法やオイラー＝マクローリンの公式に現れます。

よくある質問

第1種スターリング数とは何ですか？

符号なし第1種スターリング数は |s(n,k)| と表記され、n個の要素をちょうどk個の互いに素なサイクルに分解する置換の数を数えます。漸化式 |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)|（ただし |s(0,0)| = 1）を満たします。各行の和は n! になります。

第2種スターリング数とは何ですか？

第2種スターリング数は S(n,k) と表記され、n個の要素の集合をちょうどk個の空でない部分集合に分割する方法の数を数えます。漸化式 S(n,k) = k·S(n−1,k) + S(n−1,k−1)（ただし S(0,0) = 1）を満たします。各行の和はベル数 B(n) になります。

第1種スターリング数と第2種スターリング数の違いは何ですか？

第1種（符号なし）はk個のサイクルを持つ置換を数え、各サイクル内の順序が重要です。第2種はk個の部分集合への集合の分割を数え、部分集合内の順序は不問です。これらは逆行列の関係にあります。

数学でスターリング数はどのように使われますか？

スターリング数は、降階乗/昇階乗と通常の累乗の間の多項式変換、確率分布のモーメント計算、組合せ論的恒等式、数論、およびアルゴリズムの解析で使用されます。

スターリング数とベル数の関係は何ですか？

n番目のベル数 B(n) は、n行目にあるすべての第2種スターリング数の合計に等しくなります：B(n) = Σ S(n,k) (k = 0 to n)。

スターリング数の明示的な公式はありますか？

はい、第2種には包除原理による明示的な公式 S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n があります。第1種は主に漸化式を用いて計算されます。

その他のリソース

• スターリング数 - Wikipedia
• OEIS A008277 - 第2種スターリング数 (英語)
• OEIS A130534 - 符号なし第1種スターリング数 (英語)