1. přednáška KOMBINATORIKA Kombinatorika je obor matematiky, který se zabývá uspořádáním daných prvků podle určitých pravidel do určitých skupin. Základním pojmem v kombinatorice je pojem (k-prvková) skupina, nebo také k-tice prvků, kde k je přirozené číslo.
Věta (pravidlo součinu): Počet všech uspořádaných k-tic (dvojic, trojic,...), jejichž první člen lze vybrat n1 způsoby, druhý člen po výběru prvního členu n2 způsoby atd. až k-tý člen po výběru všech předcházejících členů nk způsoby, je roven n1 × n 2 × ... × n k .
Příklad: Při cestě z Ostravy do Tábora (přes Prahu) lze použít tyto dopravní prostředky: Ostrava - Praha: autobus, vlak, letadlo, auto Praha - Tábor: autobus, vlak, auto. Kolika možnými způsoby se dostaneme z Ostravy do Tábora? Řešení:
Věta (pravidlo součtu): Mějme konečné množiny A1, A2, ... , Ak, které mají po řadě n1, n2, ..., nk prvků. Jsou-li každé dvě množiny navzájem disjunktní, tzn. neobsahují žádný společný prvek, pak počet prvků množiny A1 È A 2 È K A k je roven n1 + n2 + K nk . Příklad: Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou. Řešení:
Kombinatorika tedy zkoumá skupiny (podmnožiny) prvků vybraných z jisté základní množiny. Nejdříve si ujasníme s jakými výběry se v praxi můžeme setkat. Prvním kritériem je uspořádanost výběru:
1
Uspořádaný výběr (variace) - záleží na pořadí prvků Neuspořádaný výběr (kombinace) - nezáleží na pořadí prvků
Druhým kritériem je, zda se prvky po výběru do původní množiny vracejí či nikoliv. Podle toho výběry rozlišujeme na:
Výběry s opakováním - vybraný prvek se vrací do původní množiny Výběry bez opakování - vybraný prvek se nevrací do původní množiny
1) VARIACE bez opakování Definice: k-členná variace z n prvků ( 0 < k £ n ) je uspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše jednou. Značíme ji Vk (n) - variační číslo.
Věta : Počet variací Vk (n) je roven: Vk (n) = n × (n - 1) × (n - 2) × ... × (n - k + 1) =
n! . (n - k )!
Příklad: Členové správní rady hokejového klubu volí prezidenta, viceprezidenta a revizora účtů klubu. Určete, kolik existuje způsobů, jak mohou být tyto funkce obsazeny, víme-li, že členů rady je 8, do funkcí lze volit pouze členy správní rady a žádný člen nemůže zastávat více než jednu funkci. Řešení:
2
2) PERMUTACE bez opakování Permutace je zvláštní případ variace, kde k = n. To znamená, že ze zadaných prvků postupně vybereme všechny. Definice: Permutace z n prvků je uspořádaná n-tice sestavená tak, že každý prvek se v ní vyskytuje právě jednou. Značíme ji P (n) .
Věta : Počet permutací P (n) je roven: P ( n ) = Vn ( n) =
n! n! = = n!. (n - n)! 0!
Příklad: Kolika způsoby lze seřadit 8 sprinterů na startovní čáru? Řešení:
3) VARIACE s opakováním Definice: k-členná variace s opakováním z n prvků je uspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše k-krát. Značíme ji Vk¢ (n) . Věta : Počet variací s opakováním Vk¢ (n) je roven: Vk¢ (n) = n k .
Příklad: Určete, kolik čtyřciferných přirozených čísel lze sestavit z cifer 1,2,3 a kolik jich je menších než 3 000. Řešení:
3
4) PERMUTACE s opakováním
Definice: Permutace s opakováním je uspořádaná n-tice z k různých prvků, v níž se každý prvek ni -krát opakuje ( i = 1,..., k ). Značíme ji Pn¢1 ,...,nk .
Věta : Počet permutací s opakováním je roven: Pn¢1 ,...,nk =
n! . n1!×n 2 !×... × n k !
Příklad: Určete, kolika způsoby je možné srovnat do řady 2 šedé, 3 modré a 4 černé kostky. Řešení:
5) KOMBINACE bez opakování Definice: k-členná kombinace z n prvků ( 1 £ k £ n ) je neuspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše jednou. Značíme ji C k (n) - kombinační číslo.
Věta : Počet kombinací C k (n) je roven: ænö n! C k (n) = çç ÷÷ = . è k ø (n - k )!k!
ænö ænö ænö ænö æ n ö ÷÷ Platí: çç ÷÷ = çç ÷÷ = 1 , çç ÷÷ = n a çç ÷÷ = çç è0ø ènø è1ø èk ø èn - k ø
Příklad: Na výtah, do něhož můžou nastoupit nejvýše 2 osoby, čeká 6 osob. a) Kolik je možností, jak vybrat 2 osoby, kteří pojedou? b) Kolik je možností, jak vybrat 4 osoby, které nepojedou? Řešení:
4
6) KOMBINACE s opakováním Definice: k-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená tak, že každý prvek se v ní vyskytuje nejvýše k-krát. Značíme ji C k¢ (n) . Věta : Počet kombinací C k¢ (n) je roven: æ n + k - 1ö (n + k - 1)! ÷÷ = C k¢ (n) = çç . è k ø (n - 1)!k!
Příklad: V cukrárně prodávají čtyři druhy zákusků,.Kolika způsoby lze nakoupit 8 zákusků. Řešení:
5
