Kombinatorika- 1. Základy diskrétní matematiky, BI-ZDM

Kombinatorika - 1 doc. RNDr. Josef Kolář, CSc. Katedra teoretické informatiky FIT České vysoké učení technické v Praze c

Josef Kolar, 2011

Základy diskrétní matematiky, BI-ZDM ZS 2011/12, Lekce 6

Evropský sociální fond. Praha & EU: Investujeme do vaší budoucnosti

doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1

ZDM, ZS 2011/12, Lekce 6

1 / 16

Základní principy

Motivační příklad 1 Příklad 1 Restaurace v Masarykově koleji nabízí ve svém denním menu tři druhy salátů, dvě polévky, tři hlavní jídla, dva zákusky a tři nabídky pití. Kolik je různých možností pro výběr oběda obsahujícího všechny chody? Výběr závisí pouze na rozhodnutí hosta, jednotlivé chody představují nezávislé možnosti, takže počty alternativ se budou násobit. Host má dispozici celkem 3 · 2 · 3 · 2 · 3 = 108 nabídek. V kolika různých pořadích je možno uvedené chody konzumovat, pokud jediným omezením je, že polévka se musí jíst dříve než hlavní jídlo? Počet pořadí, v nichž bychom mohli konzumovat kompletní oběd o pěti chodech, je roven 5! = 5 · 4 · 3 · 2 · 1 = 120. Z těchto možností přesně polovina splňuje podmínku, že polévka předchází hlavní jídlo, tedy 60. (OBRÁZEK 1) doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


2 / 16

Základní principy

Motivační příklad 2 Příklad 2 Kolik existuje různých listů (rozdání) deseti mariášových karet, ve kterých se vyskytne svršek a král stejné barvy? Mariáš se hraje kartami čtyř barev (červená, zelená, kule a žaludy), každá barva má karty osmi hodnot (7,. . . , 10, spodek, svršek, král a eso). Jsou 4 možnosti pro volbu společné barvy svrška a krále. Po zahrnutí svrška a krále stejné barvy bude následovat 8 dalších různých karet vybraných ze 30-ti zbývajících. Je zřejmé, že nezáleží na pořadí, v jakém karty do listu vybereme. Celkový počet možností tedy je 4 · 30 · 29 · 28 · 27 · 26 · 25 · 24 · 23/10! = 260130 doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


3 / 16

Základní principy

Sčítací princip Kombinatorika nás učí počítat - nelze všechno nechat jen na počítačích!

Sčítací princip Neformálně Jestliže je možné jistý proces rozdělit na N případů, kdy si proces vždy vybere právě jeden z těchto případů, a P i-tý případ je možno provést ni způsoby, pak je proces možno provést N i=1 ni způsoby. Množinově

S Uvažujme množinu M objektů. Jestliže existuje rozklad M = N i=1 Mi PN (množiny Mi jsou navzájem disjunktní), pak |M | = i=1 |Mi |


Kombinatorika - 1


4 / 16

Základní principy

Násobící princip Násobící princip Neformálně Jestliže je možno jistý proces rozdělit na N nezávislých fází, kdy si proces v i-té fázi vždy Q vybere jeden z ni způsobů jejího provedení, pak je proces možno provést N i=1 ni způsoby. Množinově

Uvažujme množinu M objektů. Jestliže je Q M = M1 × M2 × . . . × MN , pak |M | = N i=1 |Mi |

Poznámka: Množinové vyjádření není tak univerzální, jak bychom pro popis principu potřebovali. Množiny Mi (pro i > 1) nemusí být dány předem, ale každá může záviset na výsledku předchozích (i − 1) voleb, každá Mi musí mít vždy stejný počet prvků ni . doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


5 / 16

Základní principy

Doplňkový princip Doplňkový princip Neformálně Jistý proces lze provést určitým známým počtem způsobů, přitom tyto způsoby se rozpadají do dvou skupin. Pokud umíme určit počet způsobů v první skupině, bude počet způsobu ve druhé skupině roven rozdílu celkového počtu způsobů a počtu způsobů první skupiny. Množinově Uvažujme množinu M počítaných objektů. Jestliže je M1 ⊂ M , pak platí |M − M1 | = |M | − |M1 |. Poznámka: Je zřejmé, že doplňkový princip je jen jinou formulací sčítacího principu použitého na rozklad M = M1 ∪ (M − M1 ).


Kombinatorika - 1


6 / 16

Základní principy

Hezký příklad doc. Habaly Příklad 3 V obchodě mají 6 různých druhů USB flash pamětí. Čtyři kamarádi si jdou koupit každý jednu. Zkusíme řešit několik kombinatorických úloh souvisejících s popsanou situací. a) Kolika způsoby mohou vejít do prodejny jeden po druhém? Řešení: 4 fáze, postupně se vybírá ze 4, 3, 2 a 1 možností, podle násobícího principu je tedy počet způsobů 4 · 3 · 2 · 1 = 4! = 24. Existuje přesně n! permutací n různých objektů. b) Kolika způsoby si mohou vybrat každý jednu flash paměť (od každého druhu je dostatečný počet)? Zajímá nás, kdo si vybral jaký druh. Řešení: 4 fáze, každý vybírá ze všech druhů nezávisle na ostatních, podle násobícího principu je počet možností 6 · 6 · 6 · 6 = 64 = 1296. Při výběru k prvků z n s opakováním, když záleží na pořadí, je počet možností nk . doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


7 / 16

Základní principy

Hezký příklad pokračuje Příklad 4 c) Kolika různými způsoby si mohou vybrat paměti tak, aby měl každý student jiný druh? Řešení: 4 fáze, postupně se vybírá ze 6, 5, 4 a 3 možností, podle násobícího principu je počet způsobů 6·5·4·3=

6! 6! 6·5·4·3·2·1 = = = 360 2·1 2! (6 − 4)!

. Při výběru k prvků z n bez opakování, když záleží na pořadí, je počet možností n! . (n − k)!


Kombinatorika - 1


8 / 16

Základní principy

Příklad pokračuje Příklad 5 d) Kolika různými způsoby si mohou vybrat paměti tak, aby se některý druh opakoval? Řešení: Opačný požadavek než v předchozím zadání, takže použijeme doplňkový princip a zkombinujeme výsledky b) a c): 64 − 6! 2! = 1296 − 360 = 936 e) Kolika různými způsoby si mohou vybrat paměti bez opakování, když nás nezajímá, kdo má jaký druh? Řešení: Vyjdeme z výsledku c) a všechny permutace stejného výběru 6! pamětí bereme jako jednu možnost: 2!·4! = 360 24 = 15 Při výběru k prvků z n bez opakování, když nezáleží na pořadí, je počet možností n! . k! · (n − k)! doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


9 / 16

Základní principy

Příklad už skoro končí Příklad 6 f) Kolik různých možností existuje pro celkový nákup, pokud není zakázané opakování a na pořadí nezáleží? Řešení: Typy pamětí očíslujeme jako 1 až 6 a každý výběr si představíme jako neklesající čtyřprvkovou posloupnost a1 ≤ a2 ≤ a3 ≤ a4 , např. {1, 2, 2, 3}. Kolik takových posloupností existuje? Zkusme každou takovou posloupnost zakódovat pomocí binárního řetězu tak, že 0 bude vyjadřovat konec výskytu stejné číslice a 1 bude vyjadřovat místo v původní posloupnosti obsazené nějakou číslicí. Takový binární řetěz bude obsahovat čtyři 1 a pět 0 (výskyty číslice 6 není třeba ukončovat). Např. kod(1, 2, 2, 3) = 101101000, kod(3, 4, 4, 4) = 001011100, doc. Josef Kolář (FIT ČVUT)

kod(1, 3, 5, 6) = 100100101, kod(2, 2, 6, 6) = 011000011. Kombinatorika - 1


10 / 16

Základní principy

Příklad opravdu končí

Příklad 7 kod() je bijekce množiny uvažovaných výběrů na binární řetězy délky 9 obsahující čtyři jedničky. Počet takových řetězů je dán počtem způsobů, jak vybrat čtyři 9! = 126 z použitelných devíti míst, tedy 4!(9−4)! Při výběru k prvků z n s opakováním, když nezáleží na pořadí, je počet možností (n − 1 + k)! . k!(n − 1)!


Kombinatorika - 1


11 / 16

Kombinační čísla

Kombinační čísla Definice 8 Pro přirozená čísla k ≤ n definujeme kombinační číslo neboli binomický koeficient jako n n! . (1) C(n, k) = = k!(n − k)! k Základní vlastnosti n n = 1, 0 1 = n, n n k = n−k ,

n n−1

n k

n n

= n,

=

Výpočet kombinačích čísel n(n−1)···(n−k+1) n n! = k = k!(n−k)! = k!

n−1 k−1

+

= 1, n−1 k

n(n−1)···(k+1) (n−k)!

Volíme výpočetní variantu s menším počtem činitelů. doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


12 / 16


Kombinační čísla v počtech výběrů Věta 9 Uvažujme množinu o n různých prvcích. 1

Počet způsobů, jak je seřadit (neboli počet permutací) je n! .

2

Počet způsobů, jak vybrat k prvků bez opakování, přičemž záleží na n n! pořadí, je (n−k)! = k · k! .

3

4

5

Počet způsobů, jak vybrat k prvků s opakováním, přičemž záleží na pořadí, je nk .

Počet způsobů, jak vybrat k prvků bez opakování, přičemž nezáleží na pořadí, je nk . Počet způsobů, jak vybrat k prvků s opakováním, přičemž nezáleží na n+k−1 pořadí, je . k


Kombinatorika - 1


13 / 16


Kombinace, variace, permutace Pokud ve výběru nezáleží na pořadí, říkáme jim kombinace. Pokud ve výběru záleží na pořadí, říkáme jim variace. Variace n prvků z množiny mohutnosti n je její permutací. Shrnutí vzorečků s pořadím (variace) bez pořadí (kombinace)


bez opakování

s opakováním

n! (n−k)! n k

nk

Kombinatorika - 1

n+k−1 k


14 / 16


Hrátky s jedním bytem Příklad 10 Hodnota uložená v jedné slabice (bytu) paměti: binární řetěz délky 8. a) Kolik je takových binárních řetězů? Řešení: Pro každé místo se vybírá nezávisle 0 nebo 1, tedy 28 = 256. b) Kolik řetězů obsahuje přesně 4 jedničky? 8! = Řešení: 4 jedničky můžeme umístit 84 = 4!4!

8·7·6·5 1·2·3·4

= 70 způsoby.

c) Kolik řetězů obsahuje méně než 4 jedničky? Řešení: obsahující 0 až 3 jedničky, těch je celkem Budou to řetězy 8 8 8 8 + + + = 93. 0 1 2 3

d) Kolik řetězů obsahuje alespoň 2 jedničky těsně za sebou? Řešení: Existuje 7 možností, kam do řetězu umístit 2 jedničky za sebou, 6 další místa obsadíme libovolně, tedy 7 · 2 = 448 ?!? 8 8 7 6 5 Správně: 0 + 1 + 2 + 3 + 4 = 55 řetězů neobsahuje 2 jedničky za sebou (proč?). Ostatních řetězů je tedy 256 − 55 = 201. doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


15 / 16


Hrátky s množinami Příklad 11 Mějme množinu X s n prvky. Kolik existuje uspořádaných dvojic množin (A, B) splňujících podmínku A ⊆ B ⊆ X? (OBRÁZEK 2) Řešení: Je-li A ⊆ B ⊆ X, pak každý prvek z X leží právě v jedné z množin A, B − A, X − B. Stejně i naopak: pokud každý prvek z X přiřadíme do jedné z množin A (tím pádem i do B a X), B − A (tedy rovněž do X) a X − B, pak dostaneme jedinečnou uspořádanou dvojici (A, B) splňující A ⊆ B ⊆ X. Máme tedy n nezávislých fází a v každé 3 možnosti, což dává dohromady celkem 3n dvojic.


Kombinatorika - 1


16 / 16


Náročnější hrátky s množinami Příklad 12 Mějme uspořádanou trojici množin X1 , X2 , X3 , které splňují podmínky X1 ∪ X2 ∪ X3 = {1, 2, 3, 4, 5, 6, 7, 8} a X1 ∩ X2 ∩ X3 = ∅ Kolik takových trojic množin je možné určit? (Na pořadí množin záleží.) Řešení: Jak by vypadalo řešení, pokud by sjednocení tří množin mělo dát pouze množinu {1}? X1 = {1} X1 = ∅ X1 = {1}

X2 = ∅ X2 = ∅ X2 = ∅

X3 = ∅ X3 = {1} X3 = {1}

X1 = ∅ X1 = {1} X1 = ∅

X2 = {1} X2 = {1} X2 = {1}

X3 = ∅ X3 = ∅ X3 = {1}

Prvek 1 jsme tedy zkoušeli dávat do jedné nebo do dvou z množin X1 , X2 , X3 , ale ne do všech tří současně. doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


17 / 16


Náročnější hrátky pokračují Příklad 13 Když místo jednoprvkové množiny uvažujeme X = {1, 2, 3, 4, 5, 6, 7, 8}, pak musíme každý z těchto prvků rovněž umístit do jedné nebo do dvou z množin X1 , X2 , X3 , ale ne do všech tří současně. Pro každý z osmi prvků máme tedy 6 alternativ umístění, celkem 68 = 1 679 616 možností vytvoření uspořádaných trojic množin X1 , X2 , X3 . Pomocí postupu použitého v předchozím příkladu bychom mohli také vymezit následujících 6 množin (OBRÁZEK 3): X1 ∩ X2 ∩ X3 , X1 ∩ X2 ∩ X3 ,

X1 ∩ X2 ∩ X3 , X1 ∩ X2 ∩ X3 ,

X1 ∩ X2 ∩ X3 , X1 ∩ X2 ∩ X3

Každý prvek množiny X můžeme nyní přiřadit do libovolné z těchto šesti množin, což podle násobícího principu dává 68 uspořádaných trojic množin X1 , X2 , X3 . doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


18 / 16


Cestujeme po síti Příklad 14 Mějme čtvercovou síť tvořenou n × n políčky. (OBRÁZEK 4a) Kolik existuje různých tras vedoucích z levého dolního rohu sítě do pravého horního rohu, pokud se smíme pohybovat pouze nahoru a vpravo? Řešení: Je třeba udělat celkem n kroků vpravo a n kroků nahoru. Označíme-li krok nahoru symbolem N a krok vpravo symbolem V , pak můzeme každou přípustnou trasu vyjádřit jako řetěz obsahující n výskytů N a stejně tolik výskytů V , např. pro n = 4 to může být řetěz V NNV V NV N. Kolik je takových řetězů? Přesně tolik, kolika způsoby můžeme vybrat n-tici míst z 2n, do nichž zapíšeme symbol V , do zbývajících n pak přijde N . Výsledek je tedy 2n n . doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


19 / 16


Cestujeme s omezením Příklad 15 Síť je jako minule, ale určujeme počet tras z levého dolního rohu sítě do pravého horního rohu, které nesmí překročit diagonálu. Řešení: Rozdělíme-li trasy na dobré (těch je Dn ) a špatné (Sn ), pak platí 2n . Dn + Sn = n V okamžiku, kdy špatná trasa v bodu (i, i + 1) překročí diagonálu, překlopíme zbývající část trasy podle diagonály procházející bodem (i, i + 1). (OBRÁZEK 4b)


Kombinatorika - 1


20 / 16


Cestujeme s omezením - dokončení Příklad 16 Špatné trasy v n × n síti odpovídají všem trasám v (n − 1) × (n + 1) síti 2n 2n (proč?), takže jich je přesně n−1 = n+1 (proč?). Dostáváme tak 2n (2n)! 2n 2n (2n)! = − − Sn = Dn = − . n−1 n n n!n! (n − 1)!(n + 1)!

Po další trošce algebry tak máme výsledek 1 2n Dn = . n+1 n Poznámka: Získané hodnoty představují tzv. Catalanova čísla Cn . {Cn } = {1, 1, 2, 5, 14, 42, 132, 429, . . . } pro n = 0, 1, 2, . . . doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


21 / 16

Algoritmy pro generování kombinací a variací

Generování kombinací (1) Jak budeme postupovat, máme-li vytvořit všechny kombinace k prvků z množiny o n prvcích? Pro jednoduchost předpokládáme, že se výběry (kombinace nebo variace) provádějí z množiny {1, 2, 3, . . . , n}. Při výběru k-prvkových kombinací nezáleží na pořadí, takže každou kombinaci si můžeme představit seřazenou od nejměnší hodnoty (vlevo) do největší (vpravo). Takto vytvářené kombinace budeme generovat v lexikografickém pořadí, např. pro n = 6, k = 4 to bude: 1234, 1356,

1235, 1456,

1236, 2345,

1245, 2346,

1246, 2356,

1256, 2456,

1345, 3456

1346,

Jak se v tomto pořadí určí k zadané kombinaci odpovídající následující kombinace? doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


22 / 16


Generování kombinací (2) První a poslední k-prvková kombinace z n prvků v lexikografickém pořadí: 123 · · · (k − 1)k,

...

, (n − k + 1)(n − k + 2) · · · (n − 1)n

Máme-li kombinaci vyjádřenou jako posloupnost s1 s2 . . . sk , pak pro nalezení následující kombinace v pořadí t1 t2 . . . tk musíme určit první prvek zprava sm , který dosud nemá maximální možnou hodnotu (prvek sk může mít nejvýše hodnotu n, sk−1 může mít nejvýše hodnotu n − 1, atd.). Položíme tedy ti = si pro i = 1, 2, . . . , m − 1, tm = sm + 1, tj = tj−1 + 1 pro j = m + 1, . . . , k. To vede na následující algoritmus. doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


23 / 16


Generování kombinací (3) Algoritmus 17 Vstup: k, n ∈ N, 1 ≤ k ≤ n. procedure Kombinace(k, n) { (1) for i ← 1 to k do s[i] ← i; (2) print s[1], . . . , s[k]; (3) for i ← 2 to C(n, k) do (4) m ← k; maxV al ← n; (5) while s[m] = maxV al do (6) m ← m − 1; maxV al ← maxV al − 1; (7) s[m] ← s[m] + 1; (8) for j ← m + 1 to k do s[j] ← s[j − 1] + 1; (9) print s[1], . . . , s[k]; (10) }


Kombinatorika - 1


24 / 16


Generování kombinací (4) Vytvoření všech kombinací v lexikografickém uspořádání lze také vyjádřit schematicky takto:

Algoritmus 18 procedure Kombinace(k, n) { for s[1] ← 1 to n − k + 1 do for s[2] ← s[1] + 1 to n − k + 2 do ... for s[i] ← s[i − 1] + 1 to n − k + i do ... for s[k] ← s[k − 1] + 1 to n do print . . . } Jak tento proměnný počet cyklů vyjádřit programem - nejlépe rekurzí! doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


25 / 16


Generování kombinací (5) Algoritmus 19 procedure Kombinace(k, n) { (1) s[k + 1] ← n + 1; Komb(k); (2) } procedure Komb(i) (3) if (odd(i)) { (4) for j ← s[i + 1] − 1 downto i do (5) s[i] ← j; (6) if (i = 1) U seKomb; (* tiskne kombinaci *) (7) else Komb(i − 1); (8) } (9) else for j ← i to s[i + 1] − 1 do (10) s[i] ← j; Komb(i − 1); (11) } doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


26 / 16


Generování kombinací (6)

Otázka pro hloubavé Zatím umíme generovat kombinace n čísel {1, 2, . . . , n} Jak generovat kombinace vybírané ze zadané množiny libovolných n prvků?


Kombinatorika - 1


27 / 16


Generování permutací (1) Při vytváření permutací n prvků záleží (pouze!) na pořadí prvků, budeme se snažit generovat je opět v lexikografickém uspořádání. Např. pro n = 4 tak dostaneme 24 permutací seřazené takto: 1234, 2314, 3412,

1243, 2341, 3421,

1324, 2413, 4123,

1342, 2431, 4132,

1423, 3124, 4213,

1432, 3142, 4231,

2134, 3214, 4312,

2143, 3241, 4321,

První a poslední permutace n prvků v lexikografickém pořadí, případně permutace vybraných prvků a1 < a2 < · · · < ak : 123 · · · (n − 1)n, a1 a2 · · · ak ,

..., ...,

n(n − 1) · · · 321 ak ak−1 · · · a1

Jak se v této posloupnosti určí k zadané permutaci odpovídající následující permutace? Jaká část zleva zůstane zachována a jak se změní zbytek vpravo? doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


28 / 16


Generování permutací (2) Pro n = 6 uvažujme např. permutaci 241653. Jaká její část zleva zůstane zachována v lexikograficky následující permutaci? 24165 - zbývá 3, 2416 - zbývá 53, 241 - zbývá 653, 24 - zbývá 1653,

zřejmě nelze zachovat (proč?) to je lexikograficky největší permutace je rovněž lexikograficky největší permutace následující permutace je 3156, tedy 24 lze zachovat

Zjištění: prvky zprava rostou, zastavíme se na prvním poklesu hodnoty, zaměníme ho s nejmenším (prvním nalezeným) prvkem zprava, který je větší, zbylou část vpravo překlopíme, bude tedy růst zleva doprava, je to lexikálně nejmenší permutace zbylých prvků Dostali jsme následující algoritmus. doc. Josef Kolář (FIT ČVUT)

Kombinatorika - 1


29 / 16


Generování permutací (3) Algoritmus 20 procedure Permutace(n) { (1) for i ← 1 to n do s[i] ← i; (2) print s[1], . . . , s[n]; (3) for i ← 2 to n! do (4) m ← n − 1; (5) while s[m] > s[m + 1] do m ← m − 1; (6) k ← n; (7) while s[m] > s[k] do k ← k − 1; (8) swap(s[m], s[k]); p ← m + 1; q ← n; (9) while p < q do {swap(s[p], s[q]); p ← p + 1; q ← q − 1; } (10) print s[1], . . . , s[n]; (11) }


Kombinatorika - 1


30 / 16


Generování permutací (4) Máme ale stejný problém jako u kombinací: umíme permutovat pouze čísla {1, 2, . . . , n}. Jak získat všechny permutace libovolné zadané množiny A obsahující n prvků? Nabízí se následující úvaha: Jednoprvková množina A = {a} má pouze jedinou permutaci a. Pro množinu A, která má n(> 1) prvků ◮

◮

vytvoříme všechny permutace množiny B = A − {a}, kde a ∈ A je libovolný prvek, pro každou permutaci n − 1 prvků vytvoříme n permutací vložením prvku a na každé z n možných míst.


Kombinatorika - 1


31 / 16

Kombinatorika- 1. Základy diskrétní matematiky, BI-ZDM

Recommend Documents