次: 生成関数による別解 上: 生成関数の方法 前: 二つの入試問題

生成関数

南海　実は青空学園ではすでにいちど生成関数を使って入試問題の一般化を解いている． 98年の京大の入試問題の一般化だ．これを後で紹介しよう． ここで少し生成関数についてまとめよう．

数列 $\{ a_n \}\ (n=0，1，2，\cdots)$ がある． $n=1$ から始まるときは $a_0=0$ とすればよい． 有限数列なら，あるところから先の項はすべて 0 とすれば， 有限,無限数列関係なく考えられる. この数列に対して, 各項 $a_n$ を係数とする無限級数

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

を考え，これを数列の「生成関数」と呼ぶことにする． これは無限級数なので収束しなければ「関数」とはいえない. 十分小さい $t$ で

$$a_0+a_1t+a_2t^2+a_3t^3+\cdots=b_0+b_1t+b_2t^2+b_3t^3+\cdots$$

が成り立てば,

$$a_i=b_i\ \ i=0，1，2，\cdots$$

がいえる． 生成関数を考えその関係式から係数の関係を導くためには， 収束半径が 0 でさえなければよい． したがってひとつひとつの関数について収束する $t$の範囲を考える必要はない.

二つの生成関数

$$f(t)=a_0+a_1t+a_2t^2+a_3t^3+\cdots， \quad g(t)=b_0+b_1t+b_2t^2+b_3t^3+\cdots$$

に対して

$$\begin{eqnarray*} f(t)+g(t)&=&(a_0+b_0)+(a_1+b_1)t+(a_2+b_2)t^2+\cdots \\ f(t... ...=&\sum _{n=0}^{\infty} \left(\sum_{k=0}^na_kb_{n-k} \right)t^n \end{eqnarray*}$$

となる.

基本的な生成関数

1. $a_i=1\ \ i=0，1，2，\cdots$ のとき. $f(t)=1+t(1+t+t^2+\cdots )=1+tf(t)$なので，
   
   $$f(t)=1+t+t^2+t^3+\cdots =\dfrac{1}{1-t}$$
   
   

2. $a_i=i\ \ i=0，1，2，\cdots$ のとき.
   $$\begin{eqnarray*} f(t)&=&t+2t^2+3t^3+4t^4\cdots \\ f(t)-tf(t)&=&(t+2t^2+3t^3+... ...+2t^3+3t^4+4t^5\cdots)\\ &=&t+t^2+t^3+\cdots=\dfrac{1}{1-t}-1 \end{eqnarray*}$$
   
   
   ゆえに
   
   $$f(t)=\dfrac{t}{(1-t)^2}$$
   
   

3. $a_i=\dfrac{1}{i!}\ \ i=0，1，2，\cdots$ のとき. $f'(t)=f(t)$なので
   
   $$f(t)=1+t+\dfrac{1}{2!}t^2+\dfrac{1}{3!}t^3+\cdots=e^t$$
   
   

この生成関数の方法は，実に強力なものだ．漸化式を解くのにも役立つ．漸化式が与えられると, それに対応して f(t) の関係式が得られる. それをもとに, f(t) の級数展開の一般項をつくれば, それによって係数の一般項が得られる．三項間漸化式を生成関数で解く方法などもまた説明しよう．