XSZD-01 Základy kombinatoriky a klasické pravděpodobnosti Jiří Fišer (Eva Fišerová) 12. února 2024 Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 12. 2. 202' 1 /74 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. 2024 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://horne1.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. 202 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 4/74 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ů 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.2024 6/74 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 AntoineGombaud Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 7/74 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ů 17 sledky (2, 4, 6) Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 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, MVSO Olomouc) XSZD, seminář č. 1 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) Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 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, MVSO Olomouc) XSZD, seminář č. 1 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 Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 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, MVSO Olomouc) XSZD, seminář č. 1 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, MVSO Olomouc) XSZD, seminář č. 1 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, MVSO Olomouc) XSZD, seminář č. 1 Co to je statistika? Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 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 10/74 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 11/74 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, MVSO Olomouc) XSZD, seminář č. 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. Ř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 13/74 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 14/74 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 Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 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, MVSO Olomouc) XSZD, seminář č. 1 12. 2. 202' 16/74 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 Ao n Ai + Ai n A> n Art1 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, MVSO 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, MVSO Olomouc) XSZD, seminář č. 1 □ g - = 12. 2. 202' ■E "O ^ O' 19/74 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, MVSO Olomouc) XSZD, seminář č. 1 12. 2. 202' 20/74 L Variace Počet /(-prvkových variaci Z množiny M = {a^, a2,..., an_i, an} vybíráme uspořádané /c-tice \r\ I J .Ultíl I n n n-{k-2) n-(/c-1) i z i Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 21 /74 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, MVSO Olomouc) XSZD, seminář č. 1 12. 2. 202' 21 /74 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, MVSO Olomouc) XSZD, seminář č. 1 □ ► 4 .f ► < -š -š -O Q, O 22/74 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, MVSO Olomouc) XSZD, seminář č. 1 23/74 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í 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, MVSO Olomouc) XSZD, seminář č. 1 □ ► 4 .f ► < -š -š -O O 25/74 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í Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 □ ► 4 .f ► 4 -š -š -O O 26/74 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, MVSO Olomouc) XSZD, seminář č. 1 □ ► 4 .f ► < -š -š -O O 27/74 I. Permutace i r e roven cislu ■ y \J m f I f f f — \/( n n\ — Ô!=T = n! Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 28/74 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 P(n) = l/(n, n) = (n-n)\ = Ô! = T = n' Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 28/74 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, MVSO Olomouc) XSZD, seminář č. 1 29/74 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 30/74 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) l.e: = 360 možností Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 □ ► 4 .f ► < -š -š -O Q, O 31 /74 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.2024 32/74 I. Kombinace \X o "~7 ŕ°H \ / o \ í \ / k < A7 Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 33/74 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/74 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, r2) (a?, aj, 6^, &i) &2, <*2) ti, «a) («2, &li *2, Ol) *ii «a) (*a, alt &1t 05) (h. «2, tsi «l) (fe, aa, fli) (ai, aa, *j) fe2, a2l ti) 6i, ai, ta) (aa, 01= &i) Bii i2■ &a) (til «1, «2, &l) a2ř ^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, MVSO Olomouc) XSZD, seminář č. 1 □ r3P ► < š ► < -š -š -O <\ O 49/74 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\ kA = /c2 = • • • = kn = 1 ... permutace bez opakování Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 □ g .f ► < -š -O Q, O 50/74 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.2024 51/74 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í počet všech slov = permutace vytvořená z písmen písmeno # výskytů A B D K R 5 2 112 P*(5,2,1,1,2) = (5 + 2 + 1+1+2)! = rn 5!2!1!1!2! ~ 480 = 83160 slov Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 52/74 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)! 6! 2!1!1!2! 2!2! možností kombinatorický zákon součinu 7\ 6! 5/2!2! = 3780 možností Jiří Fišer (UAMI, MVSO Olomouc) XSZD, seminář č. 1 □ g .f ► < -š -O Q, O 53/74 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.2024 55/74 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í = c\(y Jiří Fišer (UAMI, MVŠO Olomouc) XSZD, seminář č. 1 12. 2. 2024 56/74 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, MVSO Olomouc) XSZD, seminář č. 1 □ ► 4 .f ► < -š -š O^O 57/74 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/74 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/74 Shrnutí Základní kombinatorická pravidla • součtu • součinu Skupiny bez opakování • Variace: uspořádaná /c-tice l/(M) = n(n-1).-^ k