Vytvárajúca funkcia

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

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ých vzťahov, čo má dôležité aplikácie pri enumerácii diskrétnych štruktúr.Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. Karolinum, 2007.  Myšlienka použitia formálnych mocninových radov na riešenie rekurentných vzťahov siaha k Abrahamovi de Moivrovi, ktorý túto metódu použil na zistenie uzavretého tvaru pre Fibonacciho čísla.Knuth, D. E.: The Art of Computer Programming, vol. I: Fundamental Algorithms. Addison-Wesley, 1997.

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  je číselná postupnosť. Obyčajná vytvárajúca funkcia k postupnosti  je formálny mocninový rad

 Exponenciálna vytvárajúca funkcia 

Nech  je číselná postupnosť. Exponenciálna vytvárajúca funkcia k postupnosti  je formálny mocninový rad

Názov exponenciálna vytvárajúca funkcia pochádza zo skutočnosti, že pre Taylorov rad exponenciálnej funkcie  platí

 Poissonova vytvárajúca funkcia 

Nech  je číselná postupnosť. Poissonova vytvárajúca funkcia k postupnosti  je formálny mocninový rad

 Lambertova vytvárajúca funkcia 

Nech  je číselná postupnosť. Lambertova vytvárajúca funkcia k postupnosti  je formálny mocninový rad

Prítomnosť výrazu  v menovateli člena vytvárajúcej funkcie implikuje nutnosť indexovať postupnosť od čísla 1, nie od čísla 0.

 Dirichletova vytvárajúca funkcia 

Nech  je číselná postupnosť. Dirichletova vytvárajúca funkcia k postupnosti  je formálny mocninový rad

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

 Zdroje 

 Externé odkazy 

 Generujúce funkcie - Cut The Knot .
 Generujúce funkcie - Wolfram MathWorld .
 1031 vytvárajúcich funkcií  .
 Stiahnutie knihy Genratingfunctionology .

Kategória:Kombinatorika