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

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

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

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.