生成関数

『数学ガール』の隣に、プログラムの教科書を置く。生成関数が二冊をつなぐ。片方は数列を一本の式に束ね、もう片方はその係数を一つずつ取り出す仕組みを組む。無限の列を見る目が、式からプログラムへ持ち替わる棚だ。

数列を、係数の席に座らせる

数列 a₀, a₁, a₂, … に対して、G(x) = a₀ + a₁x + a₂x² + … と置く。xの何乗かが項の番号、その係数が数列の値になる。これが通常型の生成関数、または母関数だ。

まずは形式的べき級数として考えられるので、xに数値を代入して収束するかどうかを決めなくても、係数ごとの加算や乗算を扱える。実数・複素数の関数として読むときには、別に収束などの条件が必要になる。

数学ガールの第4章は、フィボナッチ数列と母関数を扱う。F₀ = 0、F₁ = 1、Fₙ = Fₙ₋₁ + Fₙ₋₂ という関係を係数に並べると、G(x) = x + x² + 2x³ + 3x⁴ + … になる。

一つずらしたxG(x)、二つずらしたx²G(x)を引けば、漸化式によって高い次数の係数が消える。残る関係は (1 − x − x²)G(x) = x。数列の規則が、G(x) = x / (1 − x − x²) という式にまとまる。

無限に続く項を一つずつ追う代わりに、全体の関係を式として持つ。この見方を物語の中でたどる入口が『数学ガール』だ。

計算機プログラムの構造と解釈第2版、通称SICPの3.5.2には、べき級数の係数を無限ストリームとして表す演習がある。必要な先までを計算する流れとして、係数列をプログラムで持つ。

演習3.59から3.62へ進むと、係数から積分した級数を作り、級数どうしの積を計算し、逆数や商を組み立てる。ここでつながるのは、生成関数という名前の解説ではなく、同じ係数表現を操作する部分だ。

『数学ガール』から式を持ってきて、SICPで係数を扱う手つきを見る。一本の式に束ねた数列が、欲しい項を取り出せる流れとして姿を変える。この二冊は、数学とプログラミングの境目に並べたい。