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

カタラン数

南海　この $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}$ への最短経路の総数から対角線を越え出る場合の 総数を減じる考えにより

$$c_n={}_{2n}\mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}$$

 を示し， $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$ の漸化式を見てほしい．

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