Příklady generování funkcí - Examples of generating functions

Následující příklady generující funkce jsou v duchu George Pólya, kteří prosazovali učení matematiky tím, že provedli a znovu kapitulovali co nejvíce příkladů a důkazů.^{[Citace je zapotřebí ]} Účelem tohoto článku je představit běžné způsoby vytváření generujících funkcí.

Pracoval příklad A: základy

Nový generující funkce lze vytvořit rozšířením jednodušších generujících funkcí. Pro příklad, začínání s

${displaystyle G (1; x) = součet _ {n = 0} ^ {infty} x ^ {n} = {frac {1} {1-x}}}$

a nahrazení ${displaystyle x}$ s ${zobrazovací sekera}$, získáváme

${displaystyle G (1; ax) = {frac {1} {1-ax}} = 1+ (ax) + (ax) ^ {2} + cdots + (ax) ^ {n} + cdots = suma _ { n = 0} ^ {infty} a ^ {n} x ^ {n} = G (a ^ {n}; x).}$

Bivariate generující funkce

Lze definovat generující funkce v několika proměnných, pro řady s několika indexy. Často se jim říká super generující funkce, a pro 2 proměnné se často nazývá bivariate generující funkce.

Například od ${displaystyle (1 + x) ^ {n}}$ je generující funkce pro binomické koeficienty za pevnou n, lze požádat o funkci generování bivariate, která generuje binomické koeficienty ${displaystyle {jiný {n} {k}}}$ pro všechny k a n.Chcete-li to provést, zvažte ${displaystyle (1 + x) ^ {n}}$ tak jako sám série (v n) a najděte generující funkci v y který má tyto jako koeficienty. Od generující funkce pro ${displaystyle a ^ {n}}$ je jen ${displaystyle 1 / (1-ay)}$, generující funkce pro binomické koeficienty je:

${displaystyle {frac {1} {1- (1 + x) y}} = 1+ (1 + x) y + (1 + x) ^ {2} y ^ {2} + tečky,}$

a koeficient na ${displaystyle x ^ {k} y ^ {n}}$ je ${displaystyle {jiný {n} {k}}}$ binomický koeficient.

Pracoval příklad B: Fibonacciho čísla

Zvažte problém nalezení a uzavřený vzorec pro Fibonacciho čísla F_n definován F₀ = 0, F₁ = 1 a F_n = F_n−1 + F_n−2 pro n ≥ 2. Tvoříme běžnou generující funkci

${displaystyle f = součet _ {ngeq 0} F_ {n} x ^ {n}}$

pro tuto sekvenci. Generující funkce pro sekvenci (F_n−1) je xf a to (F_n−2) je X²F. Z relace rekurence tedy vidíme, že mocninová řada xf + X²F souhlasí s F kromě prvních dvou koeficientů:

${displaystyle {egin {array} {rcrcrcrcrcrcr} f & = & F_ {0} x ^ {0} & + & F_ {1} x ^ {1} & + & F_ {2} x ^ {2} & + & cdots & + & F_ { i} x ^ {i} & + & cdots xf & = &&& F_ {0} x ^ {1} & + & F_ {1} x ^ {2} & + & cdots & + & F_ {i-1} x ^ {i} & + & cdots x ^ {2} f & = &&&&& F_ {0} x ^ {2} & + & cdots & + & F_ {i-2} x ^ {i} & + & cdots (x + x ^ {2}) f & = &&& F_ {0} x ^ {1} & + & (F_ {0} + F_ {1}) x ^ {2} & + & cdots & + & (F_ {i-1} + F_ {i-2}) x ^ {i} & + & cdots & = &&&&& F_ {2} x ^ {2} & + & cdots & + & F_ {i} x ^ {i} & + & cdots end {pole}}}$

Když to vezmeme v úvahu, zjistíme to

${displaystyle f = xf + x ^ {2} f + x.}$

(Toto je zásadní krok; relace opakování lze téměř vždy přeložit do rovnic pro generující funkce.) Řešení této rovnice pro F, dostaneme

${displaystyle f = {frac {x} {1-x-x ^ {2}}}.}$

Jmenovatel lze započítat pomocí Zlatý řez φ₁ = (1 + √5) / 2 a φ₂ = (1 − √5) / 2 a technika rozklad částečné frakce výnosy

${displaystyle f = {frac {1} {sqrt {5}}} vlevo ({frac {1} {1-varphi _ {1} x}} - {frac {1} {1-varphi _ {2} x} } hned).}$

Tyto dvě formální mocenské řady jsou výslovně známy, protože ano geometrické řady; porovnáním koeficientů najdeme explicitní vzorec

${displaystyle F_ {n} = {frac {1} {sqrt {5}}} (varphi _ {1} ^ {n} -varphi _ {2} ^ {n}).}$

Pracoval příklad C: Počet způsobů, jak provést změnu

Počet neuspořádaný způsoby A_n provést změnu n centů využívajících mince s hodnotami 1, 5, 10 a 25 je dáno funkcí generování

${displaystyle G (a_ {n}, x) = součet _ {n = 0} ^ {infty} a_ {n} x ^ {n} = {frac {1} {(1-x) (1-x ^ { 5}) (1-x ^ {10}) (1-x ^ {25})}} ,.}$

Například existují dva neuspořádané způsoby, jak provést změnu za 6 centů; jedním způsobem je šest 1-centových mincí, druhým způsobem je jedna 1-centová mince a jedna 5-centová mince. Vidět OEIS: A001299.

Na druhou stranu, počet objednal způsoby b_n provést změnu n centů využívajících mince s hodnotami 1, 5, 10 a 25 je dáno funkcí generování

${displaystyle G (b_ {n}, x) = součet _ {n = 0} ^ {infty} b_ {n} x ^ {n} = {frac {1} {1-xx ^ {5} -x ^ { 10} -x ^ {25}}} ,.}$

Například existují tři objednané způsoby, jak provést změnu za 6 centů; jedním způsobem je šest 1-centových mincí, druhým způsobem je jedna 1-centová mince a jedna 5-centová mince a třetím způsobem je jedna 5-centová mince a jedna 1-centová mince. Porovnat s OEIS: A114044, který se od tohoto příkladu liší tím, že zahrnuje i mince s hodnotami 50 a 100.

externí odkazy

• Generování funkcí, výkonových indexů a změn mincí na cut-the-uzel
• Generovánífunkcionologie (PDF)