Základní kombinatorické principy
1.1 Princip bijekce
je vzájemně jednoznačné přiřazení prvků dvou množin:
jedna množina pro nás může být nepřehledná a vztahy v ní dokážeme těžko postihnout, zatímco druhá množina je pro řešení problému přehledná Známe-li tedy řešení na množině přehledné, známe i řešení na druhé množině. Kombinatoricky: jestliže na první množině existuje právě m - řešení, pak na vzájemně jednoznačně přiřazené množině existuje také m - řešení.
Každému prvku z množiny A je přiřazen právě jeden prvek z množiny B.
Obě množiny musí být stejně početné, tj. #A = #B.
Symbol #A budeme chápat jako počet prvků množiny A.
V praxi to znamená, že si popis množiny můžeme zjednodušit nějakou analogií - představou na papíře
Základní kombinatorické principy
1.2 Kombinatorické pravidlo o součinu
Máme vybrat k prvků: první prvek vybíráme z konečné neprázdné množiny s počtem prvků #A1 druhý prvek vybíráme z konečné neprázdné množiny s počtem prvků #A2 třetí prvek ... s počtem prvků #A3 ... poslední, k-tý prvek, vybíráme z konečné neprázdné množiny s počtem prvků #Ak
pokud výběr každého z prvku je nezávislý na výběru ostatních prvků, existuje celkem (#A1 · #A2 · . . . · #Ak) různých možností, jak vybrat tyto prvky
Příklad na Kombinatorické pravidlo o součinu V restauraci mají na jídelním lístku uvedeno 3 polévky, 6 hlavních jídel a 2 moučníky. Kolika způsoby lze sestavit menu ze všech třech chodů?
Výběr polévky je nezávislý na výběru hlavního jídla i moučníku, totéž platí o dalších chodech, proto použijeme kombinatorické pravidlo o násobení: N = 3*6*2 = 36
možností, jak sestavit menu
Základní kombinatorické principy
1.3 Kombinatorické pravidlo o součtu
Předpokládejme, že máme k disjunktních množin potom sjednocení těchto množin má právě #A1 + #A2 + . . . + #Ak prvků. A Lichá čísla 1,3,5
B
prázdný průnik ø
Sudá čísla 2,4,6
Disjunktní množiny mají prázdný průnik
Příklad 1 na Kombinatorické pravidlo o součtu
V restauraci mají na stálém jídelním lístku uvedena tato hlavní jídla: bezmasá jídla (3), ryby (2), drůbež (2), vepřové maso (5), hovězí maso (4).
Kolik dní můžete chodit do této restaurace, abyste jedli každý den jiné jídlo?
Řešení: Protože se jedná o disjunktní množiny, použijeme pravidlo o součtu: N = 3 + 2 + 2 + 5 + 4 = 16 dní
Základní kombinatorické principy
1.4 Součet prvků obecných množin Uvažujme množinu A a množinu B, které mají neprázdný průnik. Pokud sečteme prvky každé množiny, pak společné prvky jsme sečetli dvakrát, proto je jednou musíme odečíst:
A B
prvočísla < 10 1, 2, 3, 5, 7
průnik 2
Sudá čísla < 10 2, 4, 6, 8
{1, 2, 3, 5, 7} + {2, 4, 6, 8} = {1, 2, 2, 3, 4, 5, 6, 7, 8} průnik (číslo 2) musíme odečíst
Obecný zápis:
# (A ∪ B) = # A + # B - # (A ∩ B)
Příklad na Součet prvků obecných množin
Ve třídě je 16 studentů. Z celkového počtu mluví aktivně 10 anglicky a 8 německy. 5 studentů zvládá aktivně oba jazyky.
Určete, kolik studentů mluví jen anglicky nebo jen německy Kolik studentů nemluví aktivně žádným z těchto dvou jazyků Kolik studentů mluví aktivně nějakým jazykem? A
Zadání : A = 10 N = 8 A ∩ N = 5
N 5
5
3
Řešení : A − ( A ∩ N ) = 10 − 5 = 5 N − (A∩ N) = 8 − 5 = 3 16 − ( A ∪ N ) = 16 − (5 + 5 + 3) = 3 ( A ∪ N ) = 5 + 5 + 3 = 13
Kombinatorika - příklad
Když se bude státní vlajka skládat ze tří svislých pruhů v barvách červená modrá a bílá, kolika způsoby lze pruhy uspořádat?
Řešení: červená může být na 1., 2. nebo 3. místě modrá po umístění červené může být na 2 místech bílá barva na posledním - zbývajícím místě č m b m č b b m č
č b m b č m m b č
č m b m č b b m č
č b m b č m m b č
Počet možností vypočteme jako 3*2*1 = 6
Kdyby se jednalo o 4 různé barvy (žlutá, červená, modrá, bílá) Počet kombinací vypočteme jako násobek: = počet umístění žluté (4) * počet umístění červené (3) * * počet umístění modré (2) * počet umístění bílé (1) tj. 4*3*2*1 = 24
PERMUTACE
2.1 Permutace Máme n - různých přihrádek, n - různých předmětů (počet různých předmětů je stejný jako počet různých přihrádek)
Každý předmět můžeme umístit právě do jedné přihrádky a záleží na pořadí předmětu (jedná se o uspořádaný výběr) Je zřejmé, že 1. předmět můžeme umístit do jedné z n přihrádek, 2. předmět již jen do jedné z n-1 přihrádek, protože jsme již jednu vyčerpali, 3. předmět do jedné z n-2 přihrádek … Poslední n-tý předmět pak můžeme umístit jen poslední n-té přihrádky
S odvoláním na pravidlo o násobení můžeme vyjádřit počet způsobů umístění různých předmětů do různých přihrádek (záleží na pořadí) jako: P(n) = n * (n - 1) * (n - 2) * . . . · 2 * 1 To odpovídá zápisu, ve kterém využíváme faktoriál:
P(n ) = n !
Příklad na Permutace
Kolik různých slov vznikne přesmyčkou písmen ve slově POPOKATEPETL*? Řešení: Celkem písmen: 12 Pokud by byla všechna písmena rozdílná, počet různých slov bychom vypočetli jako násobek 12*11*10*9*8*7*6*5*4*3*2*1
Protože se některá písmena opakují, počet možností je menší
tolikrát, kolik různých možností bychom z nich udělali, kdyby byla rozdílná: pro dvě stejná písmena: počet možností se zmenší 2! (2 faktoriál krát) = 2 pro tři stejná písmena: počet možností se zmenší 3! (3 faktoriál krát) = 6
Četnost písmen ve slově: P 3x, O 2x, K 1x, A 1x, T 2x, E 2x, L 1x Počet možných slov:
*
12 ! = 9 979 200 3!⋅ 2 !⋅1!⋅1!⋅ 2 !⋅ 2 !⋅1!
Z aztéckého popoka - dýmati, tepetl - hora. Činná sopka ve střední části Mexika. Poslední erupce v roce 1932.
VARIACE bez opakování
2.2 Variace bez opakování Máme n - různých přihrádek, k - různých předmětů
každý předmět chceme umístit právě do jedné přihrádky a záleží na pořadí předmětu (jedná se o uspořádaný výběr) Předpokládejme, že n > k (jinak stačí zaměnit pojem přihrádka a předmět) Je zřejmé, že 1. předmět můžeme umístit do jedné z n přihrádek, 2. předmět již jen do jedné z n-1 přihrádek, protože jsme již jednu vyčerpali, 3. předmět do jedné z n-2 přihrádek … Poslední k-tý předmět pak můžeme umístit jen do n-k+1 přihrádek, jež zbyly prázdné.
S odvoláním na pravidlo o násobení můžeme vyjádřit počet způsobů, jimiž lze danou úlohu vyřešit jako: Vk(n) = n * (n-1) * (n-2) * . . . * (n-k+1)
Příklad na Variace bez opakování
V divadle je druhé zvonění. Šatnářka má volných 12 věšáků. Ve frontě stojí 5 netrpělivých lidí. Šatnářka v rychlosti bere kabát jeden po druhém, každý pověsí vždy na prázdný věšák, číslo předá majiteli kabátu. Ptáme se: Kolika způsoby může umístit 5 kabátů na 12 volných věšáků?
Řešení: první z 5 kabátů může pověsit na 12 věšáků, druhý už jen na 11, třetí na 10, ... Možností, jak kabáty umístit bude podle pravidla o násobení
12 *11*10 * 9 * 8 =
12 *11*10 * 9 * 8 7 * 6 * 5 * 4 * 3 * 2 *1 * = 95 040 1 (12 − 5)!
Z toho odvodíme vzorec pro VARIACE BEZ OPAKOVÁNÍ
n! Vk (n ) = (n − k ) !
PERMUTACE a VARIACE
2.1 Permutace P(n) = n * (n - 1) * (n - 2) * . . . * (n-n+1) To odpovídá zápisu, ve kterém využíváme faktoriál:
P(n ) = n !
2.2 Variace bez opakování Zápis: Vk(n) = n * (n-1) * (n-2) * . . . * (n-k+1) Zapíšeme pomocí faktoriálů:
n! Vk (n ) = (n − k ) !
Jedná se o vzorec pro počet variací k-té třídy z n prvků bez opakování.
Příklad na Variace bez opakování Parkoviště má 10 míst pro osobní vozy. Zaměstnanců firmy je 6. Kolika způsoby může být zaparkováno všech šest aut zaměstnanců? První zaměstnanec si může auto zaparkovat na libovolné místo z 10, druhý zaměstnanec už vybírá jen z 9 míst, třetí z osmi, čtvrtý ze sedmi, pátý z šesti a šestému zbývá pět míst, kam může zaparkovat svůj vůz. Obecný zápis : Vk(n) = n * (n-1) * (n-2) * . . . * (n-k+1) Výpočet: 10*9*8*7*6*5 = 151 200 Existuje 151 200 způsobů parkování 6 vozů na 10 parkovacích místech pomocí faktoriálů:
Vk (n ) =
n! (n − k ) !
10! 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 = = 151 200 (10 − 6) ! 4 * 3 * 2 *1
Příklad
Ve školce připravili pro děti 16 jogurtů, ale většina dětí onemocněla a zbývajících 5 dětí si mohlo vybrat ze tří druhů: 5 jahodových, 5 meruňkových a 6 borůvkových jogurtů. Určete kolika způsoby můžeme rozdat dětem jogurty tak, aby každé dítě dostalo právě jeden, který si vybere. Řešení: Každé dítě si může vybrat ze 3 druhů jogurtů.
Dětí je 5, tj. počet způsobů bude 3*3*3*3*3 = 35
Přihrádky = druhy jogurtů = n ... některé přihrádky zůstanou prázdné Předměty = děti = k ... přidělujeme dítě k jogurtu (každé musí dostat jeden, ale může si vybrat z n-druhů)
Vyjádřeno pomocí mocniny:
nk = 35 = 243
VARIACE s opakováním
2.3 Variace s opakováním Máme n - různých druhů přihrádek a k - různých předmětů Každý druh přihrádky máme nejméně k - krát Musíme přiřadit každému předmětu některou přihrádku.
Každému z k - předmětů můžeme přiřadit n - druhů přihrádek S odvoláním na pravidlo o násobení můžeme vyjádřit počet řešení jako:
V (n) = n⋅n ⋅ ... ⋅ n * k
Vzorec pro počet variací k - té třídy z n - druhů prvků s opakováním:
V (n ) = n * k
k
Příklad na Variace s opakováním
Typickou úlohou je výpočet možností, které skýtá morseova abeceda Má dva druhy znaků - tečka, čárka Písmena tvoří z 1, 2, 3 nebo 4 znaky, číslice jsou ze 4 nebo 5 znaků
pro jednoznaková písmena: 21 = 2 možnosti: pro dvouznaková písmena: 22 = 4 možnosti: pro tříznaková písmena: 23 = 8 možností: pro čtyřznaková písmena /čísla: 24 = 16 možností: pro pětiznaková čísla: 25 = 32 možností: Počet možných variací v morseově abecedě je tedy: 21 + 22 + 23 + 24 + 25 = 2 + 4 + 8 + 16 + 32 = 62
•, ̶ • ̶ , ̶ •, ••, ̶ ̶ ̶ ̶ ̶ , ̶ ̶ •, ̶ • ̶ , • ̶ ̶ •••, •• ̶ , • ̶ •, ̶ •• analogicky analogicky
Příklad na Variace s opakováním
Ve škole píší děti test. Skládá se z 10 otázek a pro každou otázku jsou uvedeny 4 odpovědi, ale jen jedna je správná.
existují tedy 4 druhy odpovědí Určete kolika způsoby mohou děti náhodně vyplnit test bez ohledu na to, zda odpovídaly správně. Určete pravděpodobnost, že dítě zodpovědělo všechny otázky správně. Řešení: n = 4 druhů odpovědí - přihrádky A, B, C, D V k* n = n k k = 10 otázek Počet variací vypočteme podle pravidla o násobení násobením počtu možností pro každou z 10 otázek: 4*4*4*4*4*4*4*4*4*4 = V*10(4) = 4 10 = 1 048 576 Jen jedna varianta je úplně správná. Pravděpodobnost, že nastane je: 1/1 048 576 = 0,00000095
( )
KOMBINACE - odvodíme z Variací bez opakování
2.4 Kombinace Máme n - různých přihrádek a k - nerozlišitelných předmětů a platí, že n > k Budeme obsazovat přihrádky předměty, ale protože jsou předměty stejné - záleží jen na tom, které přihrádky obsadíme a které zůstanou volné.
n! ( ) V n = Vyjdeme ze vzorce 2.2 pro variace bez opakování k (n − k ) !
ale počet kombinací bude tolikrát menší, kolik variant navíc dovolovalo k - různých předmětů, tj. k! n!
Ck (n ) =
(n − k ) ! ⋅ k !
Jedná se o vzorec pro počet kombinací k-té třídy z n - prvků Kombinace (angl. COMBINATION) představují neuspořádaný výběr
Příklad na KOMBINACE
V rezervačním systému do Divadelního sálu Metropolu zbývá osm volných míst. a) Kolika způsoby mohou tři zájemci obsadit volná křesla? b) Kolika způsoby je může obsadit pět zájemců?
Řešení: Pokud by záleželo na pořadí (uspořádání) zájemců, první zájemce by si mohl sednou na 8 míst, druhý na 7 míst, třetí na 6 míst, tj. počet možností by bylo 8*7*6 = 336 (variací) V rezervačním systému ale nezáleží na tom, zda na místě 125 sedí pan Novák nebo paní Housková. Důležité je pouze, zda je místo volné nebo obsazené. Proto počet variací musíme zmenšit - bude jich tolikrát méně, kolik možností přibylo díky uspořádání, tj. 3!
Výpočet a): 8 * 7 * 6 = 336 = 56 3!
6
Výpočet b): 8 * 7 * 6 * 5 * 4 = 6720 = 56 5!
Dosadíme-li do vzorce pro výpočet kombinací ověříme si, proč je výsledek stejný
Ck (n ) =
8! 8! = (8 − 3)! 3! (8 − 5) ! 5!
120
n! (n − k ) ! ⋅ k !
KOMBINAČNÍ ČÍSLO n n! Ck (n ) = = (n − k ) ! ⋅ k ! k
Základní vzorec:
Další pravidla pro počítání s kombinačními čísly:
n n = k n − k n = n 1
n = 1 n
n = 1 0
0 = 1 0
PRAVDĚPODOBNOST, KOMBINACE
Příklad 12 Mezi 8 bezvadných výrobků se přimíchaly 3 zmetky. Náhodně byly vybrány 2 výrobky.
a) Jaká je pravděpodobnost, že jsou oba bezvadné? Vypočteme počet možností, jak vybrat 2 výrobky z 11 - jedná se o kombinace 2 prvků z 11: C2(11) 11 11! 11⋅10 ⋅ 9! 110 C2 (11) = = = = = 55 9! ⋅ 2 ! 2 2 (11 − 2) ! ⋅ 2 !
počet možností, že vybereme 2 bezvadné výrobky C2(8)
8 8! 8 ⋅ 7 ⋅ 6 ! 56 C2 (8) = = = = = 28 2 2 (8 − 2) ! ⋅ 2 ! 6 ! ⋅ 2 !
Pravděpodobnost, že jsou oba bezvadné je p = 28/55 = 0,509
Řešení příkladu 12 pomocí kombinatoriky
b) Jaká je pravděpodobnost, že je jeden vadný? počet možností pro 1 vadný a 1 bezvadný C1(8)*C1(3) 3 8 3! 8! 3 ⋅ 2! 8 ⋅ 7 ! C1 (3) ⋅C1 (8) = ⋅ = ⋅ = ⋅ = 3 ⋅ 8 = 24 1 1 ( 3 − 1 ) ! ⋅ 1 ! ( 8 − 1 ) ! ⋅ 1 ! 2 ! ⋅ 1 ! 7 ! ⋅ 1 !
Pravděpodobnost, že je právě jeden vadný, je p = 24/55 = 0,436
c) Jaká je pravděpodobnost, že je alespoň jeden vadný? Jedná se o jev opačný k případu a)
p = 1 - 0,509 = 0,491
Pravděpodobnost, že je alespoň jeden vadný, je 0,491
Řešení příkladu 12 pomocí pravděpodobnosti 1. Vypočteme pravděpodobnost toho, že oba budou bezvadné, tj. 1. výrobek vybereme s p-ností 8/11 (8 bezvadných z celkem 11 výrobků) a 2. výrobek s p-ností 7/10 (zbylo 7 bezvadných a celkem 10 výrobků):
p=
8 7 ⋅ = 0,509 11 10
2. Pravděpodobnost, že bude jeden vadný, vypočteme analogicky:
p=
8 3 3 8 ⋅ + ⋅ = 0,218 + 0,218 = 0,436 11 10 11 10
První vybraný výrobek vybíráme z 11 výrobků - je bezvadný, druhý bude vadný vybraný z 10 výrobků. Nebo první bude vadný vybraný z 11 výrobků a druhý bezvadný vybraný z 10 výrobků. Obě pravděpodobnosti musíme sečíst, protože mohou nastat obě možnosti. 3. Pravděpodobnost, že bude alespoň jeden vadný, vypočteme jako opačný jev k jevu, že oba výrobky budou bezvadné
p = 1−
8 7 ⋅ = 1 − 0,509 = 0,491 11 10
Příklad: Pravděpodobnost, kombinace a variace s opakováním
Ve skříni je naházeno 5 párů střevíců. Tatínek jde potmě, aby nevzbudil děti a potřebuje si vybrat aspoň jeden pár bot. Namátkou tedy vybere 4 střevíce a doufá, že alespoň 2 půjdou do páru. Jaká je pravděpodobnost, že se mu to podaří? Jaká je pravděpodobnost, že neuspěje?
K řešení použijte selský rozum. reseny_priklad_strevice.xls
