Literatura Motivace Opa kování Vytvořující funkce (Formální) m( jcninné řady ooooo ooooooo OOOOO Diskrétní matematika B - 11. (zkrácený) týden Kombinatorické výpočty Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady ooooo ooooooo OOOOO Q Motivace Q| Opakování kombinatorických vztahů Q Vytvořující funkce Q| (Formální) mocninné řady Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady ooooo ooooooo OOOOO • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Donald E. Knuth, The Art Of Computer Programming. • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 2009. • Robert Sedgewick, Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1995. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. • H. S. Wilf, Generatingfunctionology, Academic Press, 1994, (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) Literatura Motivace Opa kování Vytvořující funkce (Formální) m( jcninné řady •oooo ooooooo ooooo mm Naším cílem nyní bude vybudovat základní prostředky pro řešení úloh obdobných těmto: odvození Cayleyho formule Určete počet stromů na daných n vrcholech. Analýza algoritmů Určete očekávaný počet porovnání během algoritmu Quicksort. Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady o»ooo ooooooo ooooo Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ]: return [] return qsort([x for x in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý největší, je ^. O Velikost tříděných polí ve fázi conquer: k — 1 a n — k. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vzta h: " 1 Cn = n-1 + ^2- (Q_i + Cn_k). k=l Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady oo»oo ooooooo ooooo " 1 Cn = n - l + + Cn-k), C0 = 0. n k=l 2 n Cn = n — 1 H— >^ Ck-i symetrie obou sum n t—' k=l n nCn = n(n — 1) + 2 Q_i vynásob n n-1 (n — l)Cn_i = (n — l)(n — 2) + 2 Q_i tentýž výraz pro C„_i nCn = (n + l)Cn_i + 2(n — 1) odečteno a upraveno Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady ooo»o ooooooo ooooo nCn = (n + l)Cn-1 + 2(n-l) Přestože jsme již rekurenci výrazně zjednodušili, takže je možné jednoduše iterativně hodnoty Cn dopočítat, je často žádoucí tyto hodnoty konkrétně (nebo alespoň přibližně) vyjádřit explicitně jako funkci n. Nejprve si pomůžeme drobným trikem, kdy vydělíme obě strany výrazem n(n + 1) : Cn = C„_! | 2{n - 1) n + 1 n n(n + l) Nyní tento vztah „rozbalíme" (telescope, příp. si pomůžeme substitucí Bn = Cn/(n + 1)): Cn = 2(n-l) 2(n-2) 2_1 Q n + 1 n(n + l) (n-l)n 2-3 2 Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady oooo» ooooooo ooooo Odkud — n—1 n + l f^(k + l)(k + 2y Výraz sečteme např. pomocí rozkladu na parciální zlomky (fc+iXfc+2) = kT2-kTTa dostaneme Cn -(.. - 1 2 Hn+1 - 2 + odkud Cn = 2(n + l)Hn+i-4(n + l) + 2 {Hn = Ylk=i \ Je SOLJčet prvních n členů harmonické řady). Přitom je možné odhadnout Hn ~ J" ^ + 7, odkud Cn ~ 2(n + l)(ln(n + 1) + 7 - 2) + 2. Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady ooooo ooooooo OOOOO Stručně nyní zopakujme některé důležité kombinatorické pojmy a vztahy: 2 Geometrická řada k xn+1 ~ 1 k=0 x- 1 Binomická věta (x + y)n = í n k k\ ín + l xkyn-k m J V m + 1 k=Q ~- ' V Horní binomická řada k=0 Vandermondova konvoluce Literatura Motivace Opakování Vytvořující funkce (Formální) mocninné řady ooooo •oooooo ooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla /', j a k taková, že /+_/' + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k G {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (X0+Xl+X2+X3+X4)(x0+X2+X4+X6+X8+X10)(x0+X5+X10+Xl5)- Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Skutečně tak dostáváme čtyři 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 Motivace Opa kování Vytvořující funkce (Formální) m jcninné řady ooooo o»ooooo OOOOO Předchozí příklad asi vypadal spíš jako složitý zápis jednoduchých „backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice /+_/' = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iei x')E/e./x'/) Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Hledáme přirozená čísla a\, 32, 35, 3io, 320 a 350 taková, že 3/ je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň 3i + 32 + 35 + 3io + 320 + a50 = 100- Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v (l+x + x2 + ...)(l+x2+x4 + ...)(l+x5+x10 + ...) (1 +x10 +x20 + +x20 +x40 + _ )(1 +x50 +x100 + _ ) Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady ooooo 00*0000 OOOOO Podobným způsobem můžeme znovu velmi snadno odvodit některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu. Věta (binomická) Pro n G N a r G M platí Na levou stranu se můžeme dívat jako na součin n polynomů, pravá je zápisem polynomu vzniklého jejich roznásobením. Dosazením čísel x = 1, resp. x = —1 dostáváme známé vzorce: Důsledek • E2=o( 2r (Z) = 0. Literatura Motivace Opa kování Vytvořující funkce (Formální) m jcninné řady ooooo ooo»ooo OOOOO Podíváme se teď na obě strany v binomické větě „spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek Platí k=0 w Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme n(l +x)"~1, derivací pravé strany (člen po členu) pak Yl"k=i ^(k)xkl- Dosazením x = 1 dostaneme tvrzení. □ Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni iné řady ooooo oooo«oo OOOOO Ještě upozorněme na vzdálenou souvislost se systémy polynomiálních rovnic, kterým jsme se věnovali minule. Ty lze použít na řešení obdobného typu úloh. Příklad Jaký je minimální počet bankovek potřebný k zaplacení 77700 Kč? Uvažujte nejprve, že k dispozici máte bankovky v hodnotě 100 Kč, 200 Kč, 500 Kč, 1000 Kč. Potom předpokládejte, že máte i bankovku 2000 Kč a na konec předpokládejte, že nemáte bankovky 2000 Kč, ale máte bankovky v hodnotě 5000 Kč. Řešení Označme si bankovky po řadě proměnnými s, d, p, t, D, P. Platbu bude reprezentovat polynom v těchto proměnných tak, že exponent každé proměnné bude určovat počet použitých příslušných bankovek. Pokud zaplatíme deseti tisícikorunami, deseti pětisetkorunami i stokorunami, pak bude q = ŕ10p10s627. Pokud máme pouze bankovky s,d,p,t, pak má ideál popisující vztah jednotlivých bankovek tvar l\ = (s2 — d, s5 — p, s10 — ŕ). Abychom minimalizovali počet použitých bankovek, spočítáme Grobnerovu bázi vzhledem ke gradovanému opačnému lexikografickému uspořádání (chceme eliminovat malé bankovky) Gi = (p2 - ŕ, s2 - d, d3 - sp, sd2 - p). Nyní vezmeme libovolný polynom reprezentující danou platbu. Redukcí tohoto polynomu vzhledem k bázi G\ dostaneme polynom, jehož stupeň je vzhledem k našemu monomiálnímu uspořádání nejmenší a je jednoduché si rozmyslet, že to je právě polynom reprezentující optimální platbu. Vezměme tedy např. q = s777. Redukce vzhledem ke G\ je pak t11 pd. To znamená, že optimální platba v prvním případě je 77 tisícikorun, jedna pětisetkoruna a jedna dvousetkoruna. Dohromady tedy 79 bankovek. Literatura Motivace Opa kování Vytvořující funkce (Formální) m jcninné řady ooooo 000000» OOOOO Řešení (pokr.) V druhém případě, kdy máme i bankovku D, je ideál I2 = (s2 — d,s5 — p, s10 — ŕ, s20 — D) a jeho Grobnerova báze je G2 = (ŕ2 - D, p2 - t, s2 - d, d3 - sp, sd2 - p). Redukce q = s111 vzhledem ke G2 dá D38tpd, takže tentokrát zaplatíme 41 bankovkami. Ve třetím případě je k = (s2 -d,s5- p, s10 - t, s50 - P) a G3 = (ŕ5 - P, p2 - t, s2 -d,d3- sp, sd2 - p), a redukce je proto rovna P15t2pd. V tomto případě tedy potřebujeme pouze 19 bankovek. □ Tuto jednoduchou úlohu lze samozřejmě vyřešit rychle prostou úvahou. Uvedený postup používající Grobnerovu bázi ovšem dává univerzální algoritmus, který lze automaticky použít pro vyšší částky a jiné, složitější případy. Definice Buď dána nekonečná posloupnost a = (so, ai, 32,...). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ 3/x' = 30 + 3lX + 32X2 H----. /=0 Poznámka O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. To ovšem vzápětí napravíme, když s využitím znalostí z analýzy nekonečných řad přejdeme od formálních mocninnných řad k příslušným funkcím. Literatura Motivace Opa kování Vytvořující funkce (Formální) m ícninné řady ooooo ooooooo o»ooo Příklad Posloupnosti samých jedniček odpovídá formální mocninná řada 1 + x + x2 + x3 + • • •. Z analýzy víme, že stejně zapsaná mocninná řada konverguje pro x G (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto „zakódování" posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale „diskrétní" matematici používají následující „podvod": • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,...) bez toho, aby se zajímali o konvergenci • jinými prostředky (často matematickou indukcí) tento vztah dokážou Literatura Motivace Opa kování Vytvořující funkce (Formální) mocnil nné řady ooooo ooooooo oo»oo Vytvořující funkce v praxi využíváme: • k nalezení explicitní formule pro n-tý člen posloupnosti; • často vytvořující funkce vycházejí z rekurentních vztahů, občas ale díky nim odvodíme rekurentní vztahy nové; • výpočet průměrů či jiných statistických závislostí (např. průměrná složitost algoritmu); • důkaz různých identit; • často je nalezení přesného vztahu příliš obtížné, ale mnohdy stačí vztah přibližný nebo alespoň asymptotické chování. Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořující funkcí pro základní posloupnost V některých případech (např. v důkazu Cayleyho věty) je použití exponenciálních vytvořujících funkcí výhodnější. 1Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Dirichletovy vytvořující funkce, kde roli faktoru x" hraje n~x), ale těmi se zde zabývat nebudeme. n>0 (1,1,1,1,...). Literatura Motivace Opa kování Vytvořující funkce (Formální) mocni nné řady ooooo ooooooo oooo» Následující větu znáte z matematické analýzy z loňského semestru: Věta Bud (sq, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G M, že pro všechna n > 1 je \an\ < Kn, pak řada a{x) = ^2 an*" n>0 konverguje pro každé x G Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Hodnotami funkce a(x) na libovolném okolí 0 je jednoznačně určena původní posloupnost, nebot má a(x) v 0 derivace všech řádů a platí _ a(")(0)