Management rekreace a sportu Kombinatorika
Download 128.4 Kb. Pdf ko'rish
|
|
Management rekreace a sportu 6. Kombinatorika 1 6. Kombinatorika V praxi se běžně setkáme s potřebou určit, kolika způsoby lze něco provést, případně kolik je možných způsobů, jak nějaký jev nastane. Výpočty zmíněného charakteru se zabývá kombinatorika. Základním principem je pravidlo součinu. KOMBINATORICKÉ PRAVIDLO SOUČINU Lze-li činnost A provést m způsoby a nezávisle na ní činnost B n způsoby, pak počet všech možných způsobů, jak provést A i B se rovná m⋅n. Příklad: V restauraci jsou na jídelníčku 3 různé polévky a 4 různá hlavní jídla. Kolik je všech možných způsobů, jak si vybrat polévku a k ní hlavní jídlo? Řešení:
Polévku lze vybrat třemi způsoby, nezávisle na ní hlavní jídlo čtyřmi způsoby. Podle pravidla součinu lze vybrat celkem 3⋅4 = 12 způsoby určitou polévku a k ní hlavní jídlo. Kombinatorické pravidlo součinu platí i pro případ více než dvou nezávislých činností. Příklad:
(a) Jana si může ze své garderoby pro odpolední vycházku vybrat z 5 různých halenek, ze 7 různých sukní a ze 4 různých párů bot. Kolika různými způsoby se může obléci? Řešení: Jana se může obléci celkem 5⋅7⋅4 = 140 různými způsoby. (b) Bezpečnostní zámek u kufříku je konstruován ze tří otočných koleček. Na každém z nich lze nastavit číslice 0, 1,…, 9. Kolik různých konfigurací má bezpečnostní zámek? Řešení: Každá konfigurace je uspořádaná trojice (a, b, c). Na každé z poloh a, b, c lze nastavit nezávisle na sobě 10 různých poloh číslicemi 0, 1,…, 9. Celkový počet konfigurací je pak 10⋅10⋅10 = 1000. K výsledku lze dospět i jinou úvahou: Počet konfigurací musí odpovídat počtu různých trojmístných čísel (tj. 000, 001,…, 100,…, 999), kterých je celkem 1000. Úvahy doposud prováděné lze převést na úvahy o uspořádaných k-ticích. Tak v předchozím příkladu (a) jde o počet uspořádaných trojic (halenka, sukně, boty),
Management rekreace a sportu 6. Kombinatorika 2 v příkladu (b) počet trojic čísel (a, b, c). Pak lze kombinatorické pravidlo součinu obecně formulovat takto: Počet všech uspořádaných k-tic, z nichž první člen lze vybrat n 1 různými způsoby, druhý člen po výběru prvního členu n 2 různými způsoby atd., až k-tý člen po výběru (k − 1). členu n k různými způsoby, se rovná n 1 ⋅n 2 ⋅…⋅n k . Příklad: Kolika různými způsoby se může seřadit 6 klientů do fronty u přepážky ve spořitelně? Řešení: Klienti vytvářejí různé uspořádané šestice (a 1 , a
2 , a
3 , a
4 , a
5 , a
6 ). Člen a 1 , tj. klienta stojícího jako prvního, lze vybrat 6 způsoby. Po výběru členu a 1 lze člen a 2 vybrat již pouze 5 způsoby (1 klient již byl vybrán na první místo), člen a 3 4 způsoby atd., až člen a 6 jediným způsobem. Celkem lze tedy vytvořit 6⋅5⋅4⋅3⋅2⋅1 = 720 různých front. Kombinatorické úlohy lze roztřídit do skupin, majících společný "výpočetní základ" tzv. variací, permutací, kombinací a jejich modifikací. VARIACE
Variace k-té třídy z n prvků (k ≤ n) je každá uspořádaná k-tice různých prvků vybraných z n prvků. Počet všech různých variací k-té třídy z n prvků se značí V k (n).
[Slovy jinak: Variace je k-tice vybraná z n prvků, přičemž v ní záleží na pořadí a každý z prvků se v ní vyskytuje nejvýše jednou]. Příklad: Všechny různé variace druhé třídy z prvků a, b, c, d jsou (přehledně): a je první b je první c je první d je první ab ac
ba bc bd ca cb cd da db dc Platí V 2 (4) = 12 . Pro počet V k (n) všech různých variací k-té třídy z n prvků platí vzorec ( ) ( ) ( ) 1 1 + − − = k n n n n k ⋯ V . (6.1)
Management rekreace a sportu 6. Kombinatorika 3 Tento vzorec se zapisuje obvykle ve tvaru ( ) ( ) ! ! k n n n k − = V , (6.2) kde ( )( ) 1 2 2 1 ! ⋅ − − = ⋯ n n n n , přičemž se definuje 0! = 1; n! se čte "n faktoriál". Příklad: Manažer portfolia dospěl k závěru, že akcie 13 společností splňují jeho investorské záměry. Z těchto třinácti má určit 3 včetně pořadí, které stanoví jejich preference. Kolika způsoby to může provést? Řešení:
Jde o variace 3. třídy ze 13 prvků, platí ( )
( ) 1716 11 12 13 ! 10 ! 10 11 12 13 ! 10 ! 13 ! 3 13 ! 13 13 3 = ⋅ ⋅ = ⋅ ⋅ ⋅ = = − = V . Výběr lze provést 1716 způsoby. Připustí-li se opakování prvků v uspořádané k-tici vybrané z n prvků, pak se hovoří o variaci s opakováním: Variace s opakováním k-té třídy z n prvků je každá uspořádaná k-tice prvků vybraných z n prvků. Počet všech různých variací s opakováním k-té třídy z n prvků se značí ( ) n
k V . Příklad: Všechny různé variace s opakováním druhé třídy z prvků a, b, c, d jsou: aa, ab, ac, ad; ba, bb, bc, bd; ca, cb, cc, cd; da, db, dc, dd. Platí ( )
16 4 2 = o V . Pro počet ( ) n
k V všech různých variací s opakováním k-té třídy z n prvků platí vzorec ( ) k o k n n = V . (6.3) Příklad: Kolik je všech možných devítimístných telefonních čísel? Management rekreace a sportu 6. Kombinatorika 4 Řešení:
Jde o variace s opakováním, ( )
1000000000 10 10 9 9 = = o V . Zvláštním případem variací jsou permutace (pro k = n). PERMUTACE Permutace n prvků je každá variace n-té třídy z n prvků. Počet všech permutací z n prvků se značí P(n). [Slovy jinak: Permutace n prvků je zápis těchto prvků v určitém pořadí.] Příklad:
Všechny různé permutace prvků a, b, c jsou: abc, acb, bac, bca, cab, cba. Platí P(3) = 6. Ze vztahu (6.2) ihned vyplývá vzorec pro počet permutací n prvků: ( ) !
n = P . (6.4) Příklad:
Kolik lze vytvořit všech slov přesmyčkou ve slově BOULE? Řešení:
P(5) = 5! = 120. Permutace s opakováním n prvků je každá variace s opakováním n-té třídy, ve které se k < n různých prvků vyskytuje v počtech n 1 , n 2 ,…, n
k (platí pak n 1 + n
2 +…+ n
k = n). Počet takových permutací se značí ( )
n o n n k , , 1 … P . Platí
( ) ! ! ! ! 2 1 , , 1 k o n n n n n n n k … … = P . (6.5)
Příklad: Kolik různých slov lze vytvořit přesmyčkou ve slově KOLOKOL? Řešení: Jde o sedmici, ve které s K vyskytuje dvakrát, O třikrát a L dvakrát. Užitím (6.5) dostaneme ( ) 210
1 2 1 2 3 1 2 1 2 3 4 5 6 7 ! 2 ! 3 ! 2 ! 7 7 2 , 3 , 2 = ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ = = o P . Management rekreace a sportu 6. Kombinatorika 5 KOMBINACE Kombinace se od variací zásadně liší v tom, že ve vybrané k-tici nezáleží na uspořádání, jinak řečeno v k-tici nezáleží na pořadí prvků. Kombinací k-té třídy z n prvků (k ≤ n) je každý výběr k různých prvků z n prvků. Počet všech různých kombinací k-té třídy z n prvků se značí C k (n). [Slovy jinak: Kombinace je k-tice prvků vybraná z n prvků, přičemž v ní nezáleží na pořadí a každý z prvků se v ní vyskytuje nejvýše jednou.] Příklad: Všechny různé kombinace druhé třídy z prvků a, b, c, d jsou: ab, ac, ad, bc, bd, cd. Pro počet C k (n) všech různých kombinací k-té třídy z n prvků platí vzorec: ( ) ( ) = − = k n k n k n n C k ! ! ! , (6.6)
kde k n se nazývá kombinační číslo a čte se "n nad k". Pro vyčíslení k n platí ( ) ( ) ( ) 1 2 1 1 1 ⋅ − + − − = ⋯ … k k k n n n k n . Například: 1 2
5 6 7 3 7 ⋅ ⋅ ⋅ ⋅ = . Příklad: Kolika způsoby lze vybrat 3 výrobky z 10 výrobků? Řešení:
Jde o kombinace třetí třídy z deseti prvků (nezáleží na pořadí), ( )
120 1 2 3 8 9 10 3 10 10 3 = ⋅ ⋅ ⋅ ⋅ = = C . Platí vzorce Management rekreace a sportu 6. Kombinatorika 6
+ + = + + = = − = 1 1 1 , 1 , 1 0 , k n k n k n n n n k n n k n . (6.7)
Kombinační čísla mají v matematice široké uplatnění, například, při formulaci binomické věty. BINOMICKÁ VĚTA Binomická věta udává vzorec pro umocnění součtu: Pro libovolná čísla a, b a libovolné přirozené číslo n platí ( ) n n n n n n b n n ab n n b a n b a n a n b a + − + + + + = + − − − 1 2 2 1 1 2 1 0 ⋯ . (6.8)
Příklad: ( ) . 4 6 4 1 2 3 2 3 4 1 2 3 4 4 4 4 3 4 2 4 1 4 0 4 4 3 2 2 3 4 4 3 2 2 3 4 4 3 1 2 2 1 3 4 4 b ab b a b a a b ab b a b a a b b a b a b a a b a + + + + = + ⋅ ⋅ ⋅ ⋅ + + ⋅ ⋅ + + = + + + + = + Příklad: Kolik je různých podmnožin množiny, která obsahuje n prvků? Řešení: Prázdná množina je jediná, podmnožin obsahujících jeden prvek je n, podmnožin obsahujících 2 prvky je 2 n (jde o kombinace druhé třídy z n prvků), podmnožin obsahujících 3 prvky je 3 n ,…, podmnožin obsahujících (n − 1) prvků je −1 n n , podmnožina obsahující všechny prvky dané množiny je jediná. Sečtením dostáváme ( ) ( ) ( )
. 2 1 1 1 pro 8 . 6 užitím 1 3 2 1 0 1 , 1 , 0 1 7 . 6 užitím vyjádříme 1 1
2 1 n n b a n n n n n n n n n n n n n n n n n n = + = = = = = + − + + + + + = = = = = + − + + + + + ⋯ ⋯ Management rekreace a sportu 6. Kombinatorika 7 Cílové znalosti 1. Užití kombinatorického pravidla součinu při řešení běžných kombinatorických úloh. 2. Rozlišení kombinatorických úloh na variace, permutace, kombinace a jejich modifikace. 3. Vzorce pro stanovení počtu variací, permutací, kombinací a jejich modifikací.
Management rekreace a sportu 6. Kombinatorika 8 VI. Kombinatorika_CVIČENÍ K OMBINATORICKÉ PRAVIDLO SOUČINU 1. Z města A do města B vedou čtyři cesty, z města B do města C pět cest. Určete počet cest, které vedou z města A do města C přes město B. 2. V hřebčíně mají 10 bílých a 8 černých závodních koní stejné výkonnosti. Na závod mají vybrat dvojice, kde bude jeden černý a jeden bílý kůň. Kolika způsoby mohou výběr provést? 3. Máme k dispozici 10 karafiátů, 12 žlutých a 14 červených tulipánů. Kolika způsoby lze udělat kytičku, která bude obsahovat 1 karafiát, 1 žlutý a 1 červený tulipán? 4. Určete počet všech čtyřciferných přirozených čísel, v nichž se vyskytuje každá číslice nejvýše jednou. 5. Jsou-li vrženy dvě kostky, výsledek lze vyjádřit uspořádanou dvojicí (a, b), kde a je číslo, které padlo na 1. kostce, a b je číslo, které padlo na 2.kostce. Kolik je takových různých dvojic? Kolik z nich je takových, že součty a + b jsou navzájem různé. V ARIACE
6. Ve škole se učí 10 různým předmětům a každému se učí nejvýše hodinu denně. Kolika způsoby lze sestavit rozvrh hodin na jeden den, je-li v něm 5 různých předmětů? 7. Upravte: ( ) ( ) ( ) ( ) ! 2 ! ! 1 ! 1 2 ! ! 2 − + − + − + n n n n n n . 8. Z kolika různých prvků lze vytvořit 870 variací druhé třídy? 9. Zvětšíme-li počet prvků o jeden, zvětší se počet variací druhé třídy o 16. Určete původní počet prvků. 10. Státní poznávací značka automobilu je tvořena trojicí číslice, písmeno, číslice a oddělenou skupinou čtyř číslic. Kolik lze státních poznávacích značek vytvořit, je-li k dispozici 14 písmen? 11. Řešte rovnici ( )
( ) 20 2 0 3 0 2 = − xV x V . Management rekreace a sportu 6. Kombinatorika 9 P
12. Jan napsal 4 dopisy, k nimž měl 4 obálky s adresami. Nedopatřením mu dopisy upadly na zem. Kolika způsoby je mohl do obálek vložit? 13. Kolik deseticiferných čísel s různými číslicemi lze vytvořit z číslic 0,
1, 2,
3,
4, 5,
6,
7, 8,
9? 14. Kolik různých slov lze vytvořit přesmyčkou ve slově JANA? K OMBINACE
15. 8 pracovníků chce vyjádřit nespokojenost řediteli. Ředitel je ochoten přijmout tříčlennou delegaci. Kolika způsoby lze takovou delegaci vytvořit? 16. Zvětší-li se počet prvků o 1, zvětší se počet kombinací třetí třídy o 21. Kolik je dáno prvků?
17. V bedně je 28 výrobků 1. jakosti a 2 výrobky vadné. Kolikerým způsobem lze vybrat pět výrobků tak, aby tři z nich byly 1. jakosti a dva z nich byly vadné? 18. Řešte rovnici 16 5 3 4 2 = − − + − − x x x x . V ŠEHOCHUŤ 19. Vypočtěte užitím Binomické věty ( )
3 1 i
− . 20. V lavici sedí 5 chlapců, z nichž dva bratři chtějí sedět vedle sebe. Kolikrát můžeme chlapce přesadit? 21. Kolik různých slov lze utvořit přesmyčkou ve slově CINCINNATI? 22. Hokejové mužstvo má 20 hráčů – 13 útočníků, 5 obránců a 2 brankáře. Kolik různých sestav by mohl vytvořit tým, má-li sestava 3 útočníky, 2 obránce a 1 brankáře? Nerozlišujeme konkrétní posty v útoku a v obraně.
Management rekreace a sportu 6. Kombinatorika 10 V
1. 20; 2. 80; 3. 1 680; 4. 4 536; 5. 36 a 11; 6. 30 240; 7. 2; 8. n = 30; 9. n = 8; 10. 14 000 000; 11. x = 10; 12. 24; 13. 3 265 920; 14. 12; 15. 56; 16. n = 7; 17. 3 276; 18. x = 7; 19. 64; 20. 48; 21. 50 400; 22. 5 720. Download 128.4 Kb. Do'stlaringiz bilan baham: 
|