Počet možných výběrů z předem daného sou
Download 411.45 Kb. Pdf ko'rish
|
|
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 neroz- liš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 vybra- né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 d d
d d d d
d d d d $$$
$
$$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $
d d d d
d d d d $$$
$
$$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ $$$ $ Č Ž 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ázd- né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)! = = 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. Po- stupně 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 zo- pakujeme 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 opako- váním symbolem V (n, k), dostaneme V (n, k) = n · n · n · · · · · n k-krát = n
k . 2.1.5 Permutace s opakováním v situaci (k 1 , k 2 , . . . , k n )
stejného druhu jsou vzájemně nerozlišitelné. Prvků prvního druhu je k 1 , druhého k 2 atd. Samozřejmě má smysl pouze případ, kdy n ≤ k, k 1 ≥ 1, k
2 ≥ 1,. . . ,k n ≥ 1,
k 1 +k 2 +· · ·+k
n = 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 k 1 -krát, druhý k 2 -krát, . . . , n-tý k n -krát. V této interpretaci můžeme připustit i k i = 0 pro nějaké i z množiny {1, 2, . . . , n}, stále ovšem musí platit, že k 1 + k 2 + · · · + k n = k.
Označme hledaný počet symbolem P (k 1 , k 2 , . . . , k n ). 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(k 1 + k
2 + · · · + k n ) = (k
1 + k
2 + · · · + k n )!.
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
a 1 b 1 a 2 b 2 b 3 a 2 b 1 a 1 b 2 b 3 různé, bez označení prvků prvního druhu nerozlišíme permutace a b 1 a b 2 b 3 a b 1 a b 2 b 3 . Rozlišitelných permutací bude tolikrát méně, kolik je možných permutací k 1 prvků,
tedy k 1 !-krát. Analogickou úvahu provedeme pro prvky všech druhů a dostaneme P (k 1 , k 2 , . . . , k n ) =
p (k 1 + k 2 + · · · + k n ) p (k 1 )p(k 2 ) · · · p(k n )
(k 1 + k 2 + · · · + k n )!
1 ! k
2 ! · · · k n !
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, k 1 = 2 (lístečky s číslicí 3), k 2 = 3 (lístečky s číslicí 5) a k 3 = 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 (vrace- ní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 (k 1 , k 2 , . . . , k n ) takových, že k 1 ≥ 0, k
2 ≥ 0, . . . , k n ≥ 0, a k
1 + k
2 + · · · + k n = k;
přitom k 1 značí počet vybraných předmětů prvního druhu, k 2 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 k 1 = 3, k
2 = 2, k
3 = 1, k
4 = 0,
k 5 = 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 po- mocí 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 · 10 12 24 2 Kombinatorika způsoby. Z hlediska ubytovaných záleží na tom, kdo na kterém lůžku leží, jaké má sou- sedy ap. Z jejich pohledu tedy je v (50, 35) = 50! 15!
= 2, 325 815 505 · 10 52 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! = 604 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 vy- skytují 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?
Download 411.45 Kb. Do'stlaringiz bilan baham: 
|