## 定義 母関数(generating function)とは、数列 f0, f1, f2, ... を係数として持つ形式的な無限級数 F(x) = f0 + f1 x + f2 x^2 + f3 x^3 + ... のことである。数列そのものを直接扱う代わりに、その係数を担う代数的対象 F(x) を扱うことで、数列に関する問題を代数的操作(和・積・シフト・微分)の問題へと変換できる。[x^n]F(x) := fn は F(x) の x^n の係数を取り出す記法である。母関数には ordinary(通常型)・exponential(指数型)・Dirichlet 型など複数の流儀があるが、単に「母関数」と言うときは通常型(ordinary generating function)を指すことが多い。有理関数(多項式の商)として表せる母関数からは、部分分数分解によって係数の閉じた形の公式を機械的に取り出せる。数列を選び方の集合として解釈すると、互いに素な2つの集合からの選び方の和集合に対する母関数は、それぞれの母関数の積(畳み込み)として得られる(畳み込み則、Convolution Rule)。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] §15.1〜§15.2) ## 横断的知見 - 母関数による線形漸化式の解法と特性方程式による解法の関係(第15章と第21章の突き合わせ)。第21章は斉次線形漸化式 f(n) = a1 f(n-1) + ... + ad f(n-d) を、解の形が指数関数 x^n であると**仮定**して代入し、特性方程式 x^d = a1 x^(d-1) + ... + ad を立てて根を求める手法(cookbook 的手続き)で解く。これに対し第15章は、同じ漸化式(フィボナッチ数列 fn = f(n-1) + f(n-2)、ハノイの塔 tn = 2 t(n-1) + 1)を、数列の母関数 F(x) を未知数とみなし、F(x) と xF(x)(・x^2 F(x)、…)を並べてシフトさせ差し引くことで F(x) を有理関数として求め、その後に部分分数分解して係数 fn を読み取るという手順で解く。この2つの手法は独立に発見的な性質が異なる。特性方程式は「解の形を先に仮定する」という天下り的な一手を要するのに対し、母関数法は「母関数を未知数とする方程式を機械的に立てる」だけで済み、仮定を要しない点で作業手順として一段階シンプルである。他方で、母関数法は最終段階で部分分数分解という別の技法を要求するため、根が単純な場合(たとえばフィボナッチ数列やハノイの塔のように分母の次数が低い場合)には両手法の労力は同程度になる。実際、フィボナッチ数列の母関数 x/(1-x-x^2) の部分分数分解(第15章 §15.3〜§15.4.1)で得られる係数 c1, c2 は、特性方程式 x^2=x+1 の根 (1±√5)/2 の逆数に一致しており、部分分数分解の分母 (1-α1 x)(1-α2 x) の α1, α2 は特性方程式の根の逆数そのものである。つまり2つの手法は表面上異なる代数操作(シフトと差分 vs. 指数関数の仮定と代入)を経由するが、最終的に同じ特性方程式の根に帰着する同型の計算であり、母関数法は特性方程式による解法を「なぜ解が x^n の形になるのか」という天下り的な仮定なしに、シフト演算という母関数の基本操作だけから再導出したものと理解できる。第21章の脚注はこの関係を「母関数を使えば推測なしに解ける」と一言で示唆するにとどめていたが、本節の突き合わせにより、両者は独立した手法というより「同じ特性方程式に至る2つの経路」であることが分かる。なお非斉次線形漸化式についても対応関係は保たれる。第21章は非斉次項 g(n) に対して同じ形の特殊解を推測する(試行関数法)という天下り的な一手を要するのに対し、第15章 §15.4.3 は非斉次項 h(n) 自身の母関数が有理関数であれば、その母関数を漸化式の母関数の式にそのまま代入するだけで済み、ここでも「試行関数を推測する」という天下り性を回避できる。この意味で母関数法は特性方程式法より発見的仮定の少ない、より機械的な手続きだと言える。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] §15.3〜§15.4, [[漸化式]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.3〜§21.4) - 母関数の積が数列の畳み込みに対応するという事実(畳み込み則)は、第14章のブックキーパー則・二項定理と表裏一体である。第14章はブックキーパー則(k 種類のものから重複を許してn個選ぶ場合の数)や二項定理を数え上げ論法(組合せ論的証明)によって直接導くのに対し、第15章はこれらを母関数の積の係数として代数的に再導出する(1/(1-x)^k の係数がブックキーパー則の式に、(1+x)^m の係数が二項係数に一致する)。同じ結論に数え上げ的経路と代数的経路の両方から到達できることは、母関数が「数え上げ問題を代数の言葉に翻訳する」という本章冒頭の主張の具体例になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] §15.2.1, §15.2.4〜§15.2.5, [[数え上げ]]) ## 未解決の問い - 指数型母関数(exponential generating function)や Dirichlet 母関数は本章では名前だけ挙げられ、扱いは通常型に限定されている。順列や集合分割の数え上げで通常型の畳み込み則がうまく機能しない場面(たとえば要素の順序を区別する数え上げ)を扱う他ソースが ingest されたら、指数型母関数との使い分けを横断的知見として追記したい。 - Z変換(Z-transform)が母関数と密接に関連すると本章冒頭で述べられているが、制御理論・信号処理の文脈での対応関係(畳み込みが伝達関数の積に対応する等)は本章の範囲外。制御理論・信号処理を扱う他ソースが ingest されたら、この対応を横断的知見として追記したい。 - 特性方程式法と母関数法のどちらが計算量的に有利かは、根の重複度や非斉次項の複雑さに依存すると推測されるが、本章・第21章のいずれも計算量比較を明示的に論じていない。アルゴリズム解析や計算代数を扱う他ソースが ingest されたら、この比較を補強したい。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] - 概念: [[形式的べき級数]](母関数を係数列として厳密に基礎付ける枠組み) / [[漸化式]](特性方程式による解法との横断的知見) / [[数え上げ]](畳み込み則・二項定理との対応) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 15, §15.1〜§15.4.