Kapitola 2 Kombinatorika 2.1 Počet možných výběrů z předem daného sou- boru Budeme se zajímat o počet možných rozlišitelných výběrů zadaného rozsahu z nějakého předem daného konečného souboru předmětů, nikoliv nutně množiny. V souboru, který není množinou, mohou být některé z předmětů navzájem nerozlišitelné. To si lze představit i tak, že některý předmět můžeme vybrat opakovaně, po výběru ho vracíme do souboru. Řešení takto formulovaného problému najdeme jen pro šest speciálních situací. Při řešení není podstatná výsledná formule (vzoreček), podstatný je způsob, jak se k ní dospěje. Analogické úvahy lze totiž provádět i v jiných, nějakým způsobem podobných, situacích. 2.1.1 Variace k-té třídy z n prvků Základní soubor je tvořen n vzájemně rozlišitelnými prvky. Z nich vybereme k prvků (smysl má samozřejmě pouze případ k ≤ n) a uspořádáme je do řady. Např. je-li základní soubor tvořen prvky a, b, c, d, e, z něho vybíráme tři prvky a uspořádáváme je, pak se výběr ‘acd’ liší od výběru ‘adc’. Modelovou úlohou je problém, kolik různých tříbarevných vlajek tvořených svislými pruhy lze vytvořit z pruhů látky v barvách červené, žluté, zelené, modré a bílé. Při řešení uvažujeme následujícím způsobem: První pruh (u žerdi) můžeme vybrat z pěti barev. Zůstanou čtyři pruhy a z nich vybereme pruh druhé barvy. Potom zůstanou tři pruhy a z nich vybereme poslední. Označíme-li barvy Č, Ž, Z, M, B, lze možnosti schématicky znázornit obrázkem 2.1. V prvním sloupci je výběr prvního prvku. Tento výběr bylo možno uskutečnit pěti způsoby. K vybranému prvku vybereme (připojíme úsečkou) druhý; tento výběr je možno k danému prvnímu prvku uskutečnit čtyřmi způsoby. Nakonec k vybraným dvěma prvkům vybereme třetí; tento výběr k dané dvojici můžeme provést třemi způsoby. Výsledný počet výběrů (počet tříbarevných vlajek) tedy je 5 · 4 · 3 = 60. 17 18 2 Kombinatorika         €€€€d d dd         €€€€d d dd         €€€€d d dd $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ         €€€€d d dd         €€€€d d dd $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ $$$$ ˆˆˆˆ Č Ž Z M B Z Ž M B M Ž Z B B Ž Z M Ž Č Z M B Z Č M B M Č Z B B Č Z M Z Č Ž M B Ž Č M B M Č Ž B B Č Ž M M Č Ž Z B Ž Č Z B Z Č Ž B B Č Ž Z B Č Ž Z M Ž Č Z M Z Č Ž M M Č Ž Z Obr. 2.1: K úloze o tříbarevných vlajkách na str. 17 Stejně postupujeme, je-li rozsah souboru n a rozsah výběru k. Když označíme počet variací k-té třídy z n prvků symbolem v(n, k), dostaneme v(n, k) = n(n − 1)(n − 2) · · · (n − k + 2)(n − k + 1). (2.1) 2.1.2 Permutace n prvků Základní soubor je tvořen n rozlišitelnými prvky. Vybereme je všechny a uspořádáme do řady. Stručněji: uspořádáme n rozlišitelných prvků a ptáme se, kolik takových uspořádání existuje. Modelová úloha může být následující: Máme šest lístečků a na každém z nich jednu z číslic 1, 2, 3, 4, 5, 6. Kolik šesticiferných čísel můžeme vytvořit různým poskládáním těchto lístečků za sebe? Jinak řečeno, kolik existuje šesticiferných čísel, v jejichž zápisu se vyskytuje každá z číslic 1, 2, 3, 4, 5, 6 právě jednou? Je zřejmé, že permutací n prvků je tolik, kolik je variací n-té třídy z n prvků. Tedy označíme-li počet permutací n prvků symbolem p(n), dostaneme p(n) = n(n − 1)(n − 2) · · · 3 · 2 · 1. 2.1 Počet výběrů z daného souboru 19 Součin n(n − 1)(n − 2) · · · 3 · 2 · 1, tj. součin všech přirozených čísel od 1 do n označíme symbolem n!, který čteme „n faktoriál , n! = n(n − 1)(n − 2) · · · 3 · 2 · 1. Faktoriál je uvedeným součinem definován pro libovolné kladné celé číslo. V dalším uvidíme, že je vhodné ho zavést i pro nulu. Klademe 0! = 1; (2.2) tuto volbu lze zdůvodnit tak, že existuje jediný způsob, jak uspořádat prvky prázdného souboru — vzít prázdný soubor. Vzoreček pro počet permutací n prvků lze pomocí faktoriálu stručně psát ve tvaru p(n) = n!. (2.3) Odpověď na otázku z modelové úlohy tedy je: 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720. Vzoreček (2.3) lze považovat za výchozí kombinatorickou formuli a odvodit ho podobnou úvahou, jaká je uvedena v 2.1.1. Počet variací k-té třídy z n prvků lze pak odvodit následující úvahou: Vytvoříme všechny permutace n prvků; bude jich n!. Permutace, které se shodují na prvních k místech a na zbývajících n − k se liší, budeme považovat za totožné (variace k-té třídy totiž můžeme tvořit tak, že z permutace n prvků „odřízneme posledních n−k prvků). Počet variací k-té třídy z n prvků je tedy tolikrát menší než počet permutací n prvků, kolik je možných uspořádání (tj. permutací) n − k prvků, tedy (n − k)!-krát menší. Dostáváme tak vzoreček pro výpočet počtu variací ve tvaru v(n, k) = n! (n − k)! . (2.4) Snadným výpočtem (krácením zlomků) se lze přesvědčit, že ho lze upravit na tvar (2.1): v(n, k) = n! (n − k)! = = n(n − 1) · · · (n − k + 1)(n − k)(n − k − 1) · · · 3 · 2 · 1 (n − k)(n − k − 1) · · · 3 · 2 · 1 = = n(n − 1) · · · (n − k + 1). Dále platí, že počet permutací n prvků je vlastně počtem variací n-té třídy z n prvků, tj. n! = p(n) = v(n, n) = n! (n − n)! = n! 0! . Z této rovnice můžeme vypočítat 0! = n! n! = 1. Tento výpočet ukazuje, že není jiná možnost, jak definovat 0!, než vztahem (2.2). 20 2 Kombinatorika 2.1.3 Kombinace k-té třídy z n prvků Základní soubor je opět tvořen n vzájemně rozlišitelnými prvky. Z nich vybereme k prvků (smysl má samozřejmě zase pouze případ k ≤ n) a neuspořádáváme je. Jinými slovy, zajímáme se o počet k-prvkových podmnožin nějaké n-prvkové množiny. Počet kombinací k-té třídy z n prvků budeme označovat symbolem c(n, k). Jako modelovou úlohu můžeme vzít: Na konferenci jisté politické strany se sešlo 58 politiků. Mají ze svých řad zvolit a jmenovat tříčlennou delegaci na kongres. Kolika způsoby to mohou udělat? Představme si, že máme jednu konkrétní kombinaci k-té třídy z n prvků; například kombinaci ‘abd’ z pěti prvků a, b, c, d, e. Z této jedné kombinace lze vytvořit různým seřazením prvků celkem p(k) = k! variací k-té třídy z n prvků; v našem příkladu jich je 3! = 6: ‘abd’, ‘adb’, ‘bad’, ‘bda’, ‘dab’, ‘dba’. Z této úvahy vidíme, že počet variací k-té třídy z n prvků je k!-krát větší, než počet kombinací, tj. v(n, k) = c(n, k) · k!. Z této rovnosti s využitím (2.1) dostaneme c(n, k) = v(n, k) k! = n(n − 1) · · · (n − k + 2)(n − k + 1) k(k − 1) · · · 3 · 2 · 1 , nebo s využitím (2.4) c(n, k) = v(n, k) k! = n! (n − k)! k! = n! (n − k)! k! . Výraz n! (n − k)! k! označíme symbolem n k , kterému říkáme kombinační číslo a čteme ho „n nad k . Formuli pro výpočet počtu kombinací tedy můžeme zapsat ve tvaru c(n, k) = n k = n! (n − k)! k! . (2.5) Nyní můžeme odpovědět na otázku z modelové úlohy. Možných delegací je c(58, 3) = 58 3 = 58! 3! 55! = 58 · 57 · 56 3 · 2 = 30 856. Kombinační čísla splňují jednoduché identity n k = n n − k , n k + n k + 1 = n + 1 k + 1 . 2.1 Počet výběrů z daného souboru 21 První z nich je zřejmá z definice kombinačního čísla, druhou ověříme následujícím výpočtem: n k + n k + 1 = n! k! (n − k)! + n! (k + 1)! (n − k − 1)! = = n! (k + 1) (k + 1)! (n − k)! + n! (n − k) (k + 1)! (n − k)! = n! (k + 1 + n − k) (k + 1)! (n − k)! = = n! (n + 1) (k + 1)! (n − k)! = (n + 1)! (k + 1)! (n − k)! = n + 1 k + 1 . 2.1.4 Variace k-té třídy z n prvků s opakováním (vracením) Základní soubor je tvořen prvky, které jsou rozděleny do n různých druhů, prvky téhož druhu jsou navzájem nerozlišitelné. Prvků každého druhu je alespoň k. Postupně vybíráme po jednom prvku a řadíme je za sebe. Celkem vybereme k prvků. Výchozí situaci si lze představit i jiným způsobem. Základní soubor je tvořen n rozlišitelnými prvky. Vybereme z něho jeden, zapíšeme si ho a vrátíme do souboru. Pak vybereme další prvek, zapíšeme ho za první a vrátíme ho. To zopakujeme celkem k-krát (započítán je i výběr prvního prvku). Výsledkem bude záznam seřazených prvků o délce k; každý z nich se může libovolně krát opakovat. Počet variací k-té třídy s opakováním lze odvodit podobnou úvahou, jako v případě variací bez opakování. První prvek výběru lze vybrat n způsoby (poněvadž v souboru je n druhů prvků nebo v případě vracení n rozlišitelných prvků). Ke každému vybranému prvku můžeme přidat další opět n způsoby (počet druhů v základním souboru zůstává n nebo po vrácení je v souboru zase n prvků). Výběr zopakujeme k-krát. Označíme-li tedy počet variací k-té třídy z n prvků s opakováním symbolem V (n, k), dostaneme V (n, k) = n · n · n · · · · · n k-krát = nk . 2.1.5 Permutace s opakováním v situaci (k1, k2, . . . , kn) Základní soubor je tvořen k prvky, které jsou rozděleny do n různých druhů, prvky stejného druhu jsou vzájemně nerozlišitelné. Prvků prvního druhu je k1, druhého k2 atd. Samozřejmě má smysl pouze případ, kdy n ≤ k, k1 ≥ 1, k2 ≥ 1,. . . ,kn ≥ 1, k1 +k2 +· · ·+kn = k. Vybereme všechny prvky a seřadíme je. Jiná formulace je, že máme n prvků, ze souboru vybíráme po jednom prvku, zapisujeme a vracíme ho do základního souboru celkem k-krát. Výsledkem je k prvků seřazených za sebou. Ptáme se, kolik může být takových uspořádaných k-tic, pokud víme, že první prvek se vyskytuje k1-krát, druhý k2-krát, . . . , n-tý kn-krát. V této interpretaci můžeme připustit i ki = 0 pro nějaké i z množiny {1, 2, . . ., n}, stále ovšem musí platit, že k1 + k2 + · · · + kn = k. Označme hledaný počet symbolem P(k1, k2, . . . , kn). Představme si, že všechny prvky máme nějak označené, abychom rozlišili i prvky i-tého druhu a permutujeme 22 2 Kombinatorika je (různým způsobem řadíme). Takových permutací bude p(k) = p(k1 + k2 + · · · + kn) = (k1 + k2 + · · · + kn)!. Pokud odstraníme označení u prvního druhu předmětů, nerozlišíme permutace, u nichž jsou prvky prvního druhu na stejných místech. Např. máme-li prvky dvou druhů a, b a vybíráme 5 prvků, pak při označení předmětů obou druhů jsou per- mutace a1 b1 a2 b2 b3 a2 b1 a1 b2 b3 různé, bez označení prvků prvního druhu nerozlišíme permutace a b1 a b2 b3 a b1 a b2 b3. Rozlišitelných permutací bude tolikrát méně, kolik je možných permutací k1 prvků, tedy k1!-krát. Analogickou úvahu provedeme pro prvky všech druhů a dostaneme P(k1, k2, . . . , kn) = p(k1 + k2 + · · · + kn) p(k1)p(k2) · · · p(kn) = (k1 + k2 + · · · + kn)! k1! k2! · · · kn! . Jako modelovou úlohu pro zkoumanou situaci můžeme vzít následující: Máme sedm lístečků, na dvou z nich je napsána číslice 3, na třech číslice 5 a na zbývajících číslice 8. Kolik různých sedmiciferných čísel lze pomocí těchto lístečků vytvořit? V tomto případě je n = 3, k = 7, k1 = 2 (lístečky s číslicí 3), k2 = 3 (lístečky s číslicí 5) a k3 = 7 − (2 + 3) = 2 (lístečky s číslicí 8). Lze utvořit P(2, 3, 2) = 7! 2! 3! 2! = 7 · 6 · 5 · 4 · 3 · 2 2 · 3 · 2 · 2 = 210 čísel. 2.1.6 Kombinace k-té třídy z n prvků s opakováním (vracením), rozdělování předmětů do přihrádek Výchozí situace je stejná jako v případě variací k-té třídy z n prvků s opakováním (viz 2.1.4) s tím rozdílem, že nerozlišujeme výběry, ve kterých jsou stejné prvky různě uspořádané (nepřihlížíme k pořadí prvků). Modelová úloha může být tato: V urně jsou kuličky pěti barev — červené, žluté, zelené, modré a bílé — všechny v dostatečném množství, tj. od každé barvy alespoň jedenáct. Vybereme jedenáct kuliček a dáme je do pytlíku. Ptáme se, kolik barevných kombinací může vzniknout. V tomto případě závisí pouze na počtech vybraných předmětů jednotlivých druhů, což znamená, že výběr je jednoznačně určen uspořádanou n-ticí celých čísel (k1, k2, . . . , kn) takových, že k1 ≥ 0, k2 ≥ 0, . . . , kn ≥ 0, a k1 + k2 + · · · + kn = k; přitom k1 značí počet vybraných předmětů prvního druhu, k2 druhého druhu atd. V modelové úloze mohou být například vybrány tři červené kuličky, dvě žluté, 2.1 Počet výběrů z daného souboru 23 jedna zelená a pět bílých. V takovém případě je k1 = 3, k2 = 2, k3 = 1, k4 = 0, k5 = 5. Uspořádanou pětici (3, 2, 1, 0, 5) můžeme také schematicky znázornit takto: ◦ ◦ ◦ | ◦ ◦ | ◦ | | ◦ ◦ ◦ ◦ ◦ , (2.6) tedy pomocí jedenácti koleček a čtyř čárek. Obecně lze každý výběr znázornit pomocí k koleček a n−1 čárek: před první čárkou je tolik koleček, kolik je vybraných předmětů prvního druhu, mezi první a druhou čárkou je tolik koleček, kolik je vybraných předmětů druhého druhu atd. až za poslední, tj. (n − 1)-ní čárkou je tolik koleček, kolik je vybraných předmětů n-tého druhu. Jinak řečeno, každý výběr odpovídá jedné permutaci s opakováním v situaci (k, n − 1). Počet kombinací k-té třídy z n prvků s opakováním, který označíme symbolem C(n, k), je podle této úvahy roven počtu permutací s opakováním v situaci (k, n − 1), tj. C(n, k) = P(k, n − 1) = (k + n − 1)! k! (n − 1)! = k + n − 1 k = k + n − 1 n − 1 . Řešení modelové úlohy je C(5, 11) = 15 5 = 15 · 14 · 13 · 12 · 11 5 · 4 · 3 · 2 = 3 003. Podívejme se ještě jednou na schéma (2.6). Stejně dobře bychom ho mohli charakterizovat jako znázornění rozdělení jedenácti předmětů do pěti přihrádek, roztřídění jedenácti objektů do pěti druhů. Odtud je vidět, že odpověď na otázku, kolika způsoby lze rozdělit k předmětů do n přihrádek, je opět C(n, k). Můžeme přidat i podmínku, že v každé přihrádce má být alespoň l předmětů. Pokud je n l < k, pak je těchto způsobů 0, předmětů je totiž příliš málo a podmínku splnit nemůžeme. Pokud je n l ≥ k, můžeme si představit, že nejprve přidělíme do každé přihrádky l předmětů (což lze udělat jediným způsobem) a na další přidělování nám zbude o n l předmětů méně. Způsobů je tedy C(n, k − n l). 2.1.7 Další příklady Příklad 1. V noclehárně je 50 lůžek. Určete, kolika způsoby je možno na ně umístit 35 nocležníků. Z hlediska provozovatele ubytovny nezáleží na tom, kdo na kterém lůžku leží. Podstatné je pouze to, která lůžka jsou obsazena. Z jeho pohledu tedy je možno lůžka obsadit c(50, 35) = 50 35 = 50 15 = = 50 · 49 · 48 · 47 · 46 · 45 · 44 · 43 · 42 · 41 · 40 · 39 · 38 · 37 · 36 15 · 14 · 13 · 12 · 11 · 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 = = 2, 250 829 575 · 1012 24 2 Kombinatorika způsoby. Z hlediska ubytovaných záleží na tom, kdo na kterém lůžku leží, jaké má sousedy ap. Z jejich pohledu tedy je v(50, 35) = 50! 15! = 2, 325 815 505 · 1052 způsobů obsazení lůžek. Příklad 2. Kolik různých slov, i bez významu, je možno vytvořit přeskládáním písmen ve slově LOKOMOTIVA? Kolik je mezi nimi takových slov, v nichž nejsou žádná dvě stejná písmena vedle sebe? A v kolika slovech se pravidelně střídají souhlásky a samohlásky? V uvedeném slově se vyskytují jednou písmena A, I, K, L, M, T, V — je jich 7 — a třikrát písmeno O. Ve slově samozřejmě na pořadí písmen záleží. Máme 8 druhů písmen, jednoho druhu jsou tři exempláře, ostatních po jednom. Počet všech slov tedy bude P(1, 1, 1, 1, 1, 1, 1, 3) = 10! 1! 1! 1! 1! 1! 1! 1! 3! = 594 800. Při hledání odpovědi na druhou otázku nejprve seřadíme písmena A, I, K, L, M, T, V. To můžeme udělat p(7) způsoby. Každé ze tří písmen O můžeme zařadit na začátek slova, na jeho konec nebo do mezery mezi zbývajícími písmeny, tedy na 8 různých pozic. Každou z těchto pozic můžeme vybrat pouze pro jedno O. Vybíráme tedy tři pozice z osmi možných, na které umístíme nerozlišitelná písmena O. Tento výběr lze udělat c(8, 3) způsoby. Celkem tedy můžeme vytvořit p(7) c(8, 3) = 7! 8 3 = 7! 8! 5! 3! = 7 · 6 · 5 · 4 · 8 · 7 · 6 = 282 240 slov požadované vlastnosti. Souhlásky jsou K, L, M, T, V a samohlásky A, I, O. Všechny souhlásky se vyskytují po jedné, lze je tedy uspořádat p(5) způsoby. Samohlásky A, I se vyskytují jednou, samohláska O třikrát. Lze je tedy seřadit P(1, 1, 3) způsoby. Dále jsou dvě možnosti volby, zda první písmeno bude souhláska nebo samohláska. Celkem tedy můžeme vytvořit 2p(5)P(1, 1, 3) = 2 · 5! · 5! 3! = (5!) 2 3 = 3 600 slov, v nichž se střídají samohlásky a souhlásky. Příklad 3. Kolika způsoby lze rozdělit 50 stejných kuliček mezi čtyři chlapce? Kolika způsoby lze toto rozdělení udělat tak, aby každý dostal alespoň jednu ku- ličku? Můžeme si představit, že každý z chlapců je charakterizován nějakou „svou přihrádkou , např. pytlíkem na kuličky nebo kapsou. Pak se jedná o rozdělení 50 2.1 Počet výběrů z daného souboru 25 předmětů do čtyř přihrádek. Podle posledního odstavce 2.1.6 je odpověď na první otázku C(4, 50) = 53 3 = 53 · 52 · 51 3 · 2 = 23 426 a na druhou C(4, 46) = 49 3 = 49 · 48 · 47 3 · 2 = 18 424. Příklad 4. Kolika způsoby lze mezi tři děti rozdělit 7 stejných hrušek a 5 stejných jablek? Prakticky neomezeně mnoha. Ovoce lze totiž krájet. Pokud z nějakého důvodu krájet nemůžeme (bojíme se úrazu, nemáme nůž), rozdělíme nejdříve hrušky, což lze C(3, 7) způsoby, a potom jablka, což lze udělat C(3, 5) způsoby. Jakékoliv přidělení hrušek lze libovolně zkombinovat s libovolným přidělením jablek. Celkem tedy lze děti podělit C(3, 7) C(3, 5) = 9 2 7 2 = 9! 2! 7! 7! 2! 5! = 576 způsoby. Příklad 5. (důležitý) Určete, kolik existuje podmnožin n-prvkové množiny. 1. způsob řešení: Podle 2.1.3 víme, že počet k-prvkových podmnožin n-prvkové množiny je c(n, k). Všech podmnožin včetně prázdné tedy je c(n, 0) + c(n, 1) + c(n, 2) + · · · + c(n, n − 1) + c(n, n) = n k=0 c(n, k) = n k=0 n k . 2. způsob řešení: Představme si, že všechny prvky množiny jsou seřazeny za sebou. Konkrétní podmnožinu můžeme určit tak, že pod každý prvek napíšeme symbol 0 nebo 1 podle toho, zda tento prvek patří nebo nepatří do podmnožiny. Např. pro pětiprvkovou množinu {a, b, c, d, e} a její tříprvkovou podmnožinu {a, c, d} máme a b c d e 1 0 1 1 0. Počet podmnožin tedy bude stejný jako počet uspořádaných n-tic prvků 0 a 1, tedy počet variací k-té třídy ze dvou prvků s opakováním, V (2, n) = 2n . Dostali jsme výsledek ve dvou různých tvarech. Musí tedy platit 2n = n k=0 n k . 26 2 Kombinatorika Tato rovnost je speciálním případem binomické věty (a + b)n = n k=0 n k an−k bk pro a = b = 1. Příklad 6. Kolika způsoby lze na šachovnici vybrat a) dvě pole; b) dvě pole různé barvy; c) dvě pole neležící v témže sloupci a téže řadě; d) dvě pole různé barvy neležící v témže sloupci a téže řadě; e) osm polí tak, aby v každém řádku a každém sloupci bylo právě jedno; f) k polí (1 ≤ k ≤ 8) tak, aby v každém řádku a každém sloupci bylo právě jedno? a) Na šachovnici je celkem 64 polí, vybíráme dvě a na uspořádání (pořadí) vybraných polí nezáleží. Možností tedy je c(64, 2) = 64 2 = 64 · 63 2 = 2 016. b) Na šachovnici je celkem 32 polí bílých a 32 polí černých. Představme si, že nejdříve vybereme pole bílé (to můžeme udělat 32 způsoby) a k němu vybereme pole černé (což můžeme udělat opět 32 způsoby). Celkem tedy máme 32·32 = 1 024 možností výběru. c) Tuto úlohu můžeme také zformulovat jako otázku, kolika způsoby lze na šachovnici umístit dvě věže tak, aby se vzájemně neohrožovaly. Nejprve vybereme jedno pole, což můžeme udělat 64 způsoby. Jako druhé již nemůžeme vybrat totéž pole ani žádné pole ze stejné řady (kterých je 7) ani žádné pole ze stejného sloupce (kterých je opět sedm); můžeme tedy vybírat ze 64−1−7−7 = 49 polí. Při tomto způsobu vybírání bude ale každá dvojice polí ve výběru dvakrát; jednou, když jedno pole vybereme jako první a zbývající jako druhé, podruhé naopak. Dvojic polí zadaných vlastností bude proto dvakrát méně. Celkem tedy můžeme vybrat dvě pole požadovaných vlastností 64 · 49 2 = 1 568 způsoby. Úlohu lze řešit i jiným způsobem. Určíme, kolika způsoby lze vybrat dvě pole nemající požadovanou vlastnost, tj. taková, která leží buď ve stejném sloupci nebo stejné řadě. Vybereme jedno pole; to můžeme udělat 64 způsoby. Potom vybereme druhé; pro jeho výběr máme 7 + 7 možností — vybíráme ze sedmi polí v témže sloupci a ze sedmi polí v téže řadě. Celkem tedy můžeme vybrat dvě pole uvažované vlastnosti, jedno po druhém, 64·(7+7) způsoby. Poněvadž ale ve výsledném výběru nezáleží na tom, v jakém pořadí jsme pole vybírali, je vyhovujících výběrů dvakrát méně, tj. 1 2 · 64 · (7 + 7) = 448. Počet výběrů dvou polí požadované vlastnosti je 2.1 Počet výběrů z daného souboru 27 roven počtu všech výběrů dvou polí (úloha a)) zmenšený o počet výběrů, které požadovanou vlastnost nemají, tedy 2 016 − 448 = 1 568. Úvaha vedoucí k výsledku může být ještě jiná. Znovu začneme určením počtu výběrů, které nemají požadovanou vlastnost. Dvě pole v témže sloupci můžeme vybrat c(8, 2) způsoby, jeden sloupec můžeme vybrat 8 způsoby, takže dvě pole ležící v témže sloupci můžeme vybrat 8·c(8, 2) způsoby. Stejnou úvahou lze ukázat, že dvě pole ležící v téže řadě, lze vybrat také 8 · c(8, 2) způsoby. Dvě pole ležící v téže řadě nebo v témže sloupci lze tedy vybrat 8 · c(8, 2) + 8 · c(8, 2) způsoby. Počet výběrů požadované vlastnosti je opět c(64, 2) − 8 · c(8, 2) + 8 · c(8, 2) = 64 · 63 2 − 8 · 8 · 7 2 + 8 · 8 · 7 2 = 1 568. d) Nejprve vybereme jedno bílé pole. Z 32 černých polí již nemůžeme vybírat ze čtyř polí ve stejné řadě a ze čtyř polí ve stejném sloupci, takže můžeme vybírat z 24 možností. Dvě pole požadovaných vlastností tedy můžeme vybrat 32·24 = 768 způsoby. e) Začneme výběrem pole v prvním sloupci. To můžeme udělat osmi způsoby. Ve druhém poli máme na výběr již jen sedm polí, neboť pole v řádku, na němž je vybrané pole z prvního sloupce podle podmínek úlohy vybrat nelze. Jedno ze sedmi polí ve druhém sloupci vybereme. Ve třetím sloupci zůstane na výběr šest polí, atd. Celkem tedy můžeme požadovaná pole vybrat 8·7·6·5·4·3·2·1 = 8! = 40 320 způsoby. f) Vybereme k sloupců, z nichž potom budeme jednotlivá pole vybírat. To můžeme udělat c(8, k) způsoby. Podobně jako v úloze e) můžeme v prvním z vybraných sloupců vybrat jedno pole osmi způsoby, ve druhém sedmi, atd. Po výběru sloupců tedy můžeme jednotlivá pole (tj. řádky) vybírat 8·7 · · ·(8−k+1) = v(8, k) způsoby. Pole požadovaných vlastností můžeme tedy celkem vybrat c(8, k) v(8, k) = 8 k 8! (8 − k)! = 8!2 k! (8 − k)!2 způsoby. Všimněme si, že úlohy c) a e) jsou speciálními případy úlohy f); úloha c) pro k = 2, úloha e) pro k = 8. Výsledky jsou stejné, každá z úvah vedoucí k výsledku v případě c) byla jiná. Příklad 7. Určete, kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu jsou tři cifry sudé a tři cifry liché. Sudé cifry jsou 0, 2, 4, 6, 8, liché jsou 1, 3, 5, 7, 9. Na první pozici může stát libovolná z pěti lichých cifer nebo sudá cifra různá od 0. Pro čísla začínající sudou cifrou je tedy jiný počet možných výběrů první cifry než v případě čísla začínajícího cifrou lichou. Věnujme se proto nejprve číslům začínajícím sudou cifrou. Nejprve určíme počet „konfigurací dvou sudých a tří lichých číslic, tj. kolika způsoby lze určit, na kterých pozicích budou sudé a na kterých liché cifry. Každou takovou „konfiguraci lze znázornit jako permutaci prvků s, s, l, l, l. Takových permutací podle 2.1.5 je P(2, 3). 28 2 Kombinatorika Pro danou „konfiguraci dvou sudých a tří lichých cifer určíme počet možných konkrétních výběrů cifer dané parity. Na každou pozici můžeme vybrat libovolnou z pěti cifer, celkový počet možností tedy je 5 · 5 · 5 · 5 · 5 = 55 . Libovolnou „konfiguraci můžeme „naplnit libovolným z 55 konkrétních výběrů cifer a jim předřadit libovolnou ze čtyř nenulových sudých cifer. Celkový počet možností tedy je P(2, 3) · 55 · 4 = 5! 2! 3! 55 4. Analogickou úvahou ukážeme, že šesticiferných čísel splňujících danou podmínku a začínajících lichou cifrou je 5! 2! 3! 55 5. Všech čísel vyhovujících zadané podmínce tedy je 5! 2! 3! 55 4 + 5! 2! 3! 55 5 = 5! 2! 3! 55 9 = 281 250. Příklad 8. (náročnější ale zajímavý) Kolik je všech permutací n prvků a1, a2, . . . , an takových, že pro žádné i ∈ {1, 2, . . ., n} není prvek ai na i-tém místě? Označme hledaný počet symbolem dn. Je-li n = 1, je d1 = 0 — jediný prvek a1 může být na jediné, tj. první pozici. Je-li n = 2, je d2 = 1 — jediná permutace vyhovující podmínce úlohy je a2a1. Buď n > 2. Rozdělme všech dn permutací na n − 1 disjunktních skupin podle toho, který prvek je na prvním místě (skupin je n − 1, neboť prvek a1 na prvním místě být nemůže). Vezmeme nějaké k z množiny {2, 3, . . ., n} a budeme se zabývat skupinou permutací, které mají na prvním místě prvek ak. Tu rozdělíme na dvě disjunktní podskupiny: do první dáme permutace, které mají prvek a1 na k-tém místě, do druhé ty ostatní. V první podskupině je dn−2 permutací — dvě místa, první a k-té, máme obsazena, na ostatních je zbývajících n − 2 prvků umístěno podle zadání úlohy. Permutací ve druhé skupině je tolik, kolik je všech možných uspořádání n − 1 prvků a2, a3, . . . , ak−1, a1, ak+1, ak+2, . . . , an takových, že žádný prvek není na té pozici, na níž je napsán. Tedy permutací ve druhé podskupině je dn−1. Permutací v uvažované skupině je celkem dn−2 +dn−1. Stejnou úvahu můžeme provést pro každou skupinu, tj. můžeme ji provést celkem (n − 1)-krát. Tím dostaneme, že hledaný počet permutací je dn = (n − 1) (dn−2 + dn−1) . Poněvadž známe d1 a d2, můžeme vypočítat d3 = (3 − 1)(0 + 1) = 2, 2.3 Princip inkluze a exkluze 29 poněvadž známe d2 a d3, můžeme dále vypočítat d4 = (4 − 1)(1 + 2) = 9 a dále d5 = (5 − 1)(2 + 9) = 44, d6 = (6 − 1)(9 + 44) = 265, d7 = (7 − 1)(44 + 265) = 1 854, d8 = (8 − 1)(265 + 1 854) = 14 833, atd. Vidíme, že hodnoty dn s přibývajícím n velmi rychle rostou, řešit úlohu vypsáním všech možností by pro větší n bylo prakticky nemožné. Jiný způsob řešení úlohy bude uveden na str. 38. 2.2 Přihrádkový princip S rozdělováním předmětů do přihrádek (sr. 2.1.6) souvisí i jednoduchý přihrádkový princip: Nechť k, n jsou přirozená čísla, k > n. Při jakémkoliv rozdělení k předmětů do n přihrádek existuje přihrádka, v níž budou alespoň dva předměty. Přihrádkový princip je obecnou formulací populární úlohy: „Zjistěte, zda mezi obyvateli Brna existují dva lidé, kteří mají stejný počet vlasů. Tuto úlohu samozřejmě nelze vyřešit spočítáním vlasů u všech obyvatel Brna. Musíme si pomoci úvahou. Jeden člověk má na hlavě maximálně 300 000 vlasů1 , Brno má 369 299 oby- vatel2 . Lidí, kteří nemají stejný počet vlasů je nejvýše 300 001 — úplně plešatý, s jedním vlasem, se dvěma vlasy, atd. až nakonec člověk s 300 000 vlasy. Protože počet obyvatel Brna je větší, musí mezi nimi být dva lidé se stejným počtem vlasů. Tato úloha je ukázkou důkazu sporem. Ten sice zaručí existenci nějakého objektu — v našem případě dvojice osob, které mají v jeden okamžik stejný počet vlasů — ale nedává žádný návod, jak tento objekt najít. Navíc ani nemůžeme znát nějaké jeho další vlastnosti — v našem případě např. nevíme, zda jsou tyto osoby téhož pohlaví; žen je totiž 194 148 a mužů 175 151, tedy počty nižší, než odhadnutý maximální počet vlasů. Matematika může dát jistotu o existenci něčeho, co nikdo nikdy neviděl, ani vidět nemohl a o čem dokonce ani nemůžeme všechno vědět. 2.3 Princip inkluze a exkluze Budeme se zajímat o počty prvků jistých konečných množin; konkrétně takových, které jsou sjednocením k jiných množin. Počet prvků množiny A označíme symbolem |A|. 1V literatuře lze najít různé údaje. Jako průměrný počet vlasů na hlavě jsou v učebnici L. Borovanský a kol., Soustavná anatomie člověka, Avicenum, Praha 1976 na str. 954 uvedeny hodnoty 80 000, 120 000, 140 000. Hodnota 300 000 je větší než dvojnásobek nejvyšší uváděné průměrné; mohl by to být rozumný odhad maximálního počtu vlasů na jedné hlavě. 2Údaj ČSÚ z 31. 3. 2004. 30 2 Kombinatorika 2.3.1 Dvě nebo tři množiny V případě k = 2, tedy v případě dvou množin A, B, je situace jednoduchá; je znázorněna na obr. 2.2 a). Sečteme-li počty prvků v jednotlivých množinách, započítáme tím prvky, které jsou oběma množinám společné (tj. prvky z A∩B, které jsou vyznačeny šrafovaně) dvakrát — poprvé spolu s prvky množiny A, podruhé s prvky množiny B. Proto je musíme odečíst. Dostaneme |A ∪ B| = |A| + |B| − |A ∩ B|. (2.7) BA BA C a) pro dvě množiny b) pro tři množiny Obr. 2.2: K principu inkluze a exkluze V případě k = 3 je situace trochu složitější, viz obr. 2.2 b), ale i zde poměrně snadno odvodíme příslušný vzorec. Sečteme-li prvky v jednotlivých množinách, započítáváme tím prvky ležící v jednoduše šrafovaných oblastech dvakrát a prvky ležící v trojitě šrafované oblasti třikrát. Každý z průniků A ∩ B, A ∩ C, B ∩ C obsahuje jednu z jednoduše šrafovaných oblastí a trojitě šrafovanou oblast. Při odečtení počtů prvků z těchto průniků tedy odečteme prvky z jednoduše šrafovaných oblastí a současně odečteme třikrát počet prvků z trojitě šrafované oblasti (průniku A ∩ B ∩ C), tj. všechny tyto prvky. Ony ovšem do sjednocení množin A∪B ∪C patří, takže je musíme k celkovému počtu přičíst. Dostáváme tak vzorec |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. (2.8) Ze vzorců (2.7) a (2.8) i ze způsobu jejich odvození vidíme, že počet prvků sjednocení nějakých množin dostane jako součet prvků jednotlivých množin od kterého odečteme počty prvků průniků těchto množin a k tomu, v případě tří množin opět přičteme počet prvků průniku množin. Z toho je také zřejmé, proč se 2.3 Princip inkluze a exkluze 31 uvedená kombinatorická úvaha nazývá princip inkluze a exkluze3 . Příklad 9. Od řeky se vrací skupina spokojených rybářů. Spokojeni jsou proto, že každý z nich něco ulovil. V jejich úlovku jsou dva druhy ryb, kapři a cejni. Kapra ulovilo osm rybářů, cejna pět rybářů, kapra i cejna si odnáší tři rybáři. Kolik je rybářů? Kolik by bylo rybářů v případě, že by dva z nich měli ve svém úlovku i sumce, přičemž dva druhy ryb ulovili čtyři rybáři a žádný z těch, kteří ulovili sumce, neulovili cejna? Označme K množinu rybářů, kteří ulovili kapra a C množinu rybářů, kteří ulovili cejna. Podle zadání je |K| = 8, |C| = 5, |K ∩ C| = 3. Poněvadž každý z rybářů něco ulovil, je jejich počet roven |K ∪ C|. Podle (2.7), kde píšeme K místo A a C místo B, dostaneme |K ∪ C| = |K| + |C| − |K ∩ C| = 8 + 5 − 3 = 10. Na první otázku lze samozřejmě odpovědět i přímočarou úvahou: Poněvadž tři rybáři ulovili kapra i cejna, tak jenom kapra ulovilo 8 − 3 = 5 rybářů a jenom cejna ulovili 5 − 3 = 2 rybáři. Celkový počet rybářů je součet těch, kteří ulovili oba druhy, těch, kteří ulovili jenom kapra a těch, kteří ulovili jenom cejna, tedy 3 + 5 + 2 = 10 rybářů. Označme dále S množinu rybářů, kteří ulovili sumce. Podle zadání je počet jejich prvků |S| = 2. Poněvadž žádný z rybářů neulovil sumce i cejna, je S ∩C = ∅ a tedy také S ∩C ∩K = ∅; to znamená, že |S ∩C| = 0, |S ∩C ∩K| = 0. Dva druhy ulovili čtyři rybáři, z nich tři mají kapra a cejna, takže jeden má kapra i sumce, |K ∩ S| = 1. Celkový počet rybářů nyní podle (2.8) je |K ∪ C ∪ S| = |K| + |C| + |S| − |K ∩ C| − |K ∩ S| − |C ∩ S| + |K ∩ C ∩ S| = = 8 + 5 + 2 − 3 − 1 − 0 + 0 = 11. Příklad 10. Z pytlíku, v němž jsou 3 žluté, 1 modrá, 10 červených a 19 zelených kuliček nabereme hrst deseti kuliček. Kolik různých hrstí můžeme dostat? Nejprve si představme, že v pytlíku je alespoň deset kuliček od každé barvy. Označme M množinu všech možných hrstí deseti kuliček uvedených barev a A, B podmnožiny množiny M takové, že A . . . množina hrstí, v nichž je více než 3 žluté kuličky, B . . . množina hrstí, v nichž je více než 1 modrá kulička. Hledaný počet hrstí bude |M| − |A ∪ B|. Podle 2.1.6 je |M| = C(4, 10) = 13 3 = 13 · 12 · 11 3 · 2 = 286, 3Z latinského includere — vložit, pojmout, vsadit; excludere — vyloučit, nevpustit, zabránit v přístupu. Tedy „princip zahrnutí a odstranění nebo „princip zařazení a vyloučení . 32 2 Kombinatorika a podle principu inkluze a exkluze (2.7) je |A ∪ B| = |A| + |B| − |A ∩ B|. Buď i ∈ {4, 5, 6, 7, 8, 9, 10} a symbolem Ai označme podmnožinu množiny A takovou, že hrsti z množiny Ai obsahují právě i žlutých kuliček. Zřejmě platí |A| = |A4| + |A5| + |A6| + |A7| + |A8| + |A9| + |A10| = 10 i=4 |Ai| . Můžeme si představit, že hrsti z množiny Ai jsme vytvořili tak, že jsme vzali i žlutých kuliček a k nim přidali hrst 10 − i kuliček zbývajících tří barev. Takových hrstí je C(3, 10 − i) a stejný je tedy i počet prvků množiny Ai, |Ai| = C(3, 10 − i) = 12 − i 2 . Platí tedy |A| = 10 i=4 12 − i 2 = 8 · 7 2 + 7 · 6 2 + 6 · 5 2 + 5 · 4 2 + 4 · 3 2 + 3 · 2 2 + 2 · 1 2 = 84. Analogickou úvahou lze odvodit, že |B| = 10 i=2 12 − i 2 = 165. Buďte nyní i ∈ {4, 5, 6, 7, 8, 9, 10}, j ∈ {2, 3, 4, 5, 6, 7, 8, 9, 10} taková čísla, že i + j ≤ 10 a označme symbolem Cij takovou podmnožinu množiny M, že hrsti z této množiny obsahují právě i žlutých a j modrých kuliček. Zřejmě platí |A ∩ B| = |C42| + |C43| + |C44| + |C45| + |C46| + + |C52| + |C53| + |C54| + |C55| + |C62| + |C63| + |C64| + + |C72| + |C73| + |C82| = 8 i=4 10−i j=2 |Cij| . Opět si můžeme představit, že hrsti z množiny Cij jsme vytvořili tak, že jsme vzali i žlutých a j modrých kuliček a k nim jsme přidávali 10−(i+j) kuliček zbývajících dvou barev. Tedy |Cij| = C(2, 10 − i − j) = 11 − i − j 1 = 11 − i − j a dále |A ∩ B| = (11 − 6) + (11 − 7) + (11 − 8) + (11 − 9) + (11 − 10)+ + (11 − 7) + (11 − 8) + (11 − 9) + (11 − 10) + (11 − 8) + (11 − 9) + (11 − 10)+ + (11 − 9) + (11 − 10) + (11 − 10) = 35. 2.3 Princip inkluze a exkluze 33 Celkem tedy |A ∪ B| = 84 + 165 − 35 = 214, takže můžeme vybrat 286 − 214 = 72 různých hrstí kuliček. Úlohu lze řešit i jinou úvahou. Nejdříve spočítáme všechny hrsti, v nichž není modrá kulička. Mezi těmi určíme počet těch, ve kterých je právě i žlutých kuliček. Takových hrstí je možno vybrat C(2, 10 − i). Hrstí, ve kterých není modrá kulička tedy je 3 i=0 C(2, 10 − i) = 3 i=0 11 − i 1 = 11 + 10 + 9 + 8 = 38. Analogicky odvodíme, že hrstí, ve kterých je modrá kulička, je celkem 3 i=0 C(2, 9 − i) = 3 i=0 10 − i 1 = 10 + 9 + 8 + 7 = 34. Celkem je tedy možno z pytlíku nabrat 38 + 34 = 72 různých hrstí kuliček. Dvěma různými způsoby jsme dostali stejný výsledek. Úvaha s využitím principu inkluze a exkluze je pro danou úlohu komplikovanější; lze ji ale použít i v obecnější, méně přehledné, situaci. Na princip inkluze a exkluze se lze podívat i z jiného úhlu. Uvažujme množinu M nějakých prvků, které mohou, ale nemusejí, mít některou z vlastností α, β, γ. Označme m = |M| počet prvků množiny M; mα, resp. mβ, resp. mγ počet prvků, které mají vlastnost α, resp. β, resp. γ; mαβ, resp. mαγ, resp. mβγ počet prvků, které mají současně vlastnosti α i β, resp. α i γ, resp. β i γ; mαβγ počet prvků, které mají všechny tři vlastnosti; mα′β′γ′ počet prvků, které nemají žádnou z vlastností α, β, γ. Označíme-li dále A, resp. B, resp. C množinu prvků z množiny M, které mají vlastnost α, resp. β, resp. γ, bude mα = |A|, mβ = |B|, mγ = |C|, mαβ = |A ∩ B|, mαγ = |A ∩ C|, mβγ = |B ∩ C|, mαβγ = |A ∩ B ∩ C|. Sjednocení množin A ∪ B ∪ C je množinou těch prvků, které mají alespoň jednu z vlastností α, β, γ. Podle principu inkluze a exkluze (2.8) je |A ∪ B ∪ C| = mα + mβ + mγ − mαβ − mαγ − mβγ + mαβγ. (2.9) Celkový počet prvků množiny M je součtem všech prvků, které mají alespoň jednu z vlastností α, β, γ a počtu prvků, které žádnou z těchto vlastností nemají, tj. |M| = |A ∪ B ∪ C| + mα′β′γ′ . Odtud dostaneme mα′β′γ′ = |M| − |A ∪ B ∪ C| 34 2 Kombinatorika a po dosazení (2.9) mα′β′γ′ = |M| − mα − mβ − mγ + mαβ + mαγ + mβγ − mαβγ. (2.10) Příklad 11. Personalistka jisté firmy poskytla řediteli následující informaci: ve firmě pracuje 250 mužů a 200 žen, přitom 160 mužů a 140 žen má vysokoškolské vzdělání, do práce dojíždí 180 mužů a 100 žen, vysokoškolsky vzdělaných mužů dojíždí 150 a vysokoškolsky vzdělaných žen 20. Co z toho může ředitel usoudit? Ve firmě podle údajů pracuje celkem 250+200=450 lidí. Spočítáme, kolik z nich je žen bez vysokoškolského vzdělání, které do práce nedojíždějí. Označme vlastnosti osob: α . . . mužské pohlaví, β . . . vysokoškolské vzdělání, γ . . . dojíždí do zaměstnání. Použijeme označení zavedené před příkladem. Pak hledaný počet je mα′β′γ′ . Podle podmínek uvedených v informaci je mα = 250, mαβ = 160, mβ = 160 + 140 = 300, mαγ = 180, mγ = 180 + 100 = 280, mβγ = 150 + 20 = 170, mαβγ = 150. Podle principu inkluze a exkluze (2.10) je mα′β′γ′ = 450 − 250 − 300 − 280 + 160 + 180 + 170 − 150 = −20. To samozřejmě není možné. Ředitel může usoudit, že personalistka si informace vymyslela. Příklad 12. V počítačové učebně je třicet počítačů. Přitom dvacet běží pod operačním systémem Linux, osm má připojen plochý monitor a dvacet pět má nainstalovanou CD mechaniku; alespoň dva z uvedených atributů má dvacet počítačů, všechny tři má šest počítačů. Kolik počítačů a) má alespoň jednu z uvedených vlastností? b) má právě jednu z uvedených vlastností? c) nemá žádnou z uvedených vlastností? Označme: L . . . množina počítačů s operačním systémem Linux, P . . . množina počítačů s plochým monitorem, C . . . množina počítačů s CD mechanikou, pj . . . počet počítačů, které mají právě j z uvedených vlastností, a1 . . . počet počítačů, které mají alespoň jednu z uvedených vlastností. Zřejmě je a1 = |L ∪ P ∪ C|. Dále položme s1 = |L| + |P| + |C|, s2 = |L ∩ P| + |L ∩ C| + |P ∩ C|, s3 = |L ∩ P ∩ C|. Podle zadání je |L| = 20, |P| = 8, |C| = 25, 2.3 Princip inkluze a exkluze 35 takže s1 = 20 + 8 + 25 = 53 a dále s3 = p3 = 6. Počet počítačů, které mají právě dvě vlastnosti, je roven počtu počítačů, které mají alespoň dvě vlastnosti zmenšenému o počet počítačů, které mají právě tři vlastnosti, tj. p2 = 20 − 6 = 14. V součtu s2 je zahrnut počet p2 a třikrát počet p3 (viz obr. 2.2 b), v němž nahradíme množinu A množinou L a množinu B množinou P), tj. s2 = p2 + 3p3 = 14 + 3 · 6 = 32. a) Podle principu inkluze a exkluze (2.8), v němž píšeme L místo A a P místo L, platí a1 = s1 − s2 + s3 = 53 − 32 + 6 = 27. b) Zřejmě je a1 = p1 + p2 + p3, takže p1 = a1 − p2 − p3 = 27 − 14 − 6 = 7. c) Podle vztahu (2.10), v němž |M| = 30, je počet počítačů, které nemají žádnou z uvedených vlastností, roven 30 − s1 + s2 − s3 = 30 − 53 + 32 − 6 = 3. Na otázku bylo možné také odpovědět prostou úvahou: všech počítačů je 30, z nich 27 má podle části a) alespoň jednu z uvedených vlastností, takže žádnou z nich nemají 30 − 27 = 3 počítače. 2.3.2 Obecný počet množin Pokud uvažované množiny místo symbolů A, B, C označíme symboly A1, A2, A3, lze princip inkluze a exkluze pro tři množiny (2.8) zapsat ve tvaru |A1 ∪ A2 ∪ A3| = = |A1| + |A2| + |A3| − |A1 ∩ A2| + |A1 ∩ A3| + |A2 ∩ A3| + |A1 ∩ A2 ∩ A3| = = 3 i=1 |Ai| − 3−1 i=1 3 j=i+1 |Ai ∩ Aj| + 3−2 i=1 3−1 j=i+1 3 l=j+1 |Ai ∩ Aj ∩ Al| = = 3 i=1 |Ai| − 2 i=1 3 j=i+1 |Ai ∩ Aj| + |A1 ∩ A2 ∩ A3|. 36 2 Kombinatorika Tento zápis napovídá, jak by bylo možné výsledek zobecnit pro libovolné k: |A1 ∪ A2 ∪ · · · ∪ Ak| = k i=1 |Ai| − k−1 i1=1 k i2=i1+1 |Ai1 ∩ Ai2 | + + k−2 i1=1 k−1 i2=i1+1 k i3=i2+1 |Ai1 ∩ Ai2 ∩ Ai3 | − · · · + · · · + (−1)k 2 i1=1 3 i2=i1+1 · · · k−1 ik−1=ik−2+1 Ai1 ∩ Ai2 ∩ · · · ∩ Aik−1 + + (−1)k+1 |A1 ∩ A2 ∩ · · · ∩ Ak| = = k j=1  (−1)j+1 1≤i1