Catalan数

長さ $2(n+1)$ の Dyck 列 $s=(s_1,\dots,s_{2n+2})$ をとる。部分和 $s_1+\cdots+s_k$ が $0$ になる最小の $k\ge1$ を $k_0$ とする（$k=2n+2$ で和は $0$ なので $k_0$ は存在する）。部分和は $1$ ずつ変わるので $k_0$ は偶数で、$k_0=2i+2$（$0\le i\le n$）と書ける。$s_1=+1$ である（$s_1=-1$ なら最初の部分和が負になる）。$s_{k_0}=-1$ である（直前の部分和が正で、$k_0$ 番目で $0$ になるので）。$s_2,\dots,s_{k_0-1}$ の部分和はどれも $s_1$ までの部分和 $1$ を引くと $0$ 以上であり（$k_0$ より前で部分和は $1$ 以上）、合計は $0$ なので、$\alpha:=(s_2,\dots,s_{2i+1})$ は長さ $2i$ の Dyck 列である。また $\beta:=(s_{2i+3},\dots,s_{2n+2})$ は、部分和 $0$ の位置から始まる残りの部分なので、長さ $2(n-i)$ の Dyck 列である。
逆に、$0\le i\le n$ と、長さ $2i$ の Dyck 列 $\alpha$ と長さ $2(n-i)$ の Dyck 列 $\beta$ から、列
$$(+1,\ \alpha,\ -1,\ \beta)$$
を作ると、これは長さ $2n+2$ の Dyck 列で、部分和が最初に $0$ になる位置は $2i+2$ である（$\alpha$ の部分でも部分和は $1$ 以上）。二つの対応は互いに逆であり、最初の復帰位置 $2i+2$ ごとに Dyck 列は $C_iC_{n-i}$ 個ある。$i$ について足し合わせて主張を得る。$\square$

$S_0:=0$、$S_k:=s_1+\cdots+s_k$（$1\le k\le2n+1$）とおく。$S_{2n+1}=-1$ である。さらに $k>2n+1$ に対しても、$s$ を周期 $2n+1$ で延長して $s_{k}:=s_{k-(2n+1)}$ とし、同じ式で $S_k$ を定める。1 周期の和は $-1$ なので、$0\le k'\le2n$ に対し $S_{k'+2n+1}=S_{k'}-1$ である。$s^{(r)}$ の最初の $j$ 項の和は $S_{r+j}-S_r$ なので、
$$s^{(r)}\text{ がよい列}\iff r< k\le r+2n\text{ を満たすすべての }k\text{ で }S_k\ge S_r$$
である。
$m:=\min\{S_0,S_1,\dots,S_{2n}\}$ とし、$S_r=m$ となる最小の $r\in\{0,\dots,2n\}$ をとる。この $r$ で $s^{(r)}$ がよい列であることを示す。$r< k\le2n$ なら $S_k\ge m=S_r$ である。$2n< k\le r+2n$ なら $k=k'+2n+1$（$0\le k'< r$）と書け、$r$ の最小性から $S_{k'}>m$、すなわち $S_{k'}\ge m+1$ なので、$S_k=S_{k'}-1\ge m=S_r$ である。
逆に $s^{(r)}$ がよい列であるとする。$r< k\le2n$ なら $S_k\ge S_r$ である。$0\le k'< r$ なら $k=k'+2n+1$ は $r< k\le r+2n$ を満たすので $S_{k'}-1=S_k\ge S_r$、すなわち $S_{k'}>S_r$ である。よって $S_r$ は $S_0,\dots,S_{2n}$ の最小値 $m$ であり、$r$ はそれを達成する最小の添字である。したがって条件を満たす $r$ はただ 1 つである。$\square$

$+1$ を $n$ 個、$-1$ を $n+1$ 個並べた列の全体を $W$ とする。$W$ の列は $+1$ の位置 $n$ 個を $2n+1$ 個の位置から選べば決まるので、$|W|=\binom{2n+1}{n}$ である。組 $(s,r)$（$s\in W$、$0\le r\le2n$）で $s^{(r)}$ がよい列となるものの集合 $Z$ の元の個数を 2 通りに数える。
lem-catalan-numbers-cycle により、各 $s\in W$ についてそのような $r$ はちょうど 1 つなので、$|Z|=|W|=\binom{2n+1}{n}$ である。一方、写像 $(s,r)\mapsto(s^{(r)},r)$ は、$Z$ から「よい列 $t$ と $r\in\{0,\dots,2n\}$ の組」全体への全単射である（$t$ と $r$ から、$t$ を逆向きに $r$ 個ずらして $s$ が一意に復元され、$s\in W$ である）。よい列は $C_n$ 個あるので $|Z|=(2n+1)C_n$ である。したがって
$$C_n=\frac{1}{2n+1}\binom{2n+1}{n}=\frac{(2n+1)!}{(2n+1)\,n!\,(n+1)!}=\frac{(2n)!}{n!\,(n+1)!}=\frac{1}{n+1}\binom{2n}{n}$$
である。$\square$

thm-catalan-numbers-formula により
$$\frac{C_{n+1}}{C_n}=\frac{(2n+2)!}{(n+1)!\,(n+2)!}\cdot\frac{n!\,(n+1)!}{(2n)!}=\frac{(2n+2)(2n+1)}{(n+1)(n+2)}=\frac{2(2n+1)}{n+2}$$
である。$\square$

$0\le k<2n$ について $\binom{2n}{k+1}\Big/\binom{2n}{k}=\frac{2n-k}{k+1}$ であり、これは $k\le n-1$ のとき $1$ より大きく、$k\ge n$ のとき $1$ より小さい。したがって $\binom{2n}{k}$（$0\le k\le2n$）の中で最大のものは $\binom{2n}{n}$ である。二項定理により $\sum_{k=0}^{2n}\binom{2n}{k}=2^{2n}=4^n$ であり、この和は $2n+1$ 個の項からなるので
$$\frac{4^n}{2n+1}\le\binom{2n}{n}\le4^n$$
である。thm-catalan-numbers-formula の式 $C_n=\binom{2n}{n}/(n+1)$ に代入して主張を得る。$\square$

頂点が $n$ 個の二分木の個数を $b_n$ とする。$b_0=1$（空の木だけ）である。頂点が $n+1$ 個の二分木は、左部分木の頂点の個数 $i$（$0\le i\le n$）と、頂点が $i$ 個の二分木 $L$、頂点が $n-i$ 個の二分木 $R$ の組で一意に決まり、逆にそのような組から一意に作られる。よって $b_{n+1}=\sum_{i=0}^nb_ib_{n-i}$ である。$b_0=C_0$ であり、$b_0,\dots,b_n$ がそれぞれ $C_0,\dots,C_n$ に等しいと仮定すると、prop-catalan-numbers-recurrence により $b_{n+1}=\sum_{i=0}^nC_iC_{n-i}=C_{n+1}$ である。数学的帰納法により、すべての $n$ で $b_n=C_n$ である。$\square$

$m\ge3$ に対し、頂点が $v_1,\dots,v_m$ の順に並ぶ凸 $m$ 角形の三角形分割の個数を $t_m$ とし、便宜上 $t_2:=1$ とおく（辺 1 本を「分割する方法」は何もしない 1 通り）。$t_3=1$ である。$m\ge3$ の三角形分割では、辺 $v_1v_m$ はちょうど 1 つの三角形に含まれ、その三つ目の頂点を $v_k$（$2\le k\le m-1$）とする。三角形 $v_1v_kv_m$ を除くと、多角形は $v_1,\dots,v_k$ の $k$ 角形と $v_k,\dots,v_m$ の $(m-k+1)$ 角形に分かれ（$k=2$ や $k=m-1$ ではその側は辺 1 本だけ）、元の三角形分割は両側の三角形分割の組を与える。逆に、$k$ と両側の三角形分割の組から、三角形 $v_1v_kv_m$ を加えて $m$ 角形の三角形分割がちょうど 1 つ得られる。したがって
$$t_m=\sum_{k=2}^{m-1}t_k\,t_{m-k+1}\qquad(m\ge3)$$
である。$T_n:=t_{n+2}$（$n\ge0$）とおくと、$T_0=1$ であり、$m=n+2$、$i=k-2$ として $T_n=\sum_{i=0}^{n-1}T_iT_{n-1-i}$（$n\ge1$）となる。これは prop-catalan-numbers-recurrence と同じ漸化式であり、初期値も $T_0=C_0=1$ なので、prf-catalan-numbers-binary-trees と同じ帰納法ですべての $n$ で $T_n=C_n$ である。$\square$