次: カタラン数を生成関数で求める 上: 生成関数の方法 前: 生成関数

生成関数による別解

耕一　それでは解いてみます．

解答［横国大の別解］

$t$ の無限級数を

$$\begin{eqnarray*} f(t)&=&a_0+a_1t+a_2t^2+\cdots\\ g(t)&=&3t+3^2t^2+3^3t^3+\cdots \end{eqnarray*}$$

とおく．ここで,

$$g(t)-3t=3^2t^2+3^3t^3+\cdots=3t\cdot g(t)$$

よって

$$g(t)=\dfrac{3t}{1-3t}$$

$$\begin{eqnarray*} f(t)g(t)&=&\sum_{n=1}^{\infty} \left( \sum_{k=1}^n3^ka_{n-k}\right)t^n\\ &=&a_1t+a_2t^2+\cdots\\ &=&f(t)-1 \end{eqnarray*}$$

つまり

$$f(t) \left(1-g(t) \right)=f(t) \left(1-\dfrac{3t}{1-3t} \right) =f(t) \left(\dfrac{1-6t}{1-3t} \right)=1$$

である．よって

$$\begin{eqnarray*} f(t)&=&\dfrac{1-3t}{1-6t}\\ &=&\dfrac{1}{2} \left(1+\dfrac{1}{1-6t} \right)\\ &=&\dfrac{1}{2} (2+6t+(6t)^2+\cdots) \end{eqnarray*}$$

これが $f(t)=a_0+a_1t+a_2t^2+\cdots$ と一致するので $n=1，2，\cdots$に対して

$$a_n=\dfrac{1}{2}\cdot6^n=3\cdot6^{n-1}$$

□

解答［北大の別解］

$a_n\ \ (n=1，2，3，\cdots)$ に対して

$$f(t)=a_1+a_2t+a_3t^2+\cdots$$

とおく.

$$tf(t)=a_1t+a_2t^2+a_3t^3+\cdots$$

である.

$$\begin{eqnarray*} (tf(t))^2&=&\sum_{n=0}^{\infty} \left( \sum_{k=1}^{n+1}a_ka_{... ...c{(2t)^2}{2!}+\dfrac{(2t)^3}{3!}+\cdots \right)\\ &=&t^2e^{2t} \end{eqnarray*}$$

$$したがって \quad tf(t)=\pm te^t， \quad ∴ \quad f(t)=\pm e^t$$

ところが $f(0)=a_1=1$ より $f(t)=e^t$

$$f(t)=1+\dfrac{t}{1!}+\dfrac{t^2}{2!}+\cdots +\dfrac{1}{n!}t^n+\cdots$$

$a_n$ は $t^{n-1}$ の係数なので

$$a_n=\dfrac{1}{(n-1)!}\ \ (n=1，2，3，\cdots)$$

□

南海　ずいぶん簡明に，見通しよく解けるだろう． ただ注意すべきは，たとえば北大の問題の別解だが，これはなにも本質的に新しい解法ではない．

耕一　といいますと…．

南海　実は

$$\begin{array}{l} e^{2t}=1+(2t)+ \dfrac{(2t)^2}{2!}+ \dfrac{... ...cdot(1+t+ \dfrac{t^2}{2!}+ \dfrac{t^3}{3!}+\cdots) \end{array}$$

この二式が形式的無限級数として一致することを示そうとすると結局

$$a_n=\dfrac{1}{(n-1)!}$$

に対して

$$a_1=1，\dfrac{2^n}{n!}=\sum_{k=1}^{n+1}a_ka_{n+2-k}\ \ (n=1，2，3，\cdots)$$

を示さねばならないのだ． 生成関数は数列を統一してひとつの関数として扱う方法だ，ということである．