Kombinatorika online nestoja vedľa seba. Základné vzorce kombinatoriky

Treba poznamenať, že kombinatorika je samostatnou sekciou vyššej matematiky (a nie súčasťou terveru) a v tejto disciplíne boli napísané vážne učebnice, ktorých obsah niekedy nie je ľahší ako abstraktná algebra. Nám však bude stačiť malý podiel teoretických vedomostí a v tomto článku sa pokúsim prístupnou formou rozobrať základy témy s typickými kombinatorickými problémami. A mnohí z vás mi pomôžu ;-)

Čo budeme robiť? V užšom zmysle je kombinatorika výpočet rôznych kombinácií, ktoré je možné vytvoriť z určitého súboru diskrétne predmety. Predmetmi sa rozumejú akékoľvek izolované predmety alebo živé bytosti – ľudia, zvieratá, huby, rastliny, hmyz atď. Kombinatoriku zároveň vôbec nezaujíma, že súpravu tvorí tanier krupice, spájkovačka a močiarna žaba. Je zásadne dôležité, aby tieto objekty boli spočítateľné - sú tri. (diskrétnosť) a je nevyhnutné, aby žiadne z nich neboli rovnaké.

Keď je toho veľa, teraz o kombináciách. Najbežnejšími typmi kombinácií sú permutácie objektov, ich výber z množiny (kombinácia) a distribúcia (umiestnenie). Pozrime sa, ako sa to deje práve teraz:

Permutácie, kombinácie a umiestnenia bez opakovania

Nebojte sa nejasných výrazov, najmä preto, že niektoré z nich naozaj nie sú veľmi úspešné. Začnime koncom názvu – čo znamená „ bez opakovania"? To znamená, že v tejto časti budeme uvažovať o množinách, ktoré pozostávajú z rôzne predmety. Napríklad ... nie, nebudem ponúkať kašu s spájkovačkou a žabkou, lepšie je niečo chutnejšie =) Predstavte si, že by sa na stole pred vami zhmotnilo jablko, hruška a banán (ak sú situáciu možno simulovať v skutočnosti). Plody rozložíme zľava doprava v tomto poradí:

jablko / hruška / banán

Otázka jedna: Koľkými spôsobmi je možné ich preusporiadať?

Jedna kombinácia už bola napísaná vyššie a so zvyškom nie sú žiadne problémy:

jablko / banán / hruška
hruška / jablko / banán
hruška / banán / jablko
banán / jablko / hruška
banán / hruška / jablko

Celkom: 6 kombinácií alebo 6 permutácií.

Dobre, nebolo ťažké tu vymenovať všetky možné prípady, ale čo ak je položiek viac? Už so štyrmi rôznymi druhmi ovocia sa počet kombinácií výrazne zvýši!

Žiadne mučenie - 3 predmety je možné preusporiadať rôznymi spôsobmi.

Otázka druhá: na koľko spôsobov si môžete vybrať a) jeden plod, b) dva druhy ovocia, c) tri druhy ovocia, d) aspoň jedno ovocie?

Prečo si vybrať? A tak si v predchádzajúcom odseku vypracovali chuť do jedla – aby jedli! a) Jedno ovocie si môžete vybrať, samozrejme, tromi spôsobmi – vezmite si buď jablko, alebo hrušku, alebo banán.

Formálny počet je založený na vzorec pre počet kombinácií:

Záznam v tomto prípade treba chápať takto: „Koľkými spôsobmi si môžete vybrať 1 ovocie z troch?

b) Uvádzame všetky možné kombinácie dvoch druhov ovocia:

jablko a hruška;
jablko a banán;
hruška a banán.

Počet kombinácií sa dá ľahko skontrolovať pomocou rovnakého vzorca:

Zápis je chápaný podobne: „Koľkými spôsobmi si môžete vybrať 2 ovocie z troch?“.

c) A nakoniec, tri druhy ovocia možno vybrať jedinečným spôsobom:

Mimochodom, vzorec pre počet kombinácií má zmysel aj pre prázdnu vzorku:
Týmto spôsobom si môžete vybrať ani jedno ovocie - v skutočnosti si nič neberte a je to.

d) Koľkými spôsobmi sa môžete vydať aspoň jeden ovocie? Podmienka „aspoň jedno“ znamená, že sme spokojní s 1 ovocím (akýmkoľvek) alebo akýmikoľvek 2 ovocím alebo všetkými 3 ovocím:
spôsoby, ako si môžete vybrať aspoň jedno ovocie.

Na zodpovedanie ďalšej otázky potrebujem dvoch dobrovoľníkov ... ... No keďže nikto nechce, potom zavolám predstavenstvo =)

Otázka 3: Koľkými spôsobmi sa dá dať Dáshe a Nataše jedno ovocie?

Aby ste mohli distribuovať dva druhy ovocia, musíte ich najprv vybrať. Podľa odseku "byť" predchádzajúcej otázky sa to dá urobiť spôsobmi, znova ich prepíšem:

jablko a hruška;
jablko a banán;
hruška a banán.

Teraz však bude kombinácií dvakrát toľko. Zoberme si napríklad prvý pár ovocia:
Dášu môžete liečiť jablkom a Natašu hruškou;
alebo naopak - Dáša dostane hrušku a Nataša jablko.

A takáto permutácia je možná pre každý pár ovocia.

V tomto prípade to funguje vzorec umiestnenia:

Od vzorca sa líši tým, že berie do úvahy Nie len počet spôsobov, ktorými možno vybrať viacero objektov, ale aj všetky permutácie objektov v každom možná vzorka. V uvažovanom príklade je teda dôležité nielen to, že si môžete jednoducho vybrať napríklad hrušku a banán, ale aj to, ako budú rozdelené (umiestnené) medzi Dášu a Natašu.

Pokúste sa dobre pochopiť rozdiel medzi permutáciami, kombináciami a umiestneniami. V najjednoduchších prípadoch môžete všetky možné kombinácie prepočítať ručne, ale najčastejšie sa to stáva zdĺhavou úlohou, a preto musíte pochopiť význam vzorcov.

Tiež vám pripomínam, že teraz hovoríme o súbore rôzne predmety, a ak sa jablko/hruška/banán nahradí 3 jablkami alebo dokonca 3 veľmi podobnými jablkami, tak v kontexte uvažovaného problému budú stále brané do úvahy rôzne.

Pozrime sa podrobnejšie na každý typ kombinácie:

Permutácie

Permutácie sa nazývajú kombinácie z toho istého rôzne objekty a líšia sa len poradím, v akom sú umiestnené. Počet všetkých možných permutácií vyjadruje vzorec

Charakteristickým rysom permutácií je, že každá z nich zahŕňa VŠETKY set, tj. všetky predmety. Napríklad priateľská rodina:

Úloha 1

Koľkými spôsobmi je možné usadiť 5 ľudí za stôl?

Riešenie: použite vzorec pre počet permutácií:

Odpoveď: 120 spôsobov

Neuveriteľné, ale je to fakt. Upozorňujeme, že tu nezáleží na tom, či je stôl okrúhly, štvorcový, alebo vo všeobecnosti všetci ľudia sedeli na lavici pozdĺž jednej steny – dôležitý je len počet predmetov a ich vzájomná poloha. Okrem permutovania ľudí sa často stretávame s problémom permutácie rôznych kníh na poličke, ale to by bolo príliš jednoduché aj pre čajník:

Úloha 2

Koľko štvorciferných čísel možno vytvoriť zo štyroch kariet s číslami 0, 5, 7, 9?

Ak chcete vytvoriť štvormiestne číslo, musíte použiť všetkyštyri karty (čísla, na ktorýchiný! ) , a to je veľmi dôležitý predpoklad pre aplikáciu vzorca. Je zrejmé, že preskupením kariet získame rôzne štvorciferné čísla, ... počkať, je tu všetko v poriadku? ;-)

Dobre si premyslite problém! Vo všeobecnosti je to charakteristická črta kombinatorických a pravdepodobnostných problémov – TREBA PREMÝŠĽAŤ. A často myslite svetským spôsobom, ako napríklad pri analýze úvodného príkladu s ovocím. Nie, samozrejme, nežiadam hlúpe vypracovanie iných častí matematiky, ale musím poznamenať, že to isté integrály môcť naučiť sa rozhodovaťčisto mechanické.

Riešenie a odpoveď na konci hodiny.

Zvýšenie obratu:

Kombinácie

Učebnice zvyčajne dávajú stručnú a nie príliš jasnú definíciu kombinácií, preto podľa mojich úst nebude znenie zvlášť racionálne, ale dúfam, že zrozumiteľné:

Kombinácie pomenovať rôzne kombinácie objektov, ktoré sú vybrané z množstva rôznych objektov a ktoré sa od seba líšia aspoň jedným objektom. Inými slovami, jediná kombinácia je jedinečný výber prvkov, v ktorých na ich poradí nezáleží(miesto). Celkový počet takýchto jedinečných kombinácií sa vypočíta podľa vzorca .

Úloha 3

V krabici je 15 dielov. Koľkými spôsobmi sa dajú zobrať 4 časti?

Riešenie: v prvom rade opäť upozorňujem na to, že podľa logiky podmienky sa zvažujú detaily rôzne- aj keď sú vlastne rovnakého typu a vizuálne rovnaké (v tomto prípade môžu byť napríklad očíslované) .

V úlohe hovoríme o výbere 4 dielov, pri ktorých nezáleží na ich „ďalšom osude“ – zhruba povedané „stačí vybrať 4 kusy a je to“. Máme teda kombináciu častí. Spočítame ich počet:

Tu, samozrejme, nie je potrebné presúvať obrovské čísla.
V podobnej situácii vám radím použiť nasledujúci trik: v menovateli vyberte najväčší faktoriál (v tomto prípade ) a zlomok oň znížte. Na tento účel by mal byť čitateľ reprezentovaný ako . Napíšem veľmi podrobne:

Z krabice si môžete vybrať 4 diely rôznymi spôsobmi.

Ešte raz, čo to znamená? To znamená, že zo sady 15 rôznych dielov môžete vyrobiť tisíc tristo šesťdesiat päť jedinečný kombinácia 4 dielov. To znamená, že každá takáto kombinácia 4 častí sa bude líšiť od ostatných kombinácií aspoň v jednom detaile.

Odpoveď: 1365 spôsobov

Vzorec treba si dávať veľký pozor, keďže ide o "hit" kombinatoriky. Zároveň je užitočné pochopiť a zapísať „extrémne“ hodnoty bez akýchkoľvek výpočtov: . Aplikované na analyzovaný problém:

Jediný spôsob je nezobrať ani jeden detail;
spôsoby, ako môžete vziať 1 časť (ktorýkoľvek z 15);
spôsoby, ako môžete vziať 14 dielov (v tomto prípade jeden z 15 zostane v krabici);
- jediný spôsob, ako môžete vziať všetkých pätnásť častí.

Odporúčam vám, aby ste sa dôkladne oboznámili s Newtonovým binomickým a Pascalovým trojuholníkom, podľa ktorých je mimochodom veľmi vhodné kontrolovať výpočty pre malé hodnoty „en“.

Úloha 4

Koľkými spôsobmi možno vybrať 3 karty z balíčka 36 kariet?

Toto je príklad „urob si sám“. Čo je na mnohých kombinatorických problémoch príjemné, je stručnosť – hlavné je pochopiť podstatu. A podstata sa niekedy otvára z rôznych uhlov. Pozrime sa na veľmi poučný príklad:

Úloha 4

Osoba sa zúčastňuje šachového turnaja a každý hrá s každým 1 partiu. Koľko hier sa odohralo na turnaji?

Keďže sám hrám šach a opakovane som sa zúčastňoval turnajov medzi sebou, hneď som sa zorientoval podľa turnajovej tabuľky podľa veľkosti buniek, v ktorej sa berie do úvahy výsledok každej partie dvakrát a navyše bunky „hlavnej diagonály“ sú zatienené (pretože členovia sa so sebou nehrajú). Na základe vyššie uvedených úvah sa celkový počet odohraných hier vypočíta podľa vzorca . Toto rozhodnutie je úplne správne. (pozri príslušný súborBanka hotových riešení ) a dlho som na to zabudol na princípe "rozhodnuté, áno, dobre."

Jeden z návštevníkov stránky si však všimol, že v skutočnosti sa tu môžete riadiť najbanálnejšími kombináciami:
zo súperov môžu tvoriť rôzne dvojice (kto hrá bieleho, kto hrá čierneho - na tom nezáleží).

Ekvivalentný problém je s podaním rúk: na oddelení pracujú muži a všetci si navzájom podávajú ruky, koľko podania rúk urobia? Mimochodom, aj šachisti si pred každou partiou podávajú ruky.

No existujú dva závery:

Po prvé, nie všetko, čo je zrejmé, je zrejmé;

A po druhé, nebojte sa riešiť problémy „out of the box“!

Veľmi pekne ďakujeme za Vaše listy, pomáhajú skvalitňovať učebné materiály!

Ubytovanie

Alebo "pokročilé" kombinácie. Umiestnenia pomenovať rôzne kombinácie objektov, ktoré sú vybrané z mnohých rôznych objektov a ktoré sa od seba líšia zložením objektov vo vzorke, tak a ich poradie. Počet umiestnení sa vypočíta podľa vzorca

Aký je náš život? Hra:

Úloha 5

Borya, Dima a Volodya sa posadili, aby hrali bod. Koľkými spôsobmi môžu každý rozdať jednu kartu? (balíček obsahuje 36 kariet)

Riešenie: situácia je podobná ako v 4. úlohe, ale líši sa tým, že je dôležité nielen to, ktoré tri karty sa z balíčka vytiahnu, ale aj AKO sa rozdelia medzi hráčov. Vzorec umiestnenia:

Spôsoby rozdania 3 kariet hráčom.

Existuje ďalšia schéma riešenia, ktorá je z môjho pohľadu ešte jasnejšia:

spôsoby, ako si môžete vytiahnuť 3 karty z balíčka.

Teraz sa pozrime na jeden zo sedemtisíc sto štyridsať kombinácie, napríklad: pikový kráľ, srdcová 9, srdcová 7. V kombinatorickej terminológii môžu byť tieto 3 karty „preskupené“ medzi Borey, Dima a Volodya nasledujúcimi spôsobmi:

KP, 9H, 7H;
KP, 7H, 9H;
9H, KP, 7H;
9H, 7H, KP;
7H, KP, 9H;
7H, 9H, KP.

A ten istý fakt je pravdou pre hocikoho jedinečná sada 3 kariet. A nezabudnite, počítali sme aj takéto sady. Nemusíte byť profesor, aby ste pochopili, že počet nájdených kombinácií by sa mal vynásobiť šiestimi:

Existujú spôsoby, ako rozdať jednu kartu 3 hráčom.

V podstate sa ukázalo, že ide o vizuálnu kontrolu vzorce, ktorého konečný význam si objasníme v ďalšej časti.

Odpoveď: 42840

Možno máte ešte otázku, ale kto rozdal karty? ...asi učiteľ =)
A aby sa nikto neurazil, celá študentská skupina sa zúčastní nasledujúcej úlohy:

Úloha 6

V skupine študentov je 23 ľudí. Koľkými spôsobmi možno vybrať riaditeľa a jeho zástupcu?

Úloha „umiestňovať“ pozície v tíme je veľmi častá a ide o skutočnú gombíkovú harmoniku. Krátke riešenie a odpoveď na konci hodiny.

KOMBINATORIKA

Kombinatorika je oblasť matematiky, ktorá študuje problémy výberu a usporiadania prvkov z nejakého základného súboru v súlade s danými pravidlami. Vzorce a princípy kombinatoriky sa v teórii pravdepodobnosti používajú na výpočet pravdepodobnosti náhodných udalostí a podľa toho na získanie zákonov rozdelenia náhodných veličín. To zase umožňuje študovať zákonitosti hromadných náhodných javov, čo je veľmi dôležité pre správne pochopenie štatistických zákonitostí, ktoré sa prejavujú v prírode a technike.

Pravidlá sčítania a násobenia v kombinatorike

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

Príklad 1

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

Riešenie

Služobne môžete určiť buď chlapca alebo dievča, t.j. ktorýkoľvek zo 16 chlapcov alebo ktorékoľvek z 10 dievčat môže byť v službe.

Podľa súčtového pravidla dostaneme, že jednému dôstojníkovi môže byť pridelených 16+10=26 spôsobov.

Produktové pravidlo. Nech je potrebné vykonať postupne k akcií. Ak je možné prvú akciu vykonať n 1 spôsobmi, druhú akciu n 2 spôsobmi, tretiu n 3 spôsobmi atď. až po k-tú akciu, ktorú možno vykonať n k spôsobmi, potom všetkých k akcií spolu môže byť vykonané:

spôsoby.

Príklad 2

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi môžu byť vymenovaní dvaja sprievodcovia?

Riešenie

Prvou osobou v službe môže byť chlapec alebo dievča. Pretože v triede je 16 chlapcov a 10 dievčat, prvého strážnika potom môžete vymenovať 16 + 10 = 26 spôsobmi.

Po tom, čo sme si vybrali prvého strážnika, môžeme zo zvyšných 25 ľudí vybrať druhého, t.j. 25 spôsobov.

Podľa násobiacej vety je možné vybrať dvoch účastníkov 26*25=650 spôsobmi.

Kombinácie bez opakovania. Kombinácie s opakovaním

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

Príklad 3

Musíte si vybrať 4 z 10 rôznych kníh dostupných ako darček. Koľkými spôsobmi sa to dá urobiť?

Riešenie

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

.

Zvážte problém počtu kombinácií s opakovaniami: existuje r rovnakých objektov každého z n rôznych typov; koľko spôsoby môcť vyberte si m() z títo (n*r) položiek?

.

Príklad 4

V cukrárni sa predávali 4 druhy koláčov: napoleon, eclairs, krehké pečivo a lístkové pečivo. Na koľko spôsobov sa dá 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 kúpiť 7 koláčov, je určený počtom kombinácií s opakovaním od 7 do 4.

.

Umiestnenia bez opakovania. Umiestnenia s opakovaniami

Klasickým problémom kombinatoriky je problém počtu umiestnení bez opakovaní, ktorého obsah možno vyjadriť otázkou: koľko spôsoby môcť vyberte si a miesto na m 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 možno urobiť, ak žiadna strana novín nesmie obsahovať viac ako jednu fotografiu?

Riešenie.

V tomto probléme fotografie len nevyberáme, 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čenia počtu umiestnení bez opakovaní z 12 prvkov po 4 prvkoch:

Takto možno 4 fotografie na 12 stranách usporiadať 11880 spôsobmi.

Klasickou úlohou kombinatoriky je tiež problém počtu umiestnení s opakovaniami, ktorých obsah možno vyjadriť otázkou: koľko spôsoby môcť vybarmády a miesto na m iný Miesta m od n položieksredi ktoré existuje rovnaký?

Príklad 6

Chlapec mal zo sady k spoločenskej hre známky s číslami 1, 3 a 7. Rozhodol sa, že týmito pečiatkami dá päťciferné čísla na všetky knihy – zostaví katalóg. Koľko rôznych päťciferných čísel dokáže chlapec vytvoriť?

Permutácie bez opakovania. Permutácie s opakovaniami

Klasickým problémom kombinatoriky je problém počtu permutácií bez opakovania, ktorého obsah možno 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“ možno vytvoriť z písmen slova „manželstvo“?

Riešenie

Všeobecný súbor je 4 písmená slova "manželstvo" (b, p, a, k). Počet „slov“ je určený permutáciami týchto 4 písmen, t.j.

Pre prípad, že medzi vybranými n prvkami sú rovnaké (výber s návratom), problém počtu permutácií s opakovaniami možno vyjadriť otázkou: Koľkými spôsobmi možno n objektov preusporiadať na n rôznych miestach, ak medzi n objektmi existuje k rôznych typov (k< n), т. е. есть одинаковые предметы.

Príklad 8

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

Riešenie

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

ZÁKLADNÉ ZHRNUTIE SEKCIE "KOMBINATORIKA"

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 umožňujú vypočítať zásadne možný počet rôznych scenárov vývoja udalostí.

Základný kombinatorický vzorec

Nech je 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 je možné takúto voľbu uskutočniť, je určený vzťahom N=n 1 * n 2 * n 3 *...* n k .

Príklad 1 Vysvetlime si toto pravidlo na jednoduchom príklade. Nech sú dve skupiny prvkov, prvá skupina pozostáva z n 1 prvkov a druhá - z n 2 prvkov. Koľko rôznych dvojíc prvkov možno vytvoriť z týchto dvoch skupín tak, aby dvojica obsahovala jeden prvok z každej skupiny? Predpokladajme, že sme vzali prvý prvok z prvej skupiny a bez toho, aby sme ho zmenili, sme prešli všetkými možnými pármi, 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 tiež k nemu vytvoríme všetky možné dvojice. Bude tiež n 2 takýchto párov. Pretože v prvej skupine je len n 1 prvkov, bude n 1 * n 2 možných možností.

Príklad 2 Koľko trojciferných párnych čísel možno vytvoriť z číslic 0, 1, 2, 3, 4, 5, 6, ak sa číslice môžu opakovať?
Riešenie: 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (keďže ako tretiu číslicu môžete použiť ľubovoľnú číslicu od 0, 2, 4, 6).
Takže, N=n1*n2*n3=6*7*4=168.

V prípade, keď 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 sa po výbere vráti do skupiny. Potom sa počet všetkých spôsobov výberu rovná n k . Tento spôsob výberu sa v kombinatorike nazýva tzv vrátiť vzorky.

Príklad 3 Koľko štvorciferných čísel možno vytvoriť z čísel 1, 5, 6, 7, 8?
Riešenie. Pre každú číslicu štvorciferného čísla existuje päť možností, takže N=5*5*5*5=5 4 =625.

Uvažujme množinu pozostávajúcu z n prvkov. Táto množina v kombinatorike je tzv všeobecná populácia.

Počet umiestnení z n prvkov na m

Definícia 1. Ubytovanie od n prvky podľa m v kombinatorike sa nazýva akýkoľvek objednaná sada od m rôzne prvky vybrané z bežnej populácie v n prvkov.

Príklad 4 Rôzne usporiadania troch prvkov (1, 2, 3) po dvoch budú množiny (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 sa označuje ako A n m a vypočíta sa podľa vzorca:

komentár: n!=1*2*3*...*n (čítaj: "en faktoriál"), navyše sa predpokladá, že 0!=1.

Príklad 5. Koľko je dvojciferných čísel, v ktorých sú desiatky a jednotka rôzne a nepárne?
Riešenie: pretože existuje päť nepárnych číslic, konkrétne 1, 3, 5, 7, 9, potom sa tento problém redukuje na výber a umiestnenie dvoch z piatich rôznych číslic na dve rôzne pozície, t.j. uvedené čísla budú:

Definícia 2. Kombinácia od n prvky podľa m v kombinatorike sa nazýva akýkoľvek neusporiadaná sada od m rôzne prvky vybrané z bežnej populácie v n prvkov.

Príklad 6. Pre množinu (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ý C n m a vypočíta sa 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ú ľubovoľné 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 sa označí P n a vypočíta sa podľa vzorca P n =n!.

Príklad 8 Koľkými spôsobmi možno sedem kníh od rôznych autorov usporiadať za sebou na poličku?

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.

Diskusia. Vidíme, že počet možných kombinácií možno vypočítať podľa rôznych pravidiel (permutácie, kombinácie, umiestnenia) a výsledok bude iný, pretože princíp počítania a samotné vzorce sú odlišné. Pri bližšom pohľade na definície môžete vidieť, ž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 všeobecná populácia prvkov).

Po druhé, výsledok závisí od toho, aké veľké sady prvkov potrebujeme.

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

Príklad 9 Na rodičovskom stretnutí je 20 ľudí. Koľko rôznych možností je zloženie materského výboru, ak by mal zahŕňať 5 ľudí?
Riešenie: V tomto príklade nás nezaujíma poradie mien na zozname komisie. Ak sa v dôsledku toho v jeho zložení objavia tí istí ľudia, potom je to pre nás významovo rovnaká možnosť. Preto môžeme použiť vzorec na výpočet čísla kombinácie z 20 prvkov, 5.

Veci budú iné, ak bude každý člen výboru spočiatku zodpovedný za určitú oblasť práce. Potom pri rovnakej výplatnej listine komisie je v nej možno 5! možnosti permutácií na tom záleží. Počet rôznych (z hľadiska zloženia aj oblasti zodpovednosti) možností je v tomto prípade určený počtom umiestnenia z 20 prvkov, 5.

Úlohy na autotest
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 si môžete zostaviť 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. Z troch matematikov a desiatich ekonómov je potrebné zostaviť komisiu zloženú z dvoch matematikov a šiestich ekonómov. Koľkými spôsobmi sa to dá urobiť?

Permutácia je kombinácia prvkov z N rôzne prvky prijaté v určitom poradí. Pri permutácii je dôležité poradie prvkov a do permutácie musia byť zapojené všetky prvky. N prvkov.

Úloha: Nájdite všetky možné permutácie pre postupnosť čísel 1, 2, 3.
Existujú nasledujúce permutácie:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Permutácie bez opakovania

Počet permutácií pre N rôznych prvkov je N!. naozaj:

• ktorýkoľvek z N prvky (celkové možnosti N),
• ktorýkoľvek zo zostávajúcich (N-1) prvky (celkové možnosti N (N-1)),
• ak budeme pokračovať v tejto sekvencii pre všetkých N miesta, dostaneme: N (N-1) (N-2) ... ... 1, to je všetko N! permutácií.

Zvážte problém získania všetkých permutácií čísel 1…N(to znamená sekvencie dĺžky N), kde sa každé z čísel vyskytuje práve 1-krát. Existuje veľa možností pre poradie, v ktorom sa získajú permutácie. Najčastejšie riešeným problémom je však generovanie permutácií v lexikografický objednávky (pozri príklad vyššie). V tomto prípade sú všetky permutácie zoradené najprv podľa prvého čísla, potom podľa druhého atď. vo vzostupnom poradí. Takže prvá permutácia bude 1 2 … N, a posledný N N-1 … 1.

Zvážte algoritmus na riešenie problému. Uvedená je počiatočná postupnosť čísel. Ak chcete získať každú nasledujúcu permutáciu, musíte vykonať nasledujúce kroky:

• Je potrebné naskenovať aktuálnu permutáciu sprava doľava a zároveň sa uistiť, že každý ďalší prvok permutácie (prvok s vyšším číslom) nie je väčší ako predchádzajúci (prvok s nižším číslom). Hneď ako dôjde k porušeniu tohto pomeru, je potrebné zastaviť a označiť aktuálne číslo (pozícia 1).
• Opäť sa pozrite na cestu sprava doľava, kým nedosiahneme prvé číslo, ktoré je väčšie ako to, ktoré ste označili v predchádzajúcom kroku.
• Vymeňte dva prijaté prvky.
• Teraz v časti poľa, ktorá sa nachádza napravo od pozície 1, musíte zoradiť všetky čísla vo vzostupnom poradí. Keďže predtým už boli všetky napísané v zostupnom poradí, je potrebné túto časť podsekvencie jednoducho prehodiť.

Dostaneme tak novú sekvenciu, ktorá bude v ďalšom kroku považovaná za počiatočnú.

Implementácia v C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
pomocou menného priestoru std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
pričom (j != -1 && a[j] >= a) j--;
if (j == -1)
vrátiť nepravdu; // už žiadne permutácie
int k = n - 1;
pričom (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
zatiaľ čo (l swap(a, l++, r--);
vrátiť true;
}
void Print(int *a, int n) // výstupná permutácia
{
static int num = 1; // permutačné číslo
šírka výrezu(3);
cout<< num++ << ": " ;
pre (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = new int[n];
pre (int i = 0; i< n; i++)
a[i] = i + 1;
Tlač(a, n);
while (NextSet(a, n))
Tlač(a, n);
cin.get(); cin.get();
návrat 0;
}

Výsledok popravy

Permutácie s opakovaniami

Osobitnú pozornosť si zasluhuje problém generovania permutácií. N prvky, ak sa prvky postupnosti môžu opakovať. Predpokladajme, že pôvodná sekvencia pozostáva z prvkov n 1, n 2 ... n k, kde prvok n 1 opakuje r1 raz, n 2 opakuje r2časy atď. V čom n1 + n2 +...+n k =N. Ak spočítame všetko n 1 + n 2 +...+n k prvky permutácie s rôznymi opakovaniami, potom celkom rôzne varianty permutácií ( n 1 + n 2 +...+n k)!. Avšak medzi týmito permutáciami nie sú všetky odlišné. Naozaj, všetko r1 prvkov n 1 môžeme sa navzájom preusporiadať a to nemení permutáciu. Rovnakým spôsobom môžeme preusporiadať prvky n 2, n 3 V dôsledku toho máme r1! varianty zápisu rovnakej permutácie s rôznym usporiadaním opakujúcich sa prvkov n 1. Takto je možné napísať akúkoľvek permutáciu r 1 ! r 2 ! ... r k ! spôsoby. Preto je počet rôznych permutácií s opakovaniami

Na generovanie permutácií s opakovaniami môžete použiť vyššie uvedený algoritmus na generovanie permutácií bez opakovaní. Zaveďme opakujúci sa prvok do poľa a. Nižšie je uvedený programový kód na generovanie permutácií s opakovaniami (zmenený bol iba kód funkcie main()).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
pomocou menného priestoru std;
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
pričom (j != -1 && a[j] >= a) j--;
if (j == -1)
vrátiť nepravdu; // už žiadne permutácie
int k = n - 1;
pričom (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // zoradiť zvyšok sekvencie
zatiaľ čo (l swap(a, l++, r--);
vrátiť true;
}
void Print(int *a, int n) // výstupná permutácia
{
static int num = 1; // permutačné číslo
šírka výrezu(3); // šírka výstupného poľa permutačného čísla
cout<< num++ << ": " ;
pre (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = new int[n];
pre (int i = 0; i< n; i++)
a[i] = i + 1;
a = 1; // opakovaný prvok
Tlač(a, n);
while (NextSet(a, n))
Tlač(a, n);
cin.get(); cin.get();
návrat 0;
}

Výstup vyššie uvedeného algoritmu je:

Počet umiestnení bez opakovaní od n na k n k rôzne súradnice.

Počet umiestnení bez opakovaní sa zistí podľa vzorca:

Príklad: Koľkými spôsobmi môžete zostrojiť 3-ciferné číslo s rôznymi číslicami, ktoré neobsahuje číslicu 0?

Počet číslic
, rozmer vektora s rôznymi súradnicami

Počet umiestnení s opakovaniami

Počet umiestnení s opakovaniami od n na k je počet spôsobov, ktorými existujú n rôzne prvky vytvárajú vektory k súradnice, medzi ktorými môžu byť rovnaké.

Počet umiestnení s opakovaním sa zistí podľa vzorca:

.

Príklad: Koľko slov s dĺžkou 6 možno vytvoriť z 26 písmen latinskej abecedy?

Počet písmen
, vektorový rozmer

Počet permutácií bez opakovania

Počet permutácií bez opakovaní od n prvkov je počet spôsobov, ktorými môže byť umiestnený na n rôznych miestach n rôzne prvky.

Počet permutácií bez opakovaní sa zistí podľa vzorca:

.

komentár: Výkon požadovanej sady ALE je vhodné hľadať podľa vzorca:
, kde X- počet spôsobov, ako vybrať požadované miesta; pri- počet spôsobov, ako na nich usporiadať potrebné prvky; z- počet spôsobov, ako usporiadať zostávajúce prvky na zvyšných miestach.

Príklad. Koľkými spôsobmi možno na poličku usporiadať 5 rôznych kníh? V koľkých prípadoch budú dve konkrétne knihy A a B vedľa seba?

Celkový počet spôsobov usporiadania 5 kníh na 5 miestach sa rovná = 5! = 120.

V úlohe X je počet spôsobov, ako vybrať dve miesta vedľa seba, X= 4;pri je počet spôsobov, ako usporiadať dve knihy na dvoch miestach, pri = 2! = 2; z- počet spôsobov, ako usporiadať zvyšné 3 knihy na zvyšných 3 miestach, z= 3! = 6. Takže
= 48.

Počet kombinácií bez opakovaní

Počet kombinácií bez opakovaní od n na k je počet spôsobov, ktorými existujú n rôzne položky na výber k kusov bez objednávky.

Počet kombinácií bez opakovaní sa zistí podľa vzorca:

.

Vlastnosti:

1)
; 2)
; 3)
;

4)
; 5)
; 6)
.

Príklad. V urne je 7 loptičiek. Z toho sú 3 biele. Náhodne sa vyberú 3 loptičky. Koľkými spôsobmi sa to dá urobiť? V koľkých prípadoch bude medzi nimi práve jeden biely?

celkové spôsoby
. Ak chcete získať počet spôsobov, ako vybrať 1 bielu guľu (z 3 bielych) a 2 čierne gule (zo 4 čiernych), musíte ich vynásobiť
a
Teda požadovaný počet spôsobov

Cvičenia

1. Z 35 žiakov mala trieda na konci roka z matematiky „5“ – 14 ľudí; vo fyzike - 15 ľudí; v chémii - 18 ľudí; v matematike a fyzike - 7 osôb; v matematike a chémii - 9 osôb; vo fyzike a chémii - 6 osôb; vo všetkých troch predmetoch - 4 osoby. Koľko ľudí má „5“ v určených predmetoch? Koľko ľudí nemá v týchto predmetoch „5“? Má „5“ iba z matematiky? Má „5“ iba v dvoch predmetoch?

2. V skupine 30 študentov vie každý aspoň jeden cudzí jazyk – anglický alebo nemecký jazyk. Anglicky hovorí 22 žiakov, nemecky 17. Koľko žiakov vie oba jazyky? Koľko študentov vie po nemecky, ale nevie po anglicky?

3. Študenti z Ruska bývajú v 20 izbách hostela Inštitútu priateľstva národov; 15 z Afriky; 20 z krajín Južnej Ameriky. Navyše v 7 - žijú Rusi a Afričania, v 8 - Rusi a Juhoameričania; v 9 - Afričania a Juhoameričania; v 3 - Rusi, Juhoameričania a Afričania. V koľkých izbách bývajú študenti: 1) len z jedného kontinentu; 2) len z dvoch kontinentov; 3) iba Afričania.

4. Každý z 500 študentov musí absolvovať aspoň jeden z troch špeciálnych kurzov: matematiku, fyziku a astronómiu. Tri špeciálne kurzy navštevuje 10 študentov, z matematiky a fyziky - 30 študentov, z matematiky a astronómie - 25; špeciálny kurz len z fyziky - 80 študentov. Je tiež známe, že 345 študentov navštevuje špeciálny kurz z matematiky, 145 študentov z fyziky a 100 študentov z astronómie. Koľko študentov navštevuje iba špeciálny kurz astronómie? Koľko študentov navštevuje dva špeciálne kurzy?

5. Vedúci kurzu predniesol nasledujúcu správu o telesnej výchove. Spolu - 45 žiakov. Futbalový oddiel - 25 osôb, basketbalový oddiel - 30 osôb, šachový oddiel - 28 osôb. Zároveň navštevuje oddiel futbalu a basketbalu 16 ľudí súčasne, 18 - futbal a šach, 17 - basketbal a šach, všetky tri oddiely navštevuje 15 ľudí. Vysvetlite, prečo správa nebola prijatá.

6. V akváriu je 11 rýb. Z toho sú 4 červené, ostatné sú zlaté. Náhodne sa vyberú 4 ryby. Koľkými spôsobmi sa to dá urobiť? Nájdite počet spôsobov, ako to urobiť, aby medzi nimi bola: 1) presne jedna červená; 2) presne 2 zlaté; 3) aspoň jedna červená.

7. Na zozname je 8 mien. Z toho sú 4 ženy. Koľkými spôsobmi ich možno rozdeliť do dvoch rovnakých skupín tak, aby každá mala ženské priezvisko?

8. Vyberte si 4 z balíčka 36 kariet. Koľko spôsobov, ako to urobiť, aby: 1) všetky karty boli rôznych farieb; 2) všetky karty boli rovnakej farby; 3) 2 červené a 2 čierne.

9. Na kartách delenej abecedy sú uvedené písmená K, K, K, U, U, A, E, R. Koľko spôsobov ich dať za sebou, aby ste dostali „vrana“.

10. Dajú sa kartičky strihanej abecedy s písmenami O, T, O, L, O, R, I, N, G, O, L, O, G. Koľko spôsobov ich poskladať, aby slovo „ otolaryngológa“ sa získa.

11. Sú uvedené kartičky lúpanej abecedy s písmenami L, I, T, E, R, A, T, U, R, A. Koľko spôsobov ich vložiť do radu, aby sa získalo slovo „literatúra“ .

12. Zoraďuje sa 8 ľudí. Koľko spôsobov to urobiť, aby dvaja konkrétni ľudia A a B boli: 1) vedľa seba; 2) na okrajoch frontu;

13. Za okrúhly stôl s 10 miestami si sadne 10 ľudí. Koľkými spôsobmi to možno urobiť, aby boli: 1) dvaja konkrétni ľudia A a B; 2) traja konkrétni ľudia A, B a C.

14. 10 arabských číslic tvorí 5-miestny kód. Koľkými spôsobmi to možno urobiť, aby: 1) všetky čísla boli odlišné; 2) posledné miesto je párne číslo.

15. Z 26 písmen latinskej abecedy (medzi nimi 6 samohlások) sa vytvorí šesťpísmenové slovo. Koľkými spôsobmi to možno urobiť, aby slovo obsahovalo: 1) práve jedno písmeno „a“; 2) presne jedna samohláska; presne dve písmená "a"; c) presne dve samohlásky.

16. Koľko štvorciferných čísel je deliteľných 5?

17. Koľko štvorciferných čísel s rôznymi číslicami je deliteľných 25?

19. Hodia sa 3 kocky. V koľkých prípadoch to vypadlo: 1) presne 1 „šestka“; 2) aspoň jedna „šestka“.

20. Hoď 3 kockami. V koľkých prípadoch to bude: 1) každý je iný; 2) presne dva rovnaké počty bodov.

21. Koľko slov s rôznymi písmenami možno poskladať z abecedy a, b, c, d. Uveďte ich všetky v lexikografickom poradí: abcd, abcd….