カタラン数
Catalan Numbers
初級
1. 概要
カタラン数（Catalan numbers）は、組合せ論において最も頻繁に現れる数列の一つである。括弧の正しい対応付け、二分木の構造、凸多角形の三角形分割など、一見無関係に思える多くの組合せ的問題が、すべて同じ数列で数え上げられるという驚くべき普遍性を持つ。
この数列の歴史は 18 世紀に遡る。1751 年、Leonhard Euler は凸多角形を対角線で三角形に分割する方法の数を考え、Johann Andreas von Segner との書簡のなかでこの問題を議論した。Segner は 1758 年にこの数列の再帰的な公式を導いた。その後 1838 年、ベルギーの数学者 Eugène Charles Catalan がこの数列を体系的に研究し、現在の名称の由来となった。
カタラン数は次の閉じた公式で定義される：
$$ C_n = \frac{1}{n+1}\binom{2n}{n} $$この単純な式が、200 以上もの異なる組合せ的対象を数え上げるという事実は、組合せ論の深い構造を反映している。
2. 定義
定義（カタラン数）
非負整数 $n \ge 0$ に対して、第 $n$ カタラン数 $C_n$ を次で定義する：
$$ C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!} $$最初のいくつかの値を計算してみよう：
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| $C_n$ | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 |
計算例
$C_4$ を計算する：
$$ C_4 = \frac{1}{5}\binom{8}{4} = \frac{1}{5} \cdot \frac{8!}{4!\,4!} = \frac{1}{5} \cdot 70 = 14 $$別の等価な表現として、次の形もよく使われる：
$$ C_n = \binom{2n}{n} - \binom{2n}{n+1} $$この式は、後述する反射原理による証明から自然に導かれる。
3. 再帰公式
定理（カタラン数の再帰関係）
カタラン数は次の再帰式を満たす：
$$ C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}, \qquad C_0 = 1 $$証明
$C_{n+1}$ が $n+1$ 組の括弧からなる正しい括弧列の数であることを用いて示す。
$n+1$ 組の括弧列の先頭は必ず開き括弧 "(" である。この最初の "(" に対応する閉じ括弧 ")" の位置で場合分けする。
括弧列全体を $w_1 w_2 \cdots w_{2(n+1)}$ とおく。$w_1 = \text{"("}$ であり、これに対応する閉じ括弧が $w_{2i+2}$ の位置にあるとする（$0 \le i \le n$）。このとき括弧列は次の構造を持つ：
$$ \underbrace{(\;\overbrace{u_1 u_2 \cdots u_{2i}}^{i \text{ 組の括弧列}}\;)}_{\text{最初の括弧対とその内側}}\;\underbrace{v_1 v_2 \cdots v_{2(n-i)}}_{{(n-i) \text{ 組の括弧列}}} $$ここで：
- 内側の $u_1 \cdots u_{2i}$ は $i$ 組の正しい括弧列でなければならない。その数は $C_i$ 通り。
- 外側（右側）の $v_1 \cdots v_{2(n-i)}$ は $n - i$ 組の正しい括弧列でなければならない。その数は $C_{n-i}$ 通り。
全単射性の確認：任意の $n+1$ 組の正しい括弧列に対して、最初の "(" の対応する ")" の位置は一意に定まる。逆に、$i$ を固定し、$i$ 組の正しい括弧列 $\alpha$ と $n-i$ 組の正しい括弧列 $\beta$ を選べば、$(\alpha)\beta$ は $n+1$ 組の正しい括弧列を与え、最初の "(" の対応する ")" は位置 $2i+2$ にある。この対応は明らかに一対一かつ全射である。
したがって、$i$ の各値に対する括弧列の数は $C_i \cdot C_{n-i}$ であり、$i = 0, 1, \ldots, n$ にわたって合計すると
$$ C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i} $$が得られる。$\square$
この再帰式を具体的に確かめてみよう：
- $C_1 = C_0 \cdot C_0 = 1$
- $C_2 = C_0 C_1 + C_1 C_0 = 1 + 1 = 2$
- $C_3 = C_0 C_2 + C_1 C_1 + C_2 C_0 = 2 + 1 + 2 = 5$
- $C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 5 + 2 + 2 + 5 = 14$
また、閉じた形の再帰式として次も有用である：
$$ C_{n+1} = \frac{2(2n+1)}{n+2}\, C_n $$これは閉じた公式から直接導かれ、逐次的な計算に便利である。
4. 母関数
定理（カタラン数の母関数）
カタラン数の通常母関数 $\displaystyle C(x) = \sum_{n=0}^{\infty} C_n x^n$ は次で与えられる：
$$ C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} $$収束半径は $|x| \le \frac{1}{4}$ である。
導出
再帰式 $\displaystyle C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$ の両辺に $x^{n+1}$ を掛けて $n = 0, 1, 2, \ldots$ で和をとる。右辺は畳み込み（Cauchy 積）の形をしているから：
$$ C(x) - 1 = x \cdot C(x)^2 $$すなわち、$C(x)$ は2次方程式
$$ x \, C(x)^2 - C(x) + 1 = 0 $$を満たす。二次方程式の解の公式より
$$ C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x} $$$C(0) = C_0 = 1$ を満たすのは負号の方（$x \to 0$ で L'Hôpital の規則を適用すると確認できる）なので
$$ C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} $$を得る。
母関数の観点から、閉じた公式を再導出することもできる。$\sqrt{1-4x}$ の展開
$$ \sqrt{1-4x} = \sum_{n=0}^{\infty} \binom{1/2}{n} (-4x)^n $$を用いて $C(x)$ の $x^n$ の係数を取り出すと $\displaystyle C_n = \frac{1}{n+1}\binom{2n}{n}$ が復元される。
5. 組合せ的解釈
カタラン数の最も注目すべき性質は、多様な組合せ的対象を統一的に数え上げることである。以下に代表的な 6 つの解釈を挙げる。
5.1 括弧の正しい対応付け
問題
$n$ 組の括弧を正しく対応させる方法は何通りあるか？
$C_n$ は $n$ 組の開き括弧 "(" と閉じ括弧 ")" からなる正しい括弧列の数に等しい。
$n = 3$: $C_3 = 5$ 通り
((()))
(()())
(())()
()(())
()()()
5.2 二分木の数
問題
$n + 1$ 枚の葉（外部節点）を持つ順序付き二分木は何通りあるか？
$C_n$ は $n$ 個の内部節点（= $n+1$ 枚の葉）を持つ相異なる順序付き完全二分木の数に等しい。
これは再帰構造から理解できる。根の左部分木に $i$ 個の内部節点、右部分木に $n - 1 - i$ 個の内部節点を割り当てると、合計は
$$ \sum_{i=0}^{n-1} C_i \, C_{n-1-i} = C_n $$となり、再帰式と一致する。
$n = 3$: $C_3 = 5$ 通りの二分木
3 個の内部節点を持つ順序付き完全二分木は 5 通りあり、これは括弧列と一対一に対応する。
5.3 凸多角形の三角形分割
問題
凸 $(n+2)$ 角形を対角線で三角形に分割する方法は何通りあるか？
$C_n$ は凸 $(n+2)$ 角形の三角形分割の数に等しい。これは Euler が最初に考えた問題であり、カタラン数の歴史的な起源でもある。
例
- $n = 1$：三角形（3 角形）は分割不要。$C_1 = 1$
- $n = 2$：四角形の対角線分割は $C_2 = 2$ 通り
- $n = 3$：五角形の三角形分割は $C_3 = 5$ 通り
- $n = 4$：六角形の三角形分割は $C_4 = 14$ 通り
一辺を固定して、その辺を含む三角形の選び方で再帰的に数えると、カタラン数の再帰式が導かれる。
5.4 格子路（Dyck 路）
問題
$(0, 0)$ から $(n, n)$ への格子路で、対角線 $y = x$ を越えない（すなわち常に $y \le x$ の）ものは何通りあるか？
$C_n$ は $(0, 0)$ から $(n, n)$ への単調格子路（右または上への移動のみ）のうち、対角線 $y = x$ より上に出ないものの数に等しい。
同等の定式化として、Dyck 路（$2n$ ステップの格子路で、上昇 "U" と下降 "D" からなり、途中で $y$ 座標が負にならないもの）の数としても表現できる。
$n = 3$: $C_3 = 5$ 通りの Dyck 路
UUUDDD
UUDUDD
UUDDUD
UDUDUD
UDUUDD
5.5 非交差分割
問題
集合 $\{1, 2, \ldots, n\}$ の非交差分割は何通りあるか？
$C_n$ は $\{1, 2, \ldots, n\}$ の非交差分割（noncrossing partition）の数に等しい。非交差分割とは、$1, 2, \ldots, n$ を円周上に配置したとき、各ブロックの凸包が互いに交差しない分割のことである。
$n = 3$: $C_3 = 5$ 通り
$\{1, 2, 3\}$ の非交差分割：
- $\{\{1\}, \{2\}, \{3\}\}$
- $\{\{1, 2\}, \{3\}\}$
- $\{\{1\}, \{2, 3\}\}$
- $\{\{1, 3\}, \{2\}\}$
- $\{\{1, 2, 3\}\}$
（注：$\{1, 3\}$ と $\{2\}$ は円周上で交差しないので許される。一方、仮に 4 要素で $\{1, 3\}$ と $\{2, 4\}$ は交差するので非交差分割には含まれない。）
5.6 山の列（Mountain ranges）
$2n$ 個のステップからなる山の列（上昇 "/" と下降 "\" を交互に行い、地面より下に行かない経路）の数は $C_n$ に等しい。これは Dyck 路と本質的に同じ対象であるが、視覚的には山脈のように見える。
6. 反射原理による証明
カタラン数の閉じた公式 $\displaystyle C_n = \frac{1}{n+1}\binom{2n}{n}$ を、反射原理（reflection principle, André の反射法）を用いて証明する。これは格子路の解釈を用いた最もエレガントな証明の一つである。
定理
$(0, 0)$ から $(n, n)$ への単調格子路のうち、対角線 $y = x$ を厳密に越えないものの数は
$$ C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n} $$証明
$(0, 0)$ から $(n, n)$ への単調格子路の総数は $\displaystyle\binom{2n}{n}$ である（$2n$ ステップのうち右方向に進む $n$ ステップを選ぶ）。
ここから「悪い路」（対角線を越える路）の数を引けばよい。「悪い路」とは、ある点で初めて直線 $y = x + 1$ に触れる路である。
反射の議論：悪い路が初めて直線 $y = x + 1$ に触れる点を $P$ とする。$P$ 以降の経路を直線 $y = x + 1$ に関して反射する（右ステップと上ステップを入れ替える）。すると、悪い路は $(0, 0)$ から $(-1, n+1)$、すなわち座標を読み替えると $(n-1, n+1)$ への単調格子路と一対一に対応する。
$(0, 0)$ から $(n-1, n+1)$ への単調格子路の数は $\displaystyle\binom{2n}{n+1}$ である。
この対応は全単射なので、良い路の数は
$$ C_n = \binom{2n}{n} - \binom{2n}{n+1} $$これを整理すると
$$ C_n = \binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n}\left(1 - \frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n} $$が得られる。$\square$
この証明は投票問題（Ballot problem）とも深く関連している。候補者 $A$ が $a$ 票、候補者 $B$ が $b$ 票を獲得し $a > b$ のとき、開票の全過程で $A$ が常にリードしている確率は $\displaystyle\frac{a - b}{a + b}$ である。$a = b = n$ の場合、$A$ が常に $B$ 以上（同点を許す）であるような開票順序の数が $C_n$ に対応する。
7. 漸近公式
定理（カタラン数の漸近評価）
$n \to \infty$ のとき
$$ C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}} $$導出
Stirling の近似 $\displaystyle n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$ を用いる。
$$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{4\pi n}\left(\frac{2n}{e}\right)^{2n}}{2\pi n \left(\frac{n}{e}\right)^{2n}} = \frac{4^n}{\sqrt{\pi n}} $$したがって
$$ C_n = \frac{1}{n+1}\binom{2n}{n} \sim \frac{1}{n} \cdot \frac{4^n}{\sqrt{\pi n}} = \frac{4^n}{n^{3/2}\sqrt{\pi}} $$この結果は、カタラン数が $4^n$ のオーダーで指数的に増大し、多項式因子 $n^{-3/2}$ で補正されることを示している。具体的な近似精度を確認してみよう：
| $n$ | $C_n$（厳密値） | $\displaystyle\frac{4^n}{n^{3/2}\sqrt{\pi}}$（近似値） | 相対誤差 |
|---|---|---|---|
| 5 | 42 | 45.6 | 8.6% |
| 10 | 16796 | 17734 | 5.6% |
| 20 | 6564120420 | 6748772354 | 2.8% |
| 50 | $1.978 \times 10^{28}$ | $2.000 \times 10^{28}$ | 1.1% |
$n$ が大きくなるにつれて近似精度が向上していくことが分かる。
参考文献
- Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
- Stanley, R. P. (2012). Enumerative Combinatorics, Vol. 2, Exercise 6.19. Cambridge University Press.
- Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley.