XSZD-01 Základy kombinatoriky a klasické pravděpodobnosti Jiří Fišer (Eva Fišerová) 12. února 2025 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 1/61 Obsah O Základní informace o kurzu Q Úvodní poznámky o pravděpodobnosti a statistice Q Kombinatorické pravidlo součinu a součtu, princip inkluze a exkluze O Skupiny bez opakování ► Variace ► Permutace Kombinace Q Skupiny s opakováním ► Variace ► Permutace ► Kombinace O Pravděpodobnost - jev a operace s jevy Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 Základní informace ke kurzu • Literatura ► Calda, E., Dupač, V. Matematika pro gymnázia - Kombinatorika, pravděpodobnost a statistika (5. vydání). Prometheus, Praha, 2008. ► Hindis, R., Hronová, S., Seger, J., Fischer, J. Statistika pro ekonomy. 8. vyd. Praha: Professional Publishing, 2007. 415 s. ISBN 978-80-869-4643-6 • Online zdroje ► Otipka, P, Šmajstrla, V. Pravděpodobnost a statistika. VŠB TU Ostrava. http://homel.vsb.cz/~oti73/cdpast1/ ► a mnoho dalších, včetně video-prezentací na YT • Zápočet: aktivní účast na cvičeních, průběžné domácí úkoly, test?, maximálně tři neomluvené absence. • Zkouška: ► písemný zkouškový test (praktické příklady a teoretické otázky), ústní dozkoušení, ► prokázat znalosti základní pojmů, orientaci v problematice a demonstrovat znalosti na příkladech. Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 3/61 Náhoda a pravděpodobnost Pokus = experiment, uskutečněný při přesném dodržení předepsaných podmínek • nenáhodný: 1 výsledek např. zahříváme-li vodu na 100 °C při atmosférickém tlaku 1015 hPa, nastane var • náhodný: 2 a více různých výsledků např. hod mincí; hod kostkou; volba otázky u maturity; střelba na terč; podání léku pacientovi Co je to pravděpodobnost? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 Náhoda a pravděpodobnost Pravděpodobnost = naděje, s jakou nastanou jevy, které nás zajímají • číslo mezi nulou a jedničkou • čím je hodnota blíže jedničce, tím vyšší je naděje, že daný jev nastane • popisuje náhodný pokus pomocí matematických (pravděpodobnostních) modelů Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 5/61 Zakladatelé moderní teorie pravděpodobnosti • Úlohy o pravděpodobnosti výhry v hazardních hrách (a) Blaise Pascal (1623-1662) (b) Pieae de Fermat (1601 -1665) Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 6/61 Hazardní hry v kostky • hod 1 kostkou: padne alespoň 1 šestka ve 4 hodech -> zisk • hod 2 kostkami: padne alespoň 1 dvojice šestek ve 24 hodech ztráta Chevalier de Mére (1607-1684) vl. jménem Antoine Gombaud Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 7/61 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledků jevu A počet všech možných výsledků V ^/ i i I I o J J \ I J J J J f pí^\ "j /c 0 17 H i d) 'ô/t 3 = 1/2 = 0.5 y J J Ky 4, bj vy / Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 8/61 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledku jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) Pi/K\ "1 /6 0 "17 pri = 1 /2 = 0,5 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 8/61 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledku jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) padne číslo 6: n/ a \ a i r* 17 ysledky (2, 4, 6) Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledku jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) ► padne číslo 6: 1 příznivý výsledek P{A) = 1/6 = 0,17 - 6) 1/2 0,5 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 8/61 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledku jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) ► padne číslo 6: 1 příznivý výsledek => P{A) = 1/6 = 0,17 ► padne sudé číslo: 3 příznivé výsledky (2, 4, 6) P (B) = 3/6 = 1/2 = 0,5 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledků jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) ► padne číslo 6: 1 příznivý výsledek P{A) = 1/6 = 0,17 ► padne sudé číslo: 3 příznivé výsledky (2, 4, 6) P(6) = 3/6 = 1/2 = 0,5 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 8/61 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledků jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) ► padne číslo 6: 1 příznivý výsledek P{A) = 1/6 = 0,17 ► padne sudé číslo: 3 příznivé výsledky (2, 4, 6) ^ P(6) = 3/6 = 1/2 = 0,5 ► padne číslo 10:; Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 8/61 Klasická pravděpodobnost • konečný počet výsledků pokusu • výsledky pokusu jsou stejně pravděpodobné Klasická pravděpodobnost P(A) = počet příznivých výsledků jevu A počet všech možných výsledků Příklad: Hod pravidelnou šestistrannou kostkou * počet možných výsledků pokusu: 6 (padne 1, 2, 3, 4, 5 nebo 6) ► padne číslo 6: 1 příznivý výsledek P{A) = 1/6 = 0,17 ► padne sudé číslo: 3 příznivé výsledky (2, 4, 6) ^ P(6) = 3/6 = 1/2 = 0,5 ► padne číslo 10: žádný příznivý výsledek P{D) = 0/6 = 0 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 8/61 Co to je statistika? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 9/61 Statistika * popisná statistika ► názorně představuje data pomocí tabulek, grafů a jednoduchých číselných charakteristik • matematická statistika ► data tvoří výběr z nějaké větší populace ► zobecňuje závěry platné pro naše data na celou populaci pravděpodobnost + statistika = stochastika Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 10/61 1. Kombinatorika o zabývá se vlastnostmi konečných množin ► vytváření navzájem různých množin (skupin) z daných prvků ► určení počtu takto vzniklých množin ► podle toho, zda se prvky v jednotlivých skupinách mohou či nemohou opakovat, rozlišujeme * skupiny s opakováním * skupiny bez opakování Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 11/61 1.1 Základní kombinatorická pravidla Příklad (Dvojciferná čísla) 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. Nějaké nápady? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 12/61 Základní kombinatorická pravidla Příklad (Dvojciferná čísla) 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í A • desítky: číslice 1,2,..., 9 -> 9 možností o jednotky: číslice 0 a jakákoliv z 8 číslic různá od číslice na místě desítek -> 9 možností =4> 9 • 9 = 81 různých dvojciferných čísel Kombinatorické pravidlo součinu Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 13/61 Kombinatorické pravidlo součinu Kombinatorické pravidlo součinu Nechť množina A, má n, prvků pro / = 1,..., k. Pak počet všech uspořádaných /c-tic (a-i,..., ak), kde a-i e , ..., ak e Ak, jejichž první člen lze vybrat n1 způsoby, druhý n2 způsoby, ..., /c-tý člen nk způsoby, je roven součinu k Ylľlj = A71 • A72 • • • A7/c. /=1 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 14/61 Kombinatorické pravidlo součtu Příklad (Dvojciferná čísla) 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í B • D ... množina všech přirozených dvojciferných čísel -> |D|=90 možností • S ... množina všech přirozených dvojciferných čísel se stejnými číslicemi -> |S|=9 možností • R ... množina všech přirozených dvojciferných čísel s různými číslicemi RuS=D, fínS = 0, R+\S\=D R\ = 90 - 9 = 81 různých dvojcifgrnýgh čísel Kombinatorické pravidlo součtu Kombinatorické pravidlo součtu Nechť množina A má / množiny A\ po dvou disji Pak pro počet prvků sje li prv^ jnktní idnoc k U A /=1 ců pro / = 1,..., k a nechť jsou ■ ení těchto množin platí k = !>■ /=i • nejsou-li množiny disjunktní -> Princip inkluze a exkluze Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 16/61 Princip inkluze a exkluze Princip inkluze a exkluze Nechť jsou dány množiny A, pro i = 1,..., k a |A| označuje počet prvků Mé množiny (/ = 1,..., k). Potom pro počet prvků sjednocení množin A,..., Ak platí U A /=1 k /=1 A n A 1AS|----+ (-1 )/c_11A n A> n • • • n Ak J\ A U /A2 U /A3 *1 + 4> - A2 + 4b - A-i nA2 A-i nA3 A2nA3 + Ai nA2nA3\ Princip inkluze a exkluze - příklad Příklad (Sportovní kluby) Ve městě fungují dva sportovní kluby. Fotbalový klub má dvanáct členů, tenisový klub devět. Přitom tři fotbalisté hrají i tenis. Kolik osob celkem je členem nějakého klubu? Nějaké nápady? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 Princip inkluze a exkluze - příklad Příklad (Sportovní kluby) Ve městě fungují dva sportovní kluby. Fotbalový klub má dvanáct členů, tenisový klub devět. Přitom tři fotbalisté hrají i tenis. Kolik osob celkem je členem nějakého klubu? Řešení: počet členů fotbalového klubu: \A\ = 12 počet členů tenisového klubu: \B\ = 9 počet osob ve fotbalovém i tenisovém klubu AnB =3 Au B = A + B - AnB =12 + 9- 3 = 18 osob Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 19/61 1.2 Skupiny bez opakování Kolika způsoby lze z n prvkové množiny {a-i,..., an} vybrat k < n různých prvků? • uspořádaná /etice: variace, permutace • neuspořádaná /c-tice: kombinace Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 20/61 I. Variace Počet /(-prvkových variaci Z množiny M = {ai, a2,..., an_-|, an} vybíráme uspořádané /c-tice i iQnnrpHíí n?i /^-ťípp 2.clen 1 ).clen /c.clen # možností n n-1 ••• n-(/c-2) n-(k- 1) (/7-/()-(A7-/C-1)---1 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 21 /61 L Variace Počet /(-prvkových variaci Z množiny M = , a2,..., an_i, an} vybíráme uspořádané /c-tice uspořádaná /c-tice # možností 1 -člen 2.člen n n - 1 (/c - 1).člen /c.člen n-{k-2) n- (k- 1) kombinatorické pravidlo součinu í/(/C,/7) = /7-(/7-1)---(/7-/C+1) í/(/C,/7)=/7-(/7-1)---(/7-/C+1) (n — /c) - (n — /c — 1) - - -1 _ n! (n — /c) • (n — /c — 1) - - • 1 " (n-/c)! Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 21/61 Variace Variace Variace je libovolná uspořádaná /c-tice sestavená z prvků množiny o n prvcích tak, že každý se v ní vyskytuje nejvýše jednou (záleží na pořadí prvků v této /c-tici a žádný z jejích prvků se nesmí opakovat). Počet všech /c-prvkových variací sestavených z n-prvkové množiny je roven číslu V(k, n) = n • (n - 1) • • • (n - k + 1) = n\ {n-k) k < n. Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 22/61 Variace - příklad vlajka Příklad (Vlajka) Sestavujeme vlajku ze tří různobarevných vodorovných pruhů. K dispozici jsou bílý, červený, modrý, zelený a žlutý pruh látky. a) Kolik vlajek lze sestavit? b) Kolik jich má modrý pruh ? c) Kolik jich má modrý pruh uprostřed? d) Kolik jich nemá červený pruh uprostřed? Nějaký nápad? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 23/61 Příklad (Vlajka) Sestavujeme vlajku ze tří různobarevných vodorovných pruhů. K dispozici jsou bílý, červený, modrý, zelený a žlutý pruh látky. a) Kolik vlajek lze sestavit? b) Kolik jich má modrý pruh ? c) Kolik jich má modrý pruh uprostřed? d) Kolik jich nemá červený pruh uprostřed? Řešení a) • vlajka - 3 různé pruhy z 5 různých barev • záleží na pořadí pruhů =4> tříčlenné variace z 5 prvků 1/(3,5) = 5-4-3 = 60 možností Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 24/61 Příklad (Vlajka) Sestavujeme vlajku ze tří různobarevných vodorovných pruhů. K dispozici jsou bílý, červený, modrý, zelený a žlutý pruh látky. b) Kolik jich má modrý pruh ? c) Kolik jich má modrý pruh uprostřed? Řešeníb) vlajka s modrým pruhem a modrý pruh - 3 způsoby umístění (nahoru, doprostřed, dolů) • zbývající 2 barevné pruhy - 2 různé pruhy ze 4 různých barev 1/(2,4) = 4-3 = 12 možností kombinatorické pravidlo součinu 3 • 1/(2,4) = 3 • 12 = 36 možností Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 25/61 Příklad (Vlajka) Sestavujeme vlajku ze tří různobarevných vodorovných pruhů. K dispozici jsou bílý, červený, modrý, zelený a žlutý pruh látky. b) Kolik jich má modrý pruh ? c) Kolik jich má modrý pruh uprostřed? d) Kolik jich nemá červený pruh uprostřed? Řešeníb) vlajka s modrým pruhem 9 modrý pruh - 3 způsoby umístění (nahoru, doprostřed, dolů) • zbývající 2 barevné pruhy - 2 různé pruhy ze 4 různých barev 1/(2,4) = 4-3 = 12 možností =4> kombinatorické pravidlo součinu 3 • 1/(2,4) = 3 • 12 = 36 možností Řešení c) vlajka s modrým pruhem uprostřed 1/(2,4) = 12 možností Příklad (Vlajka) Sestavujeme vlajku ze tří různobarevných vodorovných pruhů. K dispozici jsou bílý, červený, modrý, zelený a žlutý pruh látky. d) Kolik jich nemá červený pruh uprostřed? Řešeníd) vlajka, která nemá červený pruh uprostřed • červený pruh uprostřed - \/(2,4) = 12 možností o vlajka (3 různé pruhy) - V(3,5) = 60 možností 60 - 12 = 48 možností Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 27/61 I. Permutace i r e roven cislu ■ y P(n) = = V( ' }~{n-n)\ n\ n\ = 0!= 1 ="! <□► < ŕ3? ► < -E ► < -ž ► -š -O Q, O Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 28/61 I. Permutace Permutace Permutace je libovolné uspořádaní množiny M o n prvcích, kdy ve výsledném uspořádání (výsledné uspořádané n-tici) se prvky nesmí opakovat. Počet všech různých permutací (počet všech různých uspořádaných n-tic) prvků množiny M je roven číslu P(n) = n! = n ■ (n - 1) ■ ■ ■ 2 ■ 1, n > 1. • 0! = 1 • Permutace je speciálním případem variace n! P(n) = V{n, n) = n\ n\ {n - n)\ = Ô! = T = n' Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 28/61 Permutace - příklad parlament Príklad (Parlament) 5 připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 6 poslanců A, B, C, D, E, F. Určete 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. Nějaký nápad? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 29/61 Permutace - příklad parlament Příklad (Parlament) 5 připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 6 poslanců A, B, C, D, E, F. Určete 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. Řešení a) • počet všech uspořádání 6 různých prvků P(6) = 6! = 720 možností Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 30/61 Permutace - příklad parlament Příklad (Parlament) 5 připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 6 poslanců A, B, C, D, E, F. Určete počet a) všech možných pořadí jejich vystoupení [6\] b) všech pořadí, v nichž vystupuje A po E, c) všech pořadí, v nichž vystupuje A ihned po E. Řešeníb) • každému pořadí E po A odpovídá právě 1 pořadí A po E (A, B, C, D, E, F) (E, B, C, D, A, F) = - • 6! = 360 možností 2 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 31/61 Permutace - příklad parlament Příklad (Parlament) 5 připomínkami k navrhovanému zákonu chce v parlamentu vystoupit 6 poslanců A, B, C, D, E, F. Určete počet a) všech možných pořadí jejich vystoupení [6\] b) všech pořadí, v nichž vystupuje A po E [\ • 6 \] c) všech pořadí, v nichž vystupuje A ihned po E. Řešení c) • A ihned po E spojíme v jednoho hypotetického poslance EA • počet všech uspořádání 5 různých prvků 6, C, D, F, EA F(5) = 5! = 120 možností Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 32/61 I. Kombinace \X O "~7 ŕ°H \ / O \ í \ / k < A7 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 33/61 I. Kombinace Kombinace je libovolná neuspořádaná /etice sestavená z prvků množiny M o n prvcích tak, že každý se v ní vyskytuje nejvýše jednou (prvky se nesmí opakovat a nezáleží na jejich pořadí). Počet /c-prvkových kombinací sestavených z n-prvkové množiny je roven kombinačnímu číslu (čteme „en nad ká") □ g - = Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 33/61 Počet /c-prvkových kombinací z n prvků • např. M = {a, Ď, c, c/}, n = 4, /c = 3 3členné variace z prvku a, 6, r, d (a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a) (a, b, d) (a, d, b) (b, a, d) (b, d, a) (d, a, b) (d, b, a) (a, c, d) (", f/, c) (c, a, d) (c, i, a) (2) (ci, fl2, *i) (fl3í Oi, fti, b2) (a?, aj, 6^, &i) &2, <*2) («1 i *2i ti, «a) («2, &li *2, Ol) *ii «a) (fc, alt &1t 05) (h. «2, tsi «l) (fe, aa, fli) (ai, aa, *j) fe2, a2l ti) 6i, ai, ta) ( ^l) a2, ti) ^2t Ol p aa) *1j «1í aí) ro, a3, aj) (&2, ftt, fla> oi) Permutace s opakováním ze dvou prvků a, fr, z nichž se každý opakuje dvakrát (a, u, 6, b) (a, 6, a, t) (a, t, ŕ, a) (6, a, ú, i) (r>, ň, b, a) (6. 6, a, a) Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2025 49/61 Permutace s opakováním Permutace s opakováním Permutace je libovolná uspořádaná /c-tice sestavená z prvků množiny o n prvcích tak, že každý se v ní vyskytuje alespoň jednou (ve výsledné /etici se prvky mohou opakovat). Počet všech různých /c-členných permutací s opakováním sestavených z n-prvkové množiny tak, že prvek a\ se v nich vyskytuje /crkrát, prvek a2 se opakuje /c2-krát, atd. až prvek an se opakuje /cn-krát, přičemž /c-i + k2 H-----h kn = /c, je roven P*(/c-|,..., kn) — (fr + /c2+ ... + /cn)! /c-| !/c2! •... • kn\ ki = /co = • • • = kn = 1 ... permutace bez opakování □ g - = ■E "O ^ O' Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 50/61 Permutace s opakováním - příklad slova Příklad (Slova) Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Určete, v kolika z nich a) žádná dvojice sousedních písmen není tvořena 2 písmeny A, b) žádná pětice sousedních písmen není tvořena 5 písmeny A. Nejaký nápad? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 51/61 Příklad (Slova) Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Určete, v kolika z nich a) žádná dvojice sousedních písmen není tvořena 2 písmeny A, b) žádná pětice sousedních písmen není tvořena 5 písmeny A. Řešení 9 počet všech slov = permutace vytvořená z písmen písmeno # výskytů A B D K R 5 2 112 ry*, r- —. . . —.\ (5 + 2+1+1+2) 11 , P (5,2,1,1,2) =--- =-= 83160 sov v ' ' ' ' ; 5!2!1!1!2! 480 Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 52/61 Příklad (Slova) Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Určete, v kolika z nich a) žádná dvojice sousedních písmen není tvořena 2 písmeny A, b) žádná pětice sousedních písmen není tvořena 5 písmeny A. Řešení a) • 5x A, 6 jiných písmen • umístění A:*B*R*K*D*B*R* možností • umístění B,D,K,R: P*(2,1,1,2 (2 + 1+1+2)! 2!1!1!2! 2!2! 6! možností kombinatorický zákon součinu Příklad (Slova) Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Určete, v kolika z nich a) žádná dvojice sousedních písmen není tvořena 2 písmeny A, b) žádná pětice sousedních písmen není tvořena 5 písmeny A. Řešení b) • 5x A je vedle sebe spojíme do jednoho písmena A5 písmeno A5 B D K R # výskytů 12 112 P*(1,2,1,1,2 (1 +2 + 1 +1 +2)! 1!2!1!1!2! 2!2! 7! slov o 5x A není vedle sebe kombinatorický zákon součtu _____ . _____ . 11! 7! III. Kombinace s opakováním Příklad mince Príklad (Mince) Kolik různých částek lze zaplatit 3 mincemi, máme-li v peněžence korunové, dvoukorunové a pětikorunové mince, každý druh alespoň pětkrát? Nejaký nápad? Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 55/61 Počet kombinací s opakováním - odvození Idea: každou kombinaci s opakováním nahradíme pomocí uspořádané skupiny vytvořené ze dvou prvků • platba 3 mincemi: 3 druhy mincí -1 Kč, 2 Kč, 5 Kč - každá alespoň 5x -10 možností 1.1.1 1.1.2 1,1,6 1,2,2 1,2,5 1,5,5 2,2/2 5,5,5 K*{3,3) = P*(3,2) = (3 + 2) 3!2! 5! 3!2! = 10 možností Počet kombinací s opakováním - odvození /c-prvková kombinace s opakováním vytvořená z n prvků = uspořádaná skupina s k tečkami a n-~\ čárkami (n různých přihrádek, v každé jiný druh prvku) K*(k,n) = P*(/f,n-1) = [k + (n- 1)]! = (n + k- 1)! k\{n-J\)\ ~ k\(n-1)\ n + k-1 k Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12.2.2025 57/61 Příklad (Mince) Kolik různých částek lze zaplatit 3 mincemi, máme-li v peněžence korunové, dvoukorunové a pětikorunové mince, každý druh alespoň pětkrát? Řešení o tři různé druhy mincí (1 Kč, 2 Kč, 5 Kč), každá alespoň 5x: n = 3 • platba 3 mincemi: k = 3 • počet různých částek: 3-prvková kombinace s opakováním K*(k,n) = n + k- 1\ _ (n + k- 1)! k J ~ /c!(n- 1)! /C(3,3) = = 10 možností Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 58/61 Kombinace s opakováním Kombinace s opakováním je libovolná neuspořádaná /etice sestavená z prvků množiny M o n prvcích (prvky se mohou opakovat a nezáleží na jejich pořadí). Počet /c-prvkových kombinací s opakováním sestavených z n-prvkové množiny je roven kombinačnímu číslu (n + k- 1)! k\{n- 1)! □ g - = Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 59/61 Shrnutí Základní kombinatorická pravidla • součtu • součinu Skupiny bez opakování • Variace: uspořádaná /c-tice l/(M) = n(n-1).-^ k