C/C++でn番目のカタラン数を求めるプログラム

カタラン数（Catalan numbers）とは、組み合わせ論におけるさまざまな数え上げ問題に現れる自然数の数列です。特に、再帰的に定義される対象の個数を数える場面で頻繁に登場することで知られています。

カタラン数の主な性質

• ディック語（Dyck word）との関係

  C_n は、長さ 2n のディック語の総数を表します。ディック語とは、n 個の X と n 個の Y から構成され、文字列のどの先頭部分を見ても Y の数が X の数を超えない文字列のことです。例えば、長さ 6 のディック語は次の通りです。

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

• 正しい括弧の対応付け

  X を開き括弧「(」、Y を閉じ括弧「)」と読み替えると、C_n は n 組の括弧が正しく対応付けられた式の総数を表します。

((())) ()(()) ()()() (())() (()())

• 演算順序の組み合わせ

  C_n は、n + 1 個の因子を完全に括弧で囲む方法の総数（二項演算子を n 回適用する際の結合順序の数）でもあります。例えば n = 3 の場合、4 つの因子に対して次の 5 通りの括弧付けが存在します。

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

• 完全二分木との関係

  二項演算子の連続的な適用は、完全二分木によって表現できます（根付き二分木において、すべての頂点が子を 2 つ持つか、まったく持たないとき「完全」と呼びます）。したがって、C_n は葉を n + 1 個持つ完全二分木の総数に等しくなります。

実行サンプル

入力 - 6
出力 - 1 1 2 5 14 42

説明

n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, … に対応するカタラン数は次のように並びます。
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,

なお、カタラン数は次の漸化式で定義されます。C₀ = 1 とし、C_n+1 = Σ C_i × C_n-i（i = 0 ～ n）として計算できます。また、直接計算する場合は二項係数を用いた式 C_n = (2n)! / ((n+1)! × n!) も利用可能です。

C++による実装例

#include<iostream>
using namespace std;
long int catalan( int n) {
   if (n <= 1){
      return 1;
   }
   long int result = 0;
   for (int i=0; i<n; i++){
      result += catalan(i)*catalan(n-i-1);
   }
   return result;
}
int main(){
   for (int i=0; i<6; i++)
   cout << catalan(i) << " ";
   return 0;
}

出力結果

1 1 2 5 14 42

この実装では、漸化式に基づいて再帰的にカタラン数を計算しています。ただし、素朴な再帰では同じ値を何度も計算するため計算量が増大します。実用的にはメモ化や動的計画法を併用すると、より効率的に大きな n まで求められます。