KOMBINATORIKA
KOMBINATORIKA
Zkoumá skupiny (podmnožiny) prvků vybraných z jisté základní množiny. Podle toho, zda se prvky v jednotlivých skupinách mohou či nemohou opakovat, rozdělujeme skupiny prvků na skupiny s opakováním a skupiny bez opakování.
Poznámka
Skupiny, kde se prvky nemohou opakovat, si lze tedy představit tak, ze prvky, které vybíráme ze základní skupiny do ní nevracíme zpět a nemůžeme je tedy použít při dalším výběru. Naopak skupiny, kde se prvky mohou opakovat, vznikají tak, že vybrané prvky vracíme do základní skupiny a v dalším výběru je můžeme znovu použít.
MNOŽINY
množina
■ soubor prvků
■ prvky množiny
zápis
■M={1,2, 3}
■ M= {} nebo M=0
■ 1 eM; 5čM
FAKTORIÁL
taktonal asla n je roven součinu všech přirozených asel, která jsou menši nebo rovna číslu n.
Zápis - n!
Př. 5! = 5-4-3-2-1 = 120 0! = 1
KOMBINATORICKÉ PRAVIDLO SOUČTU
př. Máme 6 červených míčků a 8 modrých míčků. Kolik máme možností, když bud losovat jeden míček z osudí, kam dáme všechny míčky dohromady?
KOMBINATORICKÉ PRAVIDLO SOUČINU
př. Máme opět dvě množiny — množinu Z, v které jsou 3 ženy a množinu M, obsahující 4 muže. Kolik různých párů muž — žena můžeme vytvořit?
Žl	-Ml	12	-Ml	13	-Ml
Žl	-M2	12	-M2	13	-M2
Žl	-M3	12	-M3	13	-M3
Žl	-M4	12	-M4	13	-M4
4 + 4 + 4 = 12 resp. 3*4= 12 párů
Vynásobili jsme velikost obou množin.
KOMBINATORICKÉ PRAVIDLO SOUČINU
př. Kolik existuje různých dvojciferných čísel?
první pozice 1 - 9, druhá pozice 0-9 9 • 10 = 90 čísel
KOMBINATORICKÉ PRAVIDLO SOUČINU
př. Kolik existuje různých trojciferných čísel, kde se žádná číslice nesmí dvakrát?
první pozice 1 - 9
druhá pozice 0-9 bez čísla na první pozici
třetí pozice 0 — 9 bez čísel na první a druhé pozici
9 • 9 • 8 = 648 čísel
KOMBINATORICKÉ PRAVIDLO SOUČINU
Dvakrát za sebou hodíme klasickou hrací kostkou. Kolik různých výsledků můžeme získat?
_ _ - v prvním hodu 6 možností, v druhém hodu opět 6 možností
6 • 6 = 36 možností
Opět dva hody kostkou. Kolik různých výsledků můžeme získat, pokud nám v prvním hodu padlo sudé číslo?
_ _- v prvním hodu 3 možnosti, v druhém 6 možností
3*6 = 18 možností
VARIACE
variace /c-té třídy z n prvků
z nějaké množiny objektů vybíráme určitý počet objektů, přičemž záleží na poradí, jakém tyto objekty vybíráme
VARIACE-PŘÍKLAD A ODVOZENÍ
Soutěž v pojídání knedlíků. Do finále postoupilo 7 účastníků. Kolik existuje možností, jak těchto sedm účastníků může obsadit první tři místa?
první pozice — 7 možností, druhá pozice — 6 možností, třetí pozice — 5 možností 7 • 6 • 5 = 21 0 možností
obecně první pozice — n možností, druhá pozice — (n — 1) možností, třetí pozice (n 2) možností
n • (n - 1) • (n - 2) • ... • (n -k + 1)
VARIACE-VZOREC
V(k,n)
{n-k)\
VARIACE
Zůstaňme u závodů v pojídání knedlíků. Jak se změní počet medailových umístění, jestliže na závod přijel favorit, který vždy zvítězí?
první místo favorit, druhé místo 6 možností, třetí místo 5 možností
6'
V(2,6) =-— = 30
(6-2)!
VARIACE
Jak se změní počet možností, jestliže víme, že zmíněný favorit vždy obsadí medailové umístění?
3-V(2,6) = 3--— = 3-30 = 90
(6-2)!
VARIACE S OPAKOVANÍM
Kolik existuje trojciferných čísel, které lze zapsat pomocí cifer {1, 2, 3, 4, 5}?
cifry se mohou opakovat — první pozice — 5 možností, druhá pozice — 5 možností, třetí pozice — 5 možností
V'3 (5) = 5 • 5 • 5 = 53 = 125 čísel
w w
VARIACE S OPAKOVANÍM-VZOREC
V; (n) = n
k
VARIACE S OPAKOVANÍM
Kolik různých značek teoreticky existuje v Morseove abecedě, sestavují-li se tečky a čárky do skupin po jedné až pěti?
Variace s opakováním, n = 2, k = 1, 2, 3, 4, 5
V'1(2) + V'2(2) + V'3(2) + V'4(2) + V'5(2) = 21 + 22 + 23 + 24 + 25 = = 2 + 4 + 8+16 + 32 = 62 značek
PERMUTACE
uspořádaná n-tice vybraná z n prvků
příklad — kolik trojciferných čísel dokážeme sestavit z čísel {1, 2, 3, 4, 5}?
" tr°iciferná y(3,5) = = - J!_ = 60
(n-k)l (5-3)!
■ pěticiferná y(5 5) =    nl    =    51    = - = 5!= 120
(n-k)\   (5-5)! 0!
výsledek je tedy roven 5!
P(n) = nl
PERMUTACE -
Máme 6 knih a chceme je uložit na poličku v nějakém pořadí. Kolik celkem různých pořadí existuje?
P(6) = 6! = 720
720 různých pořadí uložení knih
43
PERMUTACE -
K našim šesti knihám psaných českým jazykem přidejme další čtyři knihy psané latinou. Kolik existuje různých způsobů uložení těchto 1 0 knih na poličku, pokud chceme mít všechny české knihy a všechny latinské knihy pohromadě?
české knihy — 6!, latinské knihy — 4! 6! -4! = 17 280 způsobů latinské a pak české 17 280 • 2
Celkem tedy je 34 560 různých způsobů.
43
PERMUTACE S OPAKOVÁNÍM
Kolik různých šesticiferných čísel lze vytvořit z číslic 1, 2, 2, 3, 3, 3?
P\n) = - H-
**^^2 ****** *
Jestliže se mezi n prvky vyskytuje:
první prvek    krát T>'(f\\ —
druhv nrvek n~ krát W/
druhý prvek n2 krát 1   Vw/ ^
• • •
/c-tý prvek nk krát
ni ~*~ n2    ••• ~*~ nk ~ n
Zjistěte, kolik různých pěticiferných čísel lze vytvořit použitím cifer 1, 2, 3, A, 5 (cifry se v čísle mohou opakovat).
Permutace bez opakování?
Permutace s opakováním?
Variace s opakováním? ■ k=n
V'5(5) = 55 = 3 125
43
vybíráme určitý počet objektů z nějaké množiny bez ohledu na pořadí typickým příkladem - losování Sportky kombinační číslo ^ ^
C(k,n) =
(n-k)\'k\
C5:D
KOMBINAČNÍ CISLO - ZÁKLADNI PRAVIDLA
n
\
V
n — k
lni
= 1
V osudí je 49 míčků, losuje se 6 míčků. Kolik různých možností můžeme vylosovat?
r49\
v6y
49!
49!
(49-6)!-6! 43!-6!
= 13983816
Existuje tedy 1 3 983 81 6 možností.
BTW pravděpodobnost výhry je 1:13 983 816, tedy cca 0,00000715 %. ©
C5:D
43
Na „tour de pub" máme na výběr ze 1 3 hospůdek. Stihnout ale můžeme pouze 4. Kolik různých čtveřic hospůdek můžeme navštívit?
í13l
v4,
13! 9!4!
= 715
Máme 715 možností různých čtveřic hospůdek.
C5:D
43
Máme skupinu padesáti lidí — polovina muži a polovina ženy. Kolik existuje různých trojic lidí, pokud nesmí být složeny pouze z jednoho pohlaví (tj. v trojici se nesmí vyskytnout jen tři muži nebo jen tři ženy).
2-
f 25
v2y
r 25
=15000
C5:D
43
KOMBINACE S OPAKOVÁNÍM
Cl (n) =
( n + k-
k
Ve škole je celkem 20 učitelů. Je třeba sestavit komisi pro maturity v tomto složení: jeden předseda, jeden hodný přísedící a jeden zlý přísedící. Kolik existuje celkem možností?
Variace
20'
V(3,20) = — = 6840 17!
3215
PŘÍKLADY
Kolik trojciferných čísel můžeme poskládat z číslic {0, 1, 2, 3, A, 5}, pokud se žádná číslice nesmí opakovat?
V (3,6) = - = 120
3!
Musíme odečíst ty variace, které mají na prvním místě nulu. 0__z čísel 1, 2, 3, 4, 5
V (2,5) = - = 20
3!
Celkový počet je tedy 1 20 - 20 = 100 možností.
PŘÍKLADY
Kolik různých tříciferných čísel dokážeme sestavit z číslic {1, 2, 3, 4, 5}, pokud se žádná číslice nesmí opakovat a výsledné číslo má být liché?
V(3,5) = - = 60 2!
Každá číslice se může vyskytovat na poslední pozici stejně často, takže pokud máme 5 číslic, každá se bude na posledním místě vyskytovat
(60 : 5 = ) 1 2 krát.
1 na konci — 1 2x, 3 na konci — 1 2x, 5 na konci — 1 2x 36 možností
PŘÍKLADY
S připomínkami k navrhovanému zákonu chce v parlamentu vystoupit šest poslanců (A, B, C, D, E, F). Určitě počet:
a) všech možných pořadí jejich vystoupení
b) všech pořadí, v nichž vystupuje A po E
c) všech pořadí, v nichž vystupuje A ihned po E
PŘÍKLADY
K sestavení vlajky, která má být složena ze tří různobarevných vodorovných prvků, jsou k dispozici barvy bílá, červená, modrá, zelená a žlutá. Urči:
a) počet vlajek, které můžeme z látek těchto barev sestavit
b) kolik z nich má modrý pruh
kolik jich má modrý pruh uprostřed d)   kolik jich nemá červený pruh uprostřed
Výbor sportovního klubu tvoří 6 mužů a 4 ženy. Urči:
a) kolika způsoby z nich lze vybrat předsedu, místopředsedu, jednatele a hospodáře
b) kolika způsoby z nich lze vybrat funkcionáře podle a) tak, aby ve funkci předsedy byl muž a ve funkci místopředsedy žena nebo obráceně
kolika způsoby z nich lze vybrat funkcionáře podle a) tak, aby právě jedním z nich byla žena
43
Státní poznávací značka v nějakém státě je tvořena uspořádanou sedmicí, jejíž první tři členy jsou písmena vybíraná z 28 písmen a další 4 číslice. Urči, kolik poznávacích značek je ve státě k dispozici.
V'3(28)-V'4(10) = 283-104 = 219 520 000
Mají k dispozici 219 520 000 značek
43
Kolik různých SPZ ve tvaru OSB XX-XX existuje s alespoň dvěma trojkami?
43
PRÍKLADY
Urči počet všech přirozených čísel menších než 1 000 000, která lze zapsat dekadicky pouze užitím čísel 5 a 8.
V sáčku jsou červené, modré a zelené kuličky. Kuličky téže barvy jsou nerozlišitelné. Urči, kolika způsoby lze vybrat 5 kuliček, jestliže v sáčku je:
a) alespoň 5 kuliček od každé barvy
b) 5 červených, 4 modré, 4 zelené
3215
PŘÍKLADY
Urči, kolika způsoby je možno ze 7 mužů a 4 žen vybrat šestičlennou skupinu, v níž jsou:
a) právě dvě ženy
b) alespoň dvě ženy
PRÍKLADY
Urči, kolika způsoby lze sestavit rozvrh na jeden den pro třídu, v níž se vyučuje 1 2 předmětů. Každý předmět má být nejvýše jednou denně a třída má mít 6 předmětů za den.
V kolika z nich se vyskytuje matematika?
V kolika z nich je zařazena matematika na 1. vyučovací hodinu?
PRÍKLADY
Hokejové družstvo má 20 hráčů: 1 3 útočníků, 5 obránců a 2 brankáře. Urči, kolik sestav by mohl trenér vytvořit, jestliže sestava má mít 3 útočníky, 2 obránce a 1 brankáře.
PRÍKLADY
O telefonním čísle svého spolužáka si Petr zapamatoval jen to, že je šestimístné, začíná sedmičkou, neobsahuje žádné dvě stejné číslice a je dělitelné 25. Urči, kolik telefonních čísel přichází v úvahu.
7___2 5
7 5 0
2-V3(7)
V úvahu přichází 420 telefonních čísel.
PRÍKLADY
Jméno a příjmení každého člověka bydlícího v městečku s 1 500 obyvateli může začínat jedním ze 32 písmen. Dokaž, že alespoň dva obyvatelé městečka mají stejné iniciály.
V'2(32) = 322 = 1 024
Počet možných iniciál je 1 024, což je více než polovina počtu obyvatel. Zbývajících 476 obyvatel tedy musí mít stejné iniciály jako některý z těchto 1 024 obyvatel.
PRÍKLADY
Kufřík má kódový zámek, který se otevře, když na každém z pěti kotoučů nastavíme správnou číslici. Na kazdem kotouči je V cishc. urči nejvetsi možný počet pokusu, které je nutno provést, chceme-li kufřík otevřít po zapomenutí kódu.
V'5(9) = 95 = 59 049
Největší možný počet pokusů je 59 049.
PŘÍKLADY
Urči počet způsobů, jimiž lze umístit všechny bílé šachové figurky (král, dáma, 2 věže, 2 jezdci, 2 střelci, 8 pěšců):
a) na dvě pevně zvolené řady šachovnice (8x8 polí)
b) na libovolné dvě řady šachovnice