次： $c_n$の漸化式 上： 生成関数の方法 前： 生成関数による別解

カタラン数を生成関数で求める

図1のように $\mathrm{AB}$ が対角線である正方形の各辺が $n$ に区切られ，小正方形 $n^2$ に分け られている．

$\mathrm{A}$ から $\mathrm{B}$ への最短経路のうち対角線 $\mathrm{AB}$ より上半分には出ない （対角線に乗るところまでは許される）経路の総数を $c_n$ とする．ただし $c_0=1$ とする．

 

 

 

• $c_n$ の漸化式
• カタラン数の生成関数