母関数

数学において、母関数（ぼかんすう、英: generating function; 生成関数）は、（自然数で添字付けられた）数列 {a_n} に関する情報を内包した係数を持つ、形式的冪級数である。母関数は、一般線型回帰問題の解決のためにド・モアブルによって1730年に初めて用いられた。複数の自然数で添字付けられる数の配列（多重数列）の情報を取り込んだ多変数冪級数を同様に考えることもできる。

母関数には、通常型母関数 (ordinary generating function)、指数型母関数 (exponential generating function)、ランベルト級数 (Lambert series)、ベル級数 (Bell series)、ディリクレ級数 (Dirichlet series) など様々なものがある。これらについては定義と例を後述する。原理的にはあらゆる列についてそれぞれの種類の母関数が存在する（ただし、ランベルト級数とディリクレ型は添字を 1 から始めることが必要）が、扱い易さについてはそれぞれの種類で相当異なるかもしれない。どの母関数が最も有効かは、その列の性質と解くべき問題の詳細に依存する。

母関数を、形式的冪級数に対する演算・操作を用いるなどして（級数の形ではなく）閉じた形の式で表すこともよく行われる。このような母関数の表示は、母関数の不定元を x とすれば、四則演算、母関数のx に関する微分、他の母関数へ代入すること、などを行った結果として得られる。これらの操作は関数に対しても定義されるものであるし、結果として得られる式もやはり x の関数であるかのように見える。実際、母関数を x の（十分小さい）具体的な値で評価することのできる関数として解釈することができる場合も少なくない（このとき、母関数の冪級数表示は、母関数の閉じた形の式のテイラー級数と解釈される）のであり、それがこの式が「母関数」と呼ばれる所以でもある。しかし、形式的冪級数は x に何らかの数値を代入したときに収束するかどうかは問題にしないのであって、母関数についてそのような関数としての解釈が可能であるということは必ずしも要求されるものではないし、同様に x の関数として意味を持つ式がいずれも形式的冪級数に対して意味を持つわけではない。

慣例的に母「関数」と呼ばれてはいるが、始域から終域への写像という関数の厳密な意味に照らして言えば母関数は関数ではなく、今日的には生成級数（母級数）と呼ぶこともしばしばである。

定義

通常型母関数

数列 {a_n} の通常型母関数とは、形式的冪級数

$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}$

のことである。単に「母関数」と言った場合、通常型母関数を意味することが多い。

a_n が離散確率変数の確率質量関数なら、その通常型母関数を確率母関数と呼ぶ。

通常型母関数は多重添字を持つ列に対するものに一般化できる。例えば、二重数列 {a_m,n}（n と m は自然数）の通常型母関数は

$G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}$

である。

指数型母関数

数列 {a_n} の指数型母関数とは、

$EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}$

という級数である。

ポアソン母関数

数列 {a_n} のポアソン母関数 (Poisson generating function) とは

$PG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}e^{-x}{\frac {x^{n}}{n!}}$

のことである。

ランベルト級数

数列 {a_n} のランベルト級数は

$LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}$

で定義される。ランベルト級数では、添字 n は 0 からではなく 1 から始まる点に注意。

ベル級数

数論的関数 f(n) と素数 p に対するベル級数は、

$f_{p}(x)=\sum _{n=0}^{\infty }f(p^{n})x^{n}$

で与えられる。

母関数としてのディリクレ級数

ディリクレ級数は厳密な意味では形式的冪級数でないにもかかわらず、母関数の一種にしばしば分類される。数列 {a_n} のディリクレ級数型の母関数とは

$DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}$

である。ディリクレ級数型の母関数は a_n が乗法的関数でその関数のベル級数を使ったオイラー積表示があれば、特に便利である。

$DG(a_{n};s)=\prod _{p}f_{p}(p^{-s})\,$

a_n がディリクレ指標なら、そのディリクレ級数母関数をディリクレのL関数と呼ぶ。

多項式列の母関数

母関数の概念を他の数学的対象の列に対しても拡張することができる。例えば、二項型の多項式列の母関数は

$e^{xf(t)}=\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}$

のようになる。ここで、p_n(x) は多項式列、f(t) はある形式の関数である。シェファー列も同様にして生成される。詳細は一般化アペル多項式を参照。

通常型母関数

有限列（あるいは同じことだが、ある番号以降の項が全て 0 となる実質有限列）に対応する特別の場合には、通常型母関数は多項式になる。このことは多くの有限列を、ポワンカレ多項式などの母関数によって有効に解釈できるという点で重要である。

重要な母関数として、定数列 1, 1, 1, 1, ... の通常型母関数

$\sum _{n=0}^{\infty }x^{n}={1 \over 1-x}$

がある。右辺の式は、左辺の冪級数に 1 − x を掛けるとその結果が定冪級数（つまり x⁰ の項を除く全ての係数が 0 の級数）1 に一致することを確認することで正当化できる。もっといえば、このような性質を持つ冪級数は他に存在することはできず、したがって左辺の冪級数は形式的冪級数環に於ける 1 − x の乗法的逆元を示している。

これを使えば、他のいくつかの列については、通常型母関数の閉じた式を容易に導出することができる。例えば、a を任意の定数とする等比数列 1, a, a², a³, ... の母関数は

$\sum _{n=0}^{\infty }a^{n}x^{n}={1 \over 1-ax}$

であり、特に a が −1 として

$\sum _{n=0}^{\infty }(-1)^{n}x^{n}={1 \over 1+x}$

が得られる。x を xのある冪乗で置き換えると、列に規則的なギャップを導入することができる。例えば、1, 0, 1, 0, 1, 0, .... という列の母関数は

$\sum _{n=0}^{\infty }x^{2n}={1 \over 1-x^{2}}$

で与えられる。最初の母関数の平方を計算すると、係数列が1, 2, 3, 4, 5, ... という数列を成すことは容易に確認できる。つまり、母関数について言えば

$\sum _{n=0}^{\infty }(n+1)x^{n}={1 \over (1-x)^{2}}$

が成立する。また立方は係数列として三角数 1, 3, 6, 10, 15, 21, ... を持ち、n 番目の三角数は二項係数 ${\tbinom {n+2}{2}}$ であるから、

$\sum _{n=0}^{\infty }{\tbinom {n+2}{2}}x^{n}={1 \over (1-x)^{3}}$

が得られる。また、

${\binom {n+2}{2}}={\frac {1}{2}}{(n+1)(n+2)}={\frac {1}{2}}(n^{2}+3n+2)$

であることに注意すれば、上述の数列の母関数の線型結合をとることにより、平方数の列 0, 1, 4, 9, 16, ... の通常型母関数を

$G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={2 \over (1-x)^{3}}-{3 \over (1-x)^{2}}+{1 \over 1-x}={\frac {x(x+1)}{(1-x)^{3}}}$

と求めることができる。

有理関数

数列の通常型母関数が有理式（2つの多項式の比）で表されるための必要十分条件は、その列が線型漸化式を持つことである。これは、上述の例を一般化したものである。

畳み込み積

通常型母関数の間の乗法は、級数の離散畳み込み（コーシー積）を生じる。

多変数母関数

多重添字をもつ級数に対して、多変数の母関数を定義することができる。これはしばしば超母関数 super generating function) と呼ばれる。特に2変数の場合を2変数母関数 (bivariate generating function) と呼ぶ。

例えば、(1 + x)ⁿ が固定された n に対する二項係数の通常型母関数であるから、（n をも動かして）任意の k と n に対して二項係数 ${\tbinom {n}{k}}$ を生成する二変数母関数がどうなるのかと考えるのは自然な発想である。これを計算するためには、(1 + x)ⁿ 自身を n を添字とする数列と考え、それを係数に持ち、y を不定元とする母関数を求めればよい。aⁿ の母関数はちょうど 1/(1 − ay) に等しいから、求める二項係数の母関数は

${\frac {1}{1-(1+x)y}}=1+(1+x)y+(1+x)^{2}y^{2}+\dots$

であり、x^kyⁿ の係数が二項係数 ${\tbinom {n}{k}}$ となる。

例

平方数の列 a_n = n² の各種母関数を以下に示す。

通常型母関数

$G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}$

指数型母関数

$EG(n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}$

ベル級数

$f_{p}(x)=\sum _{n=0}^{\infty }p^{2n}x^{n}={\frac {1}{1-p^{2}x}}$

ディリクレ級数母関数

$DG(n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)$

多変数母関数

多変数母関数（多変量生成関数）は、行と列の合計を与えられたとき、非負整数の分割表の数を実際に計算する際に生じる。表に r 個の行と c 個の列があり、行の合計が $t_{1},\ldots t_{r}$、列の合計が $s_{1},\ldots s_{c}$ とする。アービン・ジョン・グッドによれば、次の式における $x_{1}^{t_{1}}\ldots x_{r}^{t_{r}}y_{1}^{s_{1}}\ldots y_{c}^{s_{c}}$ の係数がその表の数である。

$\prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}$

応用

母関数は次のような用途に使われる。

• 漸化式で与えられた数列に対して、その一般項の閉じた形の式を求める。たとえば、フィボナッチ数列などについてこれを考えることができる。
• 数列に対して、それが満たす漸化式を求める。母関数の形から漸化式をある程度予想できる。

• 数列の間に成立する関係を求める。二つの数列の母関数が似た形であれば、列自体にもなんらかの関係があるかもしれない。
• 数列の漸近的な挙動を調べる。これには複素関数論の知識が用いられる。
• 数列の間で満たされる関係式（恒等式）を求める。オイラーの分割恒等式はその一例である。
• 組合せ論における数え上げ問題を解いて、それらの解を結びつける。ルーク多項式は組合せ論における応用例である。
• 無限和を評価する。

その他の母関数

さらに複雑な母関数で生成する多項式列として、次のようなものがある。

• アペル多項式
• チェビシェフ多項式
• ゲーゲンバウアー多項式
• 差分多項式
• 一般化アペル多項式
• q-差分多項式

類似の概念

多項式補間は、（係数ではなく）値を数列で与えられたとき、その多項式を求める問題である。また、これを可換環論において抽象化したものがヒルベルト多項式である。

関連項目

• 積率母関数
• 整数分割

参考文献

• Wilf, Herbert S. (1994), Generatingfunctionology (Second ed.), Academic Press, ISBN 0-12-751956-4, http://www.math.upenn.edu/%7Ewilf/DownldGF.html .
• Knuth, Donald E., “Section 1.2.9: Generating Functions”, The Art of Computer Programming, 1, Fundamental Algorithms (Third ed.), Addison-Wesley, pp. 87–96, ISBN 0-201-89683-4 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren, “Chapter 7: Generating Functions”, Concrete Mathematics. A foundation for computer science (Second Edition ed.), Addison-Wesley, pp. 320–380, ISBN 0-201-55802-5 

外部リンク

• Generating Functions, Power Indices and Coin Change at cut-the-knot
• 1031 Generating Functions (PDF)
• Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
• "Generating Functions" by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.