Literatura Motivace Elementární kombinatorické metody Binomická věta ooooo ooooooo OOOOOOO Matematika IV - 7. týden Elementární kombinatorika Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 □ g Literatura Motivace Elementární kombinatorické metody Binomická věta ooooo ooooooo OOOOOOO Obsah přednášky Q Motivace Q Elementární kombinatorické metody inomická věta Literatura Motivace Elementární kombinatorické metody Binomická věta ooooo ooooooo ooooooo 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 Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO 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. Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO Plán prednášky O Mot ivace Z V i >0 Q,o Literatura Motivace Elementární kombinatorické metody Binomická věta •oooo ooooooo ooooooo 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 Binomická věta •oooo ooooooo ooooooo 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 o«ooo Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO 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]]) Literatura Motivace O0OOO Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO 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 Binomická věta OOOOOOO 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 Binomická věta OOOOOOO Zjednodušení rekurence i Cn = n-l + y^ - (Cfr_i + Cn-k), C0 = 0. n k=l Literatura Motivace Elementární kombinatorické metody Binomická věta ootoo ooooooo ooooooo 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 Binomická věta ootoo ooooooo ooooooo 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 symetrie obou sum vynásob n Literatura Motivace Elementární kombinatorické metody Binomická věta ootoo ooooooo ooooooo 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_i k=l Literatura Motivace Elementární kombinatorické metody Binomická věta ootoo ooooooo ooooooo 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 Binomická věta OOOOOOO 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 Binomická věta OOOOOOO 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 Binomická věta OOOOOOO Vyřešení rekurence Odkud Cn n + 1 n-1 2^{k + l){k + 2y Literatura Motivace oooo« Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO 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 /c+1 Literatura Motivace oooo« Elementární kombinatorické metody OOOOOOO Binomická věta OOOOOOO 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é rady). Literatura Motivace oooo« Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO 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 Binomická věta OOOOOOO Plán prednášky Q Elementární kombinatorické metody Z V i Literatura Motivace ooooo Elementární kombinatorické metody •oooooo Binomická věta OOOOOOO 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 Binomická věta ooooo •oooooo ooooooo 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 Binomická věta ooooo •oooooo ooooooo 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) /c(/c - 1)... 1 (n- k)\k\' Literatura Motivace ooooo Elementární kombinatorické metody •oooooo Binomická věta ooooooo 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 Binomická věta OOOOO O0OOOOO ooooooo 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í Literatura Motivace Elementární kombinatorické metody Binomická věta OOOOO O0OOOOO ooooooo 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, • • • iPk) = 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 00*0000 Binomická věta OOOOOOO Pro kombinace s opakováním, C(r?, k), platí Theorem 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 Binomická věta OOOOO OOO0OOO ooooooo 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 ^ l0 0,0 Literatura Motivace ooooo Elementární kombinatorické metody oooooo* Binomická věta ooooooo Odkazovači strategie 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ě ... Motivace ooooo Elementární kombinatorické metody OOOOOOO Binomická věta OOOOOOO Plán prednášky inomická věta Motivace ooooo Elementární kombinatorické metody Binomická věta ooooooo ►oooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují Literatura Motivace ooooo Elementární kombinatorické metody OOOOOOO Binomická věta •oooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Máme v peněžence 4 korunové mince, 5 dvou korunový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? Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta •oooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Máme v peněžence 4 korunové mince, 5 dvou korunový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 / + j + k = 22 a zároveň i 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 +x15 ) 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. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta •oooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Máme v peněžence 4 korunové mince, 5 dvou korunový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 / + j + k = 22 a zároveň i 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 +x15 ) 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 ooooo Elementární kombinatorické metody ooooooo Binomická věta o«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. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta o«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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(S/eJ x"0- Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta o«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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(S/eJ x"0- Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta o«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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(S/eJ x"0- 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 ai, a2, 35, aio, ^20 a a50 taková, že a/je násobkem / pro všechna / e {1,2,5,10,20,50} a zároveň ai + a2 + a5 + ai0 + a2o + a50 = 100. Literatura Motivace Elementární kombinatorické metody Binomická věta ooooo ooooooo o«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 £ N počet řešení (ij) rovnice / + j — r splňujících / £ IJ £ J roven koeficientu u xr v polynomu x')(ž2jeJ x"0 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 ai, a2, 35, aio, ^20 a a50 taková, že a/je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň ai + a2 + 35 + aio + a2o + ^50 = 100. Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v (1 + x + x2 + ... )(1 + x2 + x4 + ... )(1 + x5 + x10 + . . . ) (l+x10+x20 + ...)(l + x20 + x40 + ...)(l+x50 +x100 + ...) Literatura Motivace ooooo Elementární kombinatorické metody OOOOOOO Binomická věta oo«oooo V krabici je 5 červených, 10 modrých a 15 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 7 míčků k vyzkoušení? A o kolik míň to bude, když chceme aspoň 1 červený, aspoň 2 modré a aspoň 3 bílé? Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta oo«oooo Příklad V krabici je 5 červených, 10 modrých a 15 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 7 míčků k vyzkoušení? A o kolik míň to bude, když chceme aspoň 1 červený, aspoň 2 modré a aspoň 3 bílé? Řešení Hledaný počet je roven koeficientu u x7 v součinu (1+x + x^H-----hxD)(l+x + x^H-----hx10)(l+x + x^H-----hx1D). .15 Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta oo«oooo Příklad V krabici je 5 červených, 10 modrých a 15 bílých míčků, míčky stejné barvy přitom nelze rozeznat. Kolika způsoby je možné vybrat soubor 7 míčků k vyzkoušení? A o kolik míň to bude, když chceme aspoň 1 červený, aspoň 2 modré a aspoň 3 bílé? Řešení Hledaný počet je roven koeficientu u x7 v součinu (1+x + x^H-----hxD)(l+x + x^H-----hx10)(l+x + x^H-----hx1D). .15 Když máme předpsaný nějaký počet jako nejmenší možný, prostě začneme až od příslušných mocnin. Literatura Motivace Elementární kombinatorické metody Binomická věta ooooo ooooooo OOOOOOO Využitím operací s polynomy lze velmi snadno odvodit také některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu. Literatura Motivace ooooo Elementární kombinatorické metody OOOOOOO Binomická věta OOOOOOO Využitím operací s polynomy lze velmi snadno odvodit také 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 eN a r eR platí Na levou stranu se můžeme dívat jako na součin n polynomů, právaje zápisem polynomu vzniklého jejich roznásobením. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta OOOOOOO Využitím operací s polynomy lze velmi snadno odvodit také 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 eN a r eR platí Na levou stranu se můžeme dívat jako na součin n polynomů, právaje 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 • ĽJU(-i)*ffi = o. Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta OOOO0OO 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í e<; H"_1 /c=0 V 7 Literatura Motivace ooooo Elementární kombinatorické metody ooooooo Binomická věta OOOO0OO 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í /c=0 V 7 Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme n(l +x)n_1, derivací pravé strany (člen po členu) pak J2k=i ^(/c)*^1- Dosazením x = 1 dostaneme tvrzení. □ Literatura Motivace Elementární kombinatorické metody Binomická věta OOOOO OOOOOOO OOOOO0O Zobecněná binomická věta Pro reálná čísla x, y, a, x + y > 0, platí 00 / \ k. .a—k kde i pro a £ N klademe a\ a(a — 1) • • • (a — k + 1) k) = k\ Literatura Motivace ooooo Elementární kombinatorické metody OOOOOOO Binomická věta 000000« Budeme dokazovat v ekvivalentním tvaru (předpokládáme y > O 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 Binomická věta 000000« Budeme dokazovat v ekvivalentním tvaru (předpokládáme y > O 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.