Catalan数 | 用語集 | AlphaInsiders

定義

Catalan 数（カタラン数）は次の漸化式で定義される非負整数の数列です。

C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}

二項係数を使った閉じた式も成立します。

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

最初の数項は $1, 1, 2, 5, 14, 42, 132, 429, 1{,}430, 4{,}862, \ldots$ と続きます。

性質

指数増加: 漸近的には $C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$ で増える
整数: $\binom{2n}{n}$ が $n+1$ で割り切れる事実は非自明な整除性を持つ
無数の組合せ問題で同一の数列が現れる: Stanley は 200 以上の等価な記述を挙げている（Stanley, Catalan Numbers, 2015）
生成関数: $C(x) = \sum_{n \ge 0} C_n x^n = \frac{1 - \sqrt{1 - 4x}}{2x}$

視覚的に見る

最初の 7 項を bar chart で並べると、 $C_4 = 14$ あたりから急激な指数増加が見えてきます。

横軸が $n$ 、縦軸が $n$ 番目の Catalan 数 $C_n$ 。棒の高さが値で、 $C_0$ から $C_5$ （青緑）までは 1, 1, 2, 5, 14, 42 と緩やかだが、 $C_6 = 132$ （緑）で急に跳ね上がる。棒の上の数字が各 $C_n$ の値。

形状的には $C_n \sim 4^n / (n^{3/2}\sqrt{\pi})$ の漸近形が示すように、ほぼ指数的に立ち上がる。 $C_{10} = 16{,}796$ 、 $C_{20} \approx 6.56 \times 10^9$ と、組合せ論の標準的な数列のなかでもとくに増加が速い部類に入ります。

実世界での使われ方

Catalan 数は組合せ論の理論的興味だけでなく、計算機科学・データ構造の解析で実用的に登場します。

構文解析（パーサー）: コンパイラの式構文解析で、 $n$ 個の演算子から作れる構文木の総数は $C_n$ 。これは構文解析アルゴリズムの計算量解析や、表現力の限界（ambiguity 評価）で参照されます。
二分探索木の数え上げ: $n$ 個のキーを格納する形の異なる二分探索木は $C_n$ 個。アルゴリズム入門書（Knuth, The Art of Computer Programming, vol. 1）で標準的な題材として扱われます。
動的計画法: 行列連鎖積（matrix chain multiplication）、最適二分探索木、回文分割など、多くの DP 問題で Catalan 数が解の総数や状態空間サイズとして登場します。
量子情報理論: 線形量子系の経路積分や bracket structure の数え上げで Catalan 数が出てきます（Eu, J. Combin. Theory, 2010）。
OEIS A000108: 整数列のオンライン百科事典「OEIS A000108」では Catalan 数が最も参照される数列の一つで、関連する組合せ的解釈が継続的に追加されています。

深掘り

形の異なる多数の組合せ的解釈

Catalan 数が「同じ数列がこれだけ多くの場面で出てくる」事実は、組合せ的同型 の宝庫として研究されています。代表的なものだけでも:

$n$ 対の括弧を正しく対応させる方法の数
$n$ 個の内部ノードを持つ完全二分木の数
$(n+1)$ 個の葉を持つ二分木の数
$(0,0)$ から $(n,n)$ への対角線を超えない格子経路の数（Dyck 経路）
凸 $(n+2)$ 角形を三角形に分割する方法の数（三角形分割）
$n+1$ 個の数の積を計算する括弧付けの方法の数

これらの構造の間には全単射が構成でき、Stanley は単行本に 200 以上の等価な記述を集めました。Catalan 構造論は単なる数え上げではなく、組合せ的構造の深い同型を発見する道具になっています。

母関数による導出

漸化式 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$ は母関数 $C(x) = \sum_n C_n x^n$ に対して

C(x) = 1 + x \cdot C(x)^2

という二次方程式を与えます。解くと

C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}

となり、これを級数展開して係数比較すると $C_n = \binom{2n}{n} / (n+1)$ が出てきます。生成関数の二乗が現れる構造（畳み込み積）が「2 つの部分構造を組み合わせて 1 つの大きな構造を作る」という Catalan 構造の核心を表しています。

EML 演算子との関係

連続数学の万能演算子 EML Sheffer $\mathrm{eml}(x, y) = \exp(x) - \ln(y)$ は、入力変数 $x$ と定数 $1$ から $\mathrm{eml}$ を再帰的に適用して任意の解析関数を生成します。式の生成規則 $S \to 1 \mid x \mid \mathrm{eml}(S, S)$ は内部ノードが eml 演算、葉が 1 か $x$ である完全二分木の集合と同型で、深さに対する式の総数は Catalan 数で支配される。Andrzej Odrzywołek 2026 の論文紹介記事 academy-eml-sheffer でこの構造が詳述されています。

詳しくは

Academy: EML Sheffer 演算子 — 連続数学の万能演算子で式空間が Catalan 数に支配される構造を扱う
Stanley, R. P. Catalan Numbers, Cambridge University Press, 2015.
OEIS A000108: https://oeis.org/A000108