Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce OOOOOO Diskrétní matematika - 9. týden Základy kombinatoriky Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2024 □ |5P Motivace Elementární kombinatorické metody Vytvořující funkce oooooo ooooooo oooooo Obsah přednášky Motivace Q Elementární kombinatorické metody Q Vytvořující funkce Motivace Elementární kombinatorické metody Vytvořující funkce oooooo ooooooo oooooo 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. Motivace Elementární kombinatorické metody Vytvořující funkce oooooo ooooooo oooooo 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 Vytvořující funkce oooooo Motivace Motivace Elementární kombinatorické metody Vytvořující funkce o»oooo ooooooo oooooo 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. Motivace Elementární kombinatorické metody Vytvořující funkce o»oooo ooooooo oooooo 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. Motivace oo«ooo Elementární kombinatorické metody ooooooo Vytvořující funkce oooooo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer): if L []: return [] return qsort([x for x i n L[l:] if x < L[0]]) + L[0:1] + qsort([x for x i n L[l:] if x >= L[0]] Motivace oo«ooo Elementární kombinatorické metody ooooooo Vytvořující funkce OOOOOO Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer): if L []: return [] return qsort([x for x i n L[l:] if x < L[0]]) + L[0:1] + 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. Motivace oo«ooo Elementární kombinatorické metody ooooooo Vytvořující funkce oooooo Quicksort - analýza průměrného případu Ukázka implementace (divide and conquer): if L []: return [] return qsort([x for x i n L[l:] if x < L[0]]) + L[0:1] + 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 Motivace ooo»oo Elementární kombinatorické metody ooooooo Vytvořující funkce oooooo Zjednodušení rekurence i Cn = n-l + y^ - (Cfr_i + Cn-k), C0 = 0. n k=l Motivace Elementární kombinatorické metody Vytvořující funkce ooo»oo ooooooo oooooo 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 Motivace Elementární kombinatorické metody Vytvořující funkce ooo»oo ooooooo oooooo 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 - 1) + 2 ^ Q.i vynásob n k=l Motivace Elementární kombinatorické metody Vytvořující funkce ooo»oo ooooooo oooooo 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? nC„ = n(n - 1) + 2 ^ Ck-i k=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 Motivace Elementární kombinatorické metody Vytvořující funkce ooo»oo ooooooo oooooo 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? nC„ = n(n - 1) + 2 ^ Ck-i k=l n-1 {n - l)Cn_i = (n - l)(n - 2) + 2 ^ C*_i /c=l nCn = {n + l)Cn-i+2{n-l) symetrie obou sum vynásob n tentýž výraz pro Cn-\ odečteno a upraveno Motivace oooo»o Elementární kombinatorické metody ooooooo Vytvořující funkce oooooo 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. Motivace oooo»o Elementární kombinatorické metody ooooooo Vytvořující funkce oooooo 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-3 2 n + 1 n(n+l) (n - l)n □ ť3? - = Motivace Elementární kombinatorické metody Vytvořující funkce ooooo* ooooooo oooooo Vyřešení rekurence Odkud Cn n-l n + 1 2E k= Motivace Elementární kombinatorické metody Vytvořující funkce ooooo* ooooooo oooooo 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 Motivace Elementární kombinatorické metody Vytvořující funkce ooooo* ooooooo oooooo Vyřešení rekurence Odkud Cn n + 1 n-l 2E k= Výraz sečteme např. pomocí rozkladu na parciální zlomky a dostaneme (/c+l)(/c+2) — /c+2 k+1 Cn n + 1 = 2 [ Hn+1 - 2 + n + 1 odkud Cn = 2(n + l)Hn+1-4(n + l) + 2 (Hn = J2k=i \ Je sou£et prvních n členů harmonické řady) Motivace Elementární kombinatorické metody Vytvořující funkce ooooo* ooooooo oooooo Vyřešení rekurence Odkud Cn n + 1 n-l 2E k= Výraz sečteme např. pomocí rozkladu na parciální zlomky a dostaneme (fc+l)(fc+2) — k+2 k+1 Cn n + 1 = 2[Hn+1-2 + n + 1 odkud Cn = 2(n + l)Hn+1-4(n + l) + 2 (Hn = Y^k=i \ Je součet prvních n členů harmonické řady) Přitom je možné odhadnout Hn ~ A" + 7, odkud Cn ~ 2(n + l)(ln(n + 1) + 7 - 2) + 2. Motivace Elementární kombinatorické metody Vytvořující funkce OOOOOO »000000 oooooo Q Elementární kombinatorické metody L V V-/ I LJ I I I I U I i r\v^ ^ Motivace OOOOOO Elementární kombinatorické metody •ooooo Vytvořující funkce OOOOOO 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í. Motivace Elementární kombinatorické metody Vytvořující funkce OOOOOO O0OOOOO oooooo 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í. Motivace Elementární kombinatorické metody Vytvořující funkce oooooo o»ooooo oooooo 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\' Motivace oooooo Elementární kombinatorické metody •ooooo Vytvořující funkce OOOOOO 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) rín m — fn\ — n(n-l)...(n- k + 1) n\ l' ; \k) /c(/c - 1)... 1 {n-k)\k\' Pro počet variací platí v(n, k) = n(n - 1) • • • (n - k + 1) pro všechny 0 < k < n (a nula jinak). Motivace oooooo Elementární kombinatorické metody •ooooo Vytvořující funkce OOOOOO 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) rín m — fn\ — n(n-l)...(n- k + 1) n\ l' ; \k) /c(/c - 1)... 1 {n-k)\k\' Pro počet variací platí v(n, k) = n(n - 1) • • • (n - k + 1) pro všechny 0 < k < n (a nula jinak). Příklad Určete, kolika způsoby lze z 15 poslanců vybrat čtyřčlennou komisi, není-li možné, aby jistí 2 poslanci pracovali spolu. Motivace Elementární kombinatorické metody Vytvořující funkce oooooo o»ooooo oooooo 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- l)...l n\ (n-k)\k\ Pro počet variací platí v(n, k) = n(n - 1) • • • (n - k + 1) pro všechny 0 < k < n (a nula jinak) Příklad Určete, kolika způsoby lze z 15 poslanců vybrat čtyřčlennou komisi, není-li možné, aby jistí 2 poslanci pracovali spolu. Výsledek je - (x23) = 1287. Motivace oooooo Elementární kombinatorické metody o»oooo Vytvořující funkce OOOOOO 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,..., p/c), platí Motivace Elementární kombinatorické metody Vytvořující funkce oooooo oo»oooo oooooo 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. Motivace oooooo Elementární kombinatorické metody OOO0OOO Vytvořující funkce OOOOOO 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 cMJ-f + í-1). Motivace Elementární kombinatorické metody Vytvořující funkce oooooo oooo«oo oooooo 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\{uUAi)\ = \M\ + ÍtU-l)i E j=l ^ l <==►o<\c- Motivace OOOOOO Elementární kombinatorické metody ooooooo Vytvořující funkce oo»ooo 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. Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce oo»ooo 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 (Yliel x')(S/eJ x"0- Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce oo»ooo 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 (Yliel 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č? Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce oo»ooo 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 (Yliel 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. 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);e/x0(X)/e.yx*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 / £ {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 + ...) Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce ooo»oo Drobný rozdíl je v tom, že se nyní nejedná o polynom, ale nekonečnou řadu; přitom ale není problém všechny výpočty končit u x100, čímž se opět dostaneme k polynomům (nicméně nekonečná geometrická řada má jednodušší vzorec pro součet!). <□► < rnP ► < -E ► < -E ► E O °n O Motivace Elementární kombinatorické metody Vytvořující funkce oooooo ooooooo ooo»oo Drobný rozdíl je v tom, že se nyní nejedná o polynom, ale nekonečnou řadu; přitom ale není problém všechny výpočty končit u x100, čímž se opět dostaneme k polynomům (nicméně nekonečná geometrická řada má jednodušší vzorec pro součet!). 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é? Motivace Elementární kombinatorické metody Vytvořující funkce oooooo ooooooo ooo»oo Drobný rozdíl je v tom, že se nyní nejedná o polynom, ale nekonečnou řadu; přitom ale není problém všechny výpočty končit u x100, čímž se opět dostaneme k polynomům (nicméně nekonečná geometrická řada má jednodušší vzorec pro součet!). 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 (l+x + x2 + - • - +x5)(l+x + x2 + - • - +x10)(l+x + x2 + + x15). Motivace Elementární kombinatorické metody Vytvořující funkce oooooo ooooooo ooo»oo Drobný rozdíl je v tom, že se nyní nejedná o polynom, ale nekonečnou řadu; přitom ale není problém všechny výpočty končit u x100, čímž se opět dostaneme k polynomům (nicméně nekonečná geometrická řada má jednodušší vzorec pro součet!). 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 (l+x + x2H-----hx5)(l+x + x2H-----hx10)(l+x + x2H-----hx15). Když máme předepsaný nějaký počet jako nejmenší možný, prostě začneme až od příslušných mocnin. Motivace OOOOOO Elementární kombinatorické metody ooooooo Vytvořující funkce oooo«o 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. Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce oooo«o 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 G N a r G R platí k=0 V J Na pravou stranu se můžeme dívat jako na součin n polynomů, levá je zápisem polynomu vzniklého jejich roznásobením. Motivace oooooo Elementární kombinatorické metody ooooooo Vytvořující funkce oooo«o 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