Vytvorte kombináciu 2 z 10. Kombinatorika: základné pravidlá a vzorce. Kombinácie. Počítanie počtu kombinácií

Najprv si rozoberieme základné pojmy kombinatoriky - výbery a ich typy: permutácie, umiestnenie a kombinácie. Je potrebné vedieť ich, aby vyriešili veľkú časť skúšky 2020 z matematiky oboch úrovní, ako aj deviatakov za absolvovanie OGE. Začnime príkladom.

Permutácie. Počítanie počtu permutácií.

Predstavte si, že ste si vybrali povolanie, ktoré, zdá sa, nemá nič spoločné s matematikou, napríklad interiérový dizajnér. Predstavte si, že by vám zákazník predložil požiadavku:

„Na poličku poukladajte 4 knihy, aby bordové a modré zväzky neboli vedľa seba. Ukážte mi to všetky možnosti umiestnenia. Vyberiem si toho, ktorý mi najviac vyhovuje. “

Čo budeš robiť? S najväčšou pravdepodobnosťou začnete aranžovať a predvádzať. Aby ste sa však nenechali zmiasť, nenechali si ujsť žiadnu z možných možností a neopakovali sa, musíte to urobiť podľa nejakého systému.

Napríklad najskôr necháme vínový objem na prvom mieste, vedľa neho môže byť zelený alebo oranžový. Ak je zelený objem na druhom mieste, potom môže stáť buď oranžová a modrá, alebo modrá a oranžová. Ak je oranžový objem na druhom mieste, potom môže stáť buď zelená a modrá, alebo modrá a zelená. Celkovo existujú 4 možné možnosti.

Na prvom mieste môže byť ktorýkoľvek zo 4 zväzkov, čo znamená, že popísaný postup sa musí opakovať ešte 3 krát. Prípad, keď je na prvom mieste modrý objem, sa získava z rovnakého dôvodu.

A ďalšie dva prípady sa líšia v tom, že zvyšné tri miesta by mali mať bordové a modré zväzky, ale nie vedľa seba. Napríklad, keď je na prvom mieste zelený objem, oranžový objem musí byť na treťom mieste, aby sa oddelili vínové a modré zväzky, ktoré môžu byť na druhom a štvrtom alebo štvrtom a druhom.

V dôsledku toho sme dostali iba 12 možností na usporiadanie 4 kníh na polici s daným limitom. Je to veľa alebo málo? Ak strávite jednu minútu presúvaním kníh a diskusiou o výslednej verzii so zákazníkom, potom je to v poriadku. 12 minút môžete presúvať knihy a rozprávať sa. (Skúste spočítať, koľko permutácií 4 kníh by sa ukázalo bez akýchkoľvek obmedzení?)

Teraz si predstavte, že zákazník má viac kníh ako 4. No, aspoň 5. Je zrejmé, že možností usporiadania bude viac, a ich preskupenie z miesta na miesto skutočne trvá dlhšie a je jednoduchšie zameniť sa a začni opakovať ... bojovať bez prípravy už nestojí za to. Najprv musíte naplánovať svoje možnosti na papieri. Kvôli stručnosti očíslujeme naše farebné zväzky a ich čísla usporiadame na papier. Aby sme urobili menej chýb, najskôr napíšeme všetky možnosti permutácie a potom odstránime tie z nich, na ktoré sa toto obmedzenie vzťahuje. Takže:

„Na poličku poukladajte 5 kníh tak, aby 1. a 2. diel neboli vedľa seba. Ukážte všetky možnosti permutácie “.

Máme 5 kníh (alebo 5 čísel), z ktorých každá môže byť na prvom mieste. Vytvorme si vlastný tanier pre každý z týchto 5 prípadov. Na druhom mieste môže byť ktorákoľvek zo zostávajúcich 4 číslic, pre každú z nich vyhradíme v doske stĺpec.

Do každého stĺpca umiestnime dvojice riadkov, v ktorých je jedna zo zvyšných 3 číslic na treťom mieste a posledné dve číslice sa zamenia. Preto starostlivo zapisujeme všetky možnosti permutácie. Spočítajme ich celkový počet.

5 (tabuľky) × 4(stĺpec) × 3(dvojice riadkov) × 2(struny) × 1 ( možnosť) = 120 (možnosti).

A nakoniec zo všetkých tabuliek odstráňte možnosti obsahujúce „12“ alebo „21“. Na prvej a druhej platni ich bolo 6 a vo zvyšných 3 12, celkom 48 možností, ktoré obmedzenie nesplnili. To znamená, že zákazník musí ukázať 120 - 48 = 72 variantov usporiadania 5 kníh. Bude to trvať viac ako hodinu, aj keď diskusia o každej možnosti bude trvať len minútu.

Ale kde ste videli človeka, ktorý si najme dizajnéra, aby usporiadal päť kníh? V skutočnosti takéto úlohy vznikajú v knižniciach, kde potrebujete usporiadať knihy pre pohodlie návštevníkov, vo veľkých kníhkupectvách, kde potrebujete usporiadať knihy tak, aby bol zaistený nárast dopytu atď. Teda tam, kde nie je len niekoľko kníh, a dokonca ani nie desiatky, ale stovky a tisíce.

Nielen knihy musia počítať permutácie. To môže byť požadované pre veľký počet akýchkoľvek predmetov v takmer akejkoľvek oblasti činnosti. To znamená, že návrhári aj ľudia z iných profesií môžu potrebovať asistenta, alebo ešte lepšie, nástroj na uľahčenie prípravnej fázy, analýzu možných výsledkov a zníženie neproduktívnej práce. Takéto nástroje vytvorili a vytvorili vedci-matematici a potom ich dali spoločnosti vo forme hotových vzorcov. Matematici neignorovali problémy súvisiace s permutáciami, ako aj s umiestnením a kombináciou rôznych prvkov. Zodpovedajúce vzorce existujú už niekoľko storočí. Tieto vzorce sú veľmi jednoduché, rastúca časť spoločnosti ich „odovzdáva“ na hodinách školskej matematiky. Preto všetko, čo bolo napísané vyššie, je v podstate „vynález bicykla“, ku ktorému sa bolo treba uchýliť kvôli predpokladu, že interiérový dizajnér nikdy nebude potrebovať matematiku. Vzdajme sa tohto predpokladu. Zopakujme si matematické koncepty a potom sa vráťme k problému s poličkou.

Kombinatorika sa nazýva oblasť matematiky, v ktorej sa študujú otázky, koľko rôznych kombinácií za určitých podmienok môžu tvoriť prvky danej sady. Pri vytváraní kombinácií skutočne vyberáme rôzne prvky z tejto množiny a kombinujeme ich do skupín podľa svojich potrieb, preto namiesto slova „kombinácie“ často používame slovo „výbery“ prvkov.

Vzorec pre počet permutácií.

Permutácie Nazývajú sa výbery prvkov, ktoré sa líšia iba v poradí prvkov, ale nie v samotných prvkoch.

Ak sa permutácie vykonávajú na sade z n prvky, ich počet je určený vzorcom
P n = n·( n−1) ( n−2) ... 3 2 1 = n!

n! - označenie, ktoré slúži na výstižné zaznamenanie práce všetkých prirodzené čísla od 1 do n vrátane a nazýva sa „ n-factorial “(v preklade z angličtiny„ faktor “-„ multiplikátor “).

Teda celkový počet permutácií 5 kníh P 5 = 5! = 1 · 2 · 3 · 4 · 5 = 120, čo je to, čo sme dostali vyššie. V skutočnosti sme odvodili tento vzorec pre malý príklad... Teraz vyriešime väčší príklad.

Problém 1.

Regál má 30 zväzkov. Koľkými spôsobmi je možné ich usporiadať tak, aby zväzky 1 a 2 nestáli bok po boku?

Riešenie.

Podľa vzorca určte celkový počet permutácií 30 prvkov P 30=30!
Ak chcete vypočítať počet „extra“ permutácií, najskôr určte, koľko možností je druhý zväzok vedľa prvého napravo od neho. V takýchto permutáciách môže 1. zväzok obsadiť miesta od prvého do 29. a 2. od druhého do 30. - iba 29 miest pre túto dvojicu kníh. A pre každú takú pozíciu prvých dvoch zväzkov môže zvyšných 28 kníh obsadiť zvyšných 28 miest v ľubovoľnom poradí. Možnosti preskupenia pre 28 kníh P 28= 28! Celkovo, ak je 2. zväzok umiestnený napravo od 1., vyjde to 29 · 28! = 29!
Podobne zvážte prípad, keď je 2. zväzok umiestnený vedľa 1., ale naľavo od neho. Ukazuje sa rovnaký počet možností 29 · 28! = 29!
To znamená, že existuje 2 · 29! „Nadbytočných“ permutácií! Vypočítajme túto hodnotu.
tridsať! = 29! 30; 30! −2 · 29! = 29! (30–2) = 29! 28.
Musíme teda vynásobiť všetky prirodzené čísla od 1 do 29 a znova vynásobiť 28.
Odpoveď: 2,4757335 10 32.

Toto je veľmi veľké číslo (za 2 je ďalších 32 číslic). Aj keď by každá permutácia trvala sekundu, trvalo by to miliardy rokov. Oplatí sa splniť takú požiadavku zákazníka, alebo je lepšie mať možnosť rozumne proti nemu vzniesť námietku a trvať na aplikácii ďalších obmedzení?

Permutácie a teória pravdepodobnosti.

Ešte častejšie vzniká v teórii pravdepodobnosti potreba spočítať počet možností. Pokračujme v knižnej téme ďalšou úlohou.

Problém 2.

Na poličke bolo 30 zväzkov. Dieťa zhodilo knihy z police a potom ich usporiadalo v náhodnom poradí. Aká je pravdepodobnosť, že on nie dať 1. a 2. zväzok vedľa seba?

Riešenie.

Najprv určíme pravdepodobnosť deja A, spočívajúceho v tom, že dieťa postavilo vedľa seba 1. a 2. zväzok.
Elementárnou udalosťou je určité usporiadanie kníh na poličke. Je zrejmé, že celkový počet zo všetkých elementárne udalosti sa budú rovnať celkovému počtu všetkých možných permutácií P 30=30!.
Počet elementárnych udalostí priaznivých pre udalosť A sa rovná počtu permutácií, v ktorých sú 1. a 2. zväzok vedľa seba. Uvažovali sme o takýchto permutáciách, riešiacich predchádzajúci problém, a dostali sme 2,29! permutácie.
Pravdepodobnosť je určená vydelením počtu priaznivých elementárnych udalostí počtom všetkých možných elementárnych udalostí:
P (A) = 2 29! / 30! = 2 29!/(29! 30) = 2/30 = 1/15.
Udalosť B - dieťa nie dajte 1. a 2. zväzok vedľa seba - oproti udalosti A, takže jeho pravdepodobnosť P (B) = 1 - P (A) = 1-1 / 15 = 14/15 = 0,9333
Odpoveď: 0,9333.

Poznámka: Ak nie je jasné, ako je možné zrušiť zlomky s faktoriálmi, nezabudnite, že faktoriál je krátka notácia výrobku. Vždy môže byť napísaný dlhý a preškrtnutý opakujúcim sa faktorom v čitateľovi a v menovateli.

Odpoveďou bolo číslo blízke jednej, čo znamená, že pri takom počte kníh je ťažšie omylom dať vedľa seba dva dané zväzky než nie.

Ubytovanie. Počítanie počtu umiestnení.

Teraz predpokladajme, že zákazník má veľa kníh a nie je možné všetky zmestiť na otvorené police. Jeho požiadavka je, aby ste vybrali určitý počet akýchkoľvek kníh a krásne ich umiestnili. Ukázalo sa to krásne alebo škaredé, je to vec vkusu zákazníka, t.j. chce znova vidieť všetky možnosti a rozhodnite sa sami. Našou úlohou je spočítať počet všetkých možných možností umiestnenia knihy, rozumne ho presvedčiť a zaviesť primerané obmedzenia.

Aby sme pochopili situáciu, najskôr predpokladajme, že „veľa“ je 5 kníh, že máme iba jednu poličku a že obsahuje iba 3 zväzky. Čo budeme robiť?
Vyberieme jednu z 5 kníh a dáme ju na prvé miesto v poličke. Môžeme to urobiť 5 spôsobmi. Teraz zostali na poličke dve miesta a zostali nám 4 knihy. Druhú knihu si môžeme vybrať 4 spôsobmi a priložiť k jednému z 5 možných prvých. Takýchto párov môže byť 5,4. Zostávajú 3 knihy a jedno miesto. Jednu z troch kníh je možné vybrať 3 spôsobmi a umiestniť vedľa jedného z možných 5 - 4 párov. Získate 5 · 4 · 3 rôznych trojčiat. To znamená, že existuje celkom niekoľko spôsobov, ako umiestniť 3 knihy z 5 5 · 4 · 3 = 60.

Obrázok ukazuje iba 4 možnosti umiestnenia zo 60 možných. Porovnajte obrázky. Upozorňujeme, že umiestnenia sa môžu navzájom líšiť buď len v poradí prvkov, ako v prvých dvoch skupinách, alebo v zložení prvkov, ako je uvedené v nasledujúcom texte.

Vzorec pre počet umiestnení.

Ubytovanie od n prvky od m(miesta) sa nazývajú také vzorky, ktoré, majúce m položky vybrané z počtu údajov n prvky sa navzájom líšia buď v zložení prvkov, alebo v poradí ich usporiadania.

Počet umiestnení od n na m označený A n m a je určený vzorcom
A n m = n·( n- 1) ( n- 2) ... ( n − m + 1) = n!/(n - m)!

Skúsme vypočítať pomocou tohto vzorca A n n, t.j. počet umiestnení od n na n.
A n n = n·( n-1) · ( n-2) ... ( n-n + 1) = n·( n-1) · ( n-2) ... 1 = n!
Preto A n n = P n = n!

Nie je prekvapujúce, že počet umiestnení od n na n Ukázalo sa, že sa rovná počtu permutácií n prvky, pretože na zostavenie umiestnení sme použili celý súbor prvkov, čo znamená, že sa už od seba nemôžu líšiť v zložení prvkov, len v poradí ich usporiadania, a to sú permutácie.

Problém 3.

Koľkými spôsobmi je možné usporiadať 15 zväzkov na polici, ak si vyberiete z 30 dostupných kníh?

Riešenie.

Podľa vzorca určte celkový počet umiestnení 30 prvkov z 15
A 30 15= 30 29 28 ... (30 –15 + 1) = 30 29 28 ... 16 = 202843204931727360000.
Odpoveď: 202843204931727360000.

Uverejní skutočné knihy? Veľa štastia! Spočítajte si, koľko životov bude potrebných na to, aby ste prešli všetkými možnosťami.

Problém 4.

Koľkými spôsobmi je možné usporiadať 30 kníh na dvoch policiach, ak každá z nich pojme iba 15 zväzkov?

Riešenie.

Metóda I.
Predstavme si, že prvú poličku naplníme rovnako ako v predchádzajúcej úlohe. Potom budú možnosti ubytovania od 30 kníh do 15 A 30 15= 30 29 28 ... (30 –15 + 1) = 30 29 28 ... 16.
A zakaždým, keď umiestnime knihy na prvú poličku, stále áno P 15= 15! spôsoby, akými môžeme usporiadať knihy na druhej poličke. Koniec koncov, pre druhú poličku máme 15 kníh, kde zostáva 15 miest, t.j. sú možné iba permutácie.
Spôsobov bude celkom A 30 15 P 15, v tomto prípade bude súčin všetkých čísel od 30 do 16 stále potrebné vynásobiť súčinom všetkých čísel od 1 do 15, dostanete súčin všetkých prirodzených čísel od 1 do 30, t.j. tridsať!
Metóda II.
Teraz si predstavme, že sme mali jednu dlhú policu s 30 miestami na sedenie. Položili sme naň všetkých 30 kníh a potom sme policu napílili na dve rovnaké časti, aby splnili podmienku problému. Koľko možností umiestnenia môže byť? Čo najviac permutácií z 30 kníh, t.j. P 30 = 30!
Odpoveď: 30!.

Nezáleží na tom, ako vyriešite matematický problém. Riešite to tak, ako si predstavujete svoje činy životná situácia... Aby ste aj tak dostali správnu odpoveď, je dôležité neodchyľovať sa od logiky.

Umiestnenie a teória pravdepodobnosti.

V teórii pravdepodobnosti sú problémy s umiestnením o niečo menej časté ako problémy s inými typmi vzoriek, pretože umiestnenia majú viac identifikačných znakov - poradie aj zloženie prvkov, a preto sú menej náchylné na náhodný výber.

Problém 5.

Polička s knihami obsahuje zbierku diel jedného autora v 6 zväzkoch. Knihy rovnakého formátu nie sú usporiadané v žiadnom konkrétnom poradí. Čitateľ si bez pozerania vezme 3 knihy. Aká je pravdepodobnosť, že vzal prvé tri diely?

Riešenie.

Udalosť A - čitateľ má prvé tri zväzky. Ak vezmeme do úvahy poradie výberu, mohol ich vziať 6 spôsobmi. (Toto sú permutácie troch prvkov P 3 = 3! = 1 2 3 = 6, ktorých zoznam je ľahké zapísať 123, 132, 213, 231, 312, 321.)
Počet priaznivých základných udalostí je teda 6.
Celkový počet možných elementárnych udalostí sa rovná počtu umiestnení od 6 do 3, t.j. A 6 3 = 6 ... (6−3 + 1) = 6 5 4 = 120.
P (A) = 6/120 = 1/20 = 0,05.
Odpoveď: 0,05.

Kombinácie. Počítanie počtu kombinácií.

A posledný prípad - všetky zákaznícke knihy sú rovnakej farby a rovnakej veľkosti, ale iba časť z nich je možné umiestniť na poličku. Zdá sa, že návrhár nemá vôbec žiadne problémy, vyberte si z celkového počtu toľko kníh, koľko potrebujete, a naaranžujte ich na poličku v žiadnom konkrétnom poradí, pretože knihy navonok nie sú na nerozoznanie. Ale líšia sa a výrazne! Tieto knihy sa líšia obsahom. A zákazníkovi možno nie je jedno, kde sú Shakespearove tragédie a kde sú detektívi Rexa Stouta, na otvorenej poličke alebo v skrini. Máme teda situáciu, keď je zloženie prvkov vzorky dôležité, ale poradie ich usporiadania nie je dôležité.

Na obrázku sú dva výbery zo „zozbieraných diel jedného autora v 5 zväzkoch“. Prvý poteší zákazníka viac, ak si často prečíta rané diela tohto autora umiestnené v prvých troch zväzkoch, druhý - ak sa častejšie odvoláva na neskoršie diela umiestnené v posledných zväzkoch. Obe skupiny vyzerajú rovnako krásne (alebo rovnako škaredo) a je jedno, či sa skupina nachádza ako 123 alebo ako 321 ...

Vzorec pre počet kombinácií.

Nazýva sa neusporiadaný výber od n prvky od m a označil S n m.
Počet kombinácií je určený vzorcom S n m = n!/(n- m)! / m!

V tomto vzorci sú dva delitelia a symbol „ / „čo je pre webové stránky priateľskejšie. Rozdelenie však možno označiť aj dvojbodkou“ : "alebo vodorovná čiara" −−− ". V druhom prípade vzorec vyzerá ako bežná frakcia, v ktorom postupné delenie predstavujú dva faktory v menovateli ... Pre tých, ktorí lepšie chápu zlomkové zobrazenie, sú všetky vzorce duplikované na začiatku a na úplnom konci stránky. Pri analýze riešení problémov porovnajte môj záznam s tým, na ktorý ste zvyknutí.
Navyše všetky faktory a delitele v tomto vzorci sú súčinom po sebe nasledujúcich prirodzených čísel, takže zlomok je možné dobre znížiť, ak je napísaný podrobne. Podrobnú redukciu problémov však vynechávam, je ľahké sa o tom presvedčiť sami.

Je zrejmé, že pre rovnaké počiatočné sady od n prvkov a identických veľkostí vzorky (podľa m prvkov) počet kombinácií musí byť menší ako počet umiestnení. Pri výpočte umiestnení pre každú vybranú skupinu skutočne berieme do úvahy aj všetky permutácie vybratej skupiny m prvky a pri výpočte kombinácií sa neberú do úvahy permutácie: C n m = A n m/Popoludnie = n!/(n - m)!/m!

Problém 6.

Koľkými spôsobmi môžete usporiadať 15 zväzkov na poličke, ak si ich vyberiete z navonok nerozlíšiteľných 30 dostupných kníh?

Riešenie.

Tento problém riešime v kontexte práce interiérového dizajnéra, takže na poradí 15 zdanlivo rovnakých kníh vybraných na poličke nezáleží. Podľa vzorca je potrebné určiť celkový počet kombinácií 30 prvkov z 15
S 30 15 = 30! /(30 − 15)!/15! = 155117520.
Odpoveď: 155117520.

Problém 7.

Koľkými spôsobmi je možné na dve poličky poskladať 30 zdanlivo nerozoznateľných kníh, ak každá z nich pojme iba 15 zväzkov?

Ak znova odpovieme na túto otázku z pohľadu interiérového dizajnéra, potom je poradie kníh na každej poličke irelevantné. Ale zákazníkovi môže, ale nemusí byť jedno, ako sú knihy rozdelené medzi regály.
1) Ak sú napríklad obe police vedľa seba, obe sú otvorené, obe v rovnakej výške, potom zákazník môže povedať, že na tom nezáleží. Potom je odpoveď zrejmá - 1 spôsob, pretože usporiadanie používa celú sadu 30 kníh a neberú sa do úvahy žiadne permutácie.
2) Ale keď je jedna z políc príliš vysoká, je pre zákazníka dôležité, ktoré knihy sa na nej nachádzajú. V tomto prípade bude odpoveď rovnaká ako v predchádzajúcom probléme - 155117520 spôsobov, pretože prvú poličku naplníme kombinovaným výberom od 30 do 15 a na druhú umiestnime zvyšných 15 kníh bez toho, aby sme zohľadnili permutácie.

Existujú teda také formulácie problémov, že odpovede môžu byť nejednoznačné. Na presné riešenie potrebujete Ďalšie informácie ktoré zvyčajne dostávame z kontextu situácie. Tvorcovia úloh k skúškam spravidla neumožňujú dvojitú interpretáciu stavu problému, formulujú ho o niečo dlhšie. Ak však máte pochybnosti, najlepšie je opýtať sa svojho učiteľa.

Kombinácie a teória pravdepodobnosti.

V teórii pravdepodobnosti sú najbežnejšie problémy s kombináciou, pretože zoskupovanie bez poradia je dôležitejšie práve pre nerozlíšiteľné prvky. Ak sa niektoré prvky od seba výrazne líšia, je ťažké ich náhodne vybrať, existujú pravidlá pre nenáhodný výber.

Problém 8.

Polička s knihami obsahuje zbierku diel jedného autora v 6 zväzkoch. Knihy sú podobne zdobené a usporiadané v žiadnom konkrétnom poradí. Čitateľ vyberie 3 knihy náhodne. Aká je pravdepodobnosť, že vzal prvé tri diely?

Riešenie.

Udalosť A - čitateľ má prvé tri zväzky. Ide o 1., 2. a 3. zväzok. Bez ohľadu na poradie, v ktorom knihy vyberal, ale iba podľa konečného výsledku, ich mohol brať jedným spôsobom. Počet priaznivých základných udalostí je 1.
Celkový počet možných elementárnych udalostí sa rovná počtu skupín od 6 do 3 vytvorených bez ohľadu na poradie prvkov v skupine, t.j. rovná počtu kombinácií S 6 3= 6! / 3! / (6 - 3)! = 4 5 6 / (1 2 3) = 4 5 = 20.
P (A) = 1/20 = 0,05.
Odpoveď: 0,05.

Porovnajte tento problém s problémom 5 (pri umiestnení). Oba problémy majú veľmi podobné podmienky a veľmi podobné odpovede. V zásade je to rovnaká každodenná situácia a podľa toho aj rovnaká úloha, ktorú je možné interpretovať tak či onak. Hlavná vec je, že pri výpočte elementárnych udalostí, priaznivých aj všetkých možných, dochádza k rovnakému chápaniu situácie.

Záverečné poznámky.

Na prísne odvodenie všetkých vzorcov (ktoré som tu neuviedol) použite dve základné pravidlá kombinatoriky:

Pravidlo násobenia (pravidlo " a"). Podľa nej, ak sa dá vybrať prvok A n spôsobov a pre akýkoľvek výber A je možné vybrať prvok B. m spôsobov, potom dvojica A a B je možné zvoliť n m spôsoby.

Toto pravidlo zovšeobecňuje na ľubovoľnú dĺžku sekvencie.

Pravidlo sčítania (pravidlo " alebo"). Uvádza, že ak je možné zvoliť prvok A. n spôsobov a prvok B je možné vybrať m spôsobov, potom zvoľte A. alebo B môže n + m spôsoby.

Tieto pravidlá sú potrebné aj pri riešení problémov.

Koncept faktoriál platí aj pre nulu: 0! = 1 , pretože sa verí, že prázdnu súpravu je možné objednať jedinečným spôsobom.

Výpočet faktoriálov veľkých čísel priamym násobením na kalkulačke je veľmi dlhý a veľmi veľké čísla - dokonca ani na počítači nie sú rýchle. Ako ste sa s tým vysporiadali, kým nevznikli počítače a kalkulačky? Na začiatku 18. storočia J. Stirling a nezávisle na ňom A. Moivre získali vzorec na približný výpočet faktoriálov, ktorý je tým presnejší, čím je číslo väčšie. n... Tento vzorec sa teraz nazýva podľa Stirlingovho vzorca:

Posledná výzva.

Pri riešení problémov v teórii pravdepodobnosti pomocou kombinatorických metód je potrebné starostlivo analyzovať navrhovanú situáciu, aby ste vybrali správny typ vzorky. Skúste to s nasledujúcim problémom. Vyriešte to, porovnajte odpoveď a potom kliknutím na tlačidlo otvorte moje riešenie.

Problém 9.

Z akvária, v ktorom 6 kaprov a 4 kapry, ulovilo 5 rýb sieťou. Aká je pravdepodobnosť, že medzi nimi budú 2 kapry a 3 kapry?

Riešenie.

Základnou udalosťou je „skupina 5 rýb v sieti“. Udalosť A - „medzi 5 ulovenými rybami boli 3 kapry a 2 kapry “.
Nechaj byť n- celkový počet všetkých možných základných udalostí, sa rovná počtu spôsobov, ako zoskupiť 5 rýb. Celkový počet rýb v akváriu je 6 + 4 = 10. V procese chytania sieťou sú ryby navonok nerozoznateľné. (Nevieme, či sme chytili rybu s názvom Baška alebo Koska. Navyše, kým sme sieť nevytiahli a nepozreli do nej, nevieme ani, či ide o kapra alebo kapra.) „Ulovte teda 5 rýb z 10. „znamená vybrať typ kombinácie od 10 do 5.
n = S 10 5 = 10!/5!/(10 - 5)!
Keď vytiahneme sieť a pozrieme sa do nej, môžeme určiť, či je to priaznivý výsledok alebo nie, t.j. Úlovok pozostáva z dvoch skupín - 2 kapry a 3 kapry?
Skupinu kaprov možno vytvoriť výberom zo 6 kaprov po 2. A je jedno, ktorý z nich vliezol do siete ako prvý a kto ako druhý. toto je vzorka typu kombinácie 6 až 2. Označme celkový počet takýchto vzoriek m 1 a vypočítať to.
m 1 = S 6 2 = 6!/2!/(6 - 2)!
Podobne je celkový počet možných skupín 3 kaprov určený počtom kombinácií od 4 do 3. Označme to m 2.
m 2 = S 4 3 = 4!/3!/(4 - 3)!
Skupiny kaprov a kaprov sa tvoria v sieti navzájom nezávisle, preto na výpočet počtu elementárnych udalostí priaznivých pre udalosť A používame pravidlo násobenia („a“ -rule) kombinatoriky. Celkový počet priaznivých základných udalostí
m = m 1 m 2 = S 6 2· S 4 3
Pravdepodobnosť udalosti A je určená vzorcom P (A) = m / n = С 6 2 С 4 3 / С 10 5
Nahradíme všetky hodnoty v tomto vzorci, napíšeme faktoriály, zlomok zrušíme a dostaneme odpoveď:
P (A) = 6! 4! 5! (10 - 5)! / 2! / (6 - 2)! / 3! / (4 - 3)! / 10! = 5/21 ≈ 0,238

Poznámky.
1) Kombinácie sa zvyčajne nachádzajú v úlohách, kde nie je dôležitý proces formovania skupiny, ale dôležitý je iba výsledok. U Sazana Baskeho nezáleží na tom, či trafil sieť prvý alebo posledný, ale je pre neho veľmi dôležité, v ktorej skupine skončil - medzi tými v sieti, alebo medzi tými na slobode.
2) Upozorňujeme, že používame „i-pravidlo“, pretože zväzok „a“ je priamo v popise udalosti A, pre ktorú potrebujeme vypočítať pravdepodobnosť kombinovaného úlovku dvoch skupín. Aplikujeme ho však až potom, čo sme sa presvedčili o nezávislosti vzoriek. Kapor, ktorý pláva až k sieti, tam v skutočnosti nemôže spočítať svojich bratov a povedať kaprovi: „Si na rade, už sú naši dvaja.“ A bude kapor súhlasiť, že vylezie do siete, aby kapra potešil? Ak by sa však dokázali dohodnúť, potom by toto pravidlo už neplatilo. Bolo by potrebné obrátiť sa na koncept podmienenej pravdepodobnosti.

Odpoveď: 0,238.

Zobraziť riešenie.

Ak ste absolvent školy a budete používať USE, potom sa po preštudovaní tejto časti vráťte (10 pre základné a 4 pre profilové úrovne USE 2020 v matematike), ktoré je možné vyriešiť pomocou kombinatorických prvkov a bez neho (pre napríklad hod mincou). Ktorý z možných spôsobov riešenia problému máte teraz najradšej?

A ak si chcete trochu viac precvičiť riešenie kombinatorických problémov, aby ste sa naučili rýchlo určiť typ výberu a nájsť potrebné vzorce, potom prejdite na stránku

Priatelia! Keďže mám tento mŕtvy zápisník, pýtam sa ho na problém, s ktorým včera zápasili traja fyzici, dvaja ekonómovia, jedna polytechnická univerzita a jeden humanista. Zlomili sme si celý mozog a neustále dosahujeme rôzne výsledky. Možno sú medzi vami programátori a matematickí géniovia, okrem toho je úloha spravidla školská a veľmi jednoduchá, jednoducho neodvodíme vzorec. Pretože sme prestali študovať presné vedy a namiesto toho z nejakého dôvodu píšeme knihy a kreslíme obrázky. Prepáč.

Takže pozadie.

Dostal som novú bankovú kartu a ako obvykle som ľahko uhádol jej PIN kód. Nie však za sebou. Myslím, povedzme, PIN kód bol 8794 a nazval som ho 9748. To znamená, že víťazím uhádol všetky čísla ktoré boli obsiahnuté v tomto štvorcifernom čísle. No áno, nie samotné číslo, ale len jeho zložky majúčudoval sa. Ale všetky čísla sú správne! POZNÁMKA - Konal som náhodne, to znamená, že som už nemusel usporiadať už známe čísla v správnom poradí, konal som len v duchu: tu sú pre mňa neznáme štyri čísla a verím, že medzi nimi môžu byť 9, 7, 4 a 8 a ich poradie nie je dôležité. Hneď sme sa čudovali koľko možností som vôbec mal(asi aby som pochopil, aké je to cool, že som to jednoducho zobral a uhádol). To znamená, z koľkých kombinácií štyroch čísel som mal na výber? A potom sa, prirodzene, začalo peklo. Celý večer nám explodovali hlavy a v dôsledku toho mal každý úplne iné odpovede! Dokonca som začal písať všetky tieto kombinácie do zošita za sebou, keď sa zvyšovali, ale pri štyristo som zistil, že ich je viac ako štyristo (v každom prípade to vyvrátilo odpoveď fyzika Threcha, ktorý uistil ja, že bolo štyristo kombinácií, ale stále to nebolo úplne jednoznačné) - a vzdal to.

Vlastne, podstata otázky. Aká je pravdepodobnosť uhádnutia (v akomkoľvek poradí) štyroch čísel obsiahnutých v štvorcifernom čísle?

Alebo nie, preformulujeme sa (som humanista, odpusť mi, aj keď som mal vždy veľkú slabosť na matematiku), aby to bolo jasnejšie a jasnejšie. koľko neopakujúce sa kombinácie čísel sú obsiahnuté v rade radových čísiel od 0 do 9999? ( Nezamieňajte si to s otázkou „koľko kombinácií neopakujúce sačíslice “!!! čísla sa môžu opakovať! Myslím, že 2233 a 3322 sú v tomto prípade rovnaká kombinácia !!).

Alebo konkrétnejšie. Potrebujem štyrikrát uhádnuť jedno číslo z desiatich. Nie však za sebou.

No, alebo niečo iné. Vo všeobecnosti musíte zistiť, koľko možností som mal pre číselnú kombináciu, z ktorej bol vytvorený PIN kód karty. Pomoc, dobrí ľudia! Pomáhajte, prosím, nezačnite hneď písať, že týchto 9 999 možností je(včera to najskôr napadlo každému), pretože je to nezmysel - koniec koncov, z perspektívy, ktorá nás znepokojuje, sú číslo 1234, číslo 3421, číslo 4312 a tak ďalej rovnaký! Áno, čísla sa môžu opakovať, pretože existuje PIN kód 1111 alebo napríklad 0007. Namiesto PIN kódu môžete uviesť číslo auta. Povedzme si, aká je pravdepodobnosť uhádnutia všetkých číslic, ktoré tvoria číslo auta? Alebo, aby som celkom odstránil teóriu pravdepodobnosti - koľko numerických kombinácií som musel vybrať?

Podporte svoje odpovede a úvahy niekoľkými presnými vzorcami, pretože včera sme sa včera takmer zbláznili. Vopred veľká vďaka!

P.S. Jeden múdry muž, programátor, výtvarník a vynálezca, veľmi správne navrhol správne riešenie problému a poskytol mi niekoľko minút skvelej nálady: „ riešenie problému je toto: má obsedantno-kompulzívnu poruchu, liečba znie: vydať sa a zhlukovať paradajky. Viac by ma na jej mieste znepokojovala otázka „aká je pravdepodobnosť“, ale otázka „všímam si všetky tieto čísla“? Vo všeobecnosti nie je ani čo dodať :)

Nasledujúca kalkulačka je navrhnutá na generovanie všetkých kombinácií n až m prvkov.
Počet takýchto kombinácií je možné vypočítať pomocou kalkulačky kombinatorických prvkov. Permutácie, umiestnenie, kombinácie.

Popis generačného algoritmu pod kalkulačkou.

Algoritmus

Kombinácie sú generované v lexikografickom poradí. Algoritmus pracuje s radovými indexmi prvkov sady.
Uvažujme o príklade algoritmu.
Pre jednoduchosť zvážte súbor piatich prvkov, ktorých indexy začínajú 1, konkrétne 1 2 3 4 5.
Je potrebné vygenerovať všetky kombinácie veľkosti m = 3.
Najprv sa inicializuje prvá kombinácia danej veľkosti m - indexy vo vzostupnom poradí
1 2 3
Ďalej sa skontroluje posledný prvok, to znamená i = 3. Ak je jeho hodnota menšia ako n - m + i, zvýši sa o 1.
1 2 4
Posledný prvok sa znova skontroluje a opäť sa zvýši.
1 2 5
Teraz je hodnota prvku rovná maximálnemu možnému: n - m + i = 5 - 3 + 3 = 5, skontroluje sa predchádzajúci prvok s i = 2.
Ak je jeho hodnota menšia ako n - m + i, potom sa zvýši o 1 a pre všetky nasledujúce prvky sa hodnota rovná hodnote predchádzajúceho prvku plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Potom znova nasleduje kontrola i = 3.
1 3 5
Potom - skontrolujte, či i = 2.
1 4 5
Potom príde obrat i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
A ďalej,
2 3 5
2 4 5
3 4 5 - posledná kombinácia, pretože všetky jej prvky sú rovné n - m + i.

Napriek dôležitej úlohe, ktorú PINy zohrávajú vo svetovej infraštruktúre, neprebehol žiadny akademický výskum o tom, ako si ľudia PIN vlastne vyberajú.

Vedci z University of Cambridge Sören Preibusch a Ross Anderson situáciu napravili pomocou prvej kvantitatívnej analýzy obtiažnosti uhádnutia 4-miestneho kódu PIN banky.

Pomocou údajov o úniku hesiel z nebankových zdrojov a online dotazníkov vedci zistili, že užívatelia berú výber PIN kódov oveľa vážnejšie ako výber hesiel pre webové stránky: väčšina kódov obsahuje takmer náhodnú množinu čísel. Napriek tomu medzi počiatočnými údajmi existujú jednoduché kombinácie aj narodeniny - to znamená, že pri troche šťastia útočník vytúžený kód jednoducho uhádne.

Východiskovým bodom výskumu bola sada 4-ciferných sekvencií hesiel z databázy RockYou (1,7 milióna) a databáza 200-tisíc PIN kódov z programu zámku obrazovky iPhone (databázu poskytol vývojár aplikácie Daniel Amitay). Na základe týchto údajov sa v grafoch objavujú zaujímavé vzorce-dátumy, roky, opakujúce sa čísla a dokonca aj kódy PIN s číslom končiacim na 69. Na základe týchto pozorovaní vedci vytvorili lineárny regresný model, ktorý odhaduje popularitu každého kódu PIN v závislosti od 25 faktorov, ako napríklad či je kód dátumom DDMM, či ide o vzostupnú postupnosť atď. Tieto všeobecné podmienky spĺňa 79% a 93% kódov PIN v každej zo sád.

Používatelia si teda vyberajú 4-miestne kódy iba na základe niekoľkých jednoduchých faktorov. Ak by boli bankové kódy PIN zvolené týmto spôsobom, 8-9% z nich by sa dalo uhádnuť iba na tri pokusy! Ale, samozrejme, ľudia sú oveľa pozornejšie na bankové kódy. Keďže neexistuje žiadny rozsiahly súbor skutočných bankových údajov, vedci urobili rozhovor s viac ako 1 300 ľuďmi, aby posúdili, ako sa skutočné kódy PIN líšia od tých, ktoré už boli skontrolované. Vzhľadom na špecifiká štúdie sa respondenti pýtali nie na samotné kódy, ale iba na ich súlad s ktorýmkoľvek z vyššie uvedených faktorov (nárast, formát DDMM atď.).

Ukázalo sa, že ľudia sú pri výbere bankových PIN kódov skutočne oveľa opatrnejší. Asi štvrtina opýtaných používa náhodný PIN vygenerovaný bankou. Viac ako tretina si vyberie svoj PIN pomocou starého telefónneho čísla, študentského identifikačného čísla alebo inej sady čísel, ktorá vyzerá náhodne. Podľa získaných výsledkov 64% držiteľov kariet používa pseudonáhodný PIN kód, čo je oveľa viac ako 23-27% v predchádzajúcich experimentoch s nebankovými kódmi. Ďalších 5% používa číselný vzor (napríklad 4545) a 9% uprednostňuje vzor klávesnice (napríklad 2684). Útočník so šiestimi pokusmi (tri s bankomatom a tri s platobným terminálom) má vo všeobecnosti menej ako 2% šancu uhádnuť PIN karty niekoho iného.

Faktor	Príklad	RockYou	iPhone	Prieskum
Termíny
DDMM	2311	5.26	1.38	3.07
DMYY	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
MMYY	0683	0.67	0.20	0.94
RRRR	1984	33.39	7.12	4.95
Celkom		58.57	24.51	22.76
Vzor klávesnice
priľahlé	6351	1.52	4.99	-
námestie	1425	0.01	0.58	-
rohy	9713	0.19	1.06	-
kríž	8246	0.17	0.88	-
diagonálna čiara	1590	0.10	1.36	-
horizontálna čiara	5987	0.34	1.42	-
slovo	5683	0.70	8.39	-
zvislá čiara	8520	0.06	4.28	-
Celkom		3.09	22.97	8.96
Digitálny vzor
končí o 69	6869	0.35	0.57	-
iba čísla 0-3	2000	3.49	2.72	-
iba čísla 0-6	5155	4.66	5.96	-
opakujúce sa páry	2525	2.31	4.11	-
identické čísla	6666	0.40	6.67	-
zostupná postupnosť	3210	0.13	0.29	-
zvyšujúca sa postupnosť	4567	3.83	4.52	-
Celkom		15.16	24.85	4.60
Náhodná množina čísel		23.17	27.67	63.68

Všetko by bolo dobré, ale bohužiaľ, značná časť respondentov (23%) si ako dátum zvolilo PIN kód a takmer tretina z nich používa svoj dátum narodenia. To je podstatný rozdiel, pretože takmer všetci (99%) respondentov odpovedali, že v peňaženkách s bankovými kartami uchovávajú rôzne identifikačné karty s týmto dátumom. Ak útočník pozná narodeniny držiteľa karty, potom so správnym prístupom stúpne pravdepodobnosť uhádnutia PINu až na 9%.

100 najpopulárnejších PIN kódov

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S. V praxi je samozrejme pre útočníka oveľa jednoduchšie špehovať váš PIN, ako ho uhádnuť. Môžete sa však tiež chrániť pred vykuknutím - dokonca, ako sa zdá, v beznádejnej situácii:

KOMBINÁTORY

Kombinatorika je odvetvie matematiky, ktoré študuje problémy výberu a usporiadania prvkov z určitej základnej množiny v súlade s danými pravidlami. Na výpočet pravdepodobnosti sa v teórii pravdepodobnosti používajú kombinatorické vzorce a princípy náhodné udalosti a podľa toho aj získanie distribučných zákonov náhodné premenné... To zase umožňuje študovať vzorce hromadných náhodných javov, čo je veľmi dôležité pre správne pochopenie štatistických vzorcov prejavujúcich sa v prírode a technológii.

Pravidla sčítania a násobenia v kombinatorike

Pravidlo súčtu. Ak sú dve akcie A a B navzájom sa vylučujúce a akciu A je možné vykonať m spôsobmi a B - n spôsobov, potom ktorúkoľvek z týchto akcií (buď A alebo B) je možné vykonať n + m spôsobmi.

Príklad 1.

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi je možné priradiť jedného sprievodcu?

Riešenie

Do služby môže byť zaradený buď chlapec alebo dievča, t.j. služobným dôstojníkom môže byť ktorýkoľvek zo 16 chlapcov alebo akékoľvek z 10 dievčat.

Podľa pravidla súčtu zistíme, že jedného sprievodcu možno priradiť 16 + 10 = 26 spôsobov.

Pravidlo produktu. Nech je potrebné vykonať k krokov za sebou. Ak prvú akciu možno vykonať n 1 spôsobmi, druhú akciu n 2 spôsobmi, tretiu n n 3 spôsobmi a tak ďalej až do k -tej akcie, ktorú je možné vykonať n -tými spôsobmi, potom všetkých k akcií spoločne je možné vykonané:

spôsoby.

Príklad 2.

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi je možné priradiť dvoch služobníkov?

Riešenie

Ako prvého strážcu možno priradiť buď chlapca alebo dievča. Pretože V triede študuje 16 chlapcov a 10 dievčat, potom môžete prvého dôstojníka vymenovať 16 + 10 = 26 spôsobov.

Potom, čo sme vybrali prvého sprievodcu, môžeme zo zvyšných 25 ľudí vybrať druhého, t.j. Na 25 spôsobov.

Podľa teórie o násobení je možné vybrať dvoch sprievodcov v 26 * 25 = 650 spôsoboch.

Kombinácie bez opakovania. Kombinácie s opakovaniami

Klasickým problémom kombinatoriky je problém počtu kombinácií bez opakovaní, ktorých obsah možno vyjadriť otázkou: koľko spôsoby môcť vyberte m od n rôzne predmety ?

Príklad 3.

Musíte si vybrať 4 z 10 rôznych kníh, ktoré sú k dispozícii ako darček. Koľkými spôsobmi to môžete urobiť?

Riešenie

Musíme vybrať 4 z 10 kníh a na poradí výberu nezáleží. Preto musíte nájsť počet kombinácií 10 prvkov zo 4:

.

Uvažujme o probléme počtu kombinácií s opakovaniami: existuje r identických predmetov každého z n rôznych typov; koľko spôsoby môcť vyberte m () od z nich (n * r) položiek?

.

Príklad 4.

V cukrárni sa predávali 4 druhy koláčov: napoleóny, zákusky, pieskové a lístkové cesto. Koľkými spôsobmi si môžete kúpiť 7 koláčov?

Riešenie

Pretože medzi 7 koláčmi môžu byť koláče rovnakého druhu, potom počet spôsobov, ako si môžete kúpiť 7 koláčov, je určený počtom kombinácií s opakovaním od 7 do 4.

.

Umiestnenia bez opakovaní. Umiestnenia s opakovaniami

Klasickým problémom kombinatoriky je problém počtu umiestnení bez opakovaní, ktorých obsah možno vyjadriť otázkou: koľko spôsoby môcť vyberte a miesto na som iný Miesta m od n rôzne položky?

Príklad 5.

Niektoré noviny majú 12 strán. Na stránky týchto novín je potrebné umiestniť štyri fotografie. Koľkými spôsobmi to môžete urobiť, ak by žiadna novinová stránka nemala obsahovať viac ako jednu fotografiu?

Riešenie.

Pri tejto úlohe nevyberáme len fotografie, ale umiestňujeme ich na určité strany novín a každá strana novín by nemala obsahovať viac ako jednu fotografiu. Problém sa teda redukuje na klasický problém určovania počtu umiestnení bez opakovania 12 prvkov, po 4 prvky:

4 fotografie na 12 stranách je teda možné usporiadať 11880 spôsobmi.

Klasickým problémom kombinatoriky je tiež problém počtu umiestnení s opakovaním, ktorých obsah možno vyjadriť otázkou: koľko spôsoby môcť tybhostiteľ a miesto na som iný Miesta m od n položiek,smedzi ktoré existuje rovnaký?

Príklad 6.

Chlapcovi zostali zo sady na stolnú hru pečiatky s číslami 1, 3 a 7. Rozhodol sa pomocou týchto pečiatok dať na všetky knihy päťciferné čísla - zostaviť katalóg. Koľko rôznych päťciferných čísel môže chlapec vyrobiť?

Permutácie bez opakovaní. Permutácie s opakovaniami

Klasickým problémom kombinatoriky je problém počtu permutácií bez opakovania, ktorých obsah je možné vyjadriť otázkou: koľko spôsoby môcť miesto n rôzne položky na n rôzne Miesta?

Príklad 7.

Koľko štvorpísmenových „slov“ je možné vyvodiť z písmen slova „manželstvo“?

Riešenie

Obecná populácia má 4 písmená slova „manželstvo“ (b, p, a, k). Počet „slov“ je určený permutáciami týchto 4 písmen, tj.

V prípade, že medzi vybranými n prvkami sú rovnaké prvky (výber s návratom), problém s počtom permutácií s opakovaním možno vyjadriť otázkou: koľkými spôsobmi môžete zmeniť usporiadanie n položiek umiestnených na n rôznych miestach ak medzi n položkami existuje k rôznych typov (k< n), т. е. есть одинаковые предметы.

Príklad 8.

Koľko rôznych kombinácií písmen môžete vytvoriť z písmen slova „Mississippi“?

Riešenie

K dispozícii je 1 písmeno „m“, 4 písmená „i“, 3 písmená „c“ a 1 písmeno „p“, celkom 9 písmen. Preto počet permutácií s opakovaniami je

POZADIE SEKCIE „KOMBINÁTORY“

Všetkých N prvkov a žiadny sa neopakuje, potom je to problém počtu permutácií. Riešenie je jednoduché. Na prvom mieste v rade môže byť ktorýkoľvek z N prvkov, preto sa získa N variantov. Na druhom mieste - ktokoľvek, okrem toho, ktorý už bol použitý na prvé miesto. Preto pre každý z už nájdených N variantov existuje (N - 1) variant druhého miesta a celkový počet kombinácií sa stáva N * (N - 1).
To isté sa môže zopakovať pre ostatné prvky série. Na úplne posledné miesto zostáva iba jedna možnosť - posledný zostávajúci prvok. U predposledného existujú dve možnosti a podobne.
Preto sa pre sériu N neopakujúcich sa prvkov možných permutácií rovná súčinu všetkých celých čísel od 1 do N. Tento súčin sa nazýva faktoriál čísla N a označuje sa N! (znie „en factorial“).

V predchádzajúcom prípade sa počet možných prvkov a počet miest v rade zhodoval a ich počet sa rovnal N. Ale situácia je možná, keď je v rade menej miest, ako je možných prvkov. Inými slovami, počet prvkov vo vzorke sa rovná nejakému číslu M a M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Najprv môže byť potrebné spočítať celkový počet možných spôsobov, ktorými je možné rad M prvkov z N. usporiadať za sebou. Takéto metódy sa nazývajú umiestnenia.
Za druhé, výskumníka môže zaujímať počet spôsobov, ktorými je možné vybrať prvky M z N. V tomto prípade už nie je poradie prvkov dôležité, ale akékoľvek dve možnosti sa musia navzájom líšiť najmenej o jeden prvok. . Takéto metódy sa nazývajú kombinácie.

Na zistenie počtu umiestnení nad M prvkami z N je možné použiť rovnaké zdôvodnenie ako v prípade permutácií. Prvým miestom tu môže byť stále N prvkov, druhé (N - 1) atď. Ale pre posledné miesto sa počet možných možností nerovná jednej, ale (N - M + 1), pretože keď je umiestnenie dokončené, stále budú (N - M) nepoužité prvky.
Počet umiestnení nad M prvkov z N sa teda rovná súčinu všetkých celých čísel od (N - M + 1) do N, alebo, čo je rovnaké, k podielu N! / (N - M)!

Je zrejmé, že počet kombinácií M prvkov z N bude menší ako počet umiestnení. Pre každú možnú kombináciu existuje M! možné umiestnenia v závislosti od poradia prvkov tejto kombinácie. Preto, aby ste našli toto číslo, musíte rozdeliť počet umiestnení M prvkov z N na N!. Inými slovami, počet kombinácií M prvkov z N je rovný N! / (M! * (N - M)!).

Kombinatorika je odvetvie matematiky, ktoré študuje otázky o tom, koľko rôznych kombinácií je možné za určitých podmienok vytvoriť z daných predmetov. Základy kombinatoriky sú veľmi dôležité pre hodnotenie pravdepodobností náhodných udalostí, pretože sú to oni, ktorí umožňujú vypočítať zásadne možný počet rôznych scenárov vývoja udalostí.

Základný vzorec kombinatoriky

Nech je k skupín prvkov, a i-tá skupina pozostáva z n i prvkov. Vyberme jednu položku z každej skupiny. Potom je celkový počet N spôsobov, ktorými je možné takúto voľbu vykonať, určený pomerom N = n 1 * n 2 * n 3 * ... * n k.

Príklad 1. Vysvetlíme 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 môžete vytvoriť z týchto dvoch skupín, aby ste sa spojili s jedným prvkom z každej skupiny? Predpokladajme, že sme vzali prvý prvok z prvej skupiny a bez zmeny sme prešli všetkými možnými pármi a zmenili sme iba prvky z druhej skupiny. Také páry pre tento prvok môžu byť n 2. Potom vezmeme druhý prvok z prvej skupiny a tiež preň vytvoríme všetky možné páry. Takýchto párov bude tiež n 2. Pretože v prvej skupine je iba n 1 prvkov, bude n 1 * n 2 možných možností.

Príklad 2. Koľko trojciferných párnych čísel je možné vytvoriť z číslic 0, 1, 2, 3, 4, 5, 6, ak sa čísla dajú opakovať?
Riešenie: n 1 = 6 (pretože ako prvú číslicu môžete vziať akúkoľvek číslicu od 1, 2, 3, 4, 5, 6), n 2 = 7 (pretože ako druhú číslicu môžete vziať akúkoľvek číslicu od 0, 1, 2 , 3, 4, 5, 6), n 3 = 4 (pretože ako tretiu číslicu môžete vziať akékoľvek číslo od 0, 2, 4, 6).
Takže N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.

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á voľba je z tej istej skupiny a prvok po výbere sa vráti do skupiny. Potom sa počet všetkých spôsobov výberu rovná n k. Tento spôsob voľby v kombinatorike sa nazýva odber vzoriek s návratom.

Príklad 3. Koľko zo všetkých štvorciferných čísel je možné skladať z číslic 1, 5, 6, 7, 8?
Riešenie. Existuje päť možností pre každú číslicu štvorciferného čísla, takže N = 5 * 5 * 5 * 5 = 5 4 = 625.

Uvažujme množinu pozostávajúcu z n prvkov. Z kombinatorického hľadiska sa táto množina nazýva bežná populácia.

Počet umiestnení n prvkov, m každý

Definícia 1. Ubytovanie od n prvky od m v kombinatorike, akékoľvek objednaná sada od m rôzne prvky vybrané z bežnej populácie v n prvky.

Príklad 4. Rôzne umiestnenia troch prvkov (1, 2, 3) z dvoch budú sady (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2). Umiestnenia sa môžu navzájom líšiť v prvkoch aj v poradí.

Počet umiestnení v kombinatorike je označený ako A n m a je vypočítaný podľa vzorca:

Komentár: n! = 1 * 2 * 3 * ... * n (čítaj: „ento-faktoriál“), navyše sa predpokladá, že 0! = 1.

Príklad 5... Koľko dvojciferných čísel obsahuje rôzne a nepárne desiatky a čísla?
Riešenie: od existuje päť nepárnych číslic, a to 1, 3, 5, 7, 9, potom sa táto úloha zredukuje na výber a umiestnenie dvoch z piatich rôznych číslic na dve rôzne polohy, t.j. uvedené čísla budú:

Definícia 2. Kombinácia od n prvky od m v kombinatorike, akékoľvek neusporiadaná sada od m rôzne prvky vybrané z bežnej populácie v n prvky.

Príklad 6... Pre súpravu (1, 2, 3) sú kombinácie (1, 2), (1, 3), (2, 3).

Počet kombinácií n prvkov podľa m

Počet kombinácií je označený ako C n m a je vypočítaný podľa vzorca:

Príklad 7. Koľkými spôsobmi si môže čitateľ vybrať dve knihy zo šiestich dostupných?

Riešenie: Počet spôsobov sa rovná počtu kombinácií šiestich kníh po dvoch, t.j. rovná sa:

Permutácie n prvkov

Definícia 3. Permutácia od n Prvky sa nazývajú akékoľvek objednaná sada tieto prvky.

Príklad 7a. Všetky možné permutácie množiny pozostávajúcej z troch prvkov (1, 2, 3) sú: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2).

Počet rôznych permutácií n prvkov je označený P n a je vypočítaný podľa vzorca P n = n!

Príklad 8. Koľkými spôsobmi môže byť sedem kníh od rôznych autorov usporiadaných v jednom rade na poličke?

Riešenie: tento problém sa týka počtu permutácií sedem rôzne knihy... Existuje P 7 = 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040 spôsobov usporiadania kníh.

Diskusia. Vidíme, že počet možných kombinácií sa dá spočítať podľa rôzne pravidlá(permutácie, kombinácie, umiestnenie) a výsledok bude iný, pretože princíp počítania a samotné vzorce sú odlišné. Pri starostlivom pohľade na definície môžete vidieť, že výsledok závisí od viacerých faktorov súčasne.

Po prvé, z toho, koľko prvkov môžeme kombinovať ich sady (aká veľká je všeobecná populácia prvkov).

Za druhé, výsledok závisí od toho, aké veľké sú sady položiek.

Nakoniec je dôležité vedieť, či je pre nás poradie prvkov v súprave nevyhnutné. Vysvetlíme posledný faktor na nasledujúcom príklade.

Príklad 9. Zapnuté rodičovské stretnutie je tam 20 ľudí. Koľko rôznych možností existuje pre zloženie rodičovskej komisie, ak by mala zahŕňať 5 ľudí?
Riešenie: V tomto prípade nás nezaujíma poradie mien v zozname výborov. Ak sú v dôsledku toho do nej zahrnutí rovnakí ľudia, potom z hľadiska významu je to pre nás rovnaká možnosť. Na výpočet čísla teda môžeme použiť vzorec kombinácie z 20 prvkov po 5.

Veci sa budú líšiť, ak bude každý člen výboru spočiatku zodpovedný za určitý smer práce. Potom s rovnakou mzdou výboru môže byť v ňom aj 5! možnosti permutácie na tom záleží. Počet rôznych možností (v zložení aj v oblasti zodpovednosti) je v tomto prípade určený počtom umiestnenia z 20 prvkov po 5.

Úlohy autotestu
1. Koľko trojciferných párnych čísel je možné vytvoriť z číslic 0, 1, 2, 3, 4, 5, 6, ak sa čísla dajú opakovať?
Pretože párne číslo na treťom mieste môže byť 0, 2, 4, 6, t.j. štyri cifry. Ktorákoľvek zo siedmich číslic môže byť na druhom mieste. Na prvom mieste môže byť ktorákoľvek zo siedmich číslic okrem nuly, t.j. 6 možností. Výsledok = 4 * 7 * 6 = 168.
2. Koľko je päťciferných čísel, ktoré sa rovnako čítajú zľava doprava a sprava doľava?
Na prvom mieste môže byť akákoľvek číslica odlišná od 0, t.j. 9 možností. Na druhom mieste môže byť akékoľvek číslo, t.j. 10 možností. Akékoľvek číslo od môže byť aj na treťom mieste, t.j. 10 možností. Štvrtá a piata číslica sú vopred určené, zhodujú sa s prvou a druhou, preto je počet takýchto čísel 9 * 10 * 10 = 900.
3. V triede je desať predmetov a päť vyučovacích hodín denne. Koľkými spôsobmi si môžete naplánovať jeden deň?

4. Koľkými spôsobmi je možné vybrať 4 delegátov na konferenciu, ak je v skupine 20 ľudí?

n = C 20 4 = (20!) / (4! * (20-4)!) = (16! * 17 * 18 * 19 * 20) / ((1 * 2 * 3 * 4) * (16! )) = (17 * 18 * 19 * 20) / (1 * 2 * 3 * 4) = 4845.
5. Koľkými spôsobmi môže osem rôzne písmená osem rôznych obálok, ak je v každej obálke iba jedno písmeno?
Do prvej obálky môžete vložiť 1 z ôsmich písmen, jedno zo zvyšných siedmich do druhej, jedno zo šiestich do tretej atď. n = 8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320.
6. Komisia pozostávajúca z dvoch matematikov a šiestich ekonómov by mala byť vytvorená z troch matematikov a desiatich ekonómov. Koľkými spôsobmi sa to dá urobiť?