カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致
カタラン数 $C_n = \frac{1}{n+1}\binom{2n}{n}$ が括弧列・二分木・格子経路・三角形分割・山列など全く異なる問題に現れる理由を，反射原理と全単射の構成を通じて解明します．
組合せ論には「どこにでも現れる数」があります．その代表格がカタラン数です．括弧の並べ方，二分木の形，格子経路，多角形の三角形分割 ― まったく異なる問題を解いたはずなのに，同じ数列が出てきます．なぜこんなことが起きるのでしょうか？
1 カタラン数の定義
定義 1 (カタラン数).
番目のカタラン数 は
で定義されます．最初のいくつかの値は です．
注意 2.
は整数ですが，それを で割っても常に整数になるのは自明ではありません．組合せ的な解釈を見れば整数であることは明らかですが，代数的に証明するには少し工夫が必要です．（2つの二項係数の差）と書けることから整数性が従います．
2 5つの組合せ的解釈
カタラン数は，少なくとも以下の問題すべての答えです．
例 3 (正しい括弧列).
組の括弧からなる正しい括弧列の数は です．例えば では ((())) , (()()) , (())() , ()(()) , ()()() の5通りで です．
例 4 (二分木).
個の内部ノードをもつ（相異なる形の）二分木の数は です．
例 5 (格子経路（対角線を越えない）).
から への最短格子経路で，対角線 を越えない（つまり常に ）ものの数は です．
例 6 (凸多角形の三角形分割).
凸 角形を対角線で三角形に分割する方法の数は です．
例 7 (山列).
ステップの山列（上がる と下がる を 回ずつ，高さが常に非負）の数は です．これは正しい括弧列の「視覚化」です．
3 反射原理による導出
格子経路の解釈からカタラン数の公式を導きましょう．
定理 8.
から への最短格子経路で対角線 を越えないものの数は です．
証明.
まず条件なしの経路の総数は です（右に 回，上に 回の並べ方）．次に「悪い経路」（ となる点を通る経路）の数を求めます．悪い経路は必ず直線 に触れます．最初に に触れた地点以降の経路を，直線 に関して反射します．反射操作により，悪い経路は から …ではなく，座標を適切に変換すると から への経路と1対1に対応します．したがって悪い経路の数は です．求める数は
□
注意 9.
反射原理の核心は全単射の構成です．「悪い経路」と「別の終点への経路」の間に1対1対応を作ることで，悪い経路の数を正確に求めています．この手法は他の格子経路の問題にも広く応用できます．
4 全単射の構成 ― なぜ同じ数になるのか
カタラン数が多くの問題に現れる理由は，それらの問題の解の集合の間に全単射が構成できるからです．
注意 10.
例えば， 組の正しい括弧列と対角線を越えない格子経路の間の全単射は次のように構成します：
「(」を右への移動 に対応させる
「)」を上への移動 に対応させる
括弧列が正しいことと経路が対角線を越えないことが同値になります
5 母関数による導出
定理 11.
カタラン数の母関数 は
です．
証明.
二分木の再帰構造を考えます．空でない二分木は「根 + 左部分木 + 右部分木」に分解されます．左部分木が 個，右部分木が 個の内部ノードを持つとすると，
母関数では となります（ は に対応し， は再帰的分解に対応）． を について解くと
（有限値）なので正符号は不適切であり， が正しい選択です． □
6 まとめ
カタラン数 は少なくとも5つの異なる組合せ的解釈をもちます
反射原理は格子経路の問題で「悪い場合」を数える強力な手法です
異なる問題に同じ数が現れるのは，解の集合間に全単射が構成できるからです
母関数 は二分木の再帰構造から導かれます
次の記事では，「存在する」ことだけを証明する意外な武器 ― 鳩の巣原理について解説します．