KOMBINATORIKA Paulína Jašková Množiny •Množina: •súbor prvkov •obsahuje určitý počet prvkov, konečný/nekonečný •M={1, 2, 3} •prázdna množina •M= {} nebo M=Æ •1ÎM; 5ÏM Kombinatorika •Utvárame skupiny z prvkov nejakej konečnej množiny •napríklad máme zostaviť rozvrh hodín z daných predmetov, •potrebujeme rozhodnúť, ktoré tímy budú v turnaji hrať proti sebe, •chceme rozdať niekoľko druhov cien medzi účastníkov závodu •Prvky sa môžu opakovať ale nemusia •Podľa toho rozlišujeme: •skupiny s opakovanim (keď prvok vyberieme vrátime ho naspäť) •skupiny bez opakovania (nevraciame naspäť) • Faktoriál • • •Faktoriál čísla n je rovný súčinu všetkých prirodzených čísiel, ktoré su menšie alebo rovné číslu n •Zápis – n! •Ex.: 5! = 5·4·3·2·1 = 120 •0! = 1 Kombinatorické pravidlo súčinu Kombinatorické pravidlo súčinu •Ex. Máme dvě množiny – množinu Z, v ktorej sú 3 ženy a množinu M, obsahujúcu 4 mužov. Koľko rôznych párov muž – žena môžeme vytvoriť? • • • • • •4 + 4 + 4 = 12 resp. 3 · 4 = 12 párov •Vynásobili sme veľkosť oboch množín. Ž1 – M1 Ž2 – M1 Ž3 – M1 Ž1 – M2 Ž2 – M2 Ž3 – M2 Ž1 – M3 Ž2 – M3 Ž3 – M3 Ž1 – M4 Ž2 – M4 Ž3 – M4 Kombinatorické pravidlo súčinu •Ex. Koľko existuje rôznych dvojciferných čísiel? • •__ __ •prvá pozícia 1 – 9, druhá pozícia 0 – 9 •9 · 10 = 90 čísiel Kombinatorické pravidlo súčinu •Ex. Koľko existuje rôznych trojciferných čísiel, kde se žiadna číslica nesmie vyskytnút dvakrát? • •__ __ __ •prvá pozícia 1 – 9 •druhá pozícia 0 – 9 bez čísla na prvej pozícií •tretia pozícia 0 – 9 bez čísiel na prvej a druhej pozícií •9 · 9 · 8 = 648 čísiel Kombinatorické pravidlo súčinu •Dvakrát za sebou hodíme klasickou hraciou kockou. Koľko rôznych výsledkov môžeme získať? • •__ __ - v prvom hode 6 možností, v druhom hode opäť 6 možností •6 · 6 = 36 možností • •Opäť dva hody kockou. Koľko rôznych výsledkov môžeme získať, pokiaľ nám v prvom hode padlo sudé číslo? •__ __ - v prvom hode 3 možnosti, v druhom 6 možností •3 · 6 = 18 možností Variácie •variácie k-tej triedy z n prvkov •usporiadaný výber k prvkov zo zadanej množiny •z nejakej množiny objektov vyberáme určitý počet objektov, pričom záleží na poradí, v akom tieto objekty vyberiame Variácie – príklad a odvodenie •Sútež v jedení knedlíkov. Do finále postúpilo 7 účastníkov. Koľko existuje možností, ako týchto sedem účastníkov môže obsadiť prvé tri miesta ? •__ __ __ •prvá pozícia – 7 možností, druhá pozícia – 6 možností, tretia pozícia – 5 možností •7 · 6 · 5 = 210 možností •obecne → prvá pozícia – n možností, druhá pozícia – (n – 1) možností, tretia pozícia (n – 2) možností •n · (n – 1) · (n – 2) · … · (n – k + 1) Variácie bez opakovania - vzorec Variácie •Stále máme závody v jedení knedlíkov. Ako sa zmení počet medailových umiestnení, ak na závod prišiel favorit, ktorý vždy zvíťazí? •__ __ __ •prvé miesto favorit, druhé miesto 6 možností, tretie miesto 5 možností • • • • • Variácie •Ako sa zmení počet možností, ak vieme, že favorit vždy obsadí medailové umistnenie? •__ __ __ • • Variácie s opakovaním •Koľko existuje trojciferných čísiel, ktoré ide zapísať pomocou cifier • {1, 2, 3, 4, 5}? •__ __ __ •cifry sa môžu opakovať – prvá pozícia – 5 možností, druhá pozícia – 5 možností, tretia pozícia – 5 možností •V´3 (5) = 5 · 5 · 5 = 53 = 125 čísiel Variácie s opakováním - vzorec Variácie s opakováním •Koľko rôznych značiek teoreticky existuje v Morseovej abecede, pokiaľ sa zostavujú bodky a čiarky do skupín po jednej až päť? •Variácie s opakovaním, n = 2, k = 1, 2, 3, 4, 5 • •V´1(2) + V´2(2) + V´3(2) + V´4(2) + V´5(2) = 21 + 22 + 23 + 24 + 25 = •= 2 + 4 + 8 + 16 + 32 = 62 značiek • • • • • • • Permutácie •usporiadaná n-tica vybraná z n prvkov • •príklad – koľko trojciferných čísiel dokážeme zostaviť z čísel {1, 2, 3, 4, 5}? •trojciferné • • •päťciferné •Vzorec • Permutácie - príklad •Máme 6 kníh a chceme ich uložiť na poličku v nejakom poradí. Koľko celkom rôznych poradí existuje? • •P(6) = 6! = 720 •720 rôznych poradí uložení kníh Permutácie - príklad •K našim šiestim knihám v českom jazyku pridáme ďalšie 4 knihy písane latinou. Koľko existuje rôznych spôsobov uloženia týchto 10 kníh na poličku, pokiaľ chceme mať všetky české knihy a všetky latinské knihy pohromade? • •české knihy – 6!, latinské knihy – 4! •6! · 4! = 17 280 spôsobov •latinské a potom české •17 280 · 2 •Celkom teda je 34 560 rôznych spôsobov. Permutácie s opakovaním •Koľko rôznych šesťciferných čísiel ide vytvoriť z číslic 1, 2, 2, 3, 3, 3? • • • •Ak sa medzi n prvkami vyskytuje: •prvý prvok n1 krát druhý prvok n2 krát … k-tý prvok nk krát •n1 + n2 + ... + nk = n • Príklad •Zistite, koľko rôznych päťciferných čísiel ide vytvoriť použitím cifier 1,2,3,4,5 (môžu sa opakovať). •Permutácie bez opakovania? •Permutácie s opakovaním? •Variácie s opakovaním? •k=n • •V´5(5) = 55 = 3 125 Kombinácie •Vyberáme určitý počet objektov z nejakej množiny bez ohľadu na poradie •Typickým príkladom – losovanie športky •kombinačné číslo • Kombinačné číslo – základné pravidlá Kombinácie - príklad •V osudí je 49 loptičiek, losuje sa 6. Koľko rôznych možností môžeme vylosovať? • • • • •Existuje teda 13 983 816 možností. • •BTW pravdepodobnosť výhry je 1:13 983 816, teda cca 0,00000715 %. J Kombinácie - príklad •Na „tour de pub“ máme na výber z 13 hospod. Stihnúť ale môžeme len 4. Koľko rôznych štvoríc hospod môžeme navštíviť? • • • • •Máme 715 možností rôznych štvoríc hospod. Kombinácie - príklad •Máme skupinu pedesiatich ľudí . Polovica muži a polovica ženy. Koľko existuje rôznych trojíc ľudí, pokiaľ nesmú byť zložené len z jedneho pohlavia? Kombinácie s opakovaním Príklady •V škole je celkom 20 učiteľov. Je potřebné zostaviť komisiu pre maturtiy v tomto zložení: jeden predseda, jeden hodný prísediaci a jeden zlý prísediaci. Koľko existuje celkom možností? • • • • •Variáce • • Príklady •Koľko trojciferných čísiel môžeme poskladať z číslic {0, 1, 2, 3, 4, 5}, pokiaľ sa žiadná číslica nesmie opakovať? • • •Musíme odčítať tie variácie, ktoré majú na prvom mieste nulu. •0 __ __ z čísiel 1, 2, 3, 4, 5 • • •Celkový počet je teda 120 – 20 = 100 možností. Opakovanie •Permutácia je usporiadanie prvkov do fixného poradia. • •Kombinácia (k prvková) je výber k prvkov zo zadanej množiny. • •Kombinácia s opakovaním (k prvková) je výber k prvkov zo zadanej množiny, pričom prvky sa môžu opakovať. • •Variácia (k prvková) je usporiadaný výber k prvkov zo zadanej množiny. • •Variácia s opakovaním (k prvková) je usporiadany výber k prvkov zo zadanej množiny, pričom prvky se môžu opakovať. • Opakovanie Obrázok, na ktorom je stôl Automaticky generovaný popis