アルゴリズム

C言語で実装する組合せ論スターリング数（第一種・第二種）の計算アルゴリズムを解説

2025-04-15更新日: 2025-04-15

本記事ではC言語を用いて、組合せ論で利用される2種類のスターリング数(第一種と第二種)の計算アルゴリズムを解説します。

シンプルな実装例を交えながら解説するため、プログラミング学習やアルゴリズム研究の参考にしやすくなっています。

目次から探す

スターリング数の定義と基本性質
- 第一種スターリング数
- 第二種スターリング数
C言語による計算アルゴリズムの実装
- アルゴリズムのアプローチ
- 実装例とコード解説
実行例と検証
- 入力例と出力例
- 計算量とパフォーマンスの考察
まとめ

スターリング数の定義と基本性質

第一種スターリング数

定義と特徴

第一種スターリング数は、 $n$ 個の要素からなる順列を、ちょうど $k$ 個の巡回(サイクル)に分解できる方法の数を表します。

具体的には、 $c (n, k)$ として表記され、次の条件を満たします。

$c (0, 0) = 1$
$n > 0$ の場合は、 $c (n, 0) = 0$ および $c (0, k) = 0$ ( $k > 0$ )

また、第一種スターリング数は、符号付きと符号なしの定義があり、ここでは正の値となる符号なしの定義について扱います。

この数は、組合せ論や順列の巡回構造の解析などにも利用される興味深い数です。

再帰関係式による計算

第一種スターリング数は、再帰関係式によって効率的に計算できます。

再帰関係式は次のように表されます。

$c (n, k) = c (n - 1, k - 1) + (n - 1) \times c (n - 1, k)$

この式は、要素を1つ追加する際に新しい巡回を形成するか、既存の巡回に挿入するかの2通りの考え方に基づいています。

第二種スターリング数

定義と特徴

第二種スターリング数は、 $n$ 個の要素を、ちょうど $k$ 個の非空部分集合に分割する方法の数を表します。

通常、 $S (n, k)$ と表記され、次の特性があります。

$S (0, 0) = 1$
$n > 0$ の場合は、 $S (n, 0) = 0$ および $S (0, k) = 0$ ( $k > 0$ )

また、第二種スターリング数は集合の分割問題に応用され、組合せ論や確率論で重要な役割を果たします。

再帰関係式による計算

第二種スターリング数も再帰関係式を用いて計算できます。

その再帰関係式は以下の通りです。

$S (n, k) = S (n - 1, k - 1) + k \times S (n - 1, k)$

この関係式は、要素を新しい集合に配置する場合と、既存のどれかの集合に追加する場合に分けることで導かれます。

C言語による計算アルゴリズムの実装

アルゴリズムのアプローチ

再帰的計算法

再帰的手法では、先に説明した再帰関係式を素直にコードに反映させます。

それぞれの関数は基本ケースを定義し、再帰呼び出しを行うことで求める値を計算します。

ただし、再帰呼び出しが深くなると計算量が膨大になる可能性があり、特に重複計算が発生しやすい点に注意が必要です。

動的計画法による計算

動的計画法では再帰的計算法の欠点を補うため、計算結果をテーブルに保存し、重複した計算を避ける方法を採用します。

この方法では、下から上への計算順序でテーブルを埋めていくため、計算量は $O (n \times k)$ となり、より効率的に求めることができます。

メモリ管理にも注意しながら、必要なサイズの2次元配列(または1次元配列の2次元相当)を用いて計算結果を保持します。

実装例とコード解説

第一種スターリング数の実装例

以下は、動的計画法を用いて第一種スターリング数を計算するサンプルコードです。

コード中のコメントで各部分の役割が解説されています。

#include <stdio.h>
// 関数: stirlingFirst
// 引数: n - 要素数, k - 巡回数
// 戻り値: 第一種スターリング数(符号なし)
// 動的計画法により計算する
int stirlingFirst(int n, int k) {
    // テーブルの作成(サイズは[n+1][k+1])
    int table[n+1][k+1];
    // 基本ケースの初期化
    table[0][0] = 1; // c(0,0)=1
    for (int i = 1; i <= n; i++) {
        table[i][0] = 0; // c(n,0)=0
    }
    for (int j = 1; j <= k; j++) {
        table[0][j] = 0; // c(0,j)=0 (j>0)
    }
    // 動的計画法によるテーブル更新
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            table[i][j] = table[i-1][j-1] + (i-1) * table[i-1][j];
        }
    }
    return table[n][k];
}
int main(void) {
    int n = 5, k = 3;
    int result = stirlingFirst(n, k);
    // 第一種スターリング数の出力: 5個の要素を3巡回に分割する方法の数
    printf("First Kind Stirling Number c(%d,%d) = %d\n", n, k, result);
    return 0;
}

First Kind Stirling Number c(5,3) = 35

第二種スターリング数の実装例

次に、動的計画法で第二種スターリング数を計算するサンプルコードを示します。

こちらも基本ケースと再帰関係式に基づいてテーブルを埋める方式を採用しています。

#include <stdio.h>
// 関数: stirlingSecond
// 引数: n - 要素数, k - 分割する部分集合の数
// 戻り値: 第二種スターリング数
// 動的計画法により計算する
int stirlingSecond(int n, int k) {
    // テーブルの作成(サイズは[n+1][k+1])
    int table[n+1][k+1];
    // 基本ケースの初期化
    table[0][0] = 1; // S(0,0)=1
    for (int i = 1; i <= n; i++) {
        table[i][0] = 0; // S(n,0)=0
    }
    for (int j = 1; j <= k; j++) {
        table[0][j] = 0; // S(0,j)=0 (j>0)
    }
    // 動的計画法によるテーブル更新
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            table[i][j] = table[i-1][j-1] + j * table[i-1][j];
        }
    }
    return table[n][k];
}
int main(void) {
    int n = 5, k = 3;
    int result = stirlingSecond(n, k);
    // 第二種スターリング数の出力: 5個の要素を3集合に分割する方法の数
    printf("Second Kind Stirling Number S(%d,%d) = %d\n", n, k, result);
    return 0;
}