生成関数

数列をべき級数の「係数」として読み替える——それだけで、代数と解析が融合する。生成関数とは、数列 a₀, a₁, a₂, ... を形式的べき級数 a₀ + a₁x + a₂x² + ... として表現する手法だ。数列の問題を関数の問題に変換することで、微分・積分・部分分数分解などの解析的ツールが使えるようになる。この「見方の変換」が持つ力は、組み合わせ論から確率論、コンピュータサイエンスまで、驚くほど広い射程を持つ。

数学ガールでの登場

数学ガールで結城浩は、生成関数をフィボナッチ数列の一般項導出という具体的な問題を通じて描いた。フィボナッチ数列 F(n) の生成関数 G(x) = Σ F(n)xⁿ を立式し、漸化式から G(x) の閉じた形 G(x) = x/(1-x-x²) を導く。これを部分分数分解してべき級数に展開すると、Binet の公式（黄金比を含む一般項公式）が自然に出てくる。生成関数という「迂回路」を経ることで、漸化式の直接的な解法よりもはるかに美しく一般項を求められる。ミルカがこの過程を展開する場面は、「数学の美しさとは別の道から同じ頂に登ること」を体感させる。

組み合わせ論での威力

生成関数は組み合わせ論（数え上げ数学）で特に強力だ。「n 個から k 個を選ぶ組み合わせの数」を数え上げる問題は、生成関数を使って系統的に解ける。例えば「コインを n 回投げて表が k 回出る確率」は、生成関数 (1/2 + 1/2 x)ⁿ の xk の係数として読み取れる。「n 段の階段を1段または2段ずつ上る方法の数」はフィボナッチ数列になる——生成関数はこれを代数的に確認する。指数型生成関数（EGF）は順列問題に使われ、ベル多項式・スターリング数などの組み合わせ論的量の生成関数として自然に現れる。

確率論・情報理論との繋がり

確率の「モーメント生成関数」は生成関数の確率論版だ。確率変数の分布の特性（平均・分散・歪度・尖度）を生成関数から取り出せる。これは統計学・機械学習での確率モデルの解析に使われる。情報理論では、分布のエントロピーもある種の生成関数として表現できる。コンピュータサイエンスでは、アルゴリズムの時間複雑度の解析に生成関数が使われる（マスター定理の証明など）。数学的帰納法が「命題の構造から証明を組み立てる」アプローチなら、生成関数は「問題の構造を代数的に捉える」アプローチだ。数学の美しさの一つが「異なる分野の数学が同じ構造を持つとき」だとすれば、生成関数はその実例として最も豊かなものの一つだ。

生成関数の魔法：離散を連続で解く

生成関数の核心的な魔法は、離散的な数列という対象を連続的な関数（冪級数）というツールで分析できるようにする点にある。数列の各項を冪級数の係数として埋め込むことで、代数的な操作（加算・乗算・微分・積分）が数列の操作に対応する。例えば二つの数列の「畳み込み」（各項をすべての組み合わせで掛けて合計する操作）は、対応する生成関数の乗算として表現できる。この対応関係を使うことで、組み合わせ論の複雑な計算が代数的な変形問題に変換される。

生成関数はコンピュータサイエンスでも重要な道具だ。アルゴリズムの計算量解析、データ構造の性能評価、確率的アルゴリズムの解析などで登場する。また統計学における「モーメント母関数」や「特性関数」は確率分布の生成関数の変種であり、確率変数の和の分布を計算する際に力を発揮する。生成関数は「フォーマルな冪級数」として収束を気にせず形式的に操作できるという点で、代数的な道具としての純粋な便利さも持っている。

生成関数はフィボナッチ数列の一般項を求めるビネの公式の導出に用いられる——漸化式を生成関数に変換し、部分分数分解することで閉じた公式が得られる。数学的帰納法が「前から順に積み上げる」アプローチなら、生成関数は「全体を一気に捉える」アプローチとして相補的な関係にある。ゼータ関数は素数の分布に関わる生成関数の一種として、数論の深い構造を解析する道具だ。