母関数 応用

ウィキペディア

母関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/02/15 02:53 UTC 版)

応用

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

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

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

その他の母関数

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

• アペル多項式
• チェビシェフ多項式
• ゲーゲンバウアー多項式
• 差分多項式
• 一般化アペル多項式
• 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.