次： ある入試問題の一般化への生成関数の活用 上： カタラン数を生成関数で求める 前： の漸化式

カタラン数の生成関数

$$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+\cd... ...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(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots$$

とおくと

より

となるのでわかる.

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

耕一なるほど．

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