Literatura Vytvořující funkce Příklady vytvořujících funkcí Drsná matematika III -- 13. přednáška Vytvořující funkce Jan Slovák Masarykova univerzita Fakulta informatiky 18. 12. 2006 Literatura Vytvořující funkce Příklady vytvořujících funkcí Obsah přednášky 1 Literatura 2 Vytvořující funkce 3 Příklady vytvořujících funkcí Literatura Vytvořující funkce Příklady vytvořujících funkcí Plán přednášky 1 Literatura 2 Vytvořující funkce 3 Příklady vytvořujících funkcí Literatura Vytvořující funkce Příklady vytvořujících funkcí Kde je dobré číst? Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. Literatura Vytvořující funkce Příklady vytvořujících funkcí Plán přednášky 1 Literatura 2 Vytvořující funkce 3 Příklady vytvořujících funkcí Literatura Vytvořující funkce Příklady vytvořujících funkcí Heslo dne: ­ ,,spojité a diskrétní metody se vzájemně potřebují Literatura Vytvořující funkce Příklady vytvořujících funkcí Heslo dne: ­ ,,spojité a diskrétní metody se vzájemně potřebují Example Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme Colu za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Literatura Vytvořující funkce Příklady vytvořujících funkcí Heslo dne: ­ ,,spojité a diskrétní metody se vzájemně potřebují Example Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme Colu za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla i, j a k taková, že i + j + k = 22 a zároveň i {0, 1, 2, 3, 4}, j {0, 1, 2, 3, 4, 5}, k 0, 1, 2, 3. Uvažme součin polynomů (třeba nad reálnými čísly) (1 + x2 + x3 + x4 )(x2 + x4 + x6 + x8 + x10 )(x5 + x10 + x15 ). Mělo by být zřejmé, že hledaný počet řešení je právě koeficient u x22 ve výsledném polynomu. Literatura Vytvořující funkce Příklady vytvořujících funkcí Heslo dne: ­ ,,spojité a diskrétní metody se vzájemně potřebují Example Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme Colu za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla i, j a k taková, že i + j + k = 22 a zároveň i {0, 1, 2, 3, 4}, j {0, 1, 2, 3, 4, 5}, k 0, 1, 2, 3. Uvažme součin polynomů (třeba nad reálnými čísly) (1 + x2 + x3 + x4 )(x2 + x4 + x6 + x8 + x10 )(x5 + x10 + x15 ). Mělo by být zřejmé, že hledaný počet řešení je právě koeficient u x22 ve výsledném polynomu. Skutečně tak dostáváme 4 možnosti 3 5 + 3 2 + 1 1, 3 5 + 2 2 + 3 1, 2 5 + 5 2 + 2 1 a 2 5 + 4 2 + 4 1. Literatura Vytvořující funkce Příklady vytvořujících funkcí Příklad zasluhuje větší pozornost: Jestliže budeme (pro jistotu, abychom nemuseli předem dělat odhady velikostí) pracovat s nekonečnými posloupnostmi, pak pomocí jednotlivých korun umíme dosáhnout hodnot 0, 1, 2, . . . s četnostmi (1, 1, 1, 1, 1, 0, 0, . . . ) (pokračují samé nuly), u dvoukorun (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, . . . ), a u pětikorun to budou poslounosti četností (1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, . . . ). Literatura Vytvořující funkce Příklady vytvořujících funkcí Příklad zasluhuje větší pozornost: Jestliže budeme (pro jistotu, abychom nemuseli předem dělat odhady velikostí) pracovat s nekonečnými posloupnostmi, pak pomocí jednotlivých korun umíme dosáhnout hodnot 0, 1, 2, . . . s četnostmi (1, 1, 1, 1, 1, 0, 0, . . . ) (pokračují samé nuly), u dvoukorun (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, . . . ), a u pětikorun to budou poslounosti četností (1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, . . . ). Ke každé takové posloupnosti s konečně mnoha nulovými členy můžeme přiřadit polynom a hodou okolností řešení naší úlohy bylo možné odečíst ze součinu těchto polynomů. Literatura Vytvořující funkce Příklady vytvořujících funkcí Definition Vytvořující funkce pro nekonečnou posloupnost a = (a0, a1, a2, . . . ) je (formální) mocninná řada a(x) = a0 + a1x + a2x2 + = i=0 ai xi . Literatura Vytvořující funkce Příklady vytvořujících funkcí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Literatura Vytvořující funkce Příklady vytvořujících funkcí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení ( ai ) všech členů posloupnosti stejným skalárem odpovídá vynásobení a(x) příslušné vytvořující funkce. Literatura Vytvořující funkce Příklady vytvořujících funkcí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení ( ai ) všech členů posloupnosti stejným skalárem odpovídá vynásobení a(x) příslušné vytvořující funkce. Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami zleva. Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (a0, . . . , ak-1, 0, . . . ) a poté podělíme vytvořující funkci xk. Literatura Vytvořující funkce Příklady vytvořujících funkcí Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Sčítání (ai + bi ) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Vynásobení ( ai ) všech členů posloupnosti stejným skalárem odpovídá vynásobení a(x) příslušné vytvořující funkce. Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami zleva. Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (a0, . . . , ak-1, 0, . . . ) a poté podělíme vytvořující funkci xk. Dosazením monomu f (x) za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f (x) = x, což odpovídá vynásobení k­tého členu posloupnosti skalárem k. Dosazení f (x) = xn nám do posloupnosti mezi každé dva členy vloží n - 1 nul. Literatura Vytvořující funkce Příklady vytvořujících funkcí Plán přednášky 1 Literatura 2 Vytvořující funkce 3 Příklady vytvořujících funkcí Literatura Vytvořující funkce Příklady vytvořujících funkcí Uvedeme několik jednoduchých příkladů vytvořujících funkcí. Řadu z nich jsme viděli při práci s mocninnými řadami ve třetí části šesté kapitoly. Snad si všichni vzpomenou na vytvořující funkci zadanou geometrickou řadou: a(x) = 1 1 - x = 1 + x + x2 + . . . která tedy odpovídá konstantní posloupnosti (1, 1, 1, . . . ). Obecně, pro každou posloupnost ai s členy velikosti |an| = O(nk) s konstantním exponentem k, konverguje její vytvořující funkce na nějakém okolí nuly. Můžeme s ní pak opravdu na konvergenčním intervalu zacházet jako s funkcemi, zejména je umíme sčítat, násobit, skládat, derivovat a integrovat.