Catalan数

定義

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

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

最初の数項は $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 数は組合せ論の理論的興味だけでなく、計算機科学・データ構造の解析で実用的に登場します。

• 構文解析（パーサー）: 1種類の二項演算を $n$ 回使うとき、内部ノードが $n$ 個あるラベルなし完全二分木の形は $C_n$ 個です。葉や演算子へ複数のラベルを付ける場合、式の総数にはラベルの選び方も掛かります。これは構文解析アルゴリズムの計算量解析や、曖昧性の評価で参照されます。
• 二分探索木の数え上げ: $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_n = \binom{2n}{n} / (n+1)$ が出てきます。生成関数の二乗が現れる構造（畳み込み積）が「2 つの部分構造を組み合わせて 1 つの大きな構造を作る」という Catalan 構造の核心を表しています。

EML 演算子との関係

EML Sheffer $\mathrm{eml}(x, y) = \exp(x) - \ln(y)$ は、論文が標的にした関数電卓の有限36プリミティブを、入力変数 $x$、定数 $1$、$\mathrm{eml}$ の再帰的な適用で構成する演算子です。任意の解析関数や関数空間全体を生成するという主張ではありません。生成規則 $S \to 1 \mid x \mid \mathrm{eml}(S, S)$ の木について、内部ノードが $n$ 個のラベルなし完全二分木の形は $C_n$ 個です。ただし葉には $1$ と $x$ の選択があるため、ラベル付きの式総数は $C_n$ そのものではなく、深さだけを固定した総数とも区別が必要です。Andrzej Odrzywołek 2026 の論文紹介記事 academy-eml-sheffer で、この有限標的集合と構成過程を詳述しています。

関連する用語

• Sheffer ストローク — 離散版の機能完全な演算子（NAND）。EML 式でも、内部ノード数を固定したラベルなし完全二分木の形に Catalan 数が現れる

詳しくは

• Academy: EML Sheffer 演算子 — 有限36プリミティブの構成と、EML 式木の形が Catalan 数に対応する範囲を扱う
• Stanley, R. P. Catalan Numbers, Cambridge University Press, 2015.
• OEIS A000108: https://oeis.org/A000108