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}^{\mathrm{\infty }}=(a_0,a_1,\dots )$ 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}^{\mathrm{\infty }}{a}_n{x}^n.$

Exponenciálna vytvárajúca funkcia

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

$\mathrm{EG}(a_n;x)=\sum _{n=0}^{\mathrm{\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}^{\mathrm{\infty }}\frac{x^n}{n!}.$

Poissonova vytvárajúca funkcia

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

$\mathrm{PG}(a_n;x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{e}^{-x}\frac{x^n}{n!}=e^{-x}\mathrm{EG}(a_n;x).$

Lambertova vytvárajúca funkcia

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

$\mathrm{LG}(a_n;x)=\sum _{n=1}^{\mathrm{\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}^{\mathrm{\infty }}=(a_1,a_2,\dots )$ je číselná postupnosť. Dirichletova vytvárajúca funkcia k postupnosti $a_n$ je formálny mocninový rad

$\mathrm{DG}(a_n;x)=\sum _{n=1}^{\mathrm{\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.

Externé odkazy

• Generujúce funkcie - Cut The Knot Šablóna:Eng icon.
• Generujúce funkcie - Wolfram MathWorld Šablóna:Eng icon.
• 1031 vytvárajúcich funkcií Šablóna:Webarchive Šablóna:Fra icon.
• Stiahnutie knihy Genratingfunctionology Šablóna:Eng icon.