Catalan数（高校数学）

同義語：カタラン数（高校数学）Catalan numbers (high school mathematics)

概要

前提知識: 場合の数の数え方の体系, 最短経路の数え上げと鏡像原理

高校での出発点：3 つの数え上げ

見た目のまったく違う 3 つの数え上げの問題を考える。

正しい括弧の列

「(」を 3 個、「)」を 3 個並べて、数式の括弧として正しく対応がつく並べ方を数える。たとえば (())() は正しいが、())(() は 3 文字目の「)」に対応する「(」がないので正しくない。全部書き出すと
$$ \texttt{((()))},\quad\texttt{(()())},\quad\texttt{(())()},\quad\texttt{()(())},\quad\texttt{()()()} $$
の 5 通りである。「(」と「)」を 2 個ずつなら (()) と ()() の 2 通り、1 個ずつなら () の 1 通りである。

対角線を越えない経路

碁盤の目の上で、$(0,0)$ から $(3,3)$ まで、右か上に 1 ずつ進む経路（最短経路）のうち、通る点がすべて $y\le x$ をみたす（対角線 $y=x$ より上に出ない）ものは 5 通りである（図 1）。$(0,0)$ から $(2,2)$ までなら 2 通り、$(1,1)$ までなら 1 通りである。

(0, 0) から (3, 3) への最短経路で対角線（破線）より上に出ない 5 本。上に書いた括弧の列は、右へ 1 進むことを開き括弧、上へ 1 進むことを閉じ括弧に置き換えたもの

凸五角形の三角形分割

凸五角形に、互いに交わらない対角線を引いて、内部をいくつかの三角形に分ける方法を数える。1 本の対角線だけでは四角形が残るので、2 本引く必要がある。2 本の対角線が交わらないのは、同じ頂点から出る 2 本のときで、頂点が 5 つあるので 5 通りある（図 2）。凸四角形なら対角線 1 本で 2 通り、三角形なら何も引かない 1 通りである。

凸五角形 P0P1P2P3P4 の三角形分割 5 通り。赤い線が引いた対角線で、どれも 1 つの頂点から 2 本出ている
3 つの問題の答えは、大きさを 1 つずつ上げると、どれも $1,2,5$ と並ぶ。さらに大きさを上げても、3 つはいつも同じ数 $1,1,2,5,14,42,132,\dots$ になる。この数を Catalan 数 という。この記事で答える問いは次の 4 つである。

3 つの数え上げが同じ数になるのはなぜか。→ thm-cat-three
Catalan 数を小さい方から順に計算する方法は。→ thm-cat-recursion
Catalan 数を一つの式で表せるか。→ thm-cat-formula

数え上げの条件を少し変えると、どう崩れるか。→ ex-cat-cross、ex-cat-nonconvex、ex-cat-shift

対象	$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$	対応の作り方
括弧 $n$ 組の正しい列	$1$	$1$	$2$	$5$	$14$	$42$	定義
$(0,0)$ から $(n,n)$ への $y\le x$ の経路	$1$	$1$	$2$	$5$	$14$	$42$	「(」を右、「)」を上に置き換える
凸 $(n+2)$ 角形の三角形分割	$1$	$1$	$2$	$5$	$14$	$42$	底辺を含む三角形で 2 つに分ける

表の $n=0$ の列は、それぞれ「空の列」「動かない経路」「2 角形（線分）は分けない」の 1 通りと約束したものである。3 行の値が等しいことは thm-cat-three で示し、値そのものは ex-cat-recursion-values で漸化式から計算する。

高校の計算	この記事の言葉	大学の言葉
置き換えて 1 対 1 に対応させる	括弧と経路の対応	全単射
最初の「(」に対応する「)」で分ける	漸化式 $C_{n+1}=\sum C_kC_{n-k}$	母関数：数列を関数として扱う、二分木
越える経路を折り返して引く	$\dbinom{2n}n-\dbinom{2n}{n-1}$	鏡像原理（最短経路の数え上げと鏡像原理）
文字列を回して $2n+1$ 個ずつまとめる	巡回補題、$\dfrac1{2n+1}\dbinom{2n+1}{n}$	群の作用と軌道

Catalan 数を定義する

括弧の列が「正しい」ことを、数えられる形で言い直す。括弧の列を左から読み、「(」で $+1$、「)」で $-1$ を足していく。はじめの $i$ 文字を読んだところでの合計を、$i$ 文字目の高さと呼び $h_i$ と書く（$h_0=0$）。高さは「まだ閉じていない (」の個数である。

正しい括弧の列とCatalan数

$n\ge0$ とする。「(」を $n$ 個、「)」を $n$ 個並べた長さ $2n$ の列で、すべての $i=1,2,\dots,2n$ について高さが $h_i\ge0$ となるものを、括弧 $n$ 組の正しい列 という（$n=0$ のときは、何も並べない空の列 1 つだけとする）。括弧 $n$ 組の正しい列の個数を $C_n$ と書き、Catalan 数 という。

「(」と「)」が $n$ 個ずつなので、最後の高さは $h_{2n}=0$ である。$h_i\ge0$ は、「どこまで読んでも、閉じた数が開いた数を超えない」ということであり、「どの ) にも対応する ( がある」ことを式で言ったものである。

高さで判定する

(())() の高さは、1 文字ずつ読んで $1,2,1,0,1,0$ で、どれも $0$ 以上なので正しい。
())(() の高さは $1,0,-1,\dots$ で、3 文字目で $-1$ になるので正しくない。3 文字目の「)」に対応する「(」がないことと同じである。
()() の高さは $1,0,1,0$、(()) は $1,2,1,0$ で、どちらも正しい。)(() などほかの 4 通りの並べ方は、どこかで高さが負になる（$1$ 文字目が「)」なら $h_1=-1$、())( なら $h_3=-1$）。よって $C_2=2$ である。

漸化式

$C_3=5$ の 5 つの列を、ある規則で分けてみる。どの正しい列も「(」で始まる（1 文字目が「)」なら $h_1=-1$ になるから）。その最初の「(」に対応する「)」を探す。

最初の括弧で分ける

正しい列を、最初の「(」と、それに対応する「)」とで
$$ \texttt{(}\ A\ \texttt{)}\ B $$
の形に分ける。$A$ は最初の括弧の内側、$B$ はその後ろである。$C_3=5$ の 5 つの列では

((()))：$A=$ (())、$B=$ 空。$A$ は 2 組、$B$ は 0 組。
(()())：$A=$ ()()、$B=$ 空。2 組と 0 組。
(())()：$A=$ ()、$B=$ ()。1 組と 1 組。
()(())：$A=$ 空、$B=$ (())。0 組と 2 組。
()()()：$A=$ 空、$B=$ ()()。0 組と 2 組。
となる。$A$ が 2 組の列は $C_2\cdot C_0=2\cdot1=2$ 個、1 組は $C_1\cdot C_1=1$ 個、0 組は $C_0\cdot C_2=2$ 個で、合わせて $2+1+2=5=C_3$ である。

Catalan数の漸化式

$C_0=1$ であり、$n\ge0$ について
$$ C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k}=C_0C_n+C_1C_{n-1}+\cdots+C_nC_0 $$
が成り立つ。

括弧の列 (()())() を経路にしたもの。最初の 1 歩（開き括弧）のあと、対角線にはじめて戻る点 (3, 3) の直前の 1 歩（閉じ括弧）までの間が A、その後ろが B で、A の部分は対角線より 1 つ下の直線（点線）より上に出ない
図 3 は、この分け方を経路で見たものである（括弧と経路の対応は thm-cat-three で述べる）。最初の「(」に対応する「)」は、経路が対角線にはじめて戻る点の直前の 1 歩にあたる。

最初に高さが 0 に戻る場所で分ける

方針：括弧 $n+1$ 組の正しい列 $w$ を、はじめて高さが $0$ に戻る場所で $w=\texttt{(}A\texttt{)}B$ と分け、$A$ と $B$ がどちらも正しい列になること、逆に正しい列 $A$、$B$ から $w$ が作れることを示す。$A$ が $k$ 組なら $B$ は $n-k$ 組である。
段 1（分ける場所）。$w$ の長さは $2n+2$ で、$h_{2n+2}=0$ である。$h_i=0$ となる $i\ge1$ のうち最小のものを $t$ とする（$i=2n+2$ で $0$ になるので、$t$ は必ずある）。$h_1\ge0$ なので 1 文字目は「(」で、$h_1=1$ である。$h_t=0$ で $h_{t-1}\ge1$（$t$ より前は $0$ にならず、負にもならない）なので、$t$ 文字目は「)」である。
段 2（$A$ は正しい列）。$w$ の 2 文字目から $t-1$ 文字目までを $A$ とする。$A$ を単独で読んだときの高さは、$w$ の高さから $1$（最初の「(」の分）を引いたものである。$1\le i\le t-1$ では $h_i\ge1$ なので、$A$ の高さは $0$ 以上である。$A$ の最後の高さは $h_{t-1}-1=1-1=0$ である（$h_{t-1}=h_t+1=1$）。よって $A$ は「(」と「)」を同数含み、高さが負にならないので、正しい列である。$A$ の組の数を $k$ とすると、$A$ の長さは $2k=t-2$ で、$0\le k\le n$ である。
段 3（$B$ は正しい列）。$w$ の $t+1$ 文字目から最後までを $B$ とする。$h_t=0$ なので、$B$ を単独で読んだ高さは $w$ の高さそのものであり、$0$ 以上で、最後は $0$ である。よって $B$ は正しい列で、組の数は $(n+1)-1-k=n-k$ である。
段 4（逆の操作）。逆に、$k$ 組の正しい列 $A$ と $n-k$ 組の正しい列 $B$ から $w=\texttt{(}A\texttt{)}B$ を作る。$w$ の高さは、最初の「(」で $1$、$A$ の間は（$A$ の高さ）$+1\ge1$、次の「)」で $0$、$B$ の間は $B$ の高さ $\ge0$ である。よって $w$ は $n+1$ 組の正しい列で、はじめて高さが $0$ になるのは $A$ の直後の「)」である。したがって、段 1〜3 の分け方を $w$ に行うと、元の $A$、$B$ が戻ってくる。
段 5（数える）。段 1〜4 により、$n+1$ 組の正しい列と、「$k$（$0\le k\le n$）と、$k$ 組の正しい列 $A$ と、$n-k$ 組の正しい列 $B$ の組」とが 1 対 1 に対応する。$k$ を決めると $A$ は $C_k$ 通り、$B$ は $C_{n-k}$ 通りなので、積の法則で $C_kC_{n-k}$ 通りである。$k$ の違う場合は重ならないので、和の法則で $C_{n+1}=\sum_{k=0}^nC_kC_{n-k}$ である。$C_0=1$ は定義による。$\square$

漸化式で計算する

$C_0=1$ から順に

$C_1=C_0C_0=1$
$C_2=C_0C_1+C_1C_0=1+1=2$
$C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5$
である。同じ計算を続けると $C_4=14$、$C_5=42$ である。
$C_4$ と $C_5$ の計算を開く
$$C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0=5+2+2+5=14$$
$$C_5=C_0C_4+C_1C_3+C_2C_2+C_3C_1+C_4C_0=14+5+4+5+14=42$$

$C_2=2$、$C_3=5$ は、ex-cat-height、ex-cat-parens で列を書き出して数えた値と一致する。

この「最初の部分とその残りに分けて掛け、分け方について足す」形の漸化式は、数学的帰納法と整列性の強い帰納法（$n$ 以下のすべての場合を仮定する形）と相性がよい。次の節ではそれを使う。

3 つの数え上げが一致する

凸多角形の三角形分割を、言葉として定めておく。

三角形分割

$m\ge3$ とし、凸 $m$ 角形の頂点を順に $P_0,P_1,\dots,P_{m-1}$ とする。対角線（隣り合わない 2 頂点を結ぶ線分）をいくつか選び、どの 2 本も端点以外で交わらず、選んだ対角線で多角形の内部がすべて三角形に分かれるとき、選んだ対角線の集まりを 三角形分割 という。三角形分割でできる三角形の頂点は、どれも多角形の頂点である。

凸三角形（$m=3$）は対角線を 1 本も選ばない 1 通りである。凸四角形は対角線 2 本のどちらか 1 本を選ぶ 2 通りで、両方選ぶと 2 本が内部で交わるので三角形分割ではない。

3 つの数え上げの一致

$n\ge0$ について、次の 3 つの個数はどれも $C_n$ に等しい。
(1) 括弧 $n$ 組の正しい列の個数。
(2) $(0,0)$ から $(n,n)$ への最短経路（右か上に 1 ずつ進む経路）で、通る点がすべて $y\le x$ をみたすものの個数。
(3) 凸 $(n+2)$ 角形の三角形分割の個数（$n=0$ のときは $1$ と約束する）。

は def-cat-catalan そのものである。(2) と (3) を順に示す。

括弧の列と経路

「(」を右、「)」を上に置き換える

方針：括弧の列の各文字を、「(」なら右へ 1、「)」なら上へ 1 進む歩に置き換える。高さ $h_i$ が、$i$ 歩進んだ点の $x-y$ に等しいことを使う。
段 1（置き換え）。括弧 $n$ 組の列（正しいとは限らない）は「(」と「)」を $n$ 個ずつ含むので、置き換えると $(0,0)$ から右へ $n$、上へ $n$ 進んで $(n,n)$ に着く最短経路になる。逆に、そのような最短経路の各歩を「右なら (、上なら )」と読めば、括弧 $n$ 組の列に戻る。2 つの操作は互いに逆なので、括弧 $n$ 組の列と $(0,0)$ から $(n,n)$ への最短経路は 1 対 1 に対応する。
段 2（高さと座標）。はじめの $i$ 文字に「(」が $a$ 個、「)」が $b$ 個あるとすると、$h_i=a-b$ であり、経路は $i$ 歩で点 $(a,b)$ に着いている。よって $h_i=x-y$ である。
段 3（条件の一致）。段 2 により、すべての $i$ で $h_i\ge0$ であることは、経路の通る点がすべて $x-y\ge0$、つまり $y\le x$ をみたすことと同じである。よって段 1 の対応で、正しい列と $y\le x$ の経路がちょうど対応し、(2) の個数は $C_n$ である。$\square$

図 1 の 5 本の経路の上の括弧の列は、この対応で得たものである。図 3 の経路が対角線にはじめて戻る点は、高さがはじめて $0$ に戻る場所（prf-cat-recursion の $t$）である。

三角形分割

三角形分割でも、thm-cat-recursion と同じ漸化式が成り立つことを示す。凸 $(n+2)$ 角形の三角形分割の個数を $T_n$ とおく（$T_0=1$）。

六角形を 2 つに分ける

凸六角形 $P_0P_1\cdots P_5$（$n=4$）の三角形分割を 1 つとる。底辺 $P_0P_5$ を辺にもつ三角形がちょうど 1 つあり、その 3 つ目の頂点を $P_j$ とする。図 4 では $j=2$ で、三角形 $P_0P_2P_5$ が底辺を含む。この三角形で六角形は、左の三角形 $P_0P_1P_2$ と右の四角形 $P_2P_3P_4P_5$ に分かれ、残りの対角線 $P_2P_4$ は右の四角形の三角形分割になっている。
$j$ は $1,2,3,4$ のどれかで、左は $(j+1)$ 角形、右は $(6-j)$ 角形である（$j=1$ なら左は線分 $P_0P_1$ で分けるものがなく、$T_0=1$ 通りと数える）。よって
$$ T_4=T_0T_3+T_1T_2+T_2T_1+T_3T_0=5+2+2+5=14 $$
である。$j=1,2,3,4$ に $T_{j-1}T_{4-j}$ が対応する。

凸六角形の三角形分割を、底辺 P0P5 を含む三角形 P0P2P5（赤）で左の三角形 P0P1P2 と右の四角形 P2P3P4P5 に分けたもの。青は右の四角形の対角線

底辺を含む三角形で分ける

$n\ge0$ とし、凸 $(n+3)$ 角形 $P_0P_1\cdots P_{n+2}$ を考える。三角形分割と、「$j$（$1\le j\le n+1$）と、凸多角形 $P_0P_1\cdots P_j$ の三角形分割と、凸多角形 $P_jP_{j+1}\cdots P_{n+2}$ の三角形分割の組」とは 1 対 1 に対応する。ここで、頂点が 2 つの「多角形」（線分）の三角形分割は、何も選ばない 1 通りとする。

底辺の上の三角形

要点：底辺 $P_0P_{n+2}$ を辺にもつ三角形は分割の中にちょうど 1 つあり、その 3 つ目の頂点 $P_j$ が $j$ を決める。残りの対角線は三角形 $P_0P_jP_{n+2}$ の辺と交わらないので、左の多角形 $P_0\cdots P_j$ か右の多角形 $P_j\cdots P_{n+2}$ のどちらかに入り、それぞれを三角形に分ける。逆に、$j$ と左右の分割に $P_0P_j$、$P_jP_{n+2}$（対角線であるもの）を加えると全体の分割に戻る。凸であることは、底辺の上に多角形の頂点が $P_0$ と $P_{n+2}$ しかないこと、対角線が多角形の内部を通ることに使う。

詳しい証明を開く

段 1（底辺を含む三角形はちょうど 1 つ）。辺 $P_0P_{n+2}$ の中点のすぐ内側の点は、分割でできたどれか 1 つの三角形の内部か辺の上にある。その三角形は、辺 $P_0P_{n+2}$ を自分の辺としてもつ。

詳細

選んだ対角線はどれも多角形の頂点どうしを結ぶので、辺 $P_0P_{n+2}$ の中点を通らない（凸多角形では、頂点以外の辺の上の点を対角線は通らない）。よって中点の近くには対角線がなく、中点のすぐ内側の点は 1 つの三角形に入る。その三角形は中点の近くで辺 $P_0P_{n+2}$ に接しているので、その辺の一部を自分の辺としてもつ。三角形の頂点は多角形の頂点で、直線 $P_0P_{n+2}$ の上にある多角形の頂点は $P_0$ と $P_{n+2}$ だけ（凸だから）なので、その辺はちょうど $P_0P_{n+2}$ である。中点のすぐ内側の点を 2 つの三角形が共有することはないので、このような三角形は 1 つだけである。

その三角形の 3 つ目の頂点を $P_j$ とすると、$1\le j\le n+1$ である。

段 2（残りの対角線を振り分ける）。三角形 $P_0P_jP_{n+2}$ の辺 $P_0P_j$ と $P_jP_{n+2}$ は、多角形の辺か、選んだ対角線である。ほかの選んだ対角線は、これらと端点以外で交わらないので、多角形 $P_0P_1\cdots P_j$（左）か多角形 $P_jP_{j+1}\cdots P_{n+2}$（右）のどちらか一方の中にある。左にある対角線は左の多角形を三角形に分け、右にある対角線は右の多角形を三角形に分ける。こうして、全体の分割から $j$ と左右の分割の組が決まる。

段 3（逆の操作）。逆に、$j$ と左右の三角形分割が与えられたら、左右の対角線に、$P_0P_j$ と $P_jP_{n+2}$ のうち対角線であるもの（$j\ne1$ なら $P_0P_j$、$j\ne n+1$ なら $P_jP_{n+2}$）を加える。左の分割の三角形、右の分割の三角形、三角形 $P_0P_jP_{n+2}$ で多角形全体が分かれ、対角線どうしは交わらないので、三角形分割になる。その底辺を含む三角形は $P_0P_jP_{n+2}$ なので、段 1・2 を行うと元の $j$ と左右の分割が戻る。また、段 2 で得た組から段 3 を行うと元の分割に戻る。よって 1 対 1 に対応する。$\square$

三角形分割の個数が $C_n$ であること

thm-cat-three の (3) を示す。方針：$T_n$ が $C_n$ と同じ漸化式と初めの値をもつことを示し、強い帰納法で $T_n=C_n$ を示す。
段 1（漸化式）。lem-cat-split で、左の多角形 $P_0\cdots P_j$ は頂点が $j+1$ 個なので分割は $T_{j-1}$ 通り、右の多角形 $P_j\cdots P_{n+2}$ は頂点が $n+3-j$ 個なので $T_{n+1-j}$ 通りである。積の法則と和の法則で
$$ T_{n+1}=\sum_{j=1}^{n+1}T_{j-1}T_{n+1-j}=\sum_{k=0}^{n}T_kT_{n-k} $$
である（$k=j-1$ とおいた）。$T_0=1$ は約束による。
段 2（帰納法）。$T_0=1=C_0$ である。ある $n\ge0$ について $T_0=C_0,\ T_1=C_1,\ \dots,\ T_n=C_n$ が成り立つとすると、段 1 と thm-cat-recursion により
$$ T_{n+1}=\sum_{k=0}^nT_kT_{n-k}=\sum_{k=0}^nC_kC_{n-k}=C_{n+1} $$
である。よってすべての $n$ で $T_n=C_n$ である。$\square$

三角形分割から括弧の列への対応

この証明は、個数が等しいことを示すだけでなく、三角形分割から括弧の列への具体的な対応も与える。

対応の作り方と図 4 での計算を開く

分割 $\Delta$ に対し、底辺を含む三角形で左右の分割 $\Delta_L$、$\Delta_R$ に分け、列を $\texttt{(}\,\varphi(\Delta_L)\,\texttt{)}\,\varphi(\Delta_R)$ と定める（線分の分割には空の列を対応させる）。これを小さい多角形へくり返せば、分割 1 つに正しい列が 1 つ決まる。

図 4 の分割では、左は三角形 $P_0P_1P_2$、右は四角形 $P_2P_3P_4P_5$（対角線 $P_2P_4$）である。

三角形の底辺を含む三角形は自分自身で、左右はどちらも線分なので、対応する列は $\texttt{()}$ である。
四角形 $P_2P_3P_4P_5$ の底辺 $P_2P_5$ を含む三角形は $P_2P_4P_5$ で、左は三角形 $P_2P_3P_4$（列 $\texttt{()}$）、右は線分 $P_4P_5$（空の列）なので、対応する列は $\texttt{(())}$ である。

よって、図 4 の分割に対応する列は $\texttt{(}\,\texttt{()}\,\texttt{)}\,\texttt{(())}$、つまり $\texttt{(())(())}$ で、確かに 4 組の正しい列である。

Catalan 数の公式

Catalan数の公式

$n\ge0$ について
$$ C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{1}{2n+1}\binom{2n+1}{n} $$
である。

2 つの式が等しいことは、階乗で書くと分かる。
$$ \frac{1}{2n+1}\binom{2n+1}{n}=\frac{1}{2n+1}\cdot\frac{(2n+1)!}{n!\,(n+1)!}=\frac{(2n)!}{n!\,(n+1)!}=\frac{1}{n+1}\cdot\frac{(2n)!}{n!\,n!}=\frac1{n+1}\binom{2n}{n} $$
（2 つ目の等号は $(2n+1)!=(2n+1)\cdot(2n)!$、3 つ目は $(n+1)!=(n+1)\cdot n!$ を使った）。

公式の値

$n=3$：$\dfrac14\dbinom63=\dfrac{20}4=5$。$\dfrac17\dbinom73=\dfrac{35}7=5$ とも一致する。
$n=4$、$n=5$ でも、ex-cat-recursion-values の漸化式の値 $14$、$42$ と一致する。
$n=4$ と $n=5$ の計算を開く
$n=4$：$\dfrac15\dbinom84=\dfrac{70}5=14$。
$n=5$：$\dfrac16\dbinom{10}5=\dfrac{252}6=42$。

経路の数え方（thm-cat-three の (2)）を使うと、対角線を越える経路を折り返して数える 鏡像原理 で $C_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}$ が得られる。この証明は最短経路の数え上げと鏡像原理にある。ここでは、それとは別の、式 $\dfrac1{2n+1}\dbinom{2n+1}{n}$ の「$2n+1$ で割る」ことがそのまま見える証明を述べる。

列を回す

「(」を $n+1$ 個、「)」を $n$ 個並べた長さ $2n+1$ の列 $w=w_1w_2\cdots w_{2n+1}$ を考える。このような列は、「)」を置く $n$ か所を選べば決まるので $\dbinom{2n+1}{n}$ 個ある。最後の高さは $(n+1)-n=1$ である。
$j=0,1,\dots,2n$ について、$w$ の前から $j$ 文字を後ろに回した列
$$ R_j(w):=w_{j+1}w_{j+2}\cdots w_{2n+1}\,w_1w_2\cdots w_j $$
を、$w$ の回転という（$R_0(w)=w$）。高さ $h_1,h_2,\dots,h_{2n+1}$ がすべて $1$ 以上である列を、よい列 と呼ぶ。

よい列と正しい列

長さ $2n+1$ のよい列と、括弧 $n$ 組の正しい列とは、先頭に「(」を 1 つ付けることで 1 対 1 に対応する。とくに、よい列は $C_n$ 個ある。

先頭の「(」を外す

要点：よい列の先頭の「(」を外すと、高さがすべて $1$ ずつ下がり、$0$ 以上の高さをもつ正しい列になる。逆に正しい列の先頭に「(」を付けると、高さがすべて $1$ ずつ上がってよい列になる。

詳しい証明を開く

よい列 $v$ は $h_1\ge1$ なので「(」で始まる。先頭の「(」を外した長さ $2n$ の列を $u$ とすると、$u$ の $i$ 文字目の高さは $v$ の $i+1$ 文字目の高さから $1$ を引いたもので、$0$ 以上である。$u$ は「(」と「)」を $n$ 個ずつ含むので、正しい列である。逆に、正しい列 $u$ の先頭に「(」を付けた列の高さは、$1$ と（$u$ の高さ）$+1$ で、どれも $1$ 以上なので、よい列である。2 つの操作は互いに逆である。$\square$

$n=2$ の 10 個の列

「(」3 個と「)」2 個の列は $\dbinom52=10$ 個ある。回転で移り合うものをまとめると、次の 2 組に分かれる。
$$ \underline{\texttt{((())}},\ \texttt{(())(},\ \texttt{())((},\ \texttt{))(((},\ \texttt{)((()} $$
$$ \underline{\texttt{(()()}},\ \texttt{()()(},\ \texttt{)()((},\ \texttt{()(()},\ \texttt{)(()(} $$
各組はある列の回転 $R_0,R_1,\dots,R_4$ を並べたもので、下線を引いたものがよい列である。どちらの組にも、よい列はちょうど 1 つある。よい列は 2 個で、先頭の「(」を外すと (()) と ()() になり、$C_2=2$ と一致する。$10\mathbin{÷}5=2$ である。

ex-cat-rotations2 で見た「どの列も、回転の中によい列をちょうど 1 つもつ」ことが、いつも成り立つ。

巡回補題

「(」を $n+1$ 個、「)」を $n$ 個並べた長さ $2n+1$ の列 $w$ について、$R_j(w)$ がよい列になる $j\in\{0,1,\dots,2n\}$ はちょうど 1 つある。それは、$w$ の高さ $h_0,h_1,\dots,h_{2n}$ の最小値を $\mu$ とするとき、$h_j=\mu$ となる $j$ のうち最大のものである。

列 ())((() を 2 回続けて読んだときの高さ。最初の 7 文字の間で高さが最小になる最後の点（3 文字目のあと）から 7 文字を読むと、高さはずっと出発点より上にある
図 5 は $n=3$、$w=$ ())((() の例である。高さは $h_0,\dots,h_7=0,1,0,-1,0,1,2,1$ で、$h_0,\dots,h_6$ の最小値 $-1$ をとるのは $j=3$ だけである。$R_3(w)=$ ((()()) の高さは $1,2,3,2,3,2,1$ で、確かによい列である。

高さが最後に最小になる場所から読む

要点：$w$ を 2 回続けて読むと、後半の高さは前半より $1$ ずつ大きい。$R_j(w)$ の高さは「$w$ を 2 回続けて読んだ高さ」と $h_j$ との差なので、$R_j(w)$ がよい列であることは、$j$ から先の $2n+1$ 文字の間ずっと高さが $h_j$ より大きいことと同じである。$h_0,\dots,h_{2n}$ の最小値をとる最後の $j$ から読むとこれが成り立ち、それより前の $j$ から読むと最小の点で、後の $j$ から読むと後半の最小の点（高さ $\mu+1$）で、高さが $h_j$ 以下になる。

詳しい証明を開く

段 1（2 回続けて読む）。$w$ を 2 回続けた長さ $4n+2$ の列 $ww$ の高さを $h_0,h_1,\dots,h_{4n+2}$ とする。はじめの $2n+1$ 文字は $w$ の高さと同じで、$h_{2n+1}=1$ である。後半は同じ文字をもう一度読むので、$0\le i\le 2n+1$ について $h_{2n+1+i}=h_i+1$ である。

段 2（回転の高さ）。$R_j(w)$ は $ww$ の $j+1$ 文字目から $2n+1$ 文字を取り出した列である。よって $R_j(w)$ の $t$ 文字目の高さは $h_{j+t}-h_j$ である（$t=1,2,\dots,2n+1$）。したがって

$$R_j(w)\text{ がよい列}\iff h_{j+t}>h_j\quad(t=1,2,\dots,2n+1)$$

である（高さは整数なので、差が $1$ 以上であることと正であることは同じ）。

段 3（$j_0$ から読むとよい列）。$\mu=\min(h_0,\dots,h_{2n})$ とし、$h_j=\mu$ となる $j\in\{0,\dots,2n\}$ の最大のものを $j_0$ とする。$t=1,\dots,2n+1$ について、$j_0+t\le2n$ なら、$j_0$ が最後の最小なので $h_{j_0+t}>\mu$ である。$j_0+t\ge2n+1$ なら $j_0+t=2n+1+i$（$0\le i\le j_0$）と書けて、段 1 により $h_{j_0+t}=h_i+1\ge\mu+1>\mu$ である。よって段 2 により $R_{j_0}(w)$ はよい列である。

段 4（ほかの $j$ ではよい列でない）。$j\ne j_0$ とする。

$j< j_0$ のとき：$t=j_0-j$（$1\le t\le2n$）とすると $h_{j+t}=h_{j_0}=\mu\le h_j$ なので、$h_{j+t}>h_j$ が成り立たない。
$j>j_0$ のとき：$j_0$ が最後の最小なので $h_j\ne\mu$、よって $h_j\ge\mu+1$ である。$t=2n+1+j_0-j$（$1\le t\le2n$）とすると、段 1 により $h_{j+t}=h_{2n+1+j_0}=h_{j_0}+1=\mu+1\le h_j$ なので、$h_{j+t}>h_j$ が成り立たない。

どちらの場合も、段 2 により $R_j(w)$ はよい列でない。$\square$

組 $(w,j)$ を 2 通りに数える

thm-cat-formula を示す。方針：「列 $w$ と、$R_j(w)$ がよい列になる $j$ との組 $(w,j)$」の個数を、$w$ から数える方法と、よい列から数える方法の 2 通りで数える。
段 1（$w$ から数える）。lem-cat-cycle により、$\dbinom{2n+1}{n}$ 個の列 $w$ のそれぞれに、組になる $j$ がちょうど 1 つある。よって組の個数は $\dbinom{2n+1}{n}$ である。
段 2（よい列から数える）。よい列 $v$ と $j\in\{0,1,\dots,2n\}$ を決めると、$R_j(w)=v$ となる $w$ は、$v$ の後ろの $j$ 文字を前に戻した列ただ 1 つである（回転で前から後ろに回した $j$ 文字を、元に戻す）。この $w$ も「(」を $n+1$ 個、「)」を $n$ 個含む。よって組の個数は、（よい列の個数）$\times(2n+1)$ である。prop-cat-good により、よい列の個数は $C_n$ なので、組の個数は $(2n+1)\,C_n$ である。
段 3（結論）。段 1・段 2 により $(2n+1)\,C_n=\dbinom{2n+1}{n}$、つまり $C_n=\dfrac1{2n+1}\dbinom{2n+1}{n}$ である。これは上で見たとおり $\dfrac1{n+1}\dbinom{2n}{n}$ に等しい。$\square$

ex-cat-rotations2 では、10 個の列が 5 個ずつの 2 組に分かれ、各組によい列が 1 つあった。一般の $n$ でも、段 1・段 2 の数え方は、「$\dbinom{2n+1}{n}$ 個の列を、回転で $2n+1$ 個ずつの組に分け、各組から 1 つずつ代表を選ぶ」ことにあたる（組の中の回転が互いに異なることは rem-cat-group で補う）。「$2n+1$ で割る」の意味がここにある。

例と反例

外す条件	反例	成り立たなくなること
経路が対角線を越えない	越えてよい経路（ex-cat-cross）	個数が $C_n$
多角形が凸	凹四角形（ex-cat-nonconvex）	三角形分割が $C_2=2$ 通り
漸化式の添字の対応	$C_n=\sum_{k=0}^{n}C_kC_{n-k}$ と書く（ex-cat-shift）	漸化式が正しい値を与える
「(」が「)」より 1 個多い	`()()` の回転（ex-cat-balanced-rotation）	よい回転がちょうど 1 つ

反例：対角線を越えてよい経路

$(0,0)$ から $(3,3)$ への最短経路は、対角線の条件がなければ $\dbinom63=20$ 通りある。$C_3=5$ ではない。越える $15$ 通りを除いたものが $C_3$ である。prf-cat-paths の段 3 で使った「$h_i\ge0$ と $y\le x$ が同じ」という対応は、条件のない経路では、高さが負になる列（正しくない括弧の列）も数えてしまう。

反例：凸でない四角形

頂点 $A(0,0)$、$B(4,0)$、$C(1,1)$、$D(0,4)$ の順に結んだ四角形は、頂点 $C$ で内側にへこんだ凹四角形である。対角線 $AC$ は四角形の内部を通り、四角形を三角形 $ABC$ と $ACD$ に分ける。一方、対角線 $BD$ は直線 $x+y=4$ の上にある。へこんだ頂点 $C$ はこの直線より原点の側（$1+1<4$）にあるので、線分 $BD$ は辺 $BC$、$CD$ よりも外側を通り、四角形の内部を通らない。よって $BD$ は三角形分割に使えない。よって三角形分割は 1 通りで、凸四角形の $C_2=2$ 通りと違う。lem-cat-split の証明で使った「対角線は多角形の内部を通る」ことが、凸でない多角形では成り立たない。

反例：添字をずらした漸化式

漸化式を $C_n=\sum_{k=0}^{n}C_kC_{n-k}$ と書いてしまうと、$n=1$ で $C_1=C_0C_1+C_1C_0=2C_1$ となり、$C_1=0$ が出てしまう。正しくは、左辺の添字 $n+1$ は右辺の添字の和 $n$ より $1$ 大きい。prf-cat-recursion で、外側の 1 組の括弧（最初の「(」とそれに対応する「)」）を取り除いたので、残りの組の数が $1$ 減ったからである。

三角形分割での添字のずれを開く

三角形分割でも、底辺を含む三角形を取り除いた分だけ添字が $1$ ずれる（凸 $(n+2)$ 角形が $C_n$ に対応する）。凸五角形の分割は $C_3=5$ 通りで、$C_5=42$ 通りではない。

反例：「(」と「)」が同数の列を回す

「(」と「)」が 2 個ずつの列 ()() を回すと、$R_0=$ ()()、$R_1=$ )()(、$R_2=$ ()()、$R_3=$ )()( となる。最後の高さが $0$ なので、高さがすべて $1$ 以上になる回転（よい列）は 1 つもない。条件を「$0$ 以上」にゆるめると、今度は $R_0$ と $R_2$ の 2 つになる。さらに、4 つの回転のうち異なる列は 2 つしかない。このため、prf-cat-formula のように「回転の組ごとに代表を 1 つ選んで割り算する」ことができない。lem-cat-cycle では、「(」を 1 個多くして最後の高さを $1$ にしたことが効いている。

大学数学で見る

母関数と2次方程式

Catalan 数を係数にもつ式 $C(x)=C_0+C_1x+C_2x^2+\cdots$（母関数）を考えると、漸化式 thm-cat-recursion は
$$ C(x)=1+x\,C(x)^2 $$
という 1 つの式にまとまる。右辺の $x\,C(x)^2$ の $x^{n+1}$ の係数が $\sum_{k=0}^nC_kC_{n-k}$ だからである。これを $C(x)$ の 2 次方程式として解くと $C(x)=\dfrac{1-\sqrt{1-4x}}{2x}$ となり、$\sqrt{1-4x}$ を一般二項定理で展開すると thm-cat-formula がもう一度得られる。

展開の計算を開く

一般二項定理（二項定理と組合せの恒等式）により $\sqrt{1-4x}=\sum_{m\ge0}\dbinom{1/2}{m}(-4x)^m$ で、$m\ge1$ では $\dbinom{1/2}{m}(-4)^m=-\dfrac{2}{m}\dbinom{2m-2}{m-1}$ となる（$m=1$ で $-2$、$m=2$ で $-2$、$m=3$ で $-4$）。よって $1-\sqrt{1-4x}=\sum_{m\ge1}\dfrac2m\dbinom{2m-2}{m-1}x^m$ で、$2x$ で割って $m=n+1$ とおくと、$x^n$ の係数は $\dfrac1{n+1}\dbinom{2n}{n}$ である。2 次方程式のもう 1 つの解 $\dfrac{1+\sqrt{1-4x}}{2x}$ は $x=0$ の近くで有限の値にならないので、母関数にならない。形式的冪級数としての扱いは形式的冪級数の積と逆数、母関数の考え方は母関数：数列を関数として扱うで扱う。

二分木と、ほかの Catalan 数の対象

prf-cat-recursion の分け方 $\texttt{(}A\texttt{)}B$ は、「根から左右に枝分かれし、左に $A$、右に $B$ がぶら下がる」木の形と同じである。実際、葉以外の点から必ず 2 本の枝が左右に出る木（二分木）で、葉が $n+1$ 個のものは $C_n$ 個ある。

ほかの対象について開く

このほかにも、Catalan 数で数えられる対象は数百種類知られており、それらの間の 1 対 1 の対応を作ることは組合せ論の一つの主題になっている。

回転と群の作用

巡回補題とその数え方は、大学で学ぶ「群の作用」の典型的な例である。

群の作用の言葉と、回転が互いに異なることの確かめ方を開く

prf-cat-formula の回転 $R_0,R_1,\dots,R_{2n}$ は、$R_i$ のあとに $R_j$ を行うと $R_{i+j}$（添字は $2n+1$ で割った余り）になる。このような「操作の集まり」を群といい、群が列の集合に作用するという。回転で移り合う列の集まりを軌道という。巡回補題は、各軌道の大きさが $2n+1$ で、各軌道によい列がちょうど 1 つあることを示しており、個数を軌道の大きさで割る考え方の典型的な例になっている。

各軌道の大きさが $2n+1$ であること、つまり 1 つの列 $w$ の $2n+1$ 個の回転 $R_0(w),\dots,R_{2n}(w)$ が互いに異なることも、巡回補題から分かる。$R_i(w)=R_j(w)$（$0\le i< j\le2n$）とすると、両方をさらに $2n+1-i$ 文字回して、$d=j-i$ について $R_d(w)=w$ となる（$1\le d\le2n$）。すると、$j_0$ を lem-cat-cycle のよい回転の位置として、$R_{j_0+d}(w)=R_{j_0}(R_d(w))=R_{j_0}(w)$（添字は $2n+1$ で割った余り）もよい列になる。$j_0+d$ の余りは $j_0$ と異なるので、よい列になる回転が 2 つあることになり、lem-cat-cycle の「ちょうど 1 つ」に反する。なお、prf-cat-formula の証明そのものは、この事実を使っていない。

演習

$C_6$ を求める

漸化式 thm-cat-recursion と thm-cat-formula の両方で $C_6$ を求めよ。

解答を開く

漸化式：$C_0,\dots,C_5=1,1,2,5,14,42$ を使って

$$C_6=C_0C_5+C_1C_4+C_2C_3+C_3C_2+C_4C_1+C_5C_0=42+14+10+10+14+42=132$$

である。公式：$C_6=\dfrac17\dbinom{12}{6}=\dfrac{924}{7}=132$ で一致する。

つり銭の足りる並び方

500 円の品物を売る店に、500 円玉を 1 枚持った客 $n$ 人と、1000 円札を 1 枚持った客 $n$ 人の、計 $2n$ 人が 1 列に並ぶ。店は最初つり銭を持っておらず、受け取った 500 円玉だけをつり銭に使う。並び方 $\dbinom{2n}{n}$ 通り（500 円玉の客どうし、1000 円札の客どうしは区別しない）がすべて同じ確からしさで起こるとき、途中でつり銭が足りなくならない確率を求めよ。

解答を開く

500 円玉の客を「(」、1000 円札の客を「)」に置き換える。つり銭として手元にある 500 円玉の枚数は、その時点までの高さに等しい。1000 円札の客が来たときにつり銭が足りることは、その客を数えたあとの高さが $0$ 以上であることと同じである。よって、つり銭が足りなくならない並び方は括弧 $n$ 組の正しい列で、$C_n=\dfrac1{n+1}\dbinom{2n}{n}$ 通りある。確率は $\dfrac{C_n}{\binom{2n}{n}}=\dfrac1{n+1}$ である。たとえば $n=3$ なら $\dfrac5{20}=\dfrac14$ である。

さらに先へ

$(0,0)$ から $(n,n)$ への対角線を越えない経路の数が $\dfrac1{n+1}\dbinom{2n}{n}$ になることは KT17 §2.5 の Example 2.28（pp. 27–28）にあり、二分木の母関数が $C(x)=x+C(x)^2$ をみたし、その係数が Catalan 数になることは同書 §9.7 の Theorem 9.28（pp. 205–207）にある（そこでの添字は本記事と 1 ずれている）。
Bog17 §1.3.1 の Problem 51・52（pp. 20–22）は、鏡像原理による公式の導き方と、割り算の意味を経路で説明する別の方法（本記事の回転とは別の分け方）を、問題の形で導く。§4.3.5 の Problem 224（p. 89）は、漸化式から 2 次方程式と一般二項定理で公式を導く。
大学向けの記事 Catalan数では、ほかの数え上げの対象と、$n$ が大きいときの大きさ $C_n\approx\dfrac{4^n}{n\sqrt{\pi n}}$ を扱う。