next up previous
次: カタラン数の意味 上: カタラン数 前: ある入試問題

カタラン数

南海 この $N(i,j)$ のことを普通はカタラン数と呼んでいる.

それではまず,$i=j=n$ のとき,つまり $N(n,n)$ を考えよう.

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

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

$c_n$ を求めるほうほうは二つある.ひとつは技巧的な工夫をするものだ.


 

 

例 1.2.2   図2を参考にして, $\mathrm{A}$ から $\mathrm{B}$ への最短経路の総数から対角線を越え出る場合の 総数を減じる考えにより

\begin{displaymath}
c_n={}_{2n}\mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}
\end{displaymath}
 を示し, $c_n$ の式を求めよ.

解答

不適な場合は必ず対角線を越え出るので, 最初に対角線を越えて到達した点を C とする. C から AB に平行な向きを対称軸として折り返すと, C から B に至る経路が図の $\mathrm{B}'$ に至る経路となる. 逆に, A から $\mathrm{B}'$ に至る経路を最初に上半分の領域に入った点で逆 に折り戻すことにより, B へ一度は対角線を越えてから至る経路となる. このように, A から B へ対角線を越えて至る経路と A から $\mathrm{B}'$ への経路が対応している. したがって, 求める 経路の数は A から B に至るすべての経路の数から上の経路の数を減ずればよい. すなわち,

\begin{eqnarray*}
c_n&=&{}_{2n} \mathrm{C}_{n}-{}_{2n} \mathrm{C}_{n-1}
=\dfra...
...)!}{n!n!}\cdot\dfrac{1}{n+1}=\dfrac{{}_{2n} \mathrm{C}_{n}}{n+1}
\end{eqnarray*}

ここで$c_2,c_3,c_4$ を求めておこう.

\begin{eqnarray*}
&&c_2=\dfrac{{}_4 \mathrm{C}_2}{3}=\dfrac{4\cdot3}{3\cdot2\cd...
...}{5}
=\dfrac{8\cdot7\cdot6\cdot5}{5\cdot4\cdot3\cdot2\cdot1}=14
\end{eqnarray*}
 

南海 $c_n$ の漸化式は「生成関数の方法」のなかの$c_n$ の漸化式を見てほしい.

一般的な生成関数による方法がある. これは『数学対話』「生成関数の方法」を見てほしい.



Aozora Gakuen