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. Metóda vytvárajúcich funkcií býva často považovaná za najsilnejšiu metódu manipulácie s číselnými postupnosťami. 

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. 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.

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 \{a_n\}_{n=0}^{\infty} = (a_0,a_1,\ldots) je číselná postupnosť. Obyčajná vytvárajúca funkcia k postupnosti a_n je formálny mocninový rad

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

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

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

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

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

:e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}.

### Poissonova vytvárajúca funkcia

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

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

### Lambertova vytvárajúca funkcia

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

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

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

### Dirichletova vytvárajúca funkcia

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

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

Opäť je nutné indexovať postupnosť od čísla 1, čo spôsobila prítomnosť člena n^x 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