Literatura Motivace Elementární kombinatorické metody Zobecněná bino micka věta ooooo ooooooo 00 Matematika IV - 7. týden Elementární kombinatorika Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Motivace Elementární kombinatorické metody Zobecněná bino micka věta ooooo ooooooo 00 Q| Motivace Q Elementární kombinatorické metody Q| Zobecněná binomická věta Literatura Motivace Elementární kombinatorické metody Zobecněná bino micka věta ooooo ooooooo 00 • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Donald E. Knuth, The Art Of Computer Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo ooooooo oo Plán přednášky 0 Motivace Q Element Q Zobecněná binomická věta Literatura Motivace •oooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 Často potřebujeme umět spočítat, kolika možnými způsoby se něco může stát! Nebývá to jednoduché a naším cílem nyní bude vybudovat základní prostředky pro řešení úloh obdobných těmto: Analýza algoritmů: Např. chceme zjistit očekávaný počet porovnání během algoritmu Quicksort. Literatura Motivace •oooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 Často potřebujeme umět spočítat, kolika možnými způsoby se něco může stát! Nebývá to jednoduché a naším cílem nyní bude vybudovat základní prostředky pro řešení úloh obdobných těmto: Analýza algoritmů: Např. chceme zjistit očekávaný počet porovnání během algoritmu Quicksort. Odvození Cayleyho formule: Chceme znát počet různých stromů na daných n vrcholech. Literatura Motivace o»ooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 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]]) Literatura Motivace o»ooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 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]]) Q 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 ^. @ Velikost tříděných polí ve fázi conquer: k — 1 a n — k. Literatura Motivace o»ooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 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 oo»oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 1 Cn = n - 1 + V' - + Cn-k), C0 = 0. t—' n k=l Literatura Motivace Elementární kombinatorické metody Zobecněná bino micka věta oo»oo ooooooo 00 1 Cn = n - 1 + V' - + Cn-k), C0 = 0. t—' n k=l 2 " Cn = n — 1 H— >^ Ck-i symetrie obou sum n t—' k=l Literatura Motivace oo»oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 " 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 C/<_i vynásob n 4 □ ► 4 3 ► 4 ^ ► 4 š ► ^ "O^O Literatura Motivace oo»oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 " 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 y^ Ck-i vynásob n k=l n-1 (n — l)Cn_i = (n — — 2) + 2 y^ Ck-i tentýž výraz pro C„_i 4 □ ► 4 3 ► 4 ^ ► 4 š ► 41 "O^O Literatura Motivace oo»oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 " 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)C„_i + 2(n — 1) odečteno a upraveno Literatura Motivace ooo»o Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 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. Literatura Motivace ooo»o Elementární kombinatorické metody ooooooo Zobecněná binomická věta 00 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 - + 1 n Geometrická řada X^*^ : 2 k=0 x- 1 n / Binomická věta (x + y)n = í xkyn~k Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo ooooo»o oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvahou) Aritmetická rada ± „ = "<" + *> - + 1 n Geometrická řada X^*^ : 2 V 2 k=0 x- 1 n / Binomická věta (x + y)n = í k=o Horní binomická řada | k=Q xkyn-k n + 1 m + l Elementární kombinatorické metody ooooo»o kých rovností Dokážeme (pokud možno kombinatorickou úvahou) Aritmetická rada ± „ = "<" + *> - + 1 n Geometrická řada X^*^ : 2 V 2 k=0 x- 1 n / Binomická věta (x + y)n = i k=o ^ Horní binomická řada y^ | k=Q xkyn-k n + 1 m + l Vandermondova konvoluce m + n k=o Literatura Motivace ooooo Elementární kombinatorické metody 000000» Zobecněná binomická věta 00 Ve vězení je 100 vězňů s čísly jedna až sto. V uzavřené místnosti je 100 krabiček s čísly jedna až sto a v každé z nich náhodně rozdělené papírky s čísly také 1 až sto. Do místnosti budou po jednom postupně vcházet vězni a každý smí otevřít 50 krabic, vězni přitom spolu nekomunikují. Jestliže každý z nich najde svoje číslo, všechny pustí, v opačném případě všechny popraví. Doporučte nějakou rozumnou strategii pro vězně ... Literatura Motivace Elementární kombinatorické metody Zobecněná bino micka věta ooooo ooooooo 00 Q| Motivace Q Elementární kombinatorické metody Q| Zobecněná binomická věta Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta •O Pro reálná čísla x, y, a, x + y > 0, platí oo (x+y)« = £ oo fr=0 xkya~k, kde i pro a ^ N klademe /oĺ\ a(o! — 1) • • • [a — k + 1) Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta O* Budeme dokazovat v ekvivalentním tvaru (předpokládáme y > 0 a tedy můžeme z celého výrazu vytknout ya) Jde nám tedy o vyjádření koeficientů v mocninné řadě pro mocninnou funkcí f(x) = (1 + x)a se středem v x = 0. Jednoduchou kombinatorickou úvahou využívající pravidlo pro derivování mocninných řad člen po členu odvodíme požadovaný výsledek. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta O* Budeme dokazovat v ekvivalentním tvaru (předpokládáme y > 0 a tedy můžeme z celého výrazu vytknout ya) Jde nám tedy o vyjádření koeficientů v mocninné řadě pro mocninnou funkcí f(x) = (1 + x)a se středem v x = 0. Jednoduchou kombinatorickou úvahou využívající pravidlo pro derivování mocninných řad člen po členu odvodíme požadovaný výsledek. Všimněme si, že pro přirozené a se od jistého k v čitateli zobecněného binomického koeficientu vždy objeví jako součinitel nula, proto v takovém případě dostáváme opět klasickou konečnou sumu z binomické věty.