次： 基本的な生成関数 上： 生成関数の方法 前： 二つの入試問題

生成関数

南海　　実は青空学園ではすでにいちど生成関数を使って入試問題の一般化を解いている． 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*}$$

となる.

• 基本的な生成関数