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

場合分けを用いて $c_{n+1}$ を数える。

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

場合分けを用いて $c_{n+1}$ を数える。

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

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

場合分けを用いて $c_{n+1}$ を数える。

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

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

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