Vytvořující funkce (posloupnost)

Vytvořující (též generující) funkce posloupnosti ${\displaystyle \{a_{i}\}}$ je mocninná řada, která v sobě obsahuje informaci o dané posloupnosti. Vytvořující funkce tedy umožňuje popsat posloupnost a pracovat s ní prostřednictvím funkce, která v sobě obsahuje veškeré informace o dané posloupnosti, a naopak otázky týkající se funkcí převádět na zkoumání posloupností. Teorie vytvořujících funkcí má však svoje omezení: Ne každé funkci odpovídá nějaká mocninná řada a ne každá mocninná řada konverguje kdekoli kromě nuly (což ovšem v zásadě nebrání s ní pracovat jako s vytvořující funkcí, pokud nepotřebujeme využít analytické vlastnosti jí definované funkce, ale chápeme ji jen jako tzv. formální mocninnou řadu).

Důležitými aplikacemi teorie vytvořujících funkcí jsou momentová vytvořující funkce v teorii pravděpodobnosti, která mimo jiné umožňuje odvodit rozdělení pravděpodobnosti součtu dvou nezávislých náhodných veličin se známými rozděleními, a příbuzná pravděpodobnostní vytvořující funkce. S pomocí vytvořujících funkcí lze také řešit různé kombinatorické úlohy.^[1][2]

Definice

Obyčejnou vytvořující funkci posloupnosti ${\displaystyle (a_{0},a_{1},a_{2},...)}$ zapíšeme jako

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+...=\sum _{i=0}^{\infty }a_{i}x^{i}}$

Jedná o tzv. otevřený tvar vytvořující funkce. Poznáme ho tak, že je v něm nekonečný součet (což se nám nemusí příliš líbit). Proto často chceme nalézt tzv. uzavřený tvar, ve kterém se nekonečný součet nevyskytuje.

Vysvětlení na praktické ukázce

Mějme např. posloupnost

${\displaystyle (1,1,1,1,1,...)}$

Pak její vytvořující funkci lze zapsat (na intervalu, ve kterém tato řada konverguje) jako:

${\displaystyle a(x)=1+1x+1x^{2}+...}$

Uzavřený tvar této funkce lze snadno odvodit z obecného vztahu pro součet geometrické posloupnosti:

${\displaystyle {1} \over {1-x}}$

Tyto dva tvary spolu souvisí tak, že když do nich doplníme za ${\displaystyle x}$ libovolné reálné číslo z intervalu (-1,1) tzn. |x|<1, pro které uvedená mocninná řada konverguje, vyjde nám v obou tvarech vždy naprosto stejný výsledek.

Například doplníme ${\displaystyle x=0.5}$, pak nám vyjde součet otevřeného tvaru vytvořující funkce:

${\displaystyle a(0.5)=1+0.5+0.5^{2}+0.5^{3}+...=1+0.5+0.25+0.125+...=2}$

A pro stejné ${\displaystyle x=0.5}$ vyjde uzavřený tvar taktéž:

${\displaystyle {{1} \over {1-0.5}}=2}$

Vytvořující funkci této jednoduché posloupnosti lze dále považovat za klíčovou pro odvození uzavřených tvarů složitějších posloupností.

Například derivací řady ${\displaystyle a(x)=1+1x+1x^{2}+1x^{3}+...}$ získáme řadu ${\displaystyle b(x)=0+1+2x+3x^{2}+...}$

Pokud tedy zderivujeme uzavřený tvar ${\displaystyle a(x)}$ dostaneme

${\displaystyle a(x)'=b(x)={{1} \over {(1-x)^{2}}}}$

Tato nová odvozená funkce představuje posloupnost ${\displaystyle (1,2,3,4,5,...)}$

Podobnými úpravami lze postupně odvodit vytvořující funkce i pro vybrané posloupnosti (viz tabulka níže).

Výpočet koeficientu posloupnosti z vytvořující funkce

Máme-li vytvořující funkci ve tvaru ${\displaystyle {1} \over {(1-x)^{n}}}$, vypočítáme požadovaný koeficient ${\displaystyle a_{k}}$ následovně:

${\displaystyle a_{k}=C_{n-1+k}^{n-1}={\begin{pmatrix}n-1+k\\n-1\end{pmatrix}}}$

Nebo lze pro ${\displaystyle (1+x)^{-n}}$ použít tento vzoreček

${\displaystyle a_{k}=C_{-n}^{k}=(-1)^{k}*C_{n+k-1}^{k}}$

Příklad

Hledáme koeficient ${\displaystyle a_{8}}$ u vytv. fce ${\displaystyle (1-x)^{-3}={{1} \over {(1-x)^{3}}}}$:

${\displaystyle a_{8}=C_{3-1+8}^{3-1}=C_{10}^{2}=45}$

Poznámka: Výpočet hodnoty koeficientu u tohoto typu vytvořující funkce vychází ze zobecněné binomické věty.

Vybrané posloupnosti a jejich vytvořující funkce

Odkazy

Reference

Externí odkazy

• WILF, Herbert S. Generatingfunctionology. 3. vyd. Wellesley, Mass.: A. K. Peters, 2006. x, 245 pages s. Dostupné online. ISBN 1-56881-279-5, ISBN 978-1-56881-279-3. OCLC 62302522 

Související články

• Posloupnost
• Momentová vytvořující funkce

Externí odkazy

• Vytvořující funkce ve studijních textech semináře MKS MFF UK