母関数のソースを表示

[[数学]]において、'''母関数'''（ぼかんすう、{{lang-en-short|generating function}}; 生成関数）は、（[[自然数]]で添字付けられた）[[数列]] {''a''<sub>''n''</sub>} に関する情報を内包した[[係数]]を持つ、[[形式的冪級数]]である。母関数は、一般線型回帰問題の解決のために[[アブラーム・ド・モアブル|ド・モアブル]]によって1730年に初めて用いられた<ref>[[ドナルド・クヌース|Donald E. Knuth]], ''The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition)'' Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: Generating Functions, pp.&nbsp;86</ref>。複数の自然数で添字付けられる数の配列（多重数列）の情報を取り込んだ多変数冪級数を同様に考えることもできる。

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

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

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

== 定義 ==
=== 通常型母関数 ===
数列 {''a''<sub>''n''</sub>} の通常型母関数とは、形式的冪級数

:<math>G(a_n;x)=\sum_{n=0}^{\infty}a_nx^n</math>

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

''a''<sub>''n''</sub> が[[離散確率変数]]の[[確率質量関数]]なら、その通常型母関数を{{仮リンク|確率母関数|en|Probability-generating function}}と呼ぶ。

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

:<math>G(a_{m,n};x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n</math>

である。

=== 指数型母関数 ===
数列 {''a''<sub>''n''</sub>} の指数型母関数とは、

:<math>EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}</math>

という級数である。

=== ポアソン母関数 ===
数列 {''a''<sub>''n''</sub>} のポアソン母関数 ({{en|Poisson generating function}}) とは

:<math>PG(a_n;x)=\sum _{n=0}^{\infty} a_n e^{-x} \frac{x^n}{n!}</math>

のことである。

=== ランベルト級数 ===
数列 {''a''<sub>''n''</sub>} のランベルト級数は

:<math>LG(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}</math>

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

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

:<math>f_p(x)=\sum_{n=0}^\infty f(p^n)x^n</math>

で与えられる。

=== 母関数としてのディリクレ級数 ===
[[ディリクレ級数]]は厳密な意味では形式的冪級数でないにもかかわらず、母関数の一種にしばしば分類される。数列 {''a''<sub>''n''</sub>} のディリクレ級数型の母関数とは

:<math>DG(a_n;s)=\sum _{n=1}^{\infty} \frac{a_n}{n^s}</math>

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

:<math>DG(a_n;s)=\prod_{p} f_p(p^{-s})\,</math>

''a''<sub>''n''</sub> が[[ディリクレ指標]]なら、そのディリクレ級数母関数をディリクレの[[L関数]]と呼ぶ。

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

:<math>e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n</math>

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

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

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

:<math>\sum_{n=0}^{\infty}x^n={1\over1-x}</math>

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

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

:<math>\sum_{n=0}^{\infty}a^nx^n={1\over1-ax}</math>

であり、特に ''a'' が &minus;1 として

:<math>\sum_{n=0}^{\infty}(-1)^nx^n={1\over1+x}</math>

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

:<math>\sum_{n=0}^{\infty}x^{2n}={1\over1-x^2}</math>

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

:<math>\sum_{n=0}^{\infty}(n+1)x^n={1\over(1-x)^2}</math>

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

:<math>\sum_{n=0}^{\infty}\tbinom{n+2}2 x^n={1\over(1-x)^3}</math>

が得られる。また、

: <math>\binom{n+2}2=\frac12{(n+1)(n+2)} =\frac12(n^2+3n+2)</math>

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

:<math>G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n={2\over(1-x)^3}-{3\over(1-x)^2}+{1\over1-x}=\frac{x(x+1)}{(1-x)^3}</math>

と求めることができる。

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

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

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

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

== 例 ==
[[平方数]]の列 ''a''<sub>''n''</sub> = ''n''<sup>2</sup> の各種母関数を以下に示す。

=== 通常型母関数 ===
:<math>G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=\frac{x(x+1)}{(1-x)^3}</math>

=== 指数型母関数 ===
:<math>EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x</math>

=== ベル級数 ===
:<math>f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}</math>

=== ディリクレ級数母関数 ===
:<math>DG(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)</math>

=== 多変数母関数 ===
多変数母関数（多変量生成関数）は、行と列の合計を与えられたとき、非負整数の[[分割表]]の数を実際に計算する際に生じる。表に ''r'' 個の行と ''c'' 個の列があり、行の合計が <math>t_1,\ldots t_r</math>、列の合計が <math>s_1,\ldots s_c</math> とする。{{仮リンク|アービン・ジョン・グッド|en|I. J. Good}}によれば<ref name="Good 1986">{{cite journal| last=Good| first=I. J.|  title=On applications of symmetric Dirichlet distributions and their mixtures to contingency tables| journal=The Annals of Statistics| year=1986| volume=4| number=6|pages=1159&ndash;1189}}</ref>、次の式における <math>x_1^{t_1}\ldots x_r^{t_r}y_1^{s_1}\ldots y_c^{s_c}</math> の係数がその表の数である。

:<math>
\prod_{i=1}^{r}\prod_{j=1}^c\frac{1}{1-x_iy_j}
</math>


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

* 漸化式で与えられた数列に対して、その一般項の閉じた形の式を求める。たとえば、[[フィボナッチ数|フィボナッチ数列]]などについてこれを考えることができる。
* 数列に対して、それが満たす[[漸化式]]を求める。母関数の形から漸化式をある程度予想できる<ref>[[伏見康治]]「[[確率論及統計論]]」第I章　数学的補助手段 2節 母函数 p.12 ISBN 9784874720127 http://ebsa.ism.ac.jp/ebooks/ebook/204</ref>。

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

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

* {{仮リンク|アペル多項式|en|Appell polynomials}}
* [[チェビシェフ多項式]]
* [[ゲーゲンバウアー多項式]]
* [[差分多項式]]
* [[一般化アペル多項式]]
* {{仮リンク|q-差分多項式|en|Q-difference polynomial}}

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

== 関連項目 ==
* [[積率母関数]]
* [[整数分割]]

== 脚注==
{{Reflist}}

== 参考文献 ==
* {{citation|first=Herbert S.|last=Wilf|url=http://www.math.upenn.edu/%7Ewilf/DownldGF.html |title=Generatingfunctionology |edition=Second |date=1994|publisher=Academic Press |isbn=0-12-751956-4}}. 
* {{citation|first=Donald E.|last=Knuth |authorlink=ドナルド・クヌース|title=The Art of Computer Programming|volume=1,  Fundamental Algorithms |edition=Third |publisher=Addison-Wesley|isbn=0-201-89683-4|chapter=Section 1.2.9: Generating Functions|pages=87&ndash;96}}
* {{citation|first1=Ronald L.|last1=Graham|first2=Donald E.|last2=Knuth|first3=Oren|last3=Patashnik|title=[[Concrete Mathematics]]. A foundation for computer science|edition=Second Edition|publisher=Addison-Wesley|isbn=0-201-55802-5|chapter=Chapter 7: Generating Functions|pages=320&ndash;380}}

== 外部リンク ==
* [http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml Generating Functions, Power Indices and Coin Change] at cut-the-knot
* {{pdf|[https://web.archive.org/web/20081031163444/http://www.lacim.uqam.ca/~plouffe/articles/FonctionsGeneratrices.pdf 1031 Generating Functions]}} 
* Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, ''[https://groups.google.com/g/es.ciencia.matematicas/c/JjKKvEnhXdk#88b7b522437223ce  Suma de números equilibrados], newsgroup es.ciencia.matematicas''
* [http://demonstrations.wolfram.com/GeneratingFunctions/ "Generating Functions"] by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.

{{Normdaten}}
{{DEFAULTSORT:ほかんすう}}
[[Category:組合せ論]]
[[Category:数列]]
[[Category:多項式]]
[[Category:母関数|*]]
[[Category:数学に関する記事]]