次: ある入試問題の一般化への生成関数の活用 上: 生成関数の方法 前: 生成関数による別解

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

図1のように $\mathrm{AB}$ が対角線である正方形の各辺が $n$ に区切られ，小正方形 $n^2$ に分け られている． $\mathrm{A}$ から $\mathrm{B}$ への最短経路のうち対角線 $\mathrm{AB}$ より上半分には出ない （対角線に乗るところまでは許される）経路の総数を $c_n$ とする．ただし $c_0=1$ とする．

$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$$

カタラン数の生成関数

$$f(t)=c_0+c_1t+c_2t^2+c_3t^3+\cdots$$

とする．すると

$$\begin{eqnarray*} f(t)^2&=&c_0^2+(c_0c_1+c_1c_0)t+(c_0c_2+c_1c_1+c_2c_0)t^2 +\... ...d \{f(t)^2-c_0^2\}t&=&c_2t^2+c_3t^3+\cdots \\ &=&f(t)-c_0-c_1t \end{eqnarray*}$$

$c_0=c_1=1$ であることに注意すると，

$$tf(t)^2-f(t)+1=0$$

を得る.

ここで $y=f(t)$ とおこう. $ty^2-y+1=0$ より,

$$y=\dfrac{1\pm\sqrt{1-4t}}{2t}=\dfrac{4t}{(1\mp \sqrt{1-4t})\cdot 2t} =\dfrac{2}{1\mp\sqrt{1-4t}}\quad(複号同順)$$

$t\to 0$ のとき $y\to c_0=1$ とならねばならないので,

$$y=\dfrac{2}{1+\sqrt{1-4t}}=\dfrac{1-\sqrt{1-4t}}{2t}$$

ここで, 一般に何度も微分できる関数 $f(x)$ は

$$f(x)=f(0)+f'(0)x+\dfrac{f''(0)}{2!}t^2+\cdots+\dfrac{f^{(k)}(0)}{k!}t^k+\cdots$$

と級数に展開されることを用いる.これは $f(x)$ を

$$f(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots$$

とおくと

$$f^{(k)}(x)=k!a_k+(k+1)!a_{k+1}t+\dfrac{(k+2)!}{2!}a_{k+2}x^2+\cdots$$

より

$$f^{(k)}(0)=a_k\cdot k!$$

となるのでわかる.

$$\begin{eqnarray*} (1-4t)^{\frac{1}{2}} &=&1+\dfrac{1}{2}(-4t)+\dfrac{\dfrac{1}... ...t) \cdots\left(\dfrac{1}{2}-n\right)}{(n+1)!}(-4t)^{n+1}+\cdots \end{eqnarray*}$$

この $t^{n+1}$ の係数は

$$\begin{eqnarray*} &&\dfrac{1}{(n+1)!}\cdot\dfrac{1}{2^{n+1}}\cdot(-1)^n\cdot(2n... ...2n-1) \cdots 1 \\ &=& -\dfrac{2}{n+1}\cdot\dfrac{(2n)!}{n!n!} \end{eqnarray*}$$

よって, $\dfrac{1-\sqrt{1-4t}}{2t}$ の $t^n$ の係数は

$$\dfrac{{}_{2n} \mathrm{C}_{n}}{n+1}$$

つまり,

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

耕一　なるほど．

南海　入試問題もその気になって探求すると，いろんな広がりがあるのだ.

 

次: ある入試問題の一般化への生成関数の活用 上: 生成関数の方法 前: 生成関数による別解