目次

• カタラン数とは？
• カタラン数の漸化式
• カタラン数の具体例
• カタラン数の応用問題
• まとめ

カタラン数とは？

カタラン数（Catalan number）は、数学のさまざまな分野で登場する特別な数列の一つで、以下のような問題の数え上げに現れます：

• 正しい括弧の並べ方の数
• 二分木（二分探索木）の構成方法の数
• 格子点の経路の数（対角線を越えない道）

カタラン数の第 \(n\) 項は、以下の式で定義されます：

\[ C_n = \frac{1}{n+1} \binom{2n}{n} \]

これは「2n個のうちn個を選ぶ方法」から、ある条件に合うものだけを取り出した数です。例えば、正しい括弧列（開き括弧と閉じ括弧が対応していて、順序も正しい）の数がこれに該当します。

カタラン数の漸化式

カタラン数は以下のような漸化式（再帰的な関係）でも定義できます：

\[ C_0 = 1, \quad C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k} \]

この漸化式の意味は、構成される全体（例えば木構造や括弧列）を、部分構造に分解するという考え方に基づいています。例えば、括弧列で考えると、最初の開き括弧に対応する閉じ括弧で全体を分けたとき、内部と外部の構成が独立しているという性質を利用しています。

カタラン数の具体例

以下に、カタラン数の初めの数項を示します：

• \( C_0 = 1 \)
• \( C_1 = 1 \)
• \( C_2 = 2 \)
• \( C_3 = 5 \)
• \( C_4 = 14 \)
• \( C_5 = 42 \)
• \( C_6 = 132 \)

これを実際の問題に当てはめてみましょう。

例題1：正しい括弧の並びの数

例えば、3組の括弧があるとき、正しい並び方は以下の5通りです：

• ()()()
• ()(())
• (())()
• ((()))
• (()())

したがって、\( C_3 = 5 \) になります。

例題2：格子点のパスの数

原点から \((n,n)\) まで、右と上の移動だけで進み、かつ対角線 \(x=y\) より上に出ない経路の数も、カタラン数で表せます。例えば \(n = 2\) の場合、以下の2通りが可能です：

• 右→右→上→上
• 右→上→右→上

よって、\( C_2 = 2 \) です。

カタラン数の応用問題

応用1：二分探索木の数

\(n\) 個のノードを持つ二分探索木の構成方法の数は \(C_n\) になります。これは、再帰的に左部分木と右部分木に分け、それぞれの構成数を掛けることにより導かれます。例えば、\(n=3\) のときは \(C_3 = 5\) 通りの構成が可能です。

応用2：動的計画法との関係

カタラン数の漸化式は、動的計画法で計算可能です。以下は漸化式に基づいた疑似コードの例です：

C[0] = 1
for n from 1 to N:
    C[n] = 0
    for k from 0 to n-1:
        C[n] += C[k] * C[n-1-k]

このようにして、効率的に \(C_n\) を求めることができます。

応用3：構文解析への応用

カタラン数はコンピュータサイエンスにも応用されます。たとえば、構文解析（パース）で使われる構文木の構成パターン数の計算に使われます。言語の構文構造が正しいかを判定するアルゴリズム（LLパーサやLRパーサなど）にも関係があります。

まとめ

カタラン数は単なる数列ではなく、数学の広範な分野に応用される重要な概念です。漸化式や明示式の形でも表され、さまざまな組合せ的問題に現れます。高校数学でも十分に理解可能であり、特に数列や整数問題に興味のある人には格好の題材です。

繰り返しになりますが、以下の漸化式をぜひ覚えておきましょう：

\[ C_0 = 1, \quad C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k} \]

この美しい数列は、受験数学の応用としても、大学数学や情報科学への橋渡しとしても有益です。