Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Matematika I – 2. přednáška Masarykova univerzita Fakulta informatiky 27. 2. 2012 Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Obsah přednášky 1 Kombinatorika – pokračování Permutace, kombinace a variace Permutace, kombinace a variace s opakováním 2 Diferenční rovnice 3 Pravděpodobnost Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Plán přednášky 1 Kombinatorika – pokračování Permutace, kombinace a variace Permutace, kombinace a variace s opakováním 2 Diferenční rovnice 3 Pravděpodobnost Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Permutace Z množiny n předmětů vytváříme pořadí jejich prvků. Pro volbu prvního prvku je n možností, další je volen z n − 1 možností atd., až nám nakonec zbude jediný poslední prvek. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Permutace Z množiny n předmětů vytváříme pořadí jejich prvků. Pro volbu prvního prvku je n možností, další je volen z n − 1 možností atd., až nám nakonec zbude jediný poslední prvek. Proto je na dané konečné množině S s n prvky právě n! různých pořadí. Hovoříme o permutacích prvků množiny S. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Permutace Z množiny n předmětů vytváříme pořadí jejich prvků. Pro volbu prvního prvku je n možností, další je volen z n − 1 možností atd., až nám nakonec zbude jediný poslední prvek. Proto je na dané konečné množině S s n prvky právě n! různých pořadí. Hovoříme o permutacích prvků množiny S. Jestliže si předem prvky v S očíslujeme, tj. ztotožníme si S s množinou S = {1, . . . , n} n přirozených čísel, pak permutace odpovídají možným pořadím čísel od jedné do n. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Permutace Z množiny n předmětů vytváříme pořadí jejich prvků. Pro volbu prvního prvku je n možností, další je volen z n − 1 možností atd., až nám nakonec zbude jediný poslední prvek. Proto je na dané konečné množině S s n prvky právě n! různých pořadí. Hovoříme o permutacích prvků množiny S. Jestliže si předem prvky v S očíslujeme, tj. ztotožníme si S s množinou S = {1, . . . , n} n přirozených čísel, pak permutace odpovídají možným pořadím čísel od jedné do n. Dokázali jsme tak: Počet různých pořadí na konečné množině s n prvky je dán funkcí faktoriál: f (n) = n! Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Kombinace Dalším jednoduchým příkladem hodnoty určené formulí je počet způsobů, kterými lze vybrat k různých rozlišitelných předmětů z množiny n předmětů. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Kombinace Dalším jednoduchým příkladem hodnoty určené formulí je počet způsobů, kterými lze vybrat k různých rozlišitelných předmětů z množiny n předmětů. Zjevně máme n(n − 1) · · · (n − k + 1) možných výsledků postupného výběru našich k prvků, přitom ale stejnou výslednou k-tici dostaneme v k! různých pořadích. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Kombinace Dalším jednoduchým příkladem hodnoty určené formulí je počet způsobů, kterými lze vybrat k různých rozlišitelných předmětů z množiny n předmětů. Zjevně máme n(n − 1) · · · (n − k + 1) možných výsledků postupného výběru našich k prvků, přitom ale stejnou výslednou k-tici dostaneme v k! různých pořadích. Dokázali jsme tedy: Pro počet kombinací k-tého stupně z n prvků platí (samozřejmě je k ≤ n) c(n, k) = n k = n(n − 1) . . . (n − k + 1) k(k − 1) . . . 1 = n! (n − k)!k! . Číslům c(n, k) říkáme binomická čísla. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pokud nám ale záleží i na pořadí vybrané k-tice prvků, hovoříme o variaci k-tého stupně. Jak jsme si již ověřili: Pro počet variací platí v(n, k) = n(n − 1) · · · (n − k + 1) pro všechny 0 ≤ k ≤ n (a nula jinak). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pokud nám ale záleží i na pořadí vybrané k-tice prvků, hovoříme o variaci k-tého stupně. Jak jsme si již ověřili: Pro počet variací platí v(n, k) = n(n − 1) · · · (n − k + 1) pro všechny 0 ≤ k ≤ n (a nula jinak). Binomická čísla dostala svůj název od tzv. binomického rozvoje: (a + b)n = n k=0 n k ak bn−k protože koeficient u mocniny akbn−k je roven právě počtu možností, jak vybrat k-tici z n závorek v součinu. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pokud nám ale záleží i na pořadí vybrané k-tice prvků, hovoříme o variaci k-tého stupně. Jak jsme si již ověřili: Pro počet variací platí v(n, k) = n(n − 1) · · · (n − k + 1) pro všechny 0 ≤ k ≤ n (a nula jinak). Binomická čísla dostala svůj název od tzv. binomického rozvoje: (a + b)n = n k=0 n k ak bn−k protože koeficient u mocniny akbn−k je roven právě počtu možností, jak vybrat k-tici z n závorek v součinu. Všimněme si, že pro odvození jsme potřebovali pouze distributivitu, komutativnost a asociativitu násobení a sčítání. Formule proto platí v každém komutativním okruhu. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jako ukázku, jak vypadá matematický důkaz si odvoďme několik jednoduchých tvrzení o kombinačních číslech. Definujme n k = 0, kdykoliv je buď k < 0 nebo k > n. Pro všechna přirozená čísla k a n platí 1 n k = n n−k 2 n+1 k+1 = n k + n k+1 3 n k=0 n k = 2n 4 n k=0 k n k = n2n−1. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pascalův trojúhelník Všechna kombinační čísla si můžeme sestavit do tzv. Pascalova trojúhelníku, kde každé číslo obdržíme jako součet dvou bezprostředně nad ním ležících sousedů: n = 0 : 0 1 0 n = 1 : 0 1 1 0 n = 2 : 0 1 2 1 0 n = 3 : 0 1 3 3 1 0 n = 4 : 0 1 4 6 4 1 0 n = 5 : 1 5 10 10 5 1 Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pascalův trojúhelník Všechna kombinační čísla si můžeme sestavit do tzv. Pascalova trojúhelníku, kde každé číslo obdržíme jako součet dvou bezprostředně nad ním ležících sousedů: n = 0 : 0 1 0 n = 1 : 0 1 1 0 n = 2 : 0 1 2 1 0 n = 3 : 0 1 3 3 1 0 n = 4 : 0 1 4 6 4 1 0 n = 5 : 1 5 10 10 5 1 V jednotlivých řádcích máme právě koeficienty u jednotlivých mocnin z binomického rozvoje, např. (a + b)5 = a5 + 5a4 b + 10a3 b2 + 10a2 b3 + 5ab4 + b5 . Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pořadí n prvků, z nichž mezi některými nerozlišujeme, nazýváme permutace s opakovaním. Nechť je mezi n danými prvky p1 prvků prvního druhu, p2 prvků druhého druhu, . . . , pk prvků k-tého druhu, p1 + p2 + · · · + pk = n, potom počet pořadí těchto prvků s opakováním budeme značit P(p1, . . . , pk). Zřejmě platí: P(p1, . . . , pk) = n! p1! · · · pk! . Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Volný výběr prvků z n možností, včetně pořadí, nazýváme variace k-tého stupně s opakováním, jejich počet budeme značit V (n, k). Předpokládáme, že stále máme pro výběr stejně možností, např. díky tomu, že vybrané prvky před dalším výběrem vracíme nebo třeba házíme pořád stejnou kostkou. Zřejmě platí: V (n, k) = nk . Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Pokud nás výběr zajímá bez zohlednění pořadí, hovoříme o kombinacích s opakováním a pro jejich počet píšeme C(n, k). Počet kombinací s opakováním k-té třídy z n prvků je pro všechny 0 ≤ k a 0 < n C(n, k) = n + k − 1 k . Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Plán přednášky 1 Kombinatorika – pokračování Permutace, kombinace a variace Permutace, kombinace a variace s opakováním 2 Diferenční rovnice 3 Pravděpodobnost Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost V předchozích odstavcích jsme viděli formule, které zadávaly hodnotu skalární funkce definované na přirozených číslech (faktoriál) nebo dvojicích čísel (binomická čísla) pomocí předcházejících hodnot. Tomu lze rozumět také tak, že místo hodnoty naší funkce zadáváme její změnu při odpovídající změně nezávislé proměnné. Např. n + 1 k + 1 − n k + 1 = n k říká, že rozdíl počtu možností, jak vybrat k + 1 prvků z n + 1 možností, je vyjádřitelný pomocí (možná již známé) hodnoty. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost V předchozích odstavcích jsme viděli formule, které zadávaly hodnotu skalární funkce definované na přirozených číslech (faktoriál) nebo dvojicích čísel (binomická čísla) pomocí předcházejících hodnot. Tomu lze rozumět také tak, že místo hodnoty naší funkce zadáváme její změnu při odpovídající změně nezávislé proměnné. Např. n + 1 k + 1 − n k + 1 = n k říká, že rozdíl počtu možností, jak vybrat k + 1 prvků z n + 1 možností, je vyjádřitelný pomocí (možná již známé) hodnoty. Takto se skutečně velice často postupuje při matematické formulaci modelů, které popisují reálné systémy v ekonomice, biologii apod. My si tu povšimneme jen nejednodušších případů a budeme se k této tématice postupně vracet. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Obecnou diferenční rovnicí prvního řádu rozumíme výraz f (n + 1) = F(n, f (n)), kde F je známá skalární funkce závislá na dvojicích přirozených čísel. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Obecnou diferenční rovnicí prvního řádu rozumíme výraz f (n + 1) = F(n, f (n)), kde F je známá skalární funkce závislá na dvojicích přirozených čísel. Je zřejmé, že takový vztah, spolu s volbou pro f (0), zadává jednoznačně celou nekonečnou posloupnost hodnot f (0), f (1), . . . , f (n), . . . . Jako příklad může sloužit definiční formule pro faktoriál, tj. n! = n · (n − 1)! Vidíme, že skutečně vztah pro f (n + 1) závisí na n i na hodnotě f (n). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost lineární diferenční rovnice Po konstantní závislosti je nejjednodušší f (n + 1) = a · f (n) + b, kde a, b ∈ N. Takovou rovnici umíme snadno řešit. Je-li b = 0, pak zjevně f (n) = an f (0). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost lineární diferenční rovnice Po konstantní závislosti je nejjednodušší f (n + 1) = a · f (n) + b, kde a, b ∈ N. Takovou rovnici umíme snadno řešit. Je-li b = 0, pak zjevně f (n) = an f (0). To je např. vztah pro tzv. Malthusiánský model populačního růstu, který vychází z představy, že za zvolený časový interval vzroste populace s konstantní úměrou a vůči předchozímu stavu. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost lineární diferenční rovnice Po konstantní závislosti je nejjednodušší f (n + 1) = a · f (n) + b, kde a, b ∈ N. Takovou rovnici umíme snadno řešit. Je-li b = 0, pak zjevně f (n) = an f (0). To je např. vztah pro tzv. Malthusiánský model populačního růstu, který vychází z představy, že za zvolený časový interval vzroste populace s konstantní úměrou a vůči předchozímu stavu. Rovnice s b nenulovým se objeví při úročení (ať už vkladu nebo půjčky – jde jen o znaménko . . . ) Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Obecně pro rovnice prvního řádu s proměnnými koeficienty platí Obecné řešení diferenční rovnice prvního řádu f (n + 1) = an · f (n) + bn s počáteční podmínkou f (0) = y0 je dáno vztahem f (n) = n−1 i=0 ai y0 + n−1 r=0 n−1 i=r+1 ai br . Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Obecné řešení lineární diferenční rovnice prvního řádu s konstantními koeficienty a = 1, b a počáteční podmínkou f (0) = y0 je f (n) = an y0 + 1 − an 1 − a b. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Obecné řešení lineární diferenční rovnice prvního řádu s konstantními koeficienty a = 1, b a počáteční podmínkou f (0) = y0 je f (n) = an y0 + 1 − an 1 − a b. formule dostáváme první sčítanec okamžitě. Pro vyčíslení součtu součinů v druhém si je třeba všimnout, že se jedná o výrazy (1 + a + · · · + an−1)b. Sečtením této geometrické řady (připomeňme, že 1 − an = (1 − a)(1 + a + · · · + an−1)) dostaneme právě požadovaný výsledek. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Uveďme si praktický příklad na řešení diferenčních rovnic prvního řádu: Example Mirek si chce koupit nové auto. Auto stojí 300 000 Kč. Mirek by chtěl auto koupit na měsíční splátky. Prodávající společnost mu nabízí půjčku na koupi auta s ročním úrokem 6%. Mirek bych chtěl auto splatit za tři roky. Jak vysoká bude měsíční splátka? Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Plán přednášky 1 Kombinatorika – pokračování Permutace, kombinace a variace Permutace, kombinace a variace s opakováním 2 Diferenční rovnice 3 Pravděpodobnost Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Viděli jsme už funkce, jejichž hodnoty byly dány formulí nebo popisem změny hodnoty v závislosti na změnách závislé proměnné. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Viděli jsme už funkce, jejichž hodnoty byly dány formulí nebo popisem změny hodnoty v závislosti na změnách závislé proměnné. Další obvyklý případ – sledované hodnoty jsou výsledkem nějaké nahodilosti a my se snažíme popsat s jakou pravděpodobností nastane ta či ona možnost. Nejbanálnější příklad: házení kostkou s šesti stranami s označeními 1, 2, 3, 4, 5, 6. Matematický model takového házení „poctivou“ kostkou předepisuje, že každá ze stran padá stejně často. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Viděli jsme už funkce, jejichž hodnoty byly dány formulí nebo popisem změny hodnoty v závislosti na změnách závislé proměnné. Další obvyklý případ – sledované hodnoty jsou výsledkem nějaké nahodilosti a my se snažíme popsat s jakou pravděpodobností nastane ta či ona možnost. Nejbanálnější příklad: házení kostkou s šesti stranami s označeními 1, 2, 3, 4, 5, 6. Matematický model takového házení „poctivou“ kostkou předepisuje, že každá ze stran padá stejně často. Pro konkrétní kostku je ale jisté, že skutečné relativní četnosti výsledků nebudou stejné. Z velikého počtu pokusů lze usoudit na relativní četnosti jednotlivých výsledků hodů a tyto ustanovit jako pravděpodobnosti v našem matematickém popisu. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Viděli jsme už funkce, jejichž hodnoty byly dány formulí nebo popisem změny hodnoty v závislosti na změnách závislé proměnné. Další obvyklý případ – sledované hodnoty jsou výsledkem nějaké nahodilosti a my se snažíme popsat s jakou pravděpodobností nastane ta či ona možnost. Nejbanálnější příklad: házení kostkou s šesti stranami s označeními 1, 2, 3, 4, 5, 6. Matematický model takového házení „poctivou“ kostkou předepisuje, že každá ze stran padá stejně často. Pro konkrétní kostku je ale jisté, že skutečné relativní četnosti výsledků nebudou stejné. Z velikého počtu pokusů lze usoudit na relativní četnosti jednotlivých výsledků hodů a tyto ustanovit jako pravděpodobnosti v našem matematickém popisu. Nicméně při sebevětším počtu pokusů nemůžeme vyloučit možnost, že se náhodou povedla velice nepravděpodobná kombinace výsledků a že se tím náš matematický model skutečnosti stal (pro tento konkrétní případ) nedobrým. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost V matematice pracujeme s abstraktním matematickým popisem pravděpodobnosti. To, do jaké míry je takový popis adekvátní pro konkrétní pokusy či jiný problém, je záležitostí mimo samotnou matematiku (ta ale umí pomoci). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost V matematice pracujeme s abstraktním matematickým popisem pravděpodobnosti. To, do jaké míry je takový popis adekvátní pro konkrétní pokusy či jiný problém, je záležitostí mimo samotnou matematiku (ta ale umí pomoci). Vrátíme se k tomuto tématu, ale až na konci čtvrtého semestru v matematické statistice! Jde o teorii umožňující posoudit, do jaké míry lze očekávat, že vybraný model je ve shodě s realitou. K jejímu studiu bude již potřebný dosti rozsáhlý matematický aparát. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Náhodné jevy) Budeme pracovat s neprázdnou pevně zvolenou množinou Ω všech možných výsledků, kterou nazýváme základní prostor. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Náhodné jevy) Budeme pracovat s neprázdnou pevně zvolenou množinou Ω všech možných výsledků, kterou nazýváme základní prostor. Pro jednoduchost bude pro nás Ω konečná množina s prvky ω1, . . . , ωn, představujícími jednotlivé možné výsledky. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Náhodné jevy) Budeme pracovat s neprázdnou pevně zvolenou množinou Ω všech možných výsledků, kterou nazýváme základní prostor. Pro jednoduchost bude pro nás Ω konečná množina s prvky ω1, . . . , ωn, představujícími jednotlivé možné výsledky. Každá podmnožina A ⊂ Ω představuje možný jev. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Náhodné jevy) Budeme pracovat s neprázdnou pevně zvolenou množinou Ω všech možných výsledků, kterou nazýváme základní prostor. Pro jednoduchost bude pro nás Ω konečná množina s prvky ω1, . . . , ωn, představujícími jednotlivé možné výsledky. Každá podmnožina A ⊂ Ω představuje možný jev. Systém podmnožin A základního prostoru se nazývá jevové pole, jestliže Ω ∈ A, tj. základní prostor, je jevem, je-li A, B ∈ A, pak A \ B ∈ A, tj. pro každé dva jevy je jevem i jejich množinový rozdíl, jsou-li A, B ∈ A, pak A ∪ B ∈ A, tj. pro každé dva jevy je jevem i jejich sjednocení. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jevové pole je tedy systém podmnožin (konečného) základního prostoru uzavřený na průniky, sjednocení a rozdíly. Jednotlivé množiny A ∈ A nazýváme náhodné jevy (vzhledem k A). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jevové pole je tedy systém podmnožin (konečného) základního prostoru uzavřený na průniky, sjednocení a rozdíly. Jednotlivé množiny A ∈ A nazýváme náhodné jevy (vzhledem k A). Komplement Ac = Ω \ A jevu A je jevem, který nazýváme opačný jev k jevu A. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jevové pole je tedy systém podmnožin (konečného) základního prostoru uzavřený na průniky, sjednocení a rozdíly. Jednotlivé množiny A ∈ A nazýváme náhodné jevy (vzhledem k A). Komplement Ac = Ω \ A jevu A je jevem, který nazýváme opačný jev k jevu A. Průnik dvou jevů opět jevem, protože pro každé dvě podmnožiny A, B ⊂ Ω platí A \ (Ω \ B) = A ∩ B. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jevové pole je tedy systém podmnožin (konečného) základního prostoru uzavřený na průniky, sjednocení a rozdíly. Jednotlivé množiny A ∈ A nazýváme náhodné jevy (vzhledem k A). Komplement Ac = Ω \ A jevu A je jevem, který nazýváme opačný jev k jevu A. Průnik dvou jevů opět jevem, protože pro každé dvě podmnožiny A, B ⊂ Ω platí A \ (Ω \ B) = A ∩ B. Pro naše házení kostkou je Ω = {1, 2, 3, 4, 5, 6} a jevové pole je tvořeno všemi podmnožinami. Např. náhodný jev {1, 3, 5} pak interpretujeme jako „padne liché číslo“. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Terminologie připomíná souvislosti s popisem skutečných modelů: celý základní prostor Ω se nazývá jistý jev, prázdná podmnožina ∅ ∈ A se nazývá nemožný jev, Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Terminologie připomíná souvislosti s popisem skutečných modelů: celý základní prostor Ω se nazývá jistý jev, prázdná podmnožina ∅ ∈ A se nazývá nemožný jev, jednoprvkové podmnožiny {ω} ∈ Ω se nazývají elementární jevy, Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Terminologie připomíná souvislosti s popisem skutečných modelů: celý základní prostor Ω se nazývá jistý jev, prázdná podmnožina ∅ ∈ A se nazývá nemožný jev, jednoprvkové podmnožiny {ω} ∈ Ω se nazývají elementární jevy, společné nastoupení jevů Ai , i ∈ I, odpovídá jevu ∩i∈I Ai , nastoupení alespoň jednoho z jevů Ai , i ∈ I, odpovídá jevu ∪i∈I Ai , Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Terminologie připomíná souvislosti s popisem skutečných modelů: celý základní prostor Ω se nazývá jistý jev, prázdná podmnožina ∅ ∈ A se nazývá nemožný jev, jednoprvkové podmnožiny {ω} ∈ Ω se nazývají elementární jevy, společné nastoupení jevů Ai , i ∈ I, odpovídá jevu ∩i∈I Ai , nastoupení alespoň jednoho z jevů Ai , i ∈ I, odpovídá jevu ∪i∈I Ai , A, B ∈ A jsou neslučitelné jevy, je-li A ∩ B = ∅, Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Terminologie připomíná souvislosti s popisem skutečných modelů: celý základní prostor Ω se nazývá jistý jev, prázdná podmnožina ∅ ∈ A se nazývá nemožný jev, jednoprvkové podmnožiny {ω} ∈ Ω se nazývají elementární jevy, společné nastoupení jevů Ai , i ∈ I, odpovídá jevu ∩i∈I Ai , nastoupení alespoň jednoho z jevů Ai , i ∈ I, odpovídá jevu ∪i∈I Ai , A, B ∈ A jsou neslučitelné jevy, je-li A ∩ B = ∅, jev A má za důsledek jev B, když A ⊂ B, Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Terminologie připomíná souvislosti s popisem skutečných modelů: celý základní prostor Ω se nazývá jistý jev, prázdná podmnožina ∅ ∈ A se nazývá nemožný jev, jednoprvkové podmnožiny {ω} ∈ Ω se nazývají elementární jevy, společné nastoupení jevů Ai , i ∈ I, odpovídá jevu ∩i∈I Ai , nastoupení alespoň jednoho z jevů Ai , i ∈ I, odpovídá jevu ∪i∈I Ai , A, B ∈ A jsou neslučitelné jevy, je-li A ∩ B = ∅, jev A má za důsledek jev B, když A ⊂ B, je-li A ∈ A, pak se jev B = Ω \ A nazývá opačný jev k jevu A, píšeme B = Ac. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Pravděpodobnost) Pravděpodobnostní prostor je jevové pole A podmnožin (konečného) základního prostoru Ω, na kterém je definována skalární funkce P : A → R s následujícími vlastnosti: je nezáporná, tj. P(A) ≥ 0 pro všechny jevy A, je aditivní, tj. P(A ∪ B) = P(A) + P(B), kdykoliv je A ∩ B = ∅ a A, B ∈ A, pravděpodobnost jistého jevu je 1. Funkci P nazýváme pravděpodobností na jevovém poli (Ω, A). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Pravděpodobnost) Pravděpodobnostní prostor je jevové pole A podmnožin (konečného) základního prostoru Ω, na kterém je definována skalární funkce P : A → R s následujícími vlastnosti: je nezáporná, tj. P(A) ≥ 0 pro všechny jevy A, je aditivní, tj. P(A ∪ B) = P(A) + P(B), kdykoliv je A ∩ B = ∅ a A, B ∈ A, pravděpodobnost jistého jevu je 1. Funkci P nazýváme pravděpodobností na jevovém poli (Ω, A). Důsledky Pro všechny jevy platí P(Ac) = 1 − P(A). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Pravděpodobnost) Pravděpodobnostní prostor je jevové pole A podmnožin (konečného) základního prostoru Ω, na kterém je definována skalární funkce P : A → R s následujícími vlastnosti: je nezáporná, tj. P(A) ≥ 0 pro všechny jevy A, je aditivní, tj. P(A ∪ B) = P(A) + P(B), kdykoliv je A ∩ B = ∅ a A, B ∈ A, pravděpodobnost jistého jevu je 1. Funkci P nazýváme pravděpodobností na jevovém poli (Ω, A). Důsledky Pro všechny jevy platí P(Ac) = 1 − P(A). Additivnost platí pro jakýkoliv konečný počet neslučitelných jevů Ai ⊂ Ω, i ∈ I, tj. P(∪i∈I Ai ) = i∈I P(Ai ), kdykoliv je Ai ∩ Aj = ∅, i = j, i, j ∈ I. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Definition (Klasická konečná pravděpodobnost) Nechť Ω je konečný základní prostor a nechť jevové pole A je právě systém všech podmnožin v Ω. Klasická pravděpodobnost je takový pravděpodobnostní prostor (Ω, A, P) s pravděpodobnostní funkcí P : A → R, P(A) = |A| |Ω| . Zjevně takto zadaná funkce skutečně definuje pravděpodobnost. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jako příklad, jak z házení kostkou dostat různě pravděpodobné jevy, budeme pozorovat součty při hodu více kostkami. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jako příklad, jak z házení kostkou dostat různě pravděpodobné jevy, budeme pozorovat součty při hodu více kostkami. Uvažujme takto: při hodu jednou kostkou je každý výsledek stejně pravděpodobný s pravděpodobností 1 6 . Při hodu dvěmi kostkami je každý předem zvolený výsledek (a, b), tj. dvojice přirozených čísel od jedné do šesti (včetně pořadí), stejně pravděpodobný s pravděpodobností 1 36 . Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Jako příklad, jak z házení kostkou dostat různě pravděpodobné jevy, budeme pozorovat součty při hodu více kostkami. Uvažujme takto: při hodu jednou kostkou je každý výsledek stejně pravděpodobný s pravděpodobností 1 6 . Při hodu dvěmi kostkami je každý předem zvolený výsledek (a, b), tj. dvojice přirozených čísel od jedné do šesti (včetně pořadí), stejně pravděpodobný s pravděpodobností 1 36 . Pokud se budeme ptát po dvou pětkách, je tedy pravděpodobnost poloviční než u dvou různých hodnot bez uvedení pořadí. Pro jednotlivé možné součty uvedené v horním řádku nám vychází počet možností v řádku dolním: 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 5 4 3 2 1 Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Následující věta je promítnutím tzv. kombinatorického principu inkluze a exkluze do naší konečné pravděpodobnosti: Theorem Buďte A1, . . . , Ak ∈ A libovolné jevy na základním prostoru Ω s jevovým polem A. Pak platí P(∪k i=1Ai ) = k i=1 P(Ai ) − k−1 i=1 k j=i+1 P(Ai ∩ Aj ) + k−2 i=1 k−1 j=i+1 k =j+1 P(Ai ∩ Aj ∩ A ) − · · · + (−1)k−1 P(A1 ∩ A2 ∩ · · · ∩ Ak). Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Následující věta je promítnutím tzv. kombinatorického principu inkluze a exkluze do naší konečné pravděpodobnosti: Theorem Buďte A1, . . . , Ak ∈ A libovolné jevy na základním prostoru Ω s jevovým polem A. Pak platí P(∪k i=1Ai ) = k i=1 P(Ai ) − k−1 i=1 k j=i+1 P(Ai ∩ Aj ) + k−2 i=1 k−1 j=i+1 k =j+1 P(Ai ∩ Aj ∩ A ) − · · · + (−1)k−1 P(A1 ∩ A2 ∩ · · · ∩ Ak). Jde o dobrý příklad matematického tvrzení, kde nejtěžší je najít dobrou formulaci a pak se dá říci, že (intuitivně) je tvrzení zřejmé. Kombinatorika – pokračování Diferenční rovnice Pravděpodobnost Princip inkluze a exkluse Speciálním případem předchozí věty je situace, kdy všechny konečné podmnožniny základního prostoru jsou jevy a všechny elementární jevy mají stejnou pravděpodobnost. Ve formuli z předchozí věty pak všechny pravděpodobnosti dávají právě počet prvků příslušných podmnožin, až na společný faktor 1 n , kde n je počet prvků základního prostoru. Pak můžeme vyčíst následující tvrzení pro obecnou konečnou množinu M a její podmnožiny A1, . . . , Ak. Budeme psát |M| pro počet prvků množiny M, tj. pro mohutnost množiny M. |M \ (∪k i=1Ai )| = |M| + k j=1 (−1)i 1≤i1<···