Prednášky z kombinatoriky. Preskupenie s opakovaním

Príručka načrtáva základy kombinatoriky a kombinatorických algoritmov.
Určené pre študentov prvého a druhého ročníka matematických odborov.
Spracované na Katedre telekomunikačných systémov.

Úvod do kombinatoriky. Niektoré oblasti aplikácie kombinatoriky.
Zástupcovia širokej škály špecialít a profesií musia riešiť problémy, ktoré zahŕňajú určité kombinácie zložené z písmen, číslic a predmetov. Tu je niekoľko príkladov:
plánovanie úlohy;
v chémii: zvažovanie všetkých druhov spojení medzi atómami a molekulami;
riešenie dopravných problémov;
plány na predaj akýchkoľvek produktov;
problémy s vytváraním a dekódovaním šifier.

Definícia 1. Oblasť matematiky, v ktorej sa študujú otázky o tom, koľko rôznych kombinácií možno za určitých podmienok vytvoriť z daných predmetov, sa nazýva kombinatorika.

Obsah
Prednáška 1. Úvod do kombinatoriky. Niektoré oblasti aplikácie kombinatoriky. Priamy súčin súprav. Pravidlo súčtu a pravidlo súčinu pre konečné množiny. Dirichletov princíp. Umiestnenia bez opakovaní, umiestnenia s opakovaniami, kombinácie bez opakovaní, kombinácie s opakovaniami, permutácie. Multiset
Úvod do kombinatoriky. Niektoré oblasti aplikácie kombinatoriky
Priamy súčin súprav
Pravidlo súčtu a pravidlo súčinu
Dirichletov princíp
Umiestnenia, kombinácie, permutácie
Multiset
Prednáška 2. Základné identity súvisiace s počtom kombinácií. Binomická veta. Dôsledky Newtonovej binomickej vety. Vlastnosti binomických koeficientov
Základné identity súvisiace s počtom kombinácií
Binomická veta
Dôsledky Newtonovej binomickej vety
Vlastnosti binomických koeficientov
Prednáška 3. Pascalov trojuholník. Niektoré vlastnosti Pascalovho trojuholníka. Vlastnosti šesťuholníka pre Pascalov trojuholník. Rozdeľovacie súpravy. Stirlingove čísla druhého druhu
Pascalov trojuholník
Niektoré vlastnosti Pascalovho trojuholníka
Vlastnosti šesťuholníka
Nastavte oddiely
Stirlingove čísla druhého druhu
Prednáška 4. Čísla zvonov. Stirlingové čísla prvého druhu. Nesignované Stirlingovo číslo prvého druhu
Číslo zvončeka
Stirlingové čísla prvého druhu
Nesignované Stirlingovo číslo prvého druhu
Prednáška 5. Vzorec inklúzií a vylúčení. Problém nepokojov
Vzorec pre inklúzie a vylúčenia
Problém nepokojov
Prednáška 6. Počet prvkov s presne k vlastnosťami. Problém so stretnutiami. Počet prvkov s aspoň k vlastnosťami
Počet prvkov s presne k vlastnosťami
Problém stretnutia
Prednáška 7. Polynomická veta. Metódy kombinatorickej analýzy. Spôsob generovania funkcií. Problém s vážením
Polynomiálna veta
Metódy kombinatorickej analýzy. Metóda generovania funkcie
Problém s vážením
Prednáška 8. Generovanie funkcií. Typy generujúcich funkcií. Vlastnosti generujúcich funkcií. Korešpondenčná tabuľka generujúcich funkcií a postupností
Generovanie funkcií
Typy generujúcich funkcií
Vlastnosti generujúcich funkcií
Korešpondenčná tabuľka generujúcich funkcií a postupností
Prednáška 9. Diferenciácia a integrácia generujúcich funkcií. Niektoré elementárne generujúce funkcie. Nekonečne klesajúci geometrický postup a postupnosť jednotiek
Diferenciácia a integrácia generujúcich funkcií. Príklady použitia
Niektoré elementárne generujúce funkcie
Nekonečne klesajúci geometrický postup a postupnosť jednotiek
Prednáška 10. Príklady hľadania generujúcich funkcií pre danú postupnosť. Príklady hľadania postupnosti generujúcich funkcií
Príklady hľadania generujúcich funkcií pre danú postupnosť
Príklady hľadania postupnosti generujúcich funkcií
Prednáška 11. Riešenie homogénnych rekurentných vzťahov. Všeobecná metóda riešenia rekurentného vzťahu
Riešenie homogénnych rekurentných vzťahov
Všeobecná metóda riešenia rekurentných vzťahov
Prednáška 12. Fibonacciho postupnosť. Príklady použitia generujúcich funkcií. Výpočet odmocniny čísla pomocou generujúcich funkcií
Fibonacciho sekvencia
Príklady použitia generujúcich funkcií
Výpočet odmocniny čísla pomocou generujúcich funkcií
Prednáška 13. Katalánske čísla. Katalánska sekvencia a katalánska generujúca funkcia. Algoritmus na umiestnenie zátvoriek
Katalánske čísla
Katalánska sekvencia a katalánska generujúca funkcia
Algoritmus na umiestnenie zátvoriek
Prednáška 14. Generovanie kombinatorických objektov. Preskupenia. Kombinácie. Rozdeľovacie čísla. Podmnožiny množín
Preskupenia
Kombinácie
Číselné oddiely
Podmnožiny množiny
Literatúra
Vzdelávací a metodický komplex pre disciplínu „Kombinatorické algoritmy“
1. Miesto disciplíny v štruktúre OOP
2. Ciele a ciele disciplíny
3. Požiadavky na výsledky zvládnutia disciplíny
4. Rozsah disciplíny a typy akademickej práce
5. Obsah disciplíny
5.2. Laboratórna dielňa
5.3. Praktické hodiny (semináre) sa neposkytujú
6. Bodový systém hodnotenia vedomostí, hodnotiaca stupnica
7. Približné témy projektov kurzu (práce)
8. Edukačná, metodická a informačná podpora disciplíny
I. Informácie o učiteľoch (odkaz na stránku)
II. Literatúra
III. Databázy, informačné, referenčné a vyhľadávacie systémy
9. Logistická podpora disciplíny
10. Metodické odporúčania pre organizáciu štúdia odboru.

Stiahnite si e-knihu zadarmo vo vhodnom formáte, pozerajte a čítajte:
Stiahnite si knihu Prednášky z diskrétnej matematiky, I. časť, Kombinatorika, Zaripova E.R., Kokotchikova M.G., 2012 - fileskachat.com, rýchle a bezplatné stiahnutie.

Stiahnite si pdf
Nižšie si môžete kúpiť túto knihu za najlepšiu cenu so zľavou s doručením po celom Rusku.

Objemová vzorka zo sady je ľubovoľná sekvencia prvkov sady. Ak sa prvky vo vzorke neopakujú, vzorka sa nazýva neopakovanie, inak - vzorkovanie s opakovaniami Pri neopakovanom vzorkovaní nezáleží na tom, ako sa výber uskutoční: všetky prvky sa odoberú naraz alebo jeden po jednom (po jednom). Usporiadanie prvkov vzorky v určitom poradí sa nazýva zoradenie a vzorka sa nazýva usporiadaná, inak sa nazýva neusporiadaná.

Riešenie. Akciou v tomto prípade je vytvoriť súpravu pera, ceruzky a pravítka; Akcia je rozdelená do troch etáp (častí): vyberte si pero, vyberte si pravítko a vyberte si ceruzku. Prvú časť akcie – výber pera – je možné vykonať piatimi spôsobmi, druhú časť akcie – výber ceruzky – možno vykonať siedmimi spôsobmi, tretiu časť akcie – výber pravítka – je možné vykonať desiatimi spôsobmi. Potom je možné celú akciu vykonať 5*7*10 =350 Počet spôsobov. Tie. existuje možno 350 variantov tejto zostavy.

Príklad. Jedáleň ponúka dva rôzne prvé chody a1 a a2, tri rôzne druhé chody b1, b2, b3 a dva druhy dezertov c1 a c2. Koľko rôznych trojchodových jedál môže jedáleň ponúknuť? Riešenie. Nech A je množina prvých chodov, B je množina druhých chodov a C je množina tretích chodov. Podľa podmienok je to známe

Príklad. „Tím vesmírnej lode“ Zvážte problém vytvorenia tímu vesmírnej lode. Je známe, že sa objaví otázka psychologickej kompatibility. Predpokladajme, že potrebujeme vytvoriť tím 3 ľudí: veliteľ, inžinier a lekár. Na miesto veliteľa sú štyria kandidáti: a1, a2, a3, a4, traja na miesto inžiniera - b1, b2, b3 a traja na miesto lekára - c1, c2, c3. Kontrola ukázala, že a1 je kompatibilný s b1, b2, c2, c3; a2 je kompatibilný s b1, b2, cl, c2, c3; a3 je kompatibilný s b1 a b2, c1, c3; a4 je kompatibilný s b1, b2, b3, c2; b1 nie je kompatibilný s c3; b2 nie je kompatibilné s c1; b3 nie je kompatibilný s c2.

Usporiadanie n rôznych prvkov v určitom poradí sa nazýva permutácia n prvkov bez opakovania. Napríklad na množine troch prvkov (a,b,c) sú možné tieto permutácie: abc, acb, bca, bac, cab, cba. Počet rôznych permutácií bez opakovaní prvkov označujeme P n a rovná sa n!, t.j.

Tabuľka možností KBKSSB BSKBKS SBKSKB Strom možností Pravidlo násobenia 1 prúžok 3 spôsoby 2 prúžok 2 spôsoby 3 prúžok 1 spôsob = 6 Odpoveď: 6 spôsobov Počítanie permutácií

Kombinácia n prvkov bez opakovania pomocou k je neusporiadaná k-prvková podmnožina n-prvkovej množiny. Počet kombinácií bez opakovania prvkov sa rovná: Napríklad musíte vypočítať, koľkými spôsobmi môžete vytvoriť tím troch ľudí, ktorí budú mať službu v skupine 30 ľudí. Keďže poradie ľudí v tíme nie je pevne dané a ľudia sa neopakujú, máme prípad kombinácií 30 prvkov po 3 bez opakovania: Tím troch ľudí v službe v skupine 30 ľudí je možné vybrať v 4060 rôznymi spôsobmi.

Úloha. Jeden milovník hudby má 6 diskov slávnej popovej skupiny, iný 8. Koľkými spôsobmi si môžu vymeniť tri disky? Riešenie: Každý milovník hudby si musí vybrať zo svojich diskov tri, ktoré bude meniť. Prvý to dokáže spôsobmi C63 a druhý spôsobmi C83. Keďže výber je nezávislý, všetky možnosti sú C63*C83. Poďme si to spočítať: C 6 3 = 6*5*4/3! = 6*5*4/6 = 5*4 = 20. C83 = 8*7*6/3! = 8*7*6/6 = 8*7 = 56. Odpoveď: 20*56=1120.

Uvažujme vzorku s opakovaniami. Nech existuje vzorka n prvkov, pričom k prvkov je rovnakých. Počet rôznych permutácií na prvkoch takejto vzorky sa rovná: - počtu permutácií s k opakovaniami na množine n prvkov Kombinácii s opakovaniami prvkov o - neusporiadanému výberu prvkov s návratom z množiny obsahujúcej prvky : - počet rôznych kombinácií s opakovaním n prvkov po k Umiestnenie s opakovaním prvkov podľa - usporiadanie rôznych loptičiek v rôznych bunkách - počet rôznych umiestnení s opakovaním

Príklad. Koľko permutácií možno získať z písmen slova BELL? Riešenie. Musíte nájsť počet permutácií s opakovaniami na sade 8 písmen, medzi ktorými: písmeno K sa opakuje 2-krát; písmeno O sa opakuje 3-krát; písmeno L sa opakuje 2-krát, písmeno A sa opakuje 1-krát. teda

Príklad. Koľkými spôsobmi možno vyrobiť sadu 5 čokolád, ak existujú tri druhy čokolád, 10 z každého druhu? Riešenie. Keďže pri zostavovaní čokoládovej sady nie je dôležité poradie čokolád, použijeme na výpočet vzorec kombinácií s opakovaním:

Je zrejmé, že počet všetkých možných kombinácií 10 číslic po 4 je Počet všetkých možných kombinácií 30 písmen po dvoch je Ak vezmeme do úvahy možnosť, že písmená sa môžu opakovať, potom počet opakovaných kombinácií je 30 (jedno opakovanie možnosť pre každé písmeno). Celkovo je celkový počet kombinácií dvoch písmen 900. Ak k číslu pribudne ďalšie písmeno z abecedy s 30 písmenami, tak sa počet kombinácií zvýši 30-krát, t.j. dosahuje kombinácie. Napokon, pretože Každá kombinácia písmen môže byť spojená s číselnou kombináciou, potom sa celkový počet ŠPZ rovná príkladu. Číslo auta sa skladá z troch písmen a troch číslic. Koľko rôznych čísel je možné vytvoriť pomocou 10 čísel a abecedy s 30 písmenami.

Prepis

1 Prednáška 1. Téma: „Prvky kombinatoriky“ Definícia. Kombinatorika je oblasť matematiky, ktorá študuje otázky o tom, koľko rôznych kombinácií možno za určitých podmienok vytvoriť z daných predmetov. Základy kombinatoriky sú veľmi dôležité pre odhad pravdepodobnosti náhodných udalostí, pretože Práve tie nám umožňujú vypočítať zásadne možný počet rôznych možností vývoja udalostí. Základné pravidlá kombinatoriky Väčšina kombinatorických úloh sa rieši pomocou dvoch základných pravidiel – súčtového pravidla a súčinového pravidla. Pravidlo súčtu. Ak je možné určitý objekt vybrať spôsobmi a iný objekt je možné vybrať spôsobmi, potom výber „buď alebo“ možno urobiť spôsobmi. Produktové pravidlo. Ak je možné objekt vybrať spôsobmi a po každom takomto výbere je možné (bez ohľadu na výber objektu) spôsobmi vybrať iný objekt, potom je možné spôsobmi vyberať dvojice objektov. Príklad 1. Koľko je dvojciferných čísel? Riešenie. Keďže v dvojcifernom čísle sa číslica označujúca počet desiatok musí líšiť od nuly, potom = (1, 2,..., 9), = (0, 1, 2,..., 9) a Zákl. kombinatorika vzorce 1. Výbery prvkov bez opakovaní Definícia. Usporiadania prvkov podľa sa nazývajú také výbery, ktoré majú prvky vybrané z daných prvkov, líšia sa od seba buď zložením prvkov, alebo poradím ich usporiadania. Počet umiestnení prvkov označujeme pomocou základného pravidla kombinatoriky získame 1

2 Príklad 2. Koľko je dvojciferných čísel, v ktorých sú cifra s desiatkami a cifra jednotky odlišné a nepárne? Riešenie. Pretože Ak existuje päť nepárnych číslic, konkrétne 1, 3, 5, 7, 9, potom táto úloha spočíva v výbere a umiestnení dvoch z piatich rôznych číslic na dve rôzne pozície, t.j. z uvedených čísel bude: Príklad 3. Koľko slovníkov sa musí vydať, aby ste mohli priamo vykonávať preklady z ktoréhokoľvek z piatich jazykov: ruštiny, angličtiny, nemčiny, francúzštiny, španielčiny – do ktoréhokoľvek z týchto piatich jazykov? Riešenie. Keďže je dôležité poradie, z ktorého sa prekladá do iného jazyka, na zodpovedanie otázky je potrebné zistiť počet umiestnení od piatich do dvoch. Definícia. Ak, potom je počet takýchto usporiadaní, ktoré sa líšia iba poradím usporiadania prvkov. Takéto umiestnenia sa nazývajú permutácie. Ich počet zistíme podľa vzorca Príklad 4. Koľkými spôsobmi možno na poličke v jednom rade usporiadať sedem kníh od rôznych autorov? Riešenie. Tento problém sa týka počtu permutácií siedmich rôznych kníh. Existuje P 7 =7!=1*2*3*4*5*6*7=5040 spôsobov usporiadania kníh. Definícia. Vzorky prvkov prevzaté z údajov, ktoré sa líšia iba zložením prvkov, sa nazývajú kombinácie prvkov. Počet takýchto kombinácií je uvedený v príklade 5. Univerzitnej majstrovskej súťaže vo volejbale sa zúčastňuje 8 tímov. O koľko dlhšie bude turnaj s každým kolesom trvať ako olympijský turnaj? Riešenie. Pri turnaji typu round-robin sa každý účastník stretol medzi sebou a poradie, v ktorom boli spárované, nie je dôležité. Následne bude potrebné odohrať zápasy systémom každý s každým, ale iba 7 v olympijskom systéme (štyri stretnutia v semifinále a jedno finále). finále, dva - v 2

3 Príklad 6. Koľkými spôsobmi si môže čitateľ vybrať dve knihy zo šiestich dostupných? Riešenie. Počet metód sa rovná počtu kombinácií šiestich kníh po dvoch, t.j. rovná sa: Diskusia. Vidíme, že počet možných kombinácií možno vypočítať podľa rôznych pravidiel (permutácií, kombinácií, umiestnení) a výsledok bude iný, pretože Princíp výpočtu a samotné vzorce sú odlišné. Pri pozornom pohľade na definície si všimnete, že výsledok závisí od viacerých faktorov súčasne. Po prvé, z koľkých prvkov môžeme kombinovať ich množiny (aký veľký je súčet prvkov). Po druhé, výsledok závisí od veľkosti množín prvkov, ktoré potrebujeme. Nakoniec je dôležité vedieť, či je pre nás dôležité poradie prvkov v súbore. Vysvetlime posledný faktor na nasledujúcom príklade. Príklad 7. Na rodičovskom stretnutí je prítomných 20 ľudí. Koľko rôznych možností je na zloženie materského výboru, ak v ňom musí byť 5 osôb? Riešenie. V tomto príklade nás nezaujíma poradie mien na zozname komisie. Ak sa v dôsledku toho ukáže, že tí istí ľudia sú jeho súčasťou, znamená to pre nás rovnakú možnosť. Preto môžeme použiť vzorec na výpočet počtu kombinácií 20 prvkov z 5. Všetko bude iné, ak bude každý člen komisie spočiatku zodpovedný za určitú oblasť práce. Potom, s rovnakým zložením zoznamu v komisii, je v nej možno 5! permutácie, na ktorých záleží. Počet rôznych (v zložení aj v oblasti zodpovednosti) možností je v tomto prípade určený počtom umiestnení 20 prvkov po 5. Nech existuje k skupín prvkov a i-tá skupina pozostáva z n i prvkov. Z každej skupiny vyberieme jeden prvok. Potom celkový počet N spôsobov, ktorými možno takúto voľbu uskutočniť, je určený vzťahom N=n 1 *n 2 *n 3 *...*n k. Príklad 8. Vysvetlime si toto pravidlo na jednoduchom príklade. Nech sú dve skupiny prvkov a prvá skupina pozostáva z n 1 prvkov a druhá - z n 2 prvkov. Koľko rôznych párov prvkov možno vytvoriť z týchto dvoch 3

4 skupiny tak, aby dvojica obsahovala jeden prvok z každej skupiny? Povedzme, že sme vzali prvý prvok z prvej skupiny a bez toho, aby sme ho zmenili, prešli všetky možné dvojice, pričom sme zmenili iba prvky z druhej skupiny. Pre tento prvok existuje n 2 takýchto párov. Potom vezmeme druhý prvok z prvej skupiny a vytvoríme k nemu všetky možné dvojice. Takýchto párov bude tiež n 2 Keďže v prvej skupine je len n 1 prvkov, celkový počet možných možností bude n 1 * n 2. Príklad 9. Koľko trojciferných párnych čísel možno vytvoriť z čísel 0. , 1, 2, 3, 4, 5, 6, ak sa čísla môžu opakovať? Riešenie. n 1 = 6 (pretože ako prvú číslicu môžete vziať akékoľvek číslo od 1, 2, 3, 4, 5, 6), n 2 = 7 (pretože ako druhú číslicu môžete vziať akékoľvek číslo od 0, 1, 2 , 3, 4, 5, 6), n 3 = 4 (keďže akékoľvek číslo od 0, 2, 4, 6 môže byť brané ako tretia číslica). Takže, N=n 1 *n 2 *n 3 =6*7*4= Vzorky prvkov s opakovaniami V prípade, že všetky skupiny pozostávajú z rovnakého počtu prvkov, t.j. n 1 =n 2 =...n k =n môžeme predpokladať, že každý výber je urobený z tej istej skupiny a prvok po výbere je vrátený do skupiny. Potom je počet všetkých metód výberu n k. Tento spôsob výberu v kombinatorike sa nazýva vzorkovanie s návratom. V týchto vzorkách je povolené opakovanie prvkov, čo je celkom prirodzené (napríklad v telefónnych číslach a číslach áut je možné použiť jednu číslicu viackrát). Príklad 10. Koľko štvorciferných čísel možno zostaviť z číslic 1, 5, 6, 7, 8? Riešenie. Pre každú číslicu štvorciferného čísla existuje päť možností, čo znamená N=5*5*5*5=5 4 =625. Počet umiestnení prvkov s opakovaniami sa označí a zistí ako Počet permutácií, v ktorých sa 1. prvok opakuje raz, 2. - raz a -tý - čas, sa zistí takto: Príklad 11. Koľko “. slová“ môžete získať preskupením písmen v slove MATEMATIKA? Riešenie. Všimnite si, že ak by boli všetky písmená iné, dostali by sme nové „slová“, ale písmeno „M“ sa v „slove“ použije 2-krát, „A“ - 3-krát, 4

5 "T" - 2 krát, zvyšné tri písmená - každé raz. V dôsledku toho bude požadovaný počet koeficientom menším a rovným Počet kombinácií s opakovaniami prvkov podľa je vyjadrený počtom kombinácií bez opakovaní: Príklad 12. V kaviarni je na predaj 5 druhov koláčov . Koľkými spôsobmi si môže 8 študentov objednať každý jeden koláč? Riešenie. Zašifrujme každý nákup 8 koláčov v jednotkách po 5 odrôd, pričom odrody oddelíme nulami. Potom bude každý nákup zodpovedať objednanej sade 8 jednotiek a 4 (= 5-1) oddeľujúcich núl a celkový počet nákupov bude zodpovedať počtu permutácií týchto núl a jednotiek. Úlohy autotestu 1. Koľko trojciferných párnych čísel možno vytvoriť z čísel 0, 1, 2, 3, 4, 5, 6, ak sa čísla môžu opakovať? 2. Koľko je päťciferných čísel, ktoré sa čítajú rovnako zľava doprava a sprava doľava? 3. V triede je desať predmetov a päť vyučovacích hodín denne. Koľkými spôsobmi môžete vytvoriť rozvrh na jeden deň? 4. Koľkými spôsobmi možno vybrať 4 delegátov na konferenciu, ak je v skupine 20 ľudí? 5. Koľkými spôsobmi možno vložiť osem rôznych listov do ôsmich rôznych obálok, ak je v každej obálke vložené iba jedno písmeno? 6. Komisia zložená z dvoch matematikov a šiestich ekonómov by mala byť zložená z troch matematikov a desiatich ekonómov. Koľkými spôsobmi sa to dá urobiť? 5

6 Úlohy 1. Na majstrovstvách Ruska vo futbale sa zúčastňuje 16 tímov. Koľkými spôsobmi možno určiť troch najlepších víťazov? 2. Z balíčka obsahujúceho 36 kariet sa vybralo 10 kariet. Koľkými rôznymi spôsobmi sa to dá urobiť? V koľkých prípadoch bude medzi týmito kartami aspoň jedno eso? V koľkých prípadoch bude práve jedno eso? 3. Koľkými spôsobmi sa môže 8 ľudí postaviť vedľa seba? 4. Koľkými spôsobmi možno 5 učebníc o kombinatorike, 4 o algebre a 3 o matematickej analýze usporiadať na policu, ak sú učebnice na každý predmet rovnaké? 5. Na fyzike a matematike pracuje 76 učiteľov. Z nich 49 hovorí po anglicky, 32 po nemecky a 15 ovláda oba jazyky. Koľko učiteľov na fyzike a matematike nevie ani po anglicky, ani po nemecky? 6. Kvetinárstvo predáva 4 druhy kvetov. Koľko rôznych kytíc môžete vyrobiť z každej z piatich kvetov? 7. V Morseovej abecede sú písmená reprezentované postupnosťami pomlčiek a bodiek. Koľko znakov bude potrebných na zakódovanie písmen ruskej abecedy? 8. Aká je pravdepodobnosť výhry aspoň jednej z cien v športovom lotte? 6

KOMBINATORIKA 1. Všeobecné pravidlá kombinatoriky V praxi často musíte vybrať z určitej množiny objektov podmnožinu prvkov, ktoré majú určité vlastnosti, usporiadať prvky jedného

FEDERÁLNA VZDELÁVACIA AGENTÚRA Štátna vzdelávacia inštitúcia vyššieho odborného vzdelávania "NÁRODNÝ VÝSKUM POLYTECHNICKÁ UNIVERZITA TOMSK" PREDNÁŠKA TEÓRIE

Praktická práca 15 Výpočet počtu vzoriek Cieľ práce: naučiť sa určovať počet vzoriek pomocou pravidiel kombinatoriky a základných vzorcov. Obsah práce. Základné pojmy. 1 Pravidlo

OBSAH 1 TÉMA II. PRVKY KOMBINATORIKY... 2 1. REFERENČNÉ MATERIÁLY A PRÍKLADY... 2 1.1. PRÍKLADY... 2 2. ZÁKLADNÉ DEFINÍCIE, OZNAČENIE A VZORCE... 3 3. PRAVIDLÁ KOMBINATORIKY... 4 4.

Téma 48 „Alternatívny a simultánny výber“ Veda, ktorá študuje metódy kompozície a počet množín a ich podmnožín, sa nazýva kombinatorika. Každá konkrétna podmnožina zložená z prvkov

KOMBINATORNÉ PROBLÉMY Vendina Alla Anatolyevna docentka Katedry matematiky a informatiky Stavropoského štátneho pedagogického ústavu Vendina A.A. Kombinatorické problémy. Úlohy výberu prvkov

1) Slovo má 12 [neopakujúcich sa] písmen. Koľkými spôsobmi môžu byť písmená v tomto slove preusporiadané, aby vytvorili najrôznejšie sady písmen? Pretože všetky písmená sú rôzne, potom n P12 12!

Lekcia 2. Umiestnenie a kombinácie Ciele lekcie: vzdelávacie: naučiť študentov riešiť problémy pomocou vzorcov kombinácií a umiestnení; rozlišovať kombinatorické spojenia; naučiť, ako riešiť problémy v živote; vzdelávacie:

Kombinatorika Metódy riešenia úloh Rumyantseva LS Pravidlo súčtu Ak sa konečné množiny nepretínajú, potom sa počet prvkov X U Y (alebo) rovná súčtu počtu prvkov množiny X a počtu prvkov množiny

(definícia pravidla rovnosti, súčtu a súčinu; princíp inklúzií; výnimky; zovšeobecnenie pravidla súčinu; všeobecné pravidlo súčinu; výbery permutácií a kombinácie permutácií a kombinácií s

Katedra matematiky a informatiky Matematika Vzdelávací a metodický komplex pre študentov stredných odborných škôl študujúcich pomocou dištančných technológií Modul 6 Základy teórie pravdepodobnosti a matematickej štatistiky

Ministerstvo školstva Moskovskej oblasti Štátna rozpočtová vzdelávacia inštitúcia stredného odborného vzdelávania Moskovskej oblasti "Balashikha Industrial and Economic College"

I. V. Jakovlev Materiály z matematiky MathUs.ru Kombinatorika. Produktové pravidlo Pri riešení kombinatorických problémov často musíte vynásobiť počet spôsobov výberu jedného objektu počtom spôsobov výberu.

Teória pravdepodobnosti a matematická štatistika Doktor fyziky a matematiky. Profesor vied Michail Pavlovič Kharlamov „Stránka“ s učebnými materiálmi http://inter.vags.ru/hmp Volgogradská pobočka RANEPA (FGOU

S A Lavrenchenko TEÓRIA PRAVDEPODOBNOSTI "Tri karty, tri karty, tri karty!" (Opera Piková dáma) Praktická lekcia 1 11 Klasická definícia pravdepodobnosti 111 Najjednoduchšie úlohy pre klasickú definíciu

Kombinatorika (z latinského combinare spájať, spájať) je odvetvie matematiky, v ktorom sa študujú problémy tohto typu: koľko kombinácií, ktoré spĺňajú určité podmienky, možno vytvoriť

Teória množín a základy kombinatoriky Plán prednášky P.. Definícia množiny a podmnožiny... P.. Množiny a vzťahy... P.. Operácie na množinách... P. 4. Vlastnosti operácií na množinách... 4

Príklady kombinatorických úloh a všeobecných princípov kombinatoriky Príklad inšpirovaný Andersenovou rozprávkou „Snehová kráľovná“. Pamätajte, že keď Gerda našla Kaia v paláci Snehovej kráľovnej, neúspešne skladal

LEKCIA 1 PRVKY KOMBINATORICKÉ METODICKÉ ODPORÚČANIA PRE MISS 2013 SCHVÁLENÉ: D.E. Kaputkin predseda Výchovno-metodickej komisie pre plnenie zmluvy s rezortom školstva

Prednáška 1 Prvky kombinatoriky Kombinatorika je časť matematiky venovaná riešeniu problémov výberu a usporiadania prvkov určitej, zvyčajne konečnej, množiny podľa daných pravidiel.

RIEŠENIE PROBLÉMOV V TEÓRII PRAVDEPODOBNOSTI 1 V teórii pravdepodobnosti sa často musíme potýkať s problémami, pri ktorých je potrebné spočítať počet možných spôsobov vykonania nejakej akcie. Úlohy takých

4 Kombinatorika Permutácia je usporiadaná množina čísel 1, zvyčajne interpretovaná ako bijekcia na množine (1), ktorá priraďuje číslu i i-tý prvok z množiny

Príručka pre učiteľov všeobecných stredných škôl Odporúčaná Vedecko-metodickým ústavom „Národný inštitút vzdelávania“ Ministerstva školstva Bieloruskej republiky Mozyr „Bely“

Príručka pre učiteľov všeobecných stredných škôl Odporúčaná Vedecko-metodickým ústavom „Národný inštitút vzdelávania“ Ministerstva školstva Bieloruskej republiky Mozyr 2

Téma 53 „Kombinované úlohy“. Problémy diskutované v tejto časti sumarizujú informácie z kombinatoriky, štatistiky a teórie pravdepodobnosti. Základné vzorce kombinatoriky. Žiadne opakovania S opakovaniami

Vývojár kurzu Docent Katedry vyššej matematiky, kandidát technických vied Nekryach E.N. PRVKY KOMBINATORIKY SÚBOROV A OPERÁCIE NA NICH Takýto pojem ako súbor vo všeobecnosti nie je definovaný,

Teória pravdepodobnosti a matematická štatistika Doktor fyziky a matematiky. Profesor vied Michail Pavlovič Kharlamov Internetový zdroj s učebnými materiálmi http://www.vlgr.ranepa.ru/pp/hmp Volgogradská pobočka

009-00 škola rok. 6, 0 trieda. Matematika. Prvky kombinatoriky. Kombinatorika (z latinského combinare spájať, spájať) je odvetvie matematiky, v ktorom sa študujú problémy tohto typu: koľko

PRVKY KOMBINATORIKY. Produktové pravidlo. Ak existuje n možností výberu prvého prvku a pre každú z nich existuje m možností výberu druhého prvku, potom je celkom n m rôznych párov

Predkladám rozbor testovacích prác zo zbierky „L.A. Alexandrova. Algebra 9. ročník. Testy" Niekedy je ťažké samostatne porozumieť všetkým úlohám ponúkaným v testoch, najmä

ŠTÁTNA UNIVERZITA NIŽNÝ NOVGOROD pomenovaná po N I LOBACHEVSKIJ Fakulta výpočtovej matematiky a kybernetiky Katedra matematickej logiky a vyššej algebry PRVKY KOMBINATORIKY (Príručka pre študentov

1 Základné pojmy kombinatoriky 1 Príloha Definícia Súčin všetkých prirodzených čísel od 1 do n vrátane sa nazýva n-faktoriál a píše sa Príklad Vypočítajte 4! 3! n! 1 3 n 4!-3!= 1 3 4 1 3 4 18

Problémy teórie pravdepodobnosti N.M. Efimova, učiteľka matematiky, MBOU "Gymnázium" Teória pravdepodobnosti a matematická štatistika sa zaoberajú konštrukciou a štúdiom modelov rôznych situácií súvisiacich

Téma 49 „Vzorce pre počet kombinácií. Binomická veta“. Základné vzorce kombinatoriky. Bez opakovaní S opakovaniami A = n! n k! A = n Poradie je dôležité P = A = n! P = A = n Pk, k, k = (k + k + + k)! k! k! k!

1.1. Klasická definícia pravdepodobnosti Základným pojmom teórie pravdepodobnosti je pojem náhodnej udalosti. Náhodná udalosť je udalosť, ktorá pri splnení určitých podmienok môže

I. V. Jakovlev Materiály z matematiky MathUs.ru Obsah Desatinný zápis 1 Celoruská olympiáda pre školákov v matematike......................... 1 2 Moskovská matematická olympiáda ........................

Ministerstvo školstva a vedy Ruskej federácie Federálna štátna rozpočtová vzdelávacia inštitúcia pre doplnkové vzdelávanie detí Korešpondenčná fyzikálno-technologická škola Moskovskej fyziky a techniky

III ZÁKLADY KOMBINATORIKY Všeobecné pravidlá kombinatoriky Kombinatorika je odvetvie diskrétnej matematiky, ktoré študuje spôsoby počítania prvkov rôznych konečných množín Mnoho pravidiel kombinatoriky

Matematika (BkPl-100) M.P. Kharlamov 2011/2012 akademický rok, 1. semester Prednáška 5. Téma: Kombinatorika, úvod do teórie pravdepodobnosti 1 Téma: Kombinatorika Kombinatorika je odbor matematiky, ktorý študuje

2. prednáška: enumeratívna kombinatorika Diskrétna matematika, Vysoká škola ekonomická, Fakulta informatiky (jeseň 2014 jar 2015) Problémy enumeratívnej kombinatoriky majú typickú podobu: „koľko spôsobov robiť

PRAVDEPODOBNOSŤ NÁHODNEJ UDALOSTI Kolmogorovove axiómy V roku 1933 A. N. Kolmogorov vo svojej knihe „Basic Concepts of Probability Theory“ poskytol axiomatické zdôvodnenie teórie pravdepodobnosti. „To znamená, že potom

Základné pojmy teórie pravdepodobnosti Predchádzajúce poznámky (pozri obsah) boli venované metódam zberu údajov, metódam zostavovania tabuliek a grafov, ako aj štúdiu deskriptívnej štatistiky. V tomto

Úlohy a hádanky 1. Desatinná číselná sústava Desatinná číselná sústava je pozičná. V pozičných číselných systémoch závisí príspevok číslice k číslu od polohy tejto číslice v zápise čísla.

Mestská autonómna vzdelávacia inštitúcia "Lyceum 38" mesta Belgorod Školenie na tému: "Kombinatorické pravidlo násobenia" Učiteľ matematiky MAOU "Lyceum 38" Belgorod Reutskaya Lyudmila

Spoľahlivé podujatie. Udalosť sa nazýva spoľahlivá, ak je isté, že k nej dôjde pri splnení určitého súboru podmienok. Symbol: Ω (pravda). Nemožná udalosť. Udalosť, ktorá

TÉMA PREDNÁŠKY 1: TYPY KOMBINATORNÝCH PROBLÉMOV. ZÁKLADNÉ PRINCÍPY KOMBINATORIKY. Plán 1. História kombinatoriky 2. Niektoré problémy kombinatoriky 3. Štruktúra a metódy 4. Príklady riešenia úloh 1. História kombinatoriky

V prednáške boli použité materiály z knihy I.A. Lavrova „matematická logika“ a zo zbierky T.V. Andreeva „diskrétna matematika pre sociológov“. 1 Umiestnenie n položiek do k boxov, preusporiadanie.

Prednáška 1. Téma: ZÁKLADNÉ PRÍSTUPY K URČOVANIU PRAVDEPODOBNOSTI Predmet teórie pravdepodobnosti. Historické pozadie Predmetom teórie pravdepodobnosti je štúdium vzorov, ktoré vznikajú pod masívnym, homogénnym

Prvky kombinatoriky, profesor katedry fyziky a matematiky IPK a PRO, doktor fyzikálnych vied Mishchenko S.P. C 1. Kartézsky súčin množín Elementárna kombinatorika je spojená s jedným jednoduchým výsledkom

Korešpondenčné fyzikálne a matematické lýceum "Avangard" E. N. Filatov ALGEBRA 8 Experimentálna učebnica 1. časť MOSKVA 2016 OBSAH 1. Deliteľnosť. 2. Párne nepárne 3. Sady. 4. Zábavné úlohy. 5. Kombinatorika

MINISTERSTVO ŠKOLSTVA A VEDY ŠTÁTNEHO VZDELÁVACIEHO ÚSTAVU VYSOKÉHO ODBORNÉHO VZDELÁVANIA RUSKEJ FEDERÁCIE ŠTÁTNA TECHNICKÁ UNIVERZITA NIŽNY NOVGOROD. R.E. Alekseeva

1 Klasická definícia pravdepodobnosti 1 Balíček 3 kariet sa starostlivo zamieša Nájdite pravdepodobnosť, že všetky štyri esá sú v balíčku jedno po druhom, bez preloženia iných kariet Riešenie Číslo

Yugra Physics and Matematic Lyceum V.P. Chuvakov Deliteľnosť celých čísel v problémoch Zbierka úloh Chanty-Mansijsk 05 Deliteľnosť celých čísel v problémoch: Zbierka úloh, - Chanty-Mansijsk, Ugro fyzika a matematika

Federálna agentúra pre vzdelávanie Štátna vzdelávacia inštitúcia vyššieho odborného vzdelávania Štátna technická univerzita Ukhta (USTU) KOMBINATORIKA Metodický

Vorobiev V.V. "Lyceum" Kalachinsk, Omsk Region Workshop o riešení problémov v teórii pravdepodobnosti a matematickej štatistike Dôležitú úlohu pri štúdiu tém v teórii pravdepodobnosti a štatistike zohráva

PRAKTICKÉ Základné vzorce kombinatoriky Typy udalostí Pôsobenie na udalosti Klasická pravdepodobnosť Geometrická pravdepodobnosť Základné vzorce kombinatoriky Kombinatorika študuje počty kombinácií,

Kombinatorika DISKRÉTNA MATEMATIKA C. Prvky kombinatoriky (v rámci teórie množín) Technická univerzita v Talline Kombinatorika je odbor matematiky venovaný riešeniu problémov výberu a umiestnenia

Matematika 6. ročník Množiny a obsahový blok kombinatoriky vedieť vedieť 1 Pojem množina. Pojem množina na opis agregátov. podmnožina, položky alebo objekty, konečné,

Binárne kódovanie 1.3 Binárne kódovanie Kľúčové slová: vzorkovanie sily abecedy binárna abeceda binárne kódovanie bitová hĺbka binárneho kódu 1.3.1. Konverzia informácií z

Kombinatorika

Úlohy

Princípy kombinatoriky Princíp sčítania

Princíp sčítania

Princíp násobenia

Úlohy

Úlohy

Úlohy

Úlohy

Komentujte

Permutácie bez opakovania

Permutácie s opakovaniami

Umiestnenie bez opakovania

Umiestnenia s opakovaniami

Riešenie problémov

Úlohy

Úlohy

Úlohy

Úlohy

Úlohy

Úlohy

Úlohy

Úlohy

1. 1. DISKRÉTNA MATEMATIKA Kurz prednášok Lomonosov Moskovská štátna univerzita Ekonomická fakulta 1
2. 2. Prednáška 4 Kombinatorika 2
3. 3. Kombinatorika 3 V tejto prednáške sa naučíme počítať prvky konečných množín, ktoré spĺňajú určité vlastnosti. Zoznámime sa s typickými situáciami, v každej z nich môžete použiť špecifický vzorec na zjednodušenie výpočtov. Zoznámime sa tiež s hlavnou oblasťou použitia kombinatoriky - výpočtom pravdepodobností, ktorej úplná teória sa študuje v druhom ročníku.
4. 4. Hlavná úloha kombinatoriky 4 S prvkami konečných množín môžete vykonávať rôzne akcie: usporiadať ich, spájať do skupín, vyberať podmnožiny na základe dodatočných charakteristík a vlastností atď. V tomto prípade vznikajú nové, zložitejšie (kombinované) množiny, ktorých prvky je tiež potrebné vedieť spočítať. . Niekedy sa kombinatorika definuje aj ako veda o počítaní počtu podmnožín, ktoré spĺňajú určité vlastnosti. Predmet kombinatoriky: počítanie počtu spôsobov vykonávania určitých akcií.
5. 5. Základné princípy kombinatoriky. 5 Väčšinu kombinatorických problémov možno vyriešiť pomocou jedného z dvoch jednoduchých princípov, ktoré sú intuitívne zrejmé, ľahko overiteľné na príkladoch a používané ako axiómy. V praxi sa princíp násobenia používa oveľa častejšie, pretože zložité akcie sa často musia rozložiť na postupnosť jednoduchých. Zásada sčítania sa vzťahuje na situácie, keď existuje možnosť voľby medzi dvoma alternatívnymi žalobami (keď sa dve žaloby navzájom vylučujú). Princíp násobenia sa na druhej strane vzťahuje na akcie, ktoré sa vykonávajú spoločne (postupne alebo súčasne)
6. 6. Princíp sčítania 6 Princíp sčítania: Ak činnosť 1 možno vykonať n spôsobmi a činnosť 2 možno vykonať m spôsobmi, potom môže byť komplexná činnosť pozostávajúca z vykonania jednej z činností 1 alebo 2 (ale nie oboch). urobené n+m spôsobmi. Príklad: ako stráviť večer: kam ísť? V kine Navštívte „Ona“ „Pompeii 3D“ Misha Masha Lesha Celkom 2 + 3 = 5 spôsobov, ako stráviť večer.
7. 7. Princíp násobenia 7 Princíp násobenia: Ak činnosť A môže byť vykonaná n spôsobmi a činnosť B môže byť vykonaná m spôsobmi, potom je možné vykonať komplexnú akciu pozostávajúcu z vykonávania akcií A aj B (súčasne alebo postupne). nm spôsobmi. Do kina!!! (ale s kým?) Natasha Tanya Olya „Vampire Academy“ „Iba dievčatá v športe“ Celkom: 2*3=6 spôsobov, ako ísť do kina.
8. 8. Pravdepodobnosť 8 Pravdepodobnosť je miera spoľahlivosti, že udalosť nastane (meraná ako číslo od 0 do 1). V najjednoduchšom prípade sa pravdepodobnosť počíta kombinačne. V praxi sa výpočty vždy začínajú menovateľom, zistite, čo sa považuje za akciu, ktoré akcie sa považujú za odlišné, vypočítajte celkový počet takýchto akcií a až potom prejdite na čitateľa. Rozkladajú komplexný priaznivý výsledok na jednoduché alebo štandardné a využívajú princípy kombinatoriky. Určenie pravdepodobnosti pre najjednoduchší prípad rovnako pravdepodobných výsledkov - pomer počtu priaznivých akcií (alebo ich výsledkov) k celkovému počtu akcií (ich výsledkov): n m p 
9. 9. 9 Jeden zo študentov si každú minútu vymyslí jedno z čísel (od 0 do 9) a zapíše si ho a druhý, nachádzajúci sa na inom mieste, sa ho snaží „telepaticky prijať“ a tiež si ho zapíše (hodiny sú synchronizované). Za predpokladu, že telepatia neexistuje, aká je pravdepodobnosť, že zamýšľané číslo bude uhádnuté správne? Aká je pravdepodobnosť, že tri čísla za sebou budú uhádnuté správne? Telepatia. Úloha z iného sveta...
10. 10. Aplikácia princípu násobenia 10 PRÍKLAD: sklad. Na otvorenie skladu sa používa kombinácia 4 čísel (od 0 do 9), vytáčaných na 4 kolieskach. a) Nájdite pravdepodobnosť náhodného otvorenia odkladacej skrinky. RIEŠENIE: Postupne nastavte čísla na každom z kolies; zakaždým máme 10 možností (čísla od 0 do 9), podľa princípu násobenia sa násobia: 10101010 = 10 000 možností. Dvere otvára len jeden z nich, takže pravdepodobnosť náhodného otvorenia je 1/10000 = 0,0001. Celkom beznádejná úloha. Dokonca aj v najjednoduchších prípadoch je vhodné rozložiť zložité akcie na jednoduché, napríklad si predstaviť, že sa vykonávajú jeden po druhom.
11. 11. Hodnota informácie 11 V dôsledku použitia dodatočných informácií v správe sa vyhľadávanie znížilo na polovicu, odtiaľ je možné v zásade vypočítať, akú hodnotu majú komunikované informácie, ak by sa dali kúpiť. Pokračovanie: b) Nájdite pravdepodobnosť náhodného otvorenia odkladacej skrinky, ak sa navyše ukázalo, že všetky čísla na správnom čísle sú iné. RIEŠENIE: Teraz na druhom koliesku nemusíte opakovať číslo napísané v prvom, takže počet možností sa zníži na 9, potom sa dve čísla zakážu, takže celkovo je 8 možností a na poslednom už je 7 možností: 1098 7 = 5040 možností. Ako predtým, dvere otvára iba jeden, takže pravdepodobnosť otvorenia dverí je 1/5040  0,0002.
12. 12. Úloha s domácou úlohou 12 1. N ľudí náhodne stojí v rade na koncert známej skupiny. Aká je pravdepodobnosť, že dvaja určití ľudia (nazvime ich A a B) budú stáť vedľa seba (a budú mať šancu stretnúť sa, akoby náhodou). 2. N ľudí je pozvaných na návštevu a zasadnutie za okrúhly stôl. Aká je pravdepodobnosť, že rovnaké A a B náhodou skončia na susedných miestach. A a B sedeli...a stáli.
13. 13. Úloha domácej úlohy 13 Nočným vlakom zloženým z 8 vagónov cestuje 6 ľudí. Pri nastupovaní si každý náhodne vyberie svoj vozeň a neprestupuje do iného vozňa. Nájdite pravdepodobnosť, že: 1. každý cestuje v rôznych vozňoch 2. v tom istom vozni sedia aspoň dvaja ľudia. 3. Všetci budú natlačení v jednom vozni a budú sa spolu triasť. Posledný vlak
14. 14. Štandardné akcie kombinatoriky 14 Základné pravidlá riešenia kombinatorických úloh v zásade postačujú. Ale prakticky sa používajú iba v neštandardných úlohách. Väčšina problémov riešených v kombinatorike je typická, štandardná. Je pre nich pohodlnejšie priamo používať hotové vzorce, z ktorých každý je spojený s určitou štandardnou akciou. Štandardné operácie kombinatoriky: Permutácie Umiestnenia Sampling Partitions (do skupín)
15. 15. Permutácie 15 Dve permutácie sa od seba líšia len v poradí prvkov, všetky prvky majú spoločné. Prvý prvok môže byť umiestnený na ktoromkoľvek z n miest, ďalší prvok môže byť umiestnený na ktoromkoľvek z (n-1) miest atď. Posledný prvok zaberá jediné zostávajúce miesto. To vedie k vzorcu n!=n(n-1)(n-2)...1 (n-faktoriál). PRÍKLAD: Počet permutácií 5 kníh na poličke je 5!.
16. 16. Umiestnenia 16 Tieto dve umiestnenia sa navzájom líšia zložením a poradím prvkov. k nA – počet umiestnení k prvkov na n miestach. Pre prvý prvok je n miest, potom (n-1) miest atď. Zostáva (n–k+1) miest pre posledný k-tý prvok. To vedie k vzorcu)1)...(2)(1( knnnnAk n . („nedokončený faktoriál“). V podstate ide o permutáciu k prvkov na n miestach k
17. 17. Úloha 17 Študent nastúpi do výťahu s ďalšími 6 študentmi (do tejto chvíle sa nepoznali). Výťah ide na ktorékoľvek zo 7 poschodí (nepočítajúc spodok). Dievča, ktoré vychádzalo z výťahu na svojom poschodí, si všimlo, že s ňou vystúpil mladý muž. Mala by to považovať za viac ako nehodu? Alebo možno je...
18. 18. Úloha domácej úlohy 18 Predpokladajme, že narodeniny náhodne vybranej osoby môžu pripadnúť na ktorýkoľvek deň z 365 dní v roku. Aká je pravdepodobnosť, že dvaja alebo viacerí ľudia majú v skupine 23 ľudí rovnaké narodeniny? Veľká párty.
19. 19. 19 Jeden človek prišiel s tým, čo považoval za spôsob, ako určite vyhrať v rulete. Zdôvodňuje to takto: lopta sa môže zastaviť na ktoromkoľvek z 36 čísel: 1, 2, ... 36 (pre jednoduchosť budeme ignorovať 0). Ak vsadím na určité číslo 36-krát, pravdepodobne aspoň raz vyhrám. má pravdu? Aká je skutočná pravdepodobnosť výhry aspoň jedného? Nájdite spôsob, ako to približne odhadnúť bez kalkulačky). Cena útechy Problém s domácou úlohou
20. 20. Výber 20 Dve vzorky sa od seba líšia iba zložením prvkov, ich poradie je indiferentné (preto sa v menovateli objavuje faktoriál počtu prvkov). Počet spôsobov, ako vybrať k prvkov z dostupných n prvkov, má vzhľadom na štandardný charakter a rozšírené používanie problému výberu špeciálny názov - počet kombinácií n prvkov podľa k. PRÍKLAD: Počet spôsobov distribúcie 5 letákov na diskotéku v spoločnosti 7 osôb je 21 12345 345675 7    C . Počet vzoriek, označených k nC , sa rovná!)1)...(2)(1(k knnnn Ck n  
21. 21. Odvodenie vzorca pre počet kombinácií 21 Aby sme získali vzorec pre počet vzoriek, zredukujeme problém na už skúmaný prípad (umiestnenie s prihliadnutím na poradie). Vychádzame teda z počtu umiestnení, ktoré však teraz (keďže poradie k prvkov je indiferentné) treba vydeliť počtom permutácií k prvkov: !)1)...(2)(1(! k knnnn k A C k nk n    Upozorňujeme, že v čitateli je iba k faktorov, rovnako ako v menovateli.
22. 22. Vlastnosť symetrie kombinácií 22 Vybrané a zostávajúce z hľadiska rozdelenia do skupín sú rovnaké, preto počet spôsobov výberu k prvkov sa rovná počtu spôsobov, ako nechať n-k prvkov nevybraných kn n k n CC   PRÍKLAD : V probléme distribúcie letákov dostaneme oveľa pohodlnejší vzorec 21 12 672 7 5 7     CC .
23. 23. Pravdepodobnosť štúdia 23 Každý študent dostane na skúšku 3 otázky, náhodne vybrané z 25 otázok v programe. Študent dostane „5“, ak správne odpovie na všetky otázky, „4“ – iba dve, „3“ – iba jedna a „2“ – žiadna. Aká je pravdepodobnosť získania A, B, C a D? Skúšobná pasca.
24. 24. Riziková matematika 24 Pred dvadsiatimi rokmi bola v Rusku populárna lotéria „Sportloto“, kde ste po zakúpení tiketu museli prečiarknuť 6 názvov športov zo 45. V týždennom žrebovaní bolo vyhlásených 6 výherných typov . Výherný fond sa rozdelil medzi tých, ktorí uhádli správne. Aká je pravdepodobnosť uhádnutia troch športov? Všetkých šesť? Šťastný lístok
25. 25. Výber ako rozdelenie do dvoch skupín 25 Vzorec pre kombinácie môžete dať v symetrickom tvare, ktorý je vhodný na zapamätanie. Vynásobte čitateľa a menovateľa (n-k)! a doplňte čitateľa na úplný faktoriál.)!(! ! 123)...(! 123)...()1)...(2)(1(knk) n knk knknnnn (! knk n Ck n  rozdeliť množinu pozostávajúcu z n prvkov na dve skupiny, z ktorých prvá obsahuje k prvkov a druhá - n-k prvkov, rovná)!(! !),(knk n knkPn  
26. 26. Komplexná vzorka dvoch typov prvkov 26 Komplexná vzorka je vzorka z heterogénnej populácie, ktorá obsahuje prvky dvoch alebo viacerých typov. Ak chcete vytvoriť komplexnú vzorku, musíte najprv vybrať m prvkov z M, ktoré majú požadovanú vlastnosť, a potom samostatne vybrať n-m prvkov z N-M, ktoré požadovanú vlastnosť nemajú: mn MN m M CC   Pravdepodobnosť takejto skutočnosti je n N mn MN m M C CC p   Nech kolekcia obsahuje N prvkov, z ktorých iba M má nejakú vlastnosť (a teda N-M ju nemá).
27. 27. Aplikácia komplexnej vzorky 27 Prakticky je vhodné si predstaviť, že činnosti na vytvorenie častí komplexnej vzorky vykonávajú oddelene, napríklad, rôzni ľudia v kurze teórie pravdepodobnosti, tento vzorec bude mať hrdý názov hypergeometrickej distribúcie. PRÍKLAD: Nákup televízora na trhu Mitinsky. Stánok má 10 televízorov, z ktorých funguje iba 6. Za deň sa predalo 7 televízorov. Nájdite pravdepodobnosť, že 4 z nich fungujú. Počítame pomocou komplexného vzorového vzorca 2 1 123 8910 4 21 56 7 10 3 4 4 6        C CC p
28. 28. Komplexný odber vzoriek. Všeobecný prípad. 28 Uvažujme teraz o prípade k rôznych typov prvkov. Nech kolekcia obsahuje n prvkov, z ktorých len n1 má vlastnosť 1, n2 má vlastnosť 2, ..., nk má vlastnosť k. Analogicky s prípadom dvoch skupín a oddeleným výberom prvkov rôznych typov vo vzorke dostaneme k k n nnn n nnn n nn n n CCCC 11 3 21 2 1 1 ......  Môžete si overiť priamym počítaním, čo sa to rovná!!!!...! ! 21 knnn n 
29. 29. Rozdelenie do skupín 29 Dva oddiely sa od seba líšia zložením prvkov skupín, poradie prvkov v skupinách je indiferentné, poradie skupín je významné. Ak chcete odvodiť vzorec pre počet oddielov do skupín, môžete ísť iným spôsobom: zovšeobecniť symetrický vzorec pre kombinácie na prípad k skupín. Počet spôsobov)...,(21 kn nnnP , ktorými možno množinu n objektov rozdeliť do k rozlíšiteľných skupín obsahujúcich 1n , 2n , …, kn objektov, sa rovná!!...! ! 21 knnn n  PRÍKLAD: vedúci oddelenia zloženého z 10 zamestnancov zostavuje rozvrh práce na päť dní v týždni (dvaja zamestnanci musia mať službu každý deň, každý zamestnanec má službu jeden deň). Použitím štandardného vzorca pre počet dielikov dostaneme 10!/(2!2!2! 2!2!)=1134000.
30. 30. Úloha domácej úlohy 30 Písmená napísané na skladacích kartách abecedy sú: dve „M“, tri „A“, dve „T“ a po jednom „E“, „I“ a „K“. Malé dieťa hrá s kartami a kladie ich vedľa seba. Aká je pravdepodobnosť, že na prvý raz dostane náhodne slovo „MATEMATIKA“? . Mladý matematický génius
31. 31. Úloha domácej úlohy 31 Nájdite pravdepodobnosť, že pri ťahaní troch kariet z balíčka 52 kariet dostanete trojku, sedmičku a eso. Chudák Hermann.
32. 32. Základné vzorce kombinatoriky. 32 Zhrňme a zozbierajme získané výsledky. Permutácie sa líšia iba v poradí prvkov. Počet permutácií n prvkov sa rovná n!=n(n-1)(n-2)...1 Umiestnenia sa líšia zložením a poradím prvkov. Počet umiestnení k prvkov na n miestach sa rovná)1)...(2)(1( knnnnAk n . Vzorky sa navzájom líšia zložením prvkov, poradie je indiferentné). Počet vzoriek k prvkov z n prvkov sa rovná!) 1)...(2)(1(k knnnn Ck n   Počet rozdelení množiny n objektov do k skupín obsahujúcich 1n , 2n , …, kn prvkov sa rovná k k n nnn n nn n n k kn CCC nnn n nnnP 11 2 1 1 ... 21 21 ... !!... !),...,(!   
33. 33. Koniec prednášky