カタラン数の意味と漸化式

二項係数の定義より，

$$\begin{aligned}&{}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}\\ &=\dfrac{(2n)!}{n!n!}-\dfrac{(2n)!}{(n-1)!(n+1)!}\\ &=\dfrac{(2n)!}{(n-1)!n!}\left(\dfrac{1}{n}-\dfrac{1}{n+1}\right)\\ &=\dfrac{(2n)!}{n!n!}\times\dfrac{1}{n+1}\\ &=\dfrac{{}_{2n}\mathrm{C}_n}{n+1}\end{aligned}$$

場合分けで $a_{n+1}$ を数える。

左下の点 $(0, 0)$ からスタートして対角線をはじめて $(i, i)$ で踏み，$(n+1, n+1)$ まで到着する場合の数は，$a_{i-1}a_{n+1-i}$ 通り。

これを $i=1$ から $n+1$ まで足し上げるとカタラン数の漸化式と一致する。

• $(0,0)$ から $(n,n)$ までの最短経路の総数は ${}_{2n}\mathrm{C}_n$

• そのうち，常に $x\geqq y$ を満たすものが $c_n$（定理3）

よって，あとは「1回でも $x<y$ を満たす最短経路の数」が ${}_{2n}\mathrm{C}_{n-1}$ であることを示せば良い。これは，以下のように「$(0,0)$ から $(n-1,n+1)$ への最短経路」と一対一対応が構成できることからわかる： 1回でも $x<y$ を満たす $(n,n)$ までの経路に対して「はじめて $y=x+1$ 上を通る点 $A$ 以降を $y=x+1$ に関して折返す」と $(0,0)$ から $(n-1,n+1)$ への最短経路になる。逆に，$(0,0)$ から $(n-1,n+1)$ への最短経路に対して，「はじめて $y=x+1$ 上を通る点 $A$ 以降を $y=x+1$ に関して折返す」と 「1回でも $x<y$ を満たす $(n,n)$ への最短経路」になる。

場合分けで $a_{n+1}$ を数える。

$n+2$ 人でトーナメントをするとき，決勝に左側から上がってくる集団が $i+1$ 人の場合，右側は $n-i+1$ 人。左側のトーナメントのやり方は $a_i$ 通りで，右側は $a_{n-i}$ 通り。これを $i=0$ から $n$ まで足し合わせるとカタラン数の漸化式と一致する。

場合分けで $a_{n+1}$ を数える。

$n+3$ 角形の頂点を順番に $A_0, A_1,\cdots, A_{n+2}$ とする。

与えられた三角形分割に対して，$A_{n+1}A_{n+2}A_i$ が分割された三角形の一つであるような $i$ が $0$ から $n$ の間にただひとつ存在する。

それぞれの $i$ について，そのような三角形分割は $a_{i}a_{n-i}$ 通りあり，これを $i=0$ から $n$ まで足し上げると，カタラン数の漸化式と一致する。

$$\begin{aligned} \dfrac{1}{4^n} {c_n} &= \dfrac{1}{n+1} \dfrac{(2n)!}{4^n (n!)^2} \\ &= \dfrac{1}{n+1} \dfrac{(2n)!}{((2n)!!)^2}\\ &= \dfrac{1}{n+1} \dfrac{(2n-1)!!}{(2n)!!} \end{aligned}$$ と計算される。

二乗したものを考える。

$$\begin{aligned} \left( \dfrac{n^{\frac{3}{2}} c_n}{4^n} \right)^2 &= \dfrac{n^3}{(n+1)^2} \left( \dfrac{(2n-1)!!}{(2n)!!} \right)^2\\ &= \dfrac{n^3}{(n+1)^2 (2n+1)} \dfrac{(2n-1)!! (2n+1)!!}{((2n)!!)^2}\\ \end{aligned}$$

1項目，2項目の極限を考える。 $$\begin{aligned} \lim_{n \to \infty} \dfrac{n^3}{(n+1)^2 (2n+1)} &= \dfrac{1}{2}\\ \lim_{n \to \infty} \dfrac{(2n-1)!! (2n+1)!!}{((2n)!!)^2} &= \dfrac{2}{\pi} \end{aligned}$$ （2項目はウォリスの公式による）

よって $$\lim_{n \to \infty} \left( \dfrac{n^{\frac{3}{2}} c_n}{4^n} \right)^2 = \dfrac{1}{\pi}$$ である。

つまり $$\lim_{n \to \infty} \dfrac{n^{\frac{3}{2}} c_n}{4^n} = \dfrac{1}{\sqrt{\pi}}$$ を得る。