Kombinatorika
Př. 1) AB … 4 způsoby
BC … 3 způsoby
Kolika způsoby lze vybrat cestu z A do C přes B?
4 . 3 = 12 … 12 způsobů
CD … 2 způsoby
4 . 3 . 2 = 24 způsobů z A do D
I.) Pravidlo kombinatorického součinu
Počet uspořádaných k-tic, jejichž první člen lze vybral n1 způsoby, druhý člen n2 způsoby, až k-tý člen po výběru všech předcházejících členů nk způsoby je roven: n = n1 . n2 … nk
Př. 2) Kolik je trojciferných přirozených čísel?
a) v nichž se cifry neopakují?
b) v nichž se cifry opakují?
c) kolik z b) je dělitelných pěti?
a) 9 . 9 . 8 = 648
b) 9 . 10 . 10 = 900
c) 9 . 10 . 2 = 180
Př. 3) Kolika způsoby se může stát, že z botníku s 5 páry bot vyberu nesprávný pár?
5 . 4 = 20
5 … pravých, 4 … k nim špatné páry
Př. 4) z A do B … 4 cesty
z B do C … 3 cesty
a) z A do C?
b) z A do C a zpět?
c) z A do C a zpět tak, že žádná z těchto 7 cest nebude užita dvakrát
d) z A do C tak, že se vracíme stejně
e) z A do C a zpět tak, aby právě 1 ze 7 cest byla použita dvakrát
a) 4 . 3 = 12
b) 4 . 3 . 3 . 4 = 144
c) nc = 4 . 3 . 2 . 3 = 72
d) nd = 4 . 3 . 1 . 1 = 12
e) ne = 4 . 3 . 1 . 3 = 36 … stejná cesta z C do B
ne = 4 . 3 . 2 . 1 = 24 … stejná cesta z B do A
36 + 24 = 60 … dohromady 60 cest
II.) Variace
K-členná variace z „n“ prvků (variace z n prvků k-té třídy) je uspořádaná k-tice, sestavená z těchto prvků tak, že každý se v ní vyskytuje nanejvýš jednou.
V (k, n) … počet všech k-členných variací z „n“ prvků
k < nebo = n
V (k, n) = n . (n – 1) . (n – 2) … (n – k +1)
Př. 5) Kolik různých trikolor lze vytvořit z těchto 4 barev: č, m , b , z?
a) variace 5 barev
b) variace 7 barev
V (3, 4) … variace třetí třídy ze čtyř prvků
V (3, 4) = 4 . 3 . 2 = 24
a) V (3, 5) = 5 . 4 . 3 = 60
b) V(3, 7) = 7 . 6 . 5 = 210
Př. 6) Kolika způsoby lze na šachovnici vybrat dvě políčka různé barvy tak, aby neležela v téže řadě ani sloupci? (8 . 8 = 64 políček)
32 . 24 = 768
Př. 7) Ke hradu vedou z místa výletu dvě různé turistické trasy a silnice po ní je možné jet autobusem, nebo jít pěšky. Určete počet způsobů, kterými je možné dostat se:
a) na hrad a zpět
b) na hrad a zpět tak, aby zpáteční cesta byla jiná
c) na hrad a zpět tak, aby se nejelo autobusem
d) aby se aspoň jednou jelo autobusem
e) tam autobusem a zpátky pěšky
f) tam pěšky a zpátky autobusem
g) tam autobusem, zpátky autobusem
a) 4 . 4 = 16
b) 4 . 3 = 12
c) 3 . 3 = 9
d) 3 + 3 + 1 = 7 (e + f + g) nebo (a – c) = 16 – 9 = 7
e) 1 . 3 = 3
f) 3 . 1 = 3
g) 1
Př. 8) Kolika způsoby lze sestavit šestihodinový rozvrh na jeden den pro třídu, v niž se vyučuje dvanácti předmětům (každý předmět nejvýš jedna hodina).
a) tv na 6. hodinu
b) tv na 1. hodinu a čj na 2. hodinu
c) není ani tv ani čj
a) V (5, 11) = 11 . 10 . 9 . 8 . 7 = 55 440
b) V (4, 10) = 10 . 9 . 8 . 7 = 5040
c) V (6, 10) = 10 . 9 . 8 . 7 . 6 . 5 = 151 200
Př. 9) Kolik trikolor lze vytvořit ze tří barev?
V (3, 3 ) = 6
Př. 10) Kolika způsoby lze polici v knihovně umístit do řady šest knih?
V (6, 6) = 6 . 5. . 4 . 3 . 2 . 1 = 720
Př. 11) Kolika způsoby může do cíle doběhnout pět závodníků?
V (5, 5) = 5 . 4 . 3 . 2 . 1 = 120
III.) Permutace
Permutace je zvláštní případ variace, kde k = n. To znamená, že ze zadaných prvků postupně vybereme všechny. Každá permutace tedy odpovídá nějakému pořadí zadaných prvků: každý prvek se v pořadí musí objevit, ale žádný tam nemůže být dvakrát.
Permutace z n prvků je každá n-členná variace z těchto prvků.
Permutace z n prvků je uspořádaná n-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje právě jednou.
Počet P(n) všech permutací z n prvků je: P(n) = n . (n − 1) . (n − 2) … 3 . 2 . 1
IV.) Faktoriál
Pro každé přirozené číslo n definujeme: n! = 1 . 2 . 3 … (n − 1) . n
symbol n! čteme "n faktoriál"
Počet P(n) všech permutací z n prvků můžeme pomocí faktoriálu zapsat takto: P(n) = n!
0! = 1
(n + 1)! = (n +1) . n!
Př. 12) 1! = 1
2! = 2 . 1 = 2
3! = 3 . 2 . 1 = 6
4! = 4 . 3 . 2 . 1 = 24
4! = 4 . 3!
5! = 5 . 4 . 3 . 2 . 1 = 120
5! = 5 . 4! = 5 . 4 . 3!
Př. 13) 6! / 3! = 6 . 5 . 4 . 3 . 2 . 1 / 3 . 2 . 1 = 120
7! / 5! = 7 . 6 = 42
Př. 14) Ve výboru klubu je 7 členů, kolika způsoby lze vybrat předsedu, místopředsedu, tajemníka, pokladníka?
V (4,7) = 7 . 6 . 5 . 4 = 840 způsobů
Kolika způsoby lze vybrat tak, aby:
a) naše Káča byla předsedkyně
V (3, 6) = 6 . 5 . 4 = 120 způsobů
b) Bíďa nebyl pokladníkem – (rozklad)
Bíďa je pokladníkem V(3,6) = 120 způsobů
840 – 120 = 720 způsobů
Př. 15) Rozsazení 10 lidí u stolu.
P (10, 10)
10! = 3 628 800 možností
V.) Vztahy mezi vedlejšími faktoriály
n! / (n + 1)!=n! /(n+1) . n!=1 / (n+1)
D = N0
(n + 1)! - n!= (n + 1) . n! - n! = n! . (n + 1 – 1) = n! . n
D = N0
Př. 16) 5! / 3! = 20
100! / 99! = 100
10! + 9! = 10 . 9! + 9! = 9! . (10 + 1) = 11 . 9!
Př. 17) Dvoukolového turnaje v pingpongu se účastnilo 20 hráčů, kolik bylo sehráno utkání? (každý s každým)
V (2, 20) = 380 utkání
b) Kolik účastníků měl turnaj, bylo-li sehráno 132 utkání?
V (2 , n) = n . (n – 1) = 132
D = 529
x = 12,-11
n = 12
Př. 18) Maturitní zkoušku bude konat ve stejný den 6 žáků:
a) určete počet všech možných pořadí?
b) všech pořadí, v nichž vystupuje E po F
c) všech pořadí, kdy Emilka jde ihned po Fanoušovi
d) kdy jdou za sebou
a) P (6) = 6! = 720
b) P (6) / 2 = 360 možností
c) 5! = 120 možností
d) 2 . 5! = 240 možností
Př. 19) Jsou dány čtyři různé tóny, kolik
a) znělek ze 3 různých tónů
b) akordů ze 3 různých tónů lze vytvořit
a) V(3,4)=24
b) K (3, 4)=24 / 6=V (3, 4) / 3! = 4
VI.) Kombinace
K-členná kombinace z „n“ prvků (kombinace z n prvků k-té třídy) je k-prvková podmnožina
n-prvkové množiny (nezávisí na pořadí).
K-členná kombinace z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou.
K (k, n) = V (k, n) / P (k) = n . (n – 1) … (n – k + 1) / k!
VII.) Kombinační číslo
Kombinační číslo je symbol, který označuje počet k-členných kombinací z n prvků.
(n nad k) … kombinační číslo
(n nad k) = n! / k! . (n – k)!
K (k, n) = (n nad k)
(n nad n) = 1, n náleží N0
Př. 20) Pět plechovek barev, kolika způsoby
a) lze vytvořit trikoloru
b) kolik odstínů barev můžu vytvořit slitím tří plechovek
a) V (3, 5) = 60
b) K (3, 5) = (5 nad 3) = 5! / 3! . 2! = 20 . 3! / 3! . 2 = 10 odstínů
Př. 21) Ve třídě je 7 žáků, kolika způsoby lze vybrat ke zkoušení 2 žáky?
V (2, 7) = 42 způsoby
K (2, 7) = (7 nad 2) = 7! / 5! . 2! = 7 . 6 . 5! /5! . 2 = 21
Př. 22) 10! + 9! = 10 . 9! + 9! = 9! (10 + 1) = 11 . 9!
Př. 23) (n + 2)! / (n – 1)! = (n + 2) (n + 1) . n . (n – 1)! / (n – 1)! = (n + 2) (n + 1) . n
Př. 24) V rovině leží 10 bodů, z nich žádné 3 neleží v přímce. Určete počet všech trojúhelníků, které mají v daných bodech vrcholy.
nezávisí na pořadí → kombinace
K (3, 10) = (10 nad 3) = 10! / 3! . 7! = 120
Př. 25) (4 nad 2) = 4 . 3 . 2! / 2! . 2! = 6
(4 nad 3) = 4 . 3! / 3! . 1! = 4
(4 nad 4) = 4! / 4! = 0! = 1
Př. 26) Na tělocviku je devět členů. Kolika způsoby lze nastoupit v řad?
a) Kolik let bychom museli chodit do školy, abychom se vystřídali?
P (9, 9) = 362 880 způsobů
a) 40 týdnů → 40 nástupů, 362 880 / 40 = 9072
Př. 27) Kolika způsoby lze rozpojit vlak o třinácti vagónech na tři části?
2 zlomové body, 12 spojů
(12 nad 2) = 12! / 2! . 10! = 66
Př. 28) Kolika různými způsoby lze vyplnit tiket sportky?
6 čísel z 49
K (6, 49) = (49 nad 6) = 49! / 6! . 43! = 13 983 816
Př. 29) Hokejový trenér má k dispozici 2 brankáře, 5 obránců, 10 útočníků. Kolika různými způsoby lze sestavit mužstvo? Hokejový tým má 1 brankáře, 2 obránce a 3 útočníky.
2 B: K (1, 2) = (2 nad 1) = 2
5 O: K (2, 5) = (5 nad 2)
10 Ú: K (3, 10) = (10 nad 3)
pravidlo kombinatorického součinu:
(2 nad 1) . (5 nad 2) . (10 nad 3) = 2400 způsobů
VIII.) Doplňková kombinace
(n nad k) = (n nad n – k); k je rovno nebo menší než n
(n nad k) + (n nad k + 1) = (n + 1 nad k + 1)
Př. 30) V užším výběru na zájezdu je 5 studentů. Kolika způsoby je možné vybrat.
a) 3 studenty
b) 2 studenty
c) 3 tak, aby Jaroušek určitě jel
d) 3 tak, aby Jarda určitě nejel
a) K (3, 5) = (5 nad 3) = 5! / 3! . 2! = 10
b) K (2, 5) = (5 nad 2) = 10
c) K (2, 4) = (4 nad 2) = 4! / 2! . 2! = 12 / 2 = 6
d) K (3, 4) = (4 nad 3) = 4 . 3! / 3! . 1! = 4
Př. 31) (5 nad 3) = (5 nad 2)
Př. 32) (4 nad 2) + (4 nad 3) = (5 nad 3)
