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 □ ť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 zdroje ^^^^H^^^^^l^^^^^^^^^^l • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni. cz/Matematika_drsne_sviziie. □ s Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Doporučené zdroje 9 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 Elementární kombinatorické metody OOOOOOO Zobecněná binomická věta Plán přednášky 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 Zobecněná binomická věta o«ooo ooooooo 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]]) >0 0,0 Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta o«ooo ooooooo oo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ] : ret u r n [ ] ' return qsort([x for x in L [ 1 : ] if x=L[0]])^[ Počet porovnáni při rozděleni [divide): n — 1. Q (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. 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í (divide): n — 1. Q (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: jtlt9*c*-i)+iffa -tt-A-z)-* Cn = n-l + J^ - (Cfc_i + Cn-k). Cn = n - 1 + - (C/c_i + Cn-k), C0 = 0. n k=l □ s Literatura Motivace oo«oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Zjednodušení rekurence n i Cn = n-1 + 22- (Ck-i + Cn-k) , C0 = 0. n k=i A 2 " Cn = n — 1 H— C/c-i symetrie obou sum n f J n k=l Literatura Motivace oo«oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Zjednodušení rekurence n i Cn = n-1 + 22- (Ck-i + Cn-k) , C0 = 0. n k=l 2 " Cn = n — 1 H— Ck-i symetrie obou sum n f J n k=l n nCn = n(n — 1) + 2 Q_i vynásob n k=l Literatura Motivace oo«oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Zjednodušení rekurence n i Cn = n-1 + 22- (Ck-i + Cn-k) , C0 = 0. n k=l 2 " Cn = n — 1 H— Ck-i symetrie obou sum n f J n k=l n nCn = n(n — 1) + 2 Q_i vynásob n k=l n-1 (n - l)Cn-i = {n- l)(n - 2) + 2^Ck-i tentýž výraz pro Cn_i k=l Literatura Motivace oo«oo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Zjednodušení rekurence n i Cn = n-1 + 22- (Ck-i + Cn-k) , C0 = 0. n k=l 2 " Cn = n — 1 H— Ck-i symetrie obou sum n f J n k=l n nCn = n(n — 1) + 2 Q_i vynásob n k=l n-1 (n - l)Cn-i = (n - l)(n - 2) + 2^ Ck-i tentýž výraz pro Cn_i k=i nCn = (r? + l)Cn-i + 2(r? — 1) 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-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 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 C„_i 2(n-l) n+1 n n(n + l) V*-* ) '■M Nyní tento vztah „rozbalíme" (telescope, příp. si pomůžeme =■ substitucí Bn = Cnl n + 1): * 0 Cn 2(n - 1) 2(n - 2) 2-1 Q —— = —--- H—--- +----1---1--- n + 1 n(n + l) (n-l)n 2-3 2 Literatura Motivace oooo* Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení rekurence Odkud n + 1 ^ + 1 ^(/c + l)(/c + 2)- Literatura Motivace oooo* Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení rekurence Odkud Cn = 2 v k n + 1 fW/c + l)(/c + 2)' K = l Výraz sečteme např. pomocí rozkladu na parciální zlomky (/c+l)(/c+2) ~ k+2_ k+1 —— I"4! Ml 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 1 a dostaneme "j -/Lx£" (/c+l)(/c+2) k+2 k+1 Cn n + 1 = 2 Hn+1-2 + odkud n + 1 C„ = 2(n + l)H„+i-4(n + l) + 2 (/-/„ = Ylk=i I Je součet prvních n členů harmonické řady). . (4 * ji - >y^ v V 4 \1 fi. .— /I* *b Ml Literatura Motivace oooo* Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Vyřešení rekurence Odkud n + 1 ^ + 1 ^(/c + l)(/c + 2)- Výraz sečteme např. pomocí rozkladu na parciální zlomky (/c+i)(/f+2) = kT2 ~kTí a dostaneme Cn =2ÍHn+1-2+ 1 n + 1 V n+1 odkud C„ = 2(n + l)H„+i-4(n + l) + 2 (Hn = Ylk=i T Je součet prvních n členů harmonické řady) Přitom je možné odhadnout Hn ~ f." ^ + 7, odkud C„ - 2{n + l)(ln(n + 1) + 7 - 2) + 2. Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta Plán přednášky Q Elementární kombinatorické metody Z V i 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í. kefa,,--) /A* D / - M*- /3/ 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í. 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) n\ n(n — 1)... (r? — k + 1) n\ k) /c(/c - 1)... 1 (n-k)\k\' <□► -ír^J^ < > -E O Q, O 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 (k < n]_ c{n,k) n{n 1)...(n k ■ 1) n! /r(/r — 1)... 1 Pro počet variací platí (n- k)\k\' v(n, /c) = n(n - 1) • • • (n - /c + 1) * ^£)V pro všechny 0 < k < n (a nula jinak) 5 ) = 3 • t • \ Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO O0OOOOO 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í , . n\ "(Pi,... ,P/c) = Pll"'Pkl- i kA AO 4 4 OOAOO Pftr-M* l^pi^ lil í * / ^ÍoitäÍ pdd*S~- Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO O0OOOOO 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. ú • n ---- □ s" Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta ooooo oo«oooo oo Pro kombinace s opakováním, C(r?, k), platí Počet kombinací s opakováním k-té třídy z n prvků je pro všechna A 0 < k a 0 < n // 1 A\Lu \ 5, ?t S *>. Jrs*s* 2 >| 0 4 ^ >0 Q,o Literatura Motivace ooooo Elementární kombinatorické metody ooo«ooo Zobecněná binomická věta oo Princip inkluze a exkluse ^r^T\ lAo&M/A-l-r Í3/-/An5j _ _ 4 (A4Ď1CI Uvažujme obecnou konečnou množinu M a její podmnožiny Ai,... ,Ak. Budeme psát \M\ pro počet prvků množiny M, tj. pro mohutnost množiny M. x ít£ t*f"* * T M\ (u?=iA)l = IM\ + E(("^ E \Ak n • • • n A-,.)\ j=l ^ l 1 /l * ^ 4 i"*^" O o°nO Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO OOOOO0O oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvahou) □ s Literatura Motivace ooooo Elementární kombinatorické metody ooooo«o Zobecněná binomická věta oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvaho n(n + 1) (n Aritmetická řada * —-= I -""(Ml* "T" ř Literatura Motivace ooooo Elementární kombinatorické metody ooooo«o Zobecněná binomická věta oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvah n(n + 1) (n Aritmetická řada * —-= ( Geometrická řada k=o n X" = n+1 _ -i k X 1 X- 1 k=0 Literatura Motivace ooooo Elementární kombinatorické metody ooooo«o Zobecněná binomická věta oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvahou): n(n + 1) (n + 1 Aritmetická řada * —-= ( Geometrická řada k=o n X" = n+1 _ -i k X 1 X- 1 k=0 Binomická věta (x + y)n = ( j xkyn k=o ^ ' -k Literatura Motivace ooooo Elementární kombinatorické metody ooooo«o Zobecněná binomická věta oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvahou): n(n + 1) fn + 1 Aritmetická řada * —-= I k=0 Geometrická řada n X" = n+1 _ -i k X 1 X- 1 k=0 Binomická věta (x + y)n = i^kj^^" -k k=o n Horní binomická řada ( ) = ( k=o v 7 v 4 Z .... h / »vH J \ 1*1 J \ l ■*) - □ ► < a ► < » -= 'i -1 >0 Q,o Literatura Motivace Elementární kombinatorické metody Zobecněná binomická věta OOOOO OOOOO0O oo Příklady kombinatorických rovností Dokážeme (pokud možno kombinatorickou úvahou): n(n + 1) fn + 1 Aritmetická řada * —-= ( Geometrická řada k=o n X" = n+1 _ -i k X 1 X- 1 k=0 Binomická věta (x + y)n = i^kj^^" -k k=o n Horní binomická řada ( ) = ( Vandermondova konvoluce í J = k 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ě ... 1*0 Ptíáír J per*, k-h cJJL^ ök/k- ^>£Z) § _!----7«-- _ 10b \ - r L i I__■ j J 1 -^ř ^ í. ^ = 1- - ( 3oV. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta oo Plán přednášky Zobecněná binomická věta Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta •o Zobecněná binomická věta V" Pro reálná čísla y, z,jfry + z>0, platí oo ' a kde i pro a ^ N klademe ^ a(a — 1) • • • (a — k + 1) = k\ 7: Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Zobecněná binomická věta om 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řeni koeficientů v mocninné řadě pro v."w % 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/ý) 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.