13 – Kombinatorika a pravděpodobnost
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Zdobínský Vojtěch, 4.E
Kombinatorika a pravděpodobnost
Definice kombinatoriky
:
• Kombinatorika je podobor matematiky zabývající se kolekcemi prvků množiny
• Nejčastěji řeší problémy týkající se počtu prvků objektu s definovanou strukturou
Základní kombinatorická pravidla:
1. Kombinatorické pravidlo součtu
Jsou-li
𝐴1; 𝐴2; … 𝐴𝑘 konečné množiny, které mají po řadě 𝑝1; 𝑝2; … 𝑝𝑘 prvků, a jsou-li
každé dvě disjunktní, pak počet všech prvků množiny 𝐴1 ∪ 𝐴2 ∪ … 𝐴𝑘 roven 𝑝1 +
𝑝2 + ⋯ + 𝑝𝑘.
2. Kombinatorické pravidlo součinu
Počet všech uspořádaných k-tic, jejichž první člen lze vybrat 𝑛1 způsoby, druhý člen
po výběru prvního členu 𝑛2 způsoby atd. až k-tý člen po výběru všech předcházejících
členů 𝑛𝑘 způsoby, je roven 𝑛1 × 𝑛2 × 𝑛3 × … 𝑛𝑘.
Faktoriál:
• Faktoriál je formálně definován jako součin všech celých kladných čísel menší než
dané celé kladné číslo 𝑛.
𝑛! = 1 × 2 × 3 × … 𝑛 = ∏ 𝑘
𝑛
𝑘=1
𝑛 ∈ 𝑁
• Rekurzivně lze faktoriál vyjádřit takto:
(𝑛 + 1)! = (𝑛 + 1) × 𝑛!
• V matematice je faktoriál čísla n (značeno 𝑛! – n faktoriál) číslo rovné součinu čísel
menších než celé kladné číslo n.
• Jedná se o velmi rychle rostoucí funkce
• Dvojitý faktoriál (𝑛‼) je takový faktoriál, ve kterém se činitelé snižují po 2 a ne po 1
• Multifaktoriál (𝑛!(𝑘)) je faktoriál, ve kterém se činitelé snižují po k
• Současné značení zavedl francouzský matematik Christian Kramp roku 1808
• Kromě kombinatoriky se faktoriál využívá i v rekurzivním programování
Příklad – faktoriál:
Zadání:
𝑛!×(𝑛+1)!
(𝑛−1)!×(𝑛+2)!
Řešení:
𝑛!×(𝑛+1)!
(𝑛−1)!×(𝑛+2)!
=
𝑛!×(𝑛−1)!×(𝑛+1)!
(𝑛−1)!×(𝑛+2)!
=
𝑛×(𝑛+1)!
(𝑛+2)!
=
𝑛×(𝑛+1)!
(𝑛+2)×(𝑛+1)!
=
𝑛
𝑛+2
Práce s kombinačními čísly:
• Pří počítání s kombinačními čísly si musíme jednotlivá čísla upravit
• K úpravě kombinačních čísel slouží tyto vzorce:
1. (
𝑛
𝑘
) =
𝑛!
𝑘!(𝑛−𝑘)!
2. (
𝑛
0
) = (
𝑛
𝑛
) = 1
3. (
𝑛
1
) = 𝑛
4. (
𝑛
𝑛 − 𝑘
) = (
𝑛
𝑘
)
5. (
𝑛
𝑘
) + (
𝑛
𝑘 + 1
) = (
𝑛 + 1
𝑘 + 1
)
Příklad – Úprava kombinačních čísel:
Zadání: Výraz (15
3
) + (
8
5
) − (
15
12
) upravte a převeďte na jedno kombinační číslo.
Řešení:
(
15
3
) + (
8
5
) − (
15
12
) = (
15
3
) + (
8
8 − 3
) − (
15
15 − 12
) = (
15
3
) − (
15
3
) + (
8
3
) = (
8
3
)
Výsledkem je výraz (8
3
), hodnota tohoto výrazu je 56.
Kombinatorické skupiny:
1. Kombinace bez opakování
• Kombinace je neuspořádaná k-tice sestavená z daných prvků
• Kombinace bez opakování je taková kombinace, ve které se každý prvek nachází
právě jednou
• 𝑘 je počet možností, n je počet prvků kombinace, 𝑘 a 𝑛 jsou celá čísla