Vytvořující funkce (posloupnost)

Možná hledáte: pravděpodobnostní vytvořující funkce nebo momentová vytvořující funkce.

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

posloupnost	vytv. fce pro ${\displaystyle x\in (-1;1)}$
${\displaystyle \left(1,1,1,1,...\right)}$	${\displaystyle {1} \over {1-x}}$
${\displaystyle \left(1,-1,1,-1,...\right)}$	${\displaystyle {1} \over {1+x}}$
${\displaystyle \left(1,0,1,0,...\right)}$	${\displaystyle {1} \over {1-x^{2}}}$
${\displaystyle \left(1,0,...,0,1,0,...,0,1,0,...\right)}$	${\displaystyle {1} \over {1-x^{n}}}$
${\displaystyle \left(1,2,3,4,5,...\right)}$	${\displaystyle {1} \over {(1-x)^{2}}}$
${\displaystyle \left(1,k,k^{2},k^{3},k^{4},...\right)}$	${\displaystyle {1} \over {1-kx}}$
${\displaystyle \left(1,{\begin{pmatrix}k\\1\end{pmatrix}},{\begin{pmatrix}k\\2\end{pmatrix}},{\begin{pmatrix}k\\3\end{pmatrix}},{\begin{pmatrix}k\\4\end{pmatrix}},...\right)}$	${\displaystyle \left(1+x\right)^{k}}$
${\displaystyle \left(1,k,{\begin{pmatrix}k-1\\k-1\end{pmatrix}},{\begin{pmatrix}k\\k-1\end{pmatrix}},{\begin{pmatrix}k+1\\k-1\end{pmatrix}},...\right)}$	${\displaystyle {1} \over {\left(1-x\right)^{k}}}$
${\displaystyle \left(0,1,{{1} \over {2}},{{1} \over {3}},{{1} \over {4}},...\right)}$	${\displaystyle \ln {1 \over {1-x}}}$
${\displaystyle \left(0,1,-{{1} \over {2}},{{1} \over {3}},-{{1} \over {4}},...\right)}$	${\displaystyle \ln \left(1+x\right)}$
${\displaystyle \left(1,1,{{1} \over {2}},{{1} \over {6}},{{1} \over {24}},{{1} \over {120}},...,{{1} \over {k!}},...\right)}$	${\displaystyle e^{x}}$

Odkazy

Reference

1. CASHCOOL. Re-learning the Generating Functions by Over-Using them!. Medium [online]. 2022-11-20 [cit. 2022-11-21]. Dostupné online. (anglicky) 
2. FLAJOLET, Philippe; SEDGEWICK, Robert. Analytic combinatorics. Cambridge: Cambridge University Press, 2009. 1 online resource (xiii, 810 pages) s. Dostupné online. ISBN 978-0-511-48079-9, ISBN 0-511-48079-2. OCLC 489194625 

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

Autoritní data	BNF: cb12259609r (data) GND: 4152979-0 LCCN: sh85053815 NLI: 987007562699905171