Diskrétní matematika - 9. týden Základy kombinatoriky á věta Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 □ ť5P Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo ooooooo oo Obsah přednášky Q Mot ivace Q Elementární kombinatorické metody Q Zobecněná binomická věta Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo ooooooo oo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. □ s 1 ► Ě -O o, O Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Doporučené zdroje • 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 Programmi • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Motivace ooooo Plán prednášky Elementární kombinatorické metody OOOOOOO Zobecněná binomická věta O Mot ivace Z V i >0 Q,o Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta •oooo ooooooo oo Kombinatorika = umění počítat Č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 Elementární kombinatorické metody Zobecněná binomická věta •oooo ooooooo oo Kombinatorika = umění počítat Č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 Elementární kombinatorické metody o«ooo ooooooo Zobecněná binomická věta oo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): ifL []: return [] return qsort([x for x i n L[l:] if x=L[0]]) Literatura Motivace o«ooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): if L []: return [] return qsort([x for x i n L[l:] if x=L[0]]) Počet porovnání při rozdělení {dividé): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /c-tý největší, je ^. Q 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 oo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): if L []: return [] return qsort([x for x i n L[l:] if x=L[0]]) Počet porovnání při rozdělení {dividé): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je /c-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í vztah: n 1 Cn = n-l + y^ - (Cfr_i + Cn-k). n Literatura Motivace oo«oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Zjednodušení rekurence 1 Cn = n - l + (Ck-i + Cn_/c), C0 = 0. k=l □ s Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta oo«oo ooooooo oo Zjednodušení rekurence n i Cn = n-l + y^ - (Cfr_i + Cn-k), C0 = 0. k=l n Cn = n - 1 + - V C r? /c-l symetrie obou sum k=l Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta oo«oo ooooooo oo Zjednodušení rekurence n i Cn = n-l + y^ - (Cfr_i + Cn-k), C0 = 0. k=l n Cn = n - 1 + - V C r? /c-l symetrie obou sum k=l n nCn = n(n-l) + 2^2 Ck-i vynásob n k=l Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta oo«oo ooooooo oo Zjednodušení rekurence n i Cn = n-l + y^ - (Cfr_i + Cn-k), C0 = 0. k=l n Cn = n - 1 + - V C r? /c-l /c=l r? n C = n(n - 1) + 2 ^ Q_i /c=l n-1 symetrie obou sum vynásob n (n - l)Cn-i = {n- l)(n - 2) + 2^Ck-i tentýž výraz pro Cn k=l Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta oo«oo ooooooo oo Zjednodušení rekurence n i Cn = n-l + y^ - (Cfr_i + Cn-k), C0 = 0. k=l n Cn = n - 1 + - V C r? /c-l /c=l r? n C = n(n - 1) + 2 ^ Q_i /c=l n-1 (n - l)C„_i = (n - l)(n - 2) + 2 ^ C*_i /c=l (n + l)Cn_i+2(n-l) symetrie obou sum vynásob n tentýž výraz pro Cn-\ odečteno a upraveno Literatura Motivace ooo»o Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení reku re n ce nCn = {n+l)Cn-l+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. □ s Literatura Motivace ooo»o Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení reku re n ce 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 _ Cn-i 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) n + 1 n(n+l) (n - l)n 2-1 Ci Literatura Motivace oooo* Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení rekurence Odkud Cn n + 1 n-1 2^{k + l){k + 2y Literatura Motivace oooo* Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení rekurence Odkud Cn n + 1 n-l 2E k= Výraz sečteme např. pomocí rozkladu na parciální zlomky k _ _2___L_ (/c+l)(/c+2) — /c+2 k+1 Literatura Motivace oooo* Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení rekurence Odkud Cn n + 1 n-1 2^{k + l){k + 2y Výraz sečteme např. pomocí rozkladu na parciální zlomky (/c+i)(/f+2) = kT2 ~kTí a dostaneme n + 1 V n + 1 J odkud Cn = 2(n + l)Hn+1-4(n + l) + 2 (Hn = Y2k=i \ Je S0LJíet Pivních n členů harmonické řady). Literatura Motivace oooo* Elementární kombinatorické metody OOOOOOO Zobecněná binomická věta oo Vyřešení reku re n ce Odkud Cn n + 1 n-l 2E k= j (* + !)(*+ 2) Výraz sečteme např. pomocí rozkladu na parciální zlomky a dostaneme (/c+l)(/c+2) — /c+2 k+1 C" =2ÍHn+1-2+ 1 n + 1 n + 1 odkud Cn = 2{n + l)Hn+1 - 4(n + 1) + 2 (Hn = J2k=i I Je souč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. >0 Q,o Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta Plán prednášky Q Elementární kombinatorické metody Z V i >0 0,0 Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO «000000 oo Pravidlo součtu a součinu Vylučující se možnosti sčítáme, vzájemně nezávislé a současně se vyskytující případy se násobí. Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO «000000 oo Pravidlo součtu a součinu Vylučující se možnosti sčítáme, vzájemně nezávislé a současně se vyskytující případy se násobí. Na dané konečné množině S s n prvky je právě n\ různých pořadí. Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO «000000 oo Pravidlo součtu a součinu Vylučující se možnosti sčítáme, vzájemně nezávislé a současně se vyskytující případy se násobí. Na dané konečné množině S s n prvky je právě n\ různých pořadí. Počet kombinací /c-tého stupně z n prvků je (/c < n) n n(n - 1)... (n - k + 1) k{k- !)...! (n- k)\k\' Literatura Motivace ooooo Elementární kombinatorické metody •oooooo Zobecněná binomická věta oo Pravidlo součtu a součinu Vylučující se možnosti sčítáme, vzájemně nezávislé a současně se vyskytující případy se násobí. Na dané konečné množině S s n prvky je právě n\ různých pořadí. Počet kombinací /c-tého stupně z n prvků je (/c < n) ( u\_(n\_ n(n-l)...(n- k + 1) _ n\ c{n,k)- - - (n-k)\k\m Pro počet variací platí v(n, k) = n(n - 1) • • • (n - k + 1) pro všechny 0 < k < n (a nula jinak). Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo o«ooooo oo Kombinace a variace s opakováním Nechť je mezi n danými prvky pi prvků prvního druhu, P2 prvků druhého druhu, . . . , Pk prvků /c-tého druhu, Pi + P2 + • • • + Pk — n> potom pro počet poradí těchto prvků s opakováním, P(pi,..., Pk), platí Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo o«ooooo oo Kombinace a variace s opakováním Nechť je mezi n danými prvky pi prvků prvního druhu, P2 prvků druhého druhu, ... , Pk prvků /c-tého druhu, Pi + P2 + • • • + Pk — n> potom pro počet pořadí těchto prvků s opakováním, P(pi,..., Pk), platí P{Pi, • • • ,P/c) = pi! • • • pk\ Pro variace /c-tého stupně s opakováním z n prvků platí V(n,k) = nk. Literatura Motivace ooooo Elementární kombinatorické metody oo«oooo Zobecněná binomická věta oo Pro kombinace s opakováním, C(n, k), platí Počet kombinací s opakováním k-té třídy z n prvků je pro všechna 0 < k a 0 < n C{n,k) = Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO OOO0OOO oo Princip inkluze a exkluse Uvažujme obecnou konečnou množinu M a její podmnožiny Al,..., Ak. Budeme psát \M\ pro počet prvků množiny M, tj. mohutnost množiny M. pro M\(U?=iA)l = M\ + H(-iy £ j=l ^ l 0, platí OO , v .a—k k k=0 kde i pro a £ N klademe cA a (a — 1) • • • (a — k + 1) k) = Žď □ ^ > 4 = > 4 .= 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, označíme x = z/y) 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, označíme x = z/y) 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.