Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Diskrétní matematika - 9. týden Základy kombinatoriky Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2020 Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo ooooooo oo Obsah přednášky 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 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 Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. 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í): 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). 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 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) : n + 1 n n(n + l) Nyní tento vztah „rozbalíme" (telescope, příp. si pomůžeme substitucí Bn = Cn/n + 1): C n Cn-1 + 2(n-l) Cn 2(n-l) , 2(n-2) +----h 2-1 C --h — 2-32 n + 1 n(n+l) (n - l)n 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. 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 p\ 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, ■■-,Pk) = n\ 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(r?, k), platí Věta Počet kombinací s opakováním k-té třídy z n prvků je pro všechna 0 < k a 0 < n Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo ooo«ooo 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 E 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) = Žď 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.