次： カタラン数の生成関数 上： カタラン数を生成関数で求める 前： カタラン数を生成関数で求める

$c_n$ の漸化式

経路が最後に対角線に乗った番号で分類することにより，

$$c_n=c_0c_{n-1}+c_1c_{n-2}+ \cdots + c_{n-1}c_0$$

なぜなら

すべての経路を, 最後に対角線に乗った番号で分類する. 対角線 AB 上第 $k$ 番 $\ (k=0,\,1,\,\cdots,\,n-1)$ までの経路の総数は

$$c_k\,(通り)$$

このあとは再び対角線には乗らないのであるから, 図のように

$$c_{n-k-1}\,(通り)$$

したがって, $k=0,\,1,\,\cdots,\,n-1$ の各場合の数を加えることにより

$$c_n=c_0c_{n-1}+c_1c_{n-2}+ \cdots + c_{n-1}c_0$$