C言語でn番目のカタラン数（Catalan数）を求めるプログラム

整数 n が与えられたとき、その n 番目の位置にあるカタラン数（Catalan Number）を求めるのが本記事の課題です。プログラムを作成する前に、まず「カタラン数とは何か」をしっかり理解しておきましょう。

カタラン数とは、さまざまな組合せ論的な数え上げ問題に現れる自然数の列のことです。

カタラン数 C₀, C₁, C₂, …, C_n は、次の式によって求められます。

$$c_{n}=\frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}$$

n = 0, 1, 2, 3, … に対するカタラン数は、順に 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … となります。

例えば、n = 3 を入力した場合、プログラムは 5 を出力する必要があります。

カタラン数の主な応用例

• n 個のキーから構成できる二分探索木（BST）の総数を数える。
• n 組の括弧がすべて正しく対応している式の個数を求める。たとえば n = 3 の場合、((()))、()(())、()()()、(())()、(()()) の 5 通りが存在します。
• 円周上の点を互いに交差しない弦で結ぶ方法の数を求める、など多数。

入出力例

Input: n = 6
Output: 132
Input: n = 8
Output: 1430

解法のアプローチ

今回使用する解法の手順は以下の通りです。

• 整数 n を入力として受け取る。
• n <= 1 の場合は 1 を返す（基底ケース）。
• i = 0 から i < n までループを回す。
• 各 i に対して result = result + catalan(i) × catalan(n−i−1) を計算する。
• 結果を返し、出力する。

アルゴリズム

Start
    Step 1 -> 関数 unsigned long int catalan(unsigned int n)
        もし n <= 1 ならば
            Return 1
        End if
        unsigned long 型の変数 res = 0 を宣言
        i = 0 から i < n まで i++ でループ
            res = res + (catalan(i) * catalan(n-i-1))
        End Loop
        Return res
    Step 2 -> int main()
        入力 n = 6 を宣言
        "catalan is :" を出力し、関数 catalan(n) を呼び出す
Stop

C言語による実装例

#include <stdio.h>
// 再帰的アプローチでカタラン数を求める
unsigned long int catalan(unsigned int n) {
    // 基底ケース
    if (n <= 1) return 1;
    // catalan(n) は catalan(i)*catalan(n-i-1) の総和
    unsigned long int res = 0;
    for (int i=0; i<n; i++)
        res += catalan(i)*catalan(n-i-1);
    return res;
}
// メイン関数
int main() {
    int n = 6;
    printf("catalan is :%ld\n", catalan(n));
    return 0;
}

実行結果

catalan is :132

補足：計算量について

上記の再帰的な実装は直感的で分かりやすい一方、同じ部分問題を何度も計算するため、時間計算量は指数オーダーとなり、n が大きくなると処理が非常に遅くなります。実用的な規模の n を扱う場合は、動的計画法（DP）を用いて既に計算した値を配列にキャッシュすることで、O(n²) まで計算量を抑えることができます。また、二項係数の公式を直接利用すれば O(n) で求めることも可能です。