IB112 Základy matematiky Základy kombinatoriky a kombinatorická pravděpodobnost Jan Strejček Obsah ■ Výběry prvků bez opakování m permutace a faktoriál ■ variace ■ kombinace a kombinační čísla ■ Výběry prvků s opakováním ■ permutace ■ variace ■ kombinace ■ Obecné principy počítání složených výběrů ■ princip nezávislých výběrů ■ princip dvojího počítání ■ Kombinatorická pravděpodobnost ■ konečný pravděpodobnostní prostor ■ nezávislost jevů a podmíněná pravděpodobnost ■ střední hodnota IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 2/57 Výběry prvků bez opakování IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost Permutace bez opakování Definice (Permutace bez opakování) Nechť M je konečná množina o n prvcích. Permutace množiny M je uspořádaná posloupnost všech prvků z M. Příklad ■ Vypište všechny permutace množiny {a, b, c, d}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 4/57 Permutace bez opakování Definice (Permutace bez opakování) Nechť M je konečná množina o n prvcích. Permutace množiny M je uspořádaná posloupnost všech prvků z M. Příklad ■ Vypište všechny permutace množiny {a, b, c, d}. a, b, c, d a, b, d, c a, c, b, d a, c, d, b a, d, b, c a, d, c, b {b, a, c, d (b, a, d, c (b, c, a, d (b, c, d, a (Ď, d, a, c (Ď, d, c, a c, a, Ď, d c, a, d, b c, Ď, a, d c, Ď, d, a c, d, a, Ď c, d, b, a (d, a, Ď, c (d, a, c, Ď (d, Ď, a, c (d, Ď, c, a (d, c, a, Ď (d, c, Ď, a IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 5/57 Permutace bez opakování Věta Počet všech permutací n-prvkové množiny je n\ = n • (n — 1) • (n — 2) •... • 2 • 1. ■ Funkce n\ se nazývá faktoriál. Klademe 0! = 1. Příklad ■ Kolika způsoby lze v ruce uspořádat 7 karet? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 6/57 Permutace bez opakování Věta Počet všech permutací n-prvkové množiny je n\ = n ■ {n - 1) • {n - 2) •... • 2 • 1. ■ Funkce n\ se nazývá faktoriál. Klademe 0! = 1. Příklad ■ Kolika způsoby lze v ruce uspořádat 7 karet? ■ Odpověď je 7! = 5040. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 7/57 Variace bez opakování Definice (Variace bez opakování) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo splňující k < n. k-prvkovou variací na množině M rozumíme uspořádanou k-tici sestavenou z prvků z M tak, že se v n í každý prvek vyskytuje nejvýše jednou. Příklad ■ Vypište všechny 2-prvkové variace na množině {a, b, c, d}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 8/57 Variace bez opakování Definice (Variace bez opakování) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo splňující k < n. k-prvkovou variací na množině M rozumíme uspořádanou k-tici sestavenou z prvků z M tak, že se v n í každý prvek vyskytuje nejvýše jednou. Příklad ■ Vypište všechny 2-prvkové variace na množině {a, b, c, d}. {a, b) {b, a) {c, a) {d, a) {a, c) (b, c) (c, b) (d, b) (a, cf) (b, d) (c, cf) (cf, c) IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 9/57 Variace bez opakování Počet všech k-prvkových variaci na množine s n prvky je n\ {n-k) = /7-(/7-1)-(/7-2)-...-(/7-/C+1) Permutace množiny s n prvky je totéž jako n-prvková variace. Na množině s n prvky je vždy stejně n-prvkových variací jako (n - 1 )-prvkových variací. (Proč?) Příklad ■ Kolik trojciferných čísel lze sestavit z číslic 1,2,..., 9, jestliže se žádné číslice neopakují? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 10/57 Variace bez opakování Počet všech k-prvkových variaci na množine s n prvky je n\ {n-k) = /7-(/7-1)-(/7-2)-...-(/7-/C+1) Permutace množiny s n prvky je totéž jako n-prvková variace. Na množině s n prvky je vždy stejně n-prvkových variací jako (n - 1 )-prvkových variací. (Proč?) Příklad ■ Kolik trojciferných čísel lze sestavit z číslic 1,2,. žádné číslice neopakují? 91 ■ Odpověď je — = 504. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost ,9, jestliže se 11/57 Kombinace bez opakování Definice (Kombinace bez opakování) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo splňující k < n. k-prvkovou kombinací na množině M rozumíme k-prvkovou podmnožinu množiny M. Příklad ■ Vypište všechny 2-prvkové kombinace na množině {a, b, c, d, e}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 12/57 Kombinace bez opakování Definice (Kombinace bez opakování) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo splňující k < n. k-prvkovou kombinací na množině M rozumíme k-prvkovou podmnožinu množiny M. Příklad ■ Vypište všechny 2-prvkové kombinace na množině {a, b, c, d, e}. {a,b} {b,c} {c,d} {d,e} {a, c} {b, d} {c, e} {a, d} {b, e} {a, e} IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 13/57 Kombinace bez opakování Počet všech k-prvkových kombinací na množine s n prvky je n k n\ {n-k)\ -k\ /7-(/7-1)-(/7-2)-...-(/7-/C+1) k\ ■ Čísla (£) se nazývají kombinační čísla nebo binomické koeficienty. ■ /c-prvková kombinace se někdy popisuje jako neuspořádaný výběr k prvků. Příklad ■ Kolika způsoby může dopadnout tah Sportky (6 čísel z 49)? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 14/57 Kombinace bez opakování Počet všech k-prvkových kombinací na množine s n prvky je n k n\ (n-k)\ k\ n-(A7-1)-(n-2)-...-(n-/f + 1) k\ ■ Čísla (£) se nazývají kombinační čísla nebo binomické koeficienty. ■ /c-prvková kombinace se někdy popisuje jako neuspořádaný výběr k prvků. Příklad ■ Kolika způsoby může dopadnout tah Sportky (6 čísel z 49)? J = 13983816. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 15/57 Odpověď je Výběry prvků s opakováním IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost Permutace s opakováním Definice (Permutace s opakováním) Nechť M je konečná množina. Permutace s opakováním je uspořádaná posloupnost prvků z M, v níž se každý prvek i e M vyskytuje k,-krát, kde k-, j předem dané. Příklad ■ Vypište všechny permutace s opakováním množiny {a, b} pro ka = 2 a kb = 3. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 17/57 Permutace s opakováním Definice (Permutace s opakováním) Nechť M je konečná množina. Permutace s opakováním je uspořádaná posloupnost prvků z M, v níž se každý prvek i e M vyskytuje k,-krát, kde k-, j předem dané. Příklad ■ Vypište všechny permutace s opakováním množiny {a, b} pro ka = 2 a kb = 3. (a, a, b, b, b) (b, a, b, a, b) (a, b, a, b, b) (b, a, b, b, a) (a, b, b, a, b) (b, b, a, a, b) (a, ď, ď, ď, a) (ď, ď, a, £>, a) (£>, a, a, ď, b) (b, b, b, a, a) IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 18/57 Permutace s opakováním Věta Počet permutací množiny {1,2,... , n} pro dané počty opakování k^,k2,...,kn> Oje + k2 + ... + kn)\ k-\! • k2! • . . . * /C/7! Příklad ■ Kolika způsoby lze navléct na provázek 30 červených, 10 modrých a 3 žluté korále? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 19/57 Permutace s opakováním Počet permutací množiny {1,2,..., n} pro dané počty opakování kuk2,...,kn >0je (fr +k2 + ... + kn)\ k-\! • k2\ •... • kn\ Příklad ■ Kolika způsoby lze navléci na provázek 30 červených, 10 modrých a 3 žluté korále? ■ Odpověď je = 10460 978576048. ^ 1 30!-10!-3! IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 20/57 Variace s opakováním Definice (Variace s opakováním) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo, k-prvkovou variací s opakováním na množině M rozumíme uspořádanou k-tici sestavenou z prvků z M tak, že se v n í každý prvek vyskytuje nejvýše k-krát. Příklad ■ Vypište všechny 4-prvkové variace s opakováním na množině {a, b}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 21/57 Variace s opakováním Definice (Variace s opakováním) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo, k-prvkovou variací s opakováním na množině M rozumíme uspořádanou k-tici sestavenou z prvků z M tak, že se v n í každý prvek vyskytuje nejvýše k-krát. Příklad ■ Vypište všechny 4-prvkové variace s opakováním na množině {a, b}. (a, a, a, a) (a, b, a, a) (b, a, a, a) (b, b, a, a) (a, a, a, b) (a, Ď, a, b) (b, a, a, Ď) (b, b, a, Ď) (a, a, Ď, a) (a, Ď, b, a) (Ď, a, Ď, a) (Ď, Ď, Ď, a) (a, a, Ď, Ď) (a, b, b, b) (b, a, b, b) (b, b, b, b) IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 22/57 Variace s opakováním Počet všech k-prvkových variací s opakováním na množině s n prvky je nk. Příklad ■ Kolik podmnožin má množina {1,2,3,..., 10}? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 23/57 Variace s opakováním Počet všech k-prvkových variací s opakováním na množině s n prvky je nk. Příklad ■ Kolik podmnožin má množina {1,2,3,..., 10}? ■ Odpověď je 210 = 1 024. ■ Podmnožinu lze kódovat jako uspořádanou 10-tici nul a jedniček (jedničky značí, které prvky jsou v podmnožině): {2,5,6} odpovídá (0,1,0,0,1,1,0,0,0,0) ■ Hledáme tedy všechny 10-prvkové variace s opakováním na množině {0,1}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 24/57 Kombinace s opakováním Definice (Kombinace s opakováním) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo, k-prvkovou kombinací s opakováním na množině M rozumíme neuspořádanou k-tici prvků z M, kde se každý prvek vyskytuje libovolněkrát. Příklad ■ Vypište všechny 2-prvkové kombinace s opakováním na množině {a, b, c, d, e}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 25/57 Kombinace s opakováním Definice (Kombinace s opakováním) Nechť M je konečná množina o n prvcích a k > 0 je přirozené číslo, k-prvkovou kombinací s opakováním na množině M rozumíme neuspořádanou k-tici prvků z M, kde se každý prvek vyskytuje libovolněkrát. Příklad ■ Vypište všechny 2-prvkové kombinace s opakováním na množině {a, b, c, d, e}. {a, a} {b7b} {c,c} {d,d} {e,e} {a,b} {b,c} {c,d} {d,e} {a,c} {o,d} {c,e} {a, d} {o, e} {a, e} IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 26/57 Kombinace s opakováním Počet všech k-prvkových kombinací na množine s n prvky je n + k-Jl k ■ /c-prvkovou kombinaci na množině {1,2,..., n} lze zakódovat do posloupnosti délky n + k tak, že prvky množiny napíšeme do řady a za každý prvek vložíme tolik znaků □, kolikrát je prvek obsažen v kombinaci. Např. kombinace {2,2,3} na množině {1,2,3,4} odpovídá posloupnosti 1 2 □ □ 3 □ 4. ■ Posloupnost je přesně určená umístěním znaků □. ■ Znak □ se nesmí vyskytnout na prvním místě. ■ k znaků □ se tedy vyskytuje na některých z n + k - 1 míst. ■ Posloupností (a tedy i kombinací) je celkem IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 27/57 Kombinace s opakováním Příklad ■ Kolika způsoby může dopadnout hod třemi hracími kostkami? (Zajímá nás, co kolikrát padne: např. dvě trojky a jedna pětka). IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 28/57 Kombinace s opakováním Příklad ■ Kolika způsoby může dopadnout hod třemi hracími kostkami? (Zajímá nás, co kolikrát padne: např. dvě trojky a jedna pětka). ■ Odpověď je r + g ~ 1J = 56. ■ Jedná se o 3-prvkové kombinace s opakováním nad množinou {1,2,3,4,5,6}. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 29/57 Obecné principy počítání složených výběrů IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 30/57 Princip nezávislých výběrů Princip nezávislých výběrů neboli princip součinu Pokud se výběr skládá z dvou či více vzájemně nezávislých podvýběrů, pak je celkový počet výběrů roven součinu počtů jednotlivých podvýběrů. Příklad ■ Hokejový trenér má k dispozici 13 útočníků, 9 obránců a 2 brankáře. Kolik kombinací hokejistů se může objevit na ledě, aby tam byli 3 útočníci, 2 obránci a jeden brankář? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 31/57 Princip nezávislých výběrů Princip nezávislých výběrů neboli princip součinu Pokud se výběr skládá z dvou či více vzájemně nezávislých podvýběrů, pak je celkový počet výběrů roven součinu počtů jednotlivých podvýběrů. Příklad ■ Hokejový trenér má k dispozici 13 útočníků, 9 obránců a 2 brankáře. Kolik kombinací hokejistů se může objevit na ledě, aby tam byli 3 útočníci, 2 obránci a jeden brankář? ■ Výběr útočníků: (133) = 286 ■ Výběr obránců: (ij) = 36 ■ Výběr brankářů: (*) = 2 ■ Odpověď je 286 • 36 • 2 = 20 592. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 32/57 Princip dvojího počítání Princip dvojího počítání Nechť lze každý výběr dále zjemnit na stejný počet / zjemněných výběrů. Dále nechť existuje celkem m různých zjemněných výběrů. Potom počet všech původních výběrů je ^. Příklad ■ Výběr šestic hokejistů na ledě z minulého příkladu chceme zjemnit tím, že budeme uvažovat i pořadí útočníků a obránců. ■ Každou kombinaci na ledě lze tedy zjemnit v 3! • 2! = 12 různých výběrů. ■ Celkem těchto uspořádaných výběrů existuje (13-12-11)-(9-8)-2 = 247104. 247104 ■ Původních výběrů je ——— = 20 592 (totéž vyšlo i minule). IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 33/57 Poznámky ■ Při řešení příkladů lze někdy použít i princip inkluze a exkluze. ■ Obecně je třeba používat selský rozum. Příklad ■ Máme k dispozici celkem 12 hráčů, z toho 5 dobrých útočníků. Kolik lze sestavit 4-členných týmů, které obsahují alespoň jednoho dobrého útočníka? ■ Celkem lze sestavit (142) = 495 týmů. ■ Týmů bez dobrého útočníka je (12^5) = 35. ■ Týmů s alespoň jedním dobrým útočníkem tedy je (1) ~ (V) = 460. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 34/57 Kombinatorická pravděpodobnost IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost Kombinatorická pravděpodobnost ■ Teorie pravděpodobnosti zkoumá tzv. náhodné pokusy. Náhodným pokusem rozumíme opakovatelnou činnost prováděnou za stejných podmínek, jejíž výsledek je nejistý a závisí na náhodě (zejména není určen počátečními podmínkami). ■ Kombinatorická (nebo také klasická) pravděpodobnost zkoumá situace, kdy náhodný pokus má jen konečně mnoho možných výsledků. ■ Pravděpodobnost daného výsledku pak udává míru jeho očekávatelnosti. ■ Motivace je např. v hazardních hrách. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 36/57 Konečný pravděpodobnostní prostor Definice (Konečný pravděpodobnostní prostor) Konečný pravděpodobnostní prostor je dvojice (íí, P),kde Q je konečná množina elementárních jevů a P : V (Q) -> [0,1] je funkce pravděpodobnosti, která podmnožinám Q přiřazuje reálné hodnoty z intervalu [0,1] a splňuje m P(0) = 0, P(Q) = 1 a ■ P (A uB) = P {A) + P(B) kdykoliv A, 8cQ jsou disjunktní Libovolná podmnožina A c Q se nazývá jev a P (A) je pravděpodobnost tohoto jevu. Příklad ■ Definujte pravděpodobnostní prostor hodů (poctivou) kostkou. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 37/57 Příklady konečných pravděpodobnostní prostorů Příklad ■ Pravděpodobnostní prostor hodů kostkou je (ft, P), kde ■ elementární jevy jsou "co padne", tedy Q = {1,2,3,4,5,6}, ■ funkce pravděpodobnosti P (A) = ^ pro každou AcQ. ■ Co je jev "padne sudé číslo"? Množina {2,4,6}. ■ Pravděpodobnost tohoto jevu je P({2,4,6}) = § = \. Příklad ■ Pravděpodobnostní prostor hodů mincí je ({orel, panna}, P), kde P(0) = 0 P({orel}) = \ P({orel, panna}) = 1 P({panna}) = \ IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 38/57 Poznámky ■ Pravděpodobnost elementárního jevu a e ft obvykle zapisujeme jako P(a) namísto P({a}). ■ Pravděpodobnostní prostor je plně určený množinou Q a pravděpodobnostmi elementárních jevů. Pro neelementární jev A = {a-i, a2,..., an} totiž podle definice musí platit P(/l) = P(a1) + P(a2) + ... + P(an). ■ Jevy A, B jsou disjunktní, pokud nemohou nastat zároveň, tj. pokud A n B = 0. ■ Různé elementární jevy jsou vždy disjunktní. ■ Udejte příklady dvou různých jevů, které nejsou disjunktní. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 39/57 Uniformní pravděpodobnostní prostor Definice Konečný pravděpodobnostní prostor (íí, P) je uniformní, je-li každý elementární jev a e Q stejně pravděpodobný, tj. P (a) = ■ Pro každý jev A v uniformním prostoru platí P(A) = -—-. ■ Uvedené prostory hodů kostkou a hodů mincí jsou uniformní. Příklad ■ Namíchání 32 karet je také uniformní pravděpodobnostní prostor, kde elementární jevy jsou permutace karet (těch je 32!). ■ Pravděpodobnost každého elementárního jevu je ■ Jaká je pravděpodobnost jevu, že první karta je eso? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 40/57 Příklad Definujte pravděpodobnostní prostor hodů dvěmi kostkami, kde zjišťujeme součet bodů. Jaká je pravděpodobnost, že padne 8? Řešení 1 ■ Elementární jevy jsou součty, tedy íí = {2,3,4,..., 12}. ■ Pravděpodobnost elementárních jevů se ale liší: ■ součet 2 lze získat pouze jako 1 +1, proto P(2) = ■ součet 3 lze získat jako 1 +2 nebo 2+1, proto P(2) = ^ = ^, ■ ostatní pravděpodobnosti spočítáme analogicky. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 41/57 Příklad Definujte pravděpodobnostní prostor hodů dvěmi kostkami, kde zjišťujeme součet bodů. Jaká je pravděpodobnost, že padne 8? Řešení 1 ■ Elementární jevy jsou součty, tedy íí = {2,3,4,..., 12}. ■ Pravděpodobnost elementárních jevů se ale liší: ■ součet 2 lze získat pouze jako 1 +1, proto P(2) = ■ součet 3 lze získat jako 1 +2 nebo 2+1, proto P(2) = ^ = ^, ■ ostatní pravděpodobnosti spočítáme analogicky. P(2) = ± P(5) = l P(8) = ^ P(11) = A P(3) = ^ P(6) = Í P(9) = i P(12) = i P(4) = ^ P(7) = l P(10) = ^ ■ Jev "padne 8" je tedy elementární s pravděpodobností ■ Pravděpodobnostní prostor není uniformní. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 42/57 Příklad Definujte pravděpodobnostní prostor hodů dvěmi kostkami, kde zjišťujeme součet bodů. Jaká je pravděpodobnost, že padne 8? Řešení 2 ■ Elementární jevy jsou dvojice hodnot na jednotlivých kostkách, tedy Q = {1,2,3,4,5,6} x {1,2,3,4,5,6}. ■ Pravděpodobnost každého elementárního jevu je ^. ■ Pravděpodobnostní prostor je uniformní. ■ Jak spočítáme pravděpodobnost, že padne 8? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 43/57 Definujte pravděpodobnostní prostor hodů dvěmi kostkami, kde zjišťujeme součet bodů. Jaká je pravděpodobnost, že padne 8? Řešení 2 ■ Elementární jevy jsou dvojice hodnot na jednotlivých kostkách, tedy Q = {1,2,3,4,5,6} x {1,2,3,4,5,6}. ■ Pravděpodobnost každého elementárního jevu je ^. ■ Pravděpodobnostní prostor je uniformní. ■ Jak spočítáme pravděpodobnost, že padne 8? ■ Jev "padne 8" \eA = {(2,6), (3,5), (4,4), (5,3), (6,2)} a jeho pravděpodobnost je P (A) = |0 = ^. ■ Toto řešení umožňuje odpovědět například na otázku, zda jsou disjunktní jevy "součet je 6" a "součin je 8". Jsou disjunktní? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 44/57 Nezávislé jevy ■ Nezávislost jevů intuitivně znamená, že pravděpodobnost toho, že nastane druhý z jevů není nijak ovlivněna tím, zda nastal či nenastal první jev. ■ Kupříkladu pokud hážeme dvěma kostkami, jsou jevy "na první kostce padne 6" a "na druhé kostce padne liché číslo" nezávislé. ■ Oproti tomu jevy "na první kostce padne 5" a "součet bude 8" nezávislé nejsou. Definice (Nezávislé jevy) Jevy A, B v prostoru (Q, P) jsou nezávislé, pokud platí P(AnB) = P{A)- P{B). IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 45/57 Příklad Ukážeme, že jevy "na první kostce padne 5" a "součet bude 8" jsou závislé. ■ Pravděpodobnostní prostor (Q, P) je tvaru Q = {1,2,3,4,5,6} x {1,2,3,4,5,6} a P(a) = ± pro každý elementární jev a e ft (prostor je uniformní). ■ Jev "na první kostce padne 5" je A = {(5,1), (5,2), (5,3), (5,4), (5,5), (5,6)} a P(A) = 1. ■ Jev "součet bude 8" je B = {(2,6), (3,5), (4,4), (5,3), (6,2)} a ■ Jevy A, B jsou závislé, neboť P(A n B) = P({5,3}) = ^ a tedy P(A n B) = -1- ž P(A) ■ P(B) = 1 • ^ = IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 46/57 Poznámky ■ Dva různé elementární jevy s nenulovou pravděpodobností jsou závislé, protože P({a} n {b}) = P(0) = 0 ^ P(a) • P(b). Navíc je jasné, že pokud nastane jeden elementární jev, nemůže nastat druhý. ■ Z analogickéhu důvodu platí, že dva různé disjunktní jevy s nenulovými pravděpodobnostmi jsou také závislé. Dotazy ■ Ze zamíchaných karet rozdáme dvěma hráčům po pěti kartách. Jsou výběry karet, které dostanou, nezávislé? ■ Hodíme dvěma kostkami. Je jev "na obou padne totéž" nezávislý s jevem "na první kostce padne 2"? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 47/57 Podmíněná pravděpodobnost Definice (Podmíněná pravděpodobnost) Podmíněná pravděpodobnost P(B\A) je pravděpodobnost jevu B za předpokladu, že nastal jev A a vypočítá se jako P(B\A\ - P{A 0 B) ■ Jevy A, B jsou nezávislé právě když P(B\A) = P(B). Příklad ■ Kolik je podmíněná pravděpodobnost jevu "při hodu dvěma kostkami padne součet aspoň 10" za předpokladu, že "na první kostce padlo 5"? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 48/57 Podmíněná pravděpodobnost Definice (Podmíněná pravděpodobnost) Podmíněná pravděpodobnost P(B\A) je pravděpodobnost jevu B za předpokladu, že nastal jev A a vypočítá se jako P(B\A\ - P{A 0 B) ■ Jevy A, B jsou nezávislé právě když P(B\A) = P(S). Příklad ■ Kolik je podmíněná pravděpodobnost jevu "při hodu dvěma kostkami padne součet aspoň 10" za předpokladu, že "na první kostce padlo 5"? ■ Odpověď je g. ■ Pravděpodobnost "padne součet aspoň 10" je g (závislost jevů). IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 49/57 Střední hodnota ■ X je náhodná proměnná (nebo náhodná veličina), pokud je její hodnota jednoznačně určena výsledkem náhodného pokusu. ■ Formálně je náhodná proměnná libovolná funkce přiřazující elementárním jevům prostoru (íí, P) reálná čísla. Definice (Střední hodnota) Nechť náhodná proměnná X může nabýt hodnot fy, h2l..., hn s pravděpodobností poradě p-i, p2,..., pn, kde p-i + p2 + ... + pn = 1 - Střední hodnotou proměnné X je číslo EX = p! • fy + p2 • h2 + ... + pn • hn. ■ Střední hodnota udává průměr získaných hodnot náhodné proměnné X při mnoha opakováních náhodného pokusu. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 50/57 Příklady Příklad ■ Jaká je střední hodnota čísel padlých na hrací kostce? IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 51/57 Příklad ■ Jaká je střední hodnota čísel padlých na hrací kostce? ■ Odpověď je 1 A i i i i i i A -•1+--2 + -- 3 + -- 4 + -- 5 + -- 6 = --21 6 6 6 6 6 6 6 IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost Příklady Příklad ■ Kolik je průměrně třeba hodů mincí, aby padlo 3x totéž? ■ 3x totéž padne nejdříve třetím a nejpozději pátým hodem. ■ Pravděpodobnostní postor je (o, o,p, p,p) (o,p, o, p,p) (o,p,p, o,p) (p, o, o, p, p) (p, o, p, o, p) (p, p, o, o, p) Náhodná proměnná X je vždy rovna délce n-tice. Pravděpodobnost každé n-tice je ^. Celkem dostáváme, že průměrný počet potřebných hodů je EX = 3-(24) + 4-(6~) + 5-(12~) = ? + ? + ^ =4,125. v 8J v 16y v 327 4 2 8 (0, 0, 0) (o, o, p, 0) {o,o,p,p,o) ( (p, p, p) (o,p, o, o) (o,p,o,p,o) ( (o,p,p, p) (o,p,p,o,o) ( (p, 0, 0, 0) (p, o, o, p, 0) ( (p, o, p, p) (p, o, p, o, o) ( (p, p, o, p) (p, p, 0, 0, 0) ( IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 53/57 Výpočet středních hodnot ■ Střední hodnota konstanty c je Ec = c. m Střední hodnota součinu náhodné proměnné X a konstanty c je E{cX) = c-EX. m Střední hodnota součtu náhodných proměnných X, Y je E(X +Y) = EX+ EY. Příklad ■ Jaká je střední hodnota součtu čísel padlých na dvou kostkách? ■ Odpověď je E(X + Y) = EX + EY = 3,5 + 3,5 = 7. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 54/57 Výpočet středních hodnot Střední hodnota součinu nezávislých náhodných proměnných X,Yje E{X ■ Y) = EX ■ EY. Příklad Jaká je střední hodnota součinu čísel padlých na dvou kostkách? Odpověď je E(X ■ Y) = EX ■ EY = 3,5 • 3,5 = 12,25. IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 55/57 Poznámka ■ Vztah pro střední hodnotu součinu pro závislé náhodné proměnné neplatí. Příklad ■ Jaká je střední hodnota součinu čísel horní a spodní stěny hozené kostky? ■ Protože náhodné proměnné jsou závislé (součet protilehlých stěn kostky je vždy 7), nelze použít vztah E(X • Y) = EX • EY (tento vztah by nám dal hodnotu 12,25). IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 56/57 Poznámka ■ Vztah pro střední hodnotu součinu pro závislé náhodné proměnné neplatí. Příklad ■ Jaká je střední hodnota součinu čísel horní a spodní stěny hozené kostky? ■ Protože náhodné proměnné jsou závislé (součet protilehlých stěn kostky je vždy 7), nelze použít vztah E(X • Y) = EX • EY (tento vztah by nám dal hodnotu 12,25). ■ Z definice spočítáme střední hodnotu součinu jako 1 .6-1 +2-5-1 + 3 '4' l+4 '3' l + 5'2' ^+6'1 'l = 9 + l-o o o o o o 3 IB112 Základy matematiky: Základy kombinatoriky a kombinatorická pravděpodobnost 57/57