Zobrazenie zdroja stránky Vytvárajúca funkcia

'''Vytvárajúca funkcia''' alebo '''generujúca funkcia''' je v [[matematika|matematike]] formálny [[mocninový rad]] o jednej premennej, ktorého koeficienty obsahujú informáciu o danej [[postupnosť (matematika)|postupnosti]] čísel. Formálnosť mocninového radu znamená, že sa s ním narába ako s čisto [[algebra]]ickým objektom a neštudujú sa jeho [[matematická analýza|analytické]] vlastnosti ako napríklad polomer konvergencie a pod.<ref>Wilf, H. S.: ''Generatingfunctionology''. Academic Press, 1994.</ref> Metóda vytvárajúcich funkcií býva často považovaná za najsilnejšiu metódu manipulácie s číselnými postupnosťami. <ref>Graham, R. L., Knuth, D. E., Patashnik, O.: ''Concrete Mathematics''. Addison-Wesley, 1990.</ref>

Súvis medzi operáciami na postupnostiach a operáciami na ich vytvárajúcich funkciách sa využíva predovšetkým na riešenie [[rekurentný vzťah|rekurentných vzťahov]], čo má dôležité aplikácie pri enumerácii diskrétnych štruktúr.<ref>Matoušek, J., Nešetřil, J.: ''Kapitoly z diskrétní matematiky.'' Karolinum, 2007. </ref> Myšlienka použitia formálnych mocninových radov na riešenie rekurentných vzťahov siaha k [[Abraham de Moivre|Abrahamovi de Moivrovi]], ktorý túto metódu použil na zistenie uzavretého tvaru pre [[Fibonacciho postupnosť|Fibonacciho čísla]].<ref>Knuth, D. E.: ''The Art of Computer Programming, vol. I: Fundamental Algorithms.'' Addison-Wesley, 1997.</ref>

Podľa spôsobu konštrukcie formálneho mocninového radu k danej postupnosti je možné rozlíšiť viacero typov vytvárajúcich funkcií. Medzi najznámejšie patria '''obyčajné vytvárajúce funkcie''', '''exponenciálne vytvárajúce funkcie''', '''Poissonove vytvárajúce funkcie''', '''Lambertove vytvárajúce funkcie''' a '''Dirichletove vytvárajúce funkcie'''. Teóriu je možné z postupností rozšíriť aj na viacrozmerné štruktúry, v takom prípade nie je vytvárajúca funkcia formálnym mocninovým radom o jednej premennej, ale o toľko premenných, aká je dimenzia danej štruktúry.

== Definície ==

=== Obyčajná vytvárajúca funkcia ===

Nech <math>\{a_n\}_{n=0}^{\infty} = (a_0,a_1,\ldots)</math> je číselná [[postupnosť (matematika)|postupnosť]]. Obyčajná vytvárajúca funkcia k postupnosti <math>a_n</math> je formálny mocninový rad

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

=== Exponenciálna vytvárajúca funkcia ===

Nech <math>\{a_n\}_{n=0}^{\infty} = (a_0,a_1,\ldots)</math> je číselná [[postupnosť (matematika)|postupnosť]]. Exponenciálna vytvárajúca funkcia k postupnosti <math>a_n</math> je formálny mocninový rad

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

Názov exponenciálna vytvárajúca funkcia pochádza zo skutočnosti, že pre [[Taylorov rad]] exponenciálnej funkcie <math>e^x</math> platí

:<math>e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}.</math>

=== Poissonova vytvárajúca funkcia ===

Nech <math>\{a_n\}_{n=0}^{\infty} = (a_0,a_1,\ldots)</math> je číselná [[postupnosť (matematika)|postupnosť]]. Poissonova vytvárajúca funkcia k postupnosti <math>a_n</math> je formálny mocninový rad

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

=== Lambertova vytvárajúca funkcia ===

Nech <math>\{a_n\}_{n=1}^{\infty} = (a_1,a_2,\ldots)</math> je číselná [[postupnosť (matematika)|postupnosť]]. Lambertova vytvárajúca funkcia k postupnosti <math>a_n</math> je formálny mocninový rad

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

Prítomnosť výrazu <math>1-x^n</math> v menovateli člena vytvárajúcej funkcie implikuje nutnosť indexovať postupnosť od čísla 1, nie od čísla 0.

=== Dirichletova vytvárajúca funkcia ===

Nech <math>\{a_n\}_{n=1}^{\infty} = (a_1,a_2,\ldots)</math> je číselná [[postupnosť (matematika)|postupnosť]]. Dirichletova vytvárajúca funkcia k postupnosti <math>a_n</math> je formálny mocninový rad

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

Opäť je nutné indexovať postupnosť od čísla 1, čo spôsobila prítomnosť člena <math>n^x</math> v menovateli vytvárajúcej funkcie.

== Zdroje ==

<references />

== Externé odkazy ==

* [http://www.cut-the-knot.org/ctk/GeneratingFunctions.shtml Generujúce funkcie] - Cut The Knot {{eng icon}}.
* [http://mathworld.wolfram.com/GeneratingFunction.html Generujúce funkcie] - Wolfram MathWorld {{eng icon}}.
* [http://www.lacim.uqam.ca/~plouffe/articles/FonctionsGeneratrices.pdf 1031 vytvárajúcich funkcií] {{fra icon}}.
* [http://www.math.upenn.edu/~wilf/DownldGF.html Stiahnutie knihy] ''Genratingfunctionology'' {{eng icon}}.

[[Kategória:Kombinatorika]]