Võimalikud kombinatsioonid. Kombinatsioonid

Mõelge antud komplekti proovide loendamise probleemile üldiselt. Olgu mõni komplekt N, koosnevad n elemendid. Mis tahes alamhulk m elemente saab käsitleda nende järjestust arvestamata ja koos sellega, s.o. tellimust muutes minge teise juurde m- proovide võtmine.

Me sõnastame järgmised määratlused:

Paigutused ilma kordusteta

Pannes ilma kordamiseta väljan elemendid pooltm Nsisaldavadmerinevaid elemente.

Definitsioonist tuleneb, et kaks paigutust erinevad üksteisest nii elementide kui ka järjestuse poolest, isegi kui elemendid on samad.

3. teoreem. Korduseta paigutuste arv on võrdne tootega m tegurid, millest suurim on arv n . Kirjuta üles:

Permutatsioonid ilma kordusteta

Permutatsioonid alatesn elemente nimetatakse hulga erinevateks järjestusteksN.

Sellest definitsioonist järeldub, et kaks permutatsiooni erinevad ainult elementide järjestuse poolest ja neid võib käsitleda korralduste erijuhuna.

4. teoreem. Erinevate kordusteta permutatsioonide arv arvutatakse valemiga

Kombinatsioonid ilma kordusteta

Kombinatsioon ilma kordamisetan elemendid pooltm kutsutakse välja mis tahes hulga järjestamata alamhulkNsisaldavadm erinevaid elemente.

Definitsioonist järeldub, et kaks kombinatsiooni erinevad ainult elementide poolest, järjekord pole oluline.

5. teoreem. Kordusteta kombinatsioonide arv arvutatakse ühe järgmistest valemitest:

Näide 1. Toas on 5 tooli. Kui mitmel viisil saate paigutada

a) 7 inimest; b) 5 inimest; c) 3 inimest?

Otsus: a) Kõigepealt pead valima 5 inimest 7-st, kes toolidele istuvad. Seda saab teha
tee. Iga konkreetse viie valikuga saab toota
kohati permutatsioonid. Korrutusteoreemi järgi on soovitud maandumismeetodite arv võrdne.

Kommentaar: Probleemi saab lahendada ainult tooteteoreemi abil, argumenteerides järgmiselt: 1. toolile maandumiseks on 7 võimalust, 2. toolile 6, 3. 5, 4. 4 ja 5. -3. Siis on 7 inimese viiele toolile istumise võimaluste arv võrdne . Lahendused on mõlemal viisil järjepidevad, kuna

b) Lahendus on ilmne -

sisse) - hõivatud toolide valikute arv.

- kolme inimese paigutuste arv kolmele valitud toolile.

Valikute koguarv on .

Valemeid pole raske kontrollida
;

;

Kogumi kõigi alamhulkade arv, mis koosneb n elemendid.

Kordusega paigutused

Paigutus koos kordusega alatesn elemendid pooltm on hulga järjestatud alamhulkN, koosnevadm elemendid, nii et sellesse alamhulka saab kaasata mis tahes elemendi vahemikus 1 kunimkorda või üldse mitte.

Korduvate paigutuste arv on märgitud ja arvutatakse valemi järgi, mis on korrutusteoreemi tagajärg:

Näide 2. Olgu antud kolmest tähest koosnev hulk N = (a, b, c). Nimetagem sõna mis tahes selles komplektis sisalduvate tähtede komplektiks. Leiame nendest tähtedest moodustatavate sõnade arvu pikkusega 2:
.

Kommentaar: Ilmselt võib kaaluda ka kordamisega kokkuleppeid
.

Näide 3. Tähtedest (a, b) tuleb koostada kõik võimalikud sõnad pikkusega 3. Mitmel viisil saab seda teha?

Vastus:

Kombinatoorika on matemaatika haru, mis uurib küsimusi selle kohta, kui palju erinevaid kombinatsioone saab teatud tingimustel teha antud objektidest. Kombinatoorika põhitõed on juhuslike sündmuste tõenäosuste hindamisel väga olulised, sest just need võimaldavad arvutada sündmuste arengu erinevate stsenaariumide põhimõtteliselt võimaliku arvu.

Kombinatoorika põhivalem

Olgu siin k elementide rühma ja i-s rühm koosneb n i elemendist. Valime igast rühmast ühe elemendi. Siis määratakse sellise valiku tegemise viiside koguarv N seosega N=n 1 *n 2 *n 3 *...*n k .

Näide 1 Selgitame seda reeglit lihtsa näitega. Olgu kaks elementide rühma, esimene rühm koosneb n 1 elemendist ja teine ​​- n 2 elemendist. Mitu erinevat elemendipaari saab nendest kahest rühmast teha nii, et paar sisaldaks igast rühmast ühte elementi? Oletame, et võtsime esimesest rühmast esimese elemendi ja, muutmata seda, käisime läbi kõik võimalikud paarid, muutes ainult teise rühma elemente. Selle elemendi jaoks on n 2 sellist paari. Seejärel võtame esimesest rühmast teise elemendi ja teeme selle jaoks ka kõik võimalikud paarid. Samuti saab olema n 2 sellist paari. Kuna esimeses rühmas on ainult n 1 elementi, on võimalikke valikuid n 1 *n 2.

Näide 2 Mitu kolmekohalist paarisarvu saab numbritest 0, 1, 2, 3, 4, 5, 6 teha, kui numbrid on korduvad?
Otsus: n 1 \u003d 6 (kuna esimeseks numbriks võite võtta mis tahes numbri 1, 2, 3, 4, 5, 6), n 2 \u003d 7 (kuna teiseks numbriks võite võtta mis tahes numbri alates 0, 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (kuna kolmanda numbrina võite võtta mis tahes numbri 0, 2, 4, 6).
Niisiis, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.

Juhul, kui kõik rühmad koosnevad samast arvust elementidest, s.o. n 1 =n 2 =...n k =n võib eeldada, et iga valik tehakse samast grupist ja element naaseb peale valikut rühma. Siis on kõigi valikuviiside arv võrdne n k . Sellist kombinatoorika valikuviisi nimetatakse proovid tagastada.

Näide 3 Mitu neljakohalist arvu saab arvudest 1, 5, 6, 7, 8 teha?
Otsus. Neljakohalise arvu iga numbri jaoks on viis võimalust, seega N=5*5*5*5=5 4 =625.

Vaatleme hulka, mis koosneb n elemendist. Seda komplekti kombinatoorikas nimetatakse üldine elanikkond.

Paigutuste arv n elemendist m võrra

Definitsioon 1. Majutus alates n elemendid poolt m kombinatoorikas nimetatakse mis tahes tellitud komplekt alates m aastal üldpopulatsioonist valitud erinevad elemendid n elemendid.

Näide 4 Kolme elemendi (1, 2, 3) erinevad paigutused kahekaupa moodustavad komplektid (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Paigutused võivad üksteisest erineda nii elementide kui ka järjestuse poolest.

Paigutuste arv kombinatoorikas on tähistatud A n m-ga ja arvutatakse järgmise valemiga:

Kommentaar: n!=1*2*3*...*n (loe: "en faktoriaal"), lisaks eeldatakse, et 0!=1.

Näide 5. Mitu kahekohalist arvu on, milles kümnend ja ühikute arv on erinevad ja paaritud?
Otsus: sest seal on viis paaritut numbrit, nimelt 1, 3, 5, 7, 9, siis taandub see probleem viiest erinevast numbrist kahe valimiseks ja paigutamiseks kahele erinevale positsioonile, st. antud numbrid on järgmised:

Definitsioon 2. Kombinatsioon alates n elemendid poolt m kombinatoorikas nimetatakse mis tahes tellimata komplekt alates m aastal üldpopulatsioonist valitud erinevad elemendid n elemendid.

Näide 6. Komplekti (1, 2, 3) jaoks on kombinatsioonid (1, 2), (1, 3), (2, 3).

N elemendi kombinatsioonide arv m võrra

Kombinatsioonide arv on tähistatud C n m-ga ja arvutatakse järgmise valemiga:

Näide 7 Kui mitmel viisil saab lugeja kuuest saadaolevast raamatust kaks valida?

Otsus: Võimaluste arv võrdub kuue raamatu kombinatsioonide arvuga kahega, s.o. võrdub:

N elemendi permutatsioonid

Definitsioon 3. Permutatsioon alates n elemente nimetatakse mis tahes tellitud komplekt need elemendid.

Näide 7a. Kolmest elemendist (1, 2, 3) koosneva hulga kõikvõimalikud permutatsioonid on: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

N elemendi erinevate permutatsioonide arv on tähistatud P n-ga ja arvutatakse valemiga P n =n!.

Näide 8 Kui mitmel viisil saab riiulil järjestada seitset raamatut erinevatelt autoritelt?

Otsus: see probleem on seotud seitsme erineva raamatu permutatsioonide arvuga. Raamatute paigutamiseks on P 7 =7!=1*2*3*4*5*6*7=5040 võimalust.

Arutelu. Näeme, et võimalike kombinatsioonide arvu saab arvutada erinevate reeglite järgi (permutatsioonid, kombinatsioonid, paigutused) ja tulemus on erinev, sest loendamise põhimõte ja valemid ise on erinevad. Definitsioone tähelepanelikult vaadates on näha, et tulemus sõltub korraga mitmest tegurist.

Esiteks, mitme elemendi põhjal saame nende hulki kombineerida (kui suur on elementide üldpopulatsioon).

Teiseks sõltub tulemus sellest, millise suurusega elementide komplekte me vajame.

Lõpuks on oluline teada, kas elementide järjekord komplektis on meie jaoks oluline. Selgitame viimast tegurit järgmise näitega.

Näide 9 Lastevanemate koosolekul on 20 inimest. Kui palju erinevaid variante on lastevanemate komisjoni koosseisus, kui sellesse peaks kuuluma 5 inimest?
Otsus: Selles näites ei huvita meid komisjonide nimekirjas olevate nimede järjekord. Kui selle tulemusena ilmuvad selle koosseisus samad inimesed, siis meie jaoks on see tähenduse poolest sama variant. Seetõttu saame arvu arvutamiseks kasutada valemit kombinatsioonid 20 elemendist 5.

Asjad on teisiti, kui iga komitee liige vastutab algselt teatud töövaldkonna eest. Siis on sama komitee palgal selle sees 5 võimalik! valikuid permutatsioonid see asi. Erinevate (nii koosseisu kui ka vastutusala poolest) valikute arvu määrab sel juhul arv paigutused 20 elemendist 5.

Enesekontrolli ülesanded
1. Mitu kolmekohalist paarisarvu saab arvudest 0, 1, 2, 3, 4, 5, 6 teha, kui arve saab korrata?

2. Mitu viiekohalist numbrit on samamoodi vasakult paremale ja paremalt vasakule?

3. Klassis on kümme ainet ja viis tundi päevas. Kui mitmel viisil saate ühe päeva ajakava koostada?

4. Mitmel viisil saab konverentsile valida 4 delegaati, kui rühmas on 20 inimest?

5. Mitmel viisil saab kaheksa erinevat tähte panna kaheksasse erinevasse ümbrikusse, kui igasse ümbrikusse on pandud ainult üks täht?

6. Kolmest matemaatikust ja kümnest majandusteadlasest on vaja teha komisjon, mis koosneb kahest matemaatikust ja kuuest majandusteadlasest. Kui mitmel viisil saab seda teha?

Tuleb märkida, et kombinatoorika on kõrgema matemaatika iseseisev osa (ja mitte osa tervest) ja sellel erialal on kirjutatud kaalukaid õpikuid, mille sisu pole kohati lihtsam kui abstraktne algebra. Meile piisab aga väikesest osast teoreetilistest teadmistest ja selles artiklis püüan analüüsida teema põhitõdesid tüüpiliste kombinatoorsete probleemidega juurdepääsetaval kujul. Ja paljud teist aitavad mind ;-)

Mida me hakkame tegema? Kitsas tähenduses on kombinatoorika mitmesuguste kombinatsioonide arvutamine, mida saab teha teatud hulgast diskreetne objektid. Objektide all mõistetakse mis tahes isoleeritud objekte või elusolendeid – inimesi, loomi, seeni, taimi, putukaid jne. Samas ei huvita kombinatoorikat üldse, et komplekt koosneb mannataldrikust, jootekolbist ja rabakonnast. Põhimõtteliselt on oluline, et need objektid oleksid loendatavad – neid on kolm. (diskreetsus) ja on oluline, et ükski neist poleks sarnane.

Kui palju on lahendatud, siis nüüd kombinatsioonidest. Levinumad kombinatsioonitüübid on objektide permutatsioonid, nende valik komplektist (kombinatsioon) ja jaotus (paigutus). Vaatame, kuidas see praegu juhtub:

Permutatsioonid, kombinatsioonid ja paigutused ilma kordamiseta

Ärge kartke ebaselgeid termineid, eriti kuna mõned neist pole tõesti väga edukad. Alustame pealkirja sabast – mida teeb? ilma kordamiseta"? See tähendab, et selles jaotises käsitleme komplekte, mis koosnevad mitmesugused objektid. Näiteks ... ei, jootekolvi ja konnaga putru ei paku, midagi maitsvamat on parem =) Kujutage ette, et teie ees lauale materialiseerusid õun, pirn ja banaan (kui on mis tahes, saab olukorda reaalselt simuleerida). Laotame puuviljad vasakult paremale järgmises järjekorras:

õun / pirn / banaan

Küsimus üks: Mitmel viisil saab neid ümber korraldada?

Üks kombinatsioon on juba ülalpool kirjutatud ja ülejäänutega pole probleeme:

õun / banaan / pirn
pirn / õun / banaan
pirn / banaan / õun
banaan / õun / pirn
banaan / pirn / õun

Kokku: 6 kombinatsiooni või 6 permutatsioonid.

No ei olnud raske siin kõiki võimalikke juhtumeid loetleda, aga mis siis, kui objekte on rohkem? Juba nelja erineva viljaga suureneb kombinatsioonide arv oluliselt!

Palun avage võrdlusmaterjal (Käsiraamatut on lihtne printida) ja lõikest 2 leidke permutatsioonide arvu valem.

Ei mingit piina – 3 objekti saab mitmel viisil ümber paigutada.

Teine küsimus: Mitmel viisil saab valida a) ühe vilja, b) kahte vilja, c) kolme vilja, d) vähemalt ühe vilja?

Miks valida? Nii et nad ajasid eelmises lõigus isu üles – selleks, et süüa! =)

a) Ühte puuvilja saab valida loomulikult kolmel viisil - võtke kas õun, pirn või banaan. Ametlik loendus põhineb kombinatsioonide arvu valem:

Sel juhul tuleks kirjet mõista järgmiselt: "Mitmel viisil saate valida ühe puuvilja kolmest?"

b) Loetleme kõik võimalikud kahe puuvilja kombinatsioonid:

õun ja pirn;
õun ja banaan;
pirn ja banaan.

Kombinatsioonide arvu on lihtne kontrollida sama valemiga:

Kirjet mõistetakse sarnaselt: "mitme viisil saate valida 2 puuvilja kolmest?".

c) Ja lõpuks saab ainulaadsel viisil valida kolm puuvilja:

Muide, kombinatsioonide arvu valem on mõttekas ka tühja proovi jaoks:
Nii ei saa valida mitte ühtegi puuvilja – tegelikult ei võta midagi ja kõik.

d) Mitmel viisil saate võtta vähemalt üks puuvilju? Tingimus "vähemalt üks" tähendab, et oleme rahul 1 puuviljaga (ükskõik millise) või 2 puuviljaga või kõigi 3 puuviljaga:
kuidas saate valida vähemalt ühe puuvilja.

Lugejad, kes on sissejuhatava õppetunni hoolikalt uurinud tõenäosusteooria midagi juba välja mõelnud. Plussmärgi tähendusest aga hiljem.

Järgmisele küsimusele vastamiseks vajan kahte vabatahtlikku ... ... No kuna keegi ei taha, siis helistan juhatusse =)

Kolmas küsimus: Mitmel viisil saab Dašale ja Natašale ühte puuvilja jagada?

Kahe puuvilja levitamiseks peate need kõigepealt välja valima. Eelmise küsimuse lõigu "olla" järgi saab seda teha mitmel viisil, kirjutan need uuesti ümber:

õun ja pirn;
õun ja banaan;
pirn ja banaan.

Nüüd on aga kombinatsioone kaks korda rohkem. Mõelge näiteks esimesele puuviljapaarile:
võite ravida Dašat õunaga ja Natašat pirniga;
või vastupidi - Daša saab pirni ja Nataša saab õuna.

Ja selline permutatsioon on võimalik iga puuviljapaari jaoks.

Mõelge samale õpilasrühmale, kes käis tantsimas. Kui mitmel viisil saab poissi ja tüdrukut paari panna?

Võimalusi valida 1 noormees;
kuidas saate valida 1 tüdruku.

Nii et üks noormees ja valida saab ühe tüdruku: viise.

Kui igast komplektist on valitud 1 objekt, kehtib kombinatsioonide loendamise põhimõte: " kõikühest komplektist pärit objekt võib moodustada paari igaga teise komplekti objekt.

See tähendab, et Oleg võib kutsuda tantsima ükskõik millise 13 tüdrukust, Jevgeni võib kutsuda ka ükskõik kelle kolmeteistkümnest ja samasugune valik on ka teistel noortel. Kokku: võimalikud paarid.

Tuleb märkida, et selles näites pole paari moodustamise "ajalugu" oluline; kui aga initsiatiivi arvesse võtta, siis tuleb kombinatsioonide arvu kahekordistada, sest iga 13 tüdrukust saab tantsima kutsuda ka iga poisi. Kõik sõltub konkreetse ülesande tingimustest!

Sarnane põhimõte kehtib ka keerulisemate kombinatsioonide puhul, näiteks: mitmel viisil saab valida kahte noormeest ja kaks tüdrukut KVN-sketis osalema?

liit Ja vihjab ühemõtteliselt, et kombinatsioone tuleb korrutada:

Võimalikud kunstnike rühmad.

Teisisõnu, iga võistelda saab poistepaar (45 ainulaadset paari). ükskõik milline paar tüdrukut (78 ainulaadset paari). Ja kui arvestada rollide jaotust osalejate vahel, siis tuleb kombinatsioone veelgi rohkem. ... ma väga tahan, aga siiski hoidun jätkamast, et mitte sisendada sinus vastumeelsust tudengielu vastu =).

Korrutamisreegel kehtib rohkemate kordajate kohta:

Ülesanne 8

Mitu kolmekohalist arvu, mis jaguvad 5-ga?

Otsus: selguse huvides tähistame seda numbrit kolme tärniga: ***

AT sadade koht võite kirjutada mis tahes arvu (1, 2, 3, 4, 5, 6, 7, 8 või 9). Null ei ole hea, sest sel juhul lakkab number olemast kolmekohaline.

Aga sisse kümnete koht("keskel") saate valida mis tahes 10 numbrist: .

Tingimuse järgi peab arv jaguma 5-ga. Arv jagub 5-ga, kui see lõpeb numbriga 5 või 0. Seega kõige vähemtähtsas numbris rahuldume 2 numbriga.

Kokku on: kolmekohalised arvud, mis jaguvad 5-ga.

Samas dešifreeritakse teos järgmiselt: “9 viisi, kuidas saab numbrit valida sadade koht ja 10 võimalust numbri valimiseks kümnete koht ja 2 teed sisse ühiku number»

Või veelgi lihtsam: iga 9 numbrist kuni sadade koht kombineeritud igaühega 10 numbrit kümnete koht ja igaühega kahekohaline ühikute arv».

Vastus: 180

Ja nüüd…

Jah, ma oleks peaaegu unustanud lubatud kommentaari ülesandele nr 5, kus Borjale, Dimale ja Volodjale saab jaotada igaühele erineval viisil ühe kaardi. Korrutamisel on siin sama tähendus: mõnel viisil saate kaardipakist välja võtta 3 kaarti Ja igas proovi nende ümberkorraldamiseks.

Ja nüüd iseseisva lahenduse ülesanne ... nüüd mõtlen välja midagi huvitavamat, ... olgu see sama blackjacki vene versioon:

Ülesanne 9

Mitu 2 kaardi võidukombinatsiooni on "punkti" mängus?

Neile, kes ei tea: võidukombinatsioon 10 + ACE (11 punkti) = 21 punkti ja vaatleme kahe ässa võidukombinatsiooni.

(kaartide järjekord üheski paaris ei oma tähtsust)

Lühilahendus ja vastus tunni lõpus.

Muide, näidet pole vaja primitiivseks pidada. Blackjack on peaaegu ainus mäng, mille jaoks on olemas matemaatiliselt usaldusväärne algoritm, mis võimaldab kasiinot võita. Soovijad leiavad hõlpsalt palju teavet optimaalse strateegia ja taktika kohta. Tõsi, sellised meistrid langevad kiiresti kõigi asutuste musta nimekirja =)

On aeg koondada materjal, mis on kaetud paari kindla ülesandega:

10. ülesanne

Vasjal on kodus 4 kassi.

a) Mitmel viisil saab kasse toanurkadesse istutada?
b) Kui mitmel viisil võib kassidel hulkuma lasta?
c) mitmel viisil saab Vasya kahte kassi (üks vasakult, teine ​​paremalt) korjata?

Meie otsustame: esiteks tuleks jällegi märkida, et probleem on umbes erinev objektid (isegi kui kassid on identsed kaksikud). See on väga oluline tingimus!

a) Kasside vaikimine. Selle hukkamise suhtes kohaldatakse kõik kassid korraga
+ nende asukoht on oluline, seega on siin permutatsioone:
viisid, kuidas kasse toanurkadesse istutada.

Kordan, et permuteerimisel loeb ainult erinevate objektide arv ja nende suhteline asukoht. Vasja võib olenevalt tujust istutada loomad poolringis diivanile, ritta aknalauale jne. - permutatsioone on kõigil juhtudel 24. Mugavuse huvides võivad soovijad ette kujutada, et kassid on mitmevärvilised (näiteks valged, mustad, punased ja triibulised) ja loetleda kõik võimalikud kombinatsioonid.

b) Kui mitmel viisil võib kassidel hulkuma lasta?

Eeldatakse, et kassid lähevad jalutama ainult ukse kaudu, samas kui küsimus viitab ükskõiksusele loomade arvu suhtes - jalutama võivad minna 1, 2, 3 või kõik 4 kassi.

Kaalume kõiki võimalikke kombinatsioone:

Võimalused, kuidas saate ühe kassi (ükskõik milline neljast) jalutama lasta;
viisid, kuidas saate lasta kahel kassil jalutama minna (loetlege valikud ise);
viisid, kuidas kolm kassi jalutama lasta (üks neljast istub kodus);
kuidas saate kõik kassid vabastada.

Tõenäoliselt arvasite, et saadud väärtused tuleks kokku võtta:
viise, kuidas lasta kassil jalutama minna.

Entusiastidele pakun probleemi keerulise versiooni - kui suvaline kass suvalisest proovist saab suvaliselt õue minna, nii uksest kui ka 10. korruse aknast. Kombinatsioone tuleb veelgi!

c) Kui mitmel viisil saab Vasya kahte kassi korjata?

Olukord ei hõlma mitte ainult 2 looma valikut, vaid ka nende asetamist kätele:
kuidas saate 2 kassi peale võtta.

Teine lahendus: teatud viisil saate valida kaks kassi ja istutamise viisid iga paar käes:

Vastus: a) 24, b) 15, c) 12

Noh, südametunnistuse puhastamiseks midagi täpsemat kombinatsioonide korrutamise kohta .... Las Vasyal on 5 lisakassi =) Mitu võimalust saate lasta 2 kassil jalutama minna ja 1 kass?

See tähendab, et koos iga paar kassi saab lahti lasta iga kass.

Veel üks nupuakordion iseseisvaks lahenduseks:

Ülesanne 11

12-korruselise maja lifti pääses 3 reisijat. Igaüks, sõltumata teistest, võib sama tõenäosusega väljuda ükskõik milliselt (alates 2. korruselt). Mitmel viisil:

1) Reisijad saavad väljuda samal korrusel (väljumise järjekord ei oma tähtsust);
2) ühel korrusel saavad maha kaks inimest ja teisel kolmas;
3) inimesed saavad väljuda erinevatel korrustel;
4) Kas reisijad saavad liftist väljuda?

Ja siin küsitakse sageli uuesti, täpsustan: kui samale korrusele läheb välja 2 või 3 inimest, siis väljumise järjekord ei oma tähtsust. MÕTLE, kasuta liitmise/korrutamise kombinatsioonide jaoks valemeid ja reegleid. Raskuste korral on reisijatel kasulik nimetada ja põhjendada, millistes kombinatsioonides nad liftist välja pääsevad. Pole vaja ärrituda, kui midagi ei õnnestu, näiteks punkt number 2 on üsna salakaval.

Täielik lahendus koos üksikasjalike kommentaaridega õpetuse lõpus.

Viimane lõik on pühendatud kombinatsioonidele, mis esinevad samuti üsna sageli - minu subjektiivse hinnangu kohaselt umbes 20-30% kombinatoorsetest probleemidest:

Permutatsioonid, kombinatsioonid ja paigutused kordustega

Loetletud kombinatsioonide tüübid on välja toodud võrdlusmaterjali punktis nr 5 Kombinatoorika põhivalemid mõned neist ei pruugi aga esimesel lugemisel väga selged olla. Sel juhul on soovitatav kõigepealt tutvuda praktiliste näidetega ja alles seejärel mõista üldist sõnastust. Mine:

Permutatsioonid kordustega

Kordustega permutatsioonides, nagu "tavalistes" permutatsioonides, kogu objektide komplekt korraga, kuid on üks asi: selles komplektis kordub üks või mitu elementi (objekti). Vastake järgmisele standardile:

Ülesanne 12

Kui palju erinevaid tähekombinatsioone saab järgmiste tähtedega kaartide ümberpaigutamisel: K, O, L, O, K, O, L, L, H, I, K?

Otsus: juhul, kui kõik tähed olid erinevad, tuleks rakendada triviaalset valemit, kuid on üsna selge, et pakutud kaartide komplekti puhul töötavad mõned manipulatsioonid "tühikäigul", nii et näiteks kui vahetate suvalised kaks kaardid tähtedega "K igas sõnas, see on sama sõna. Veelgi enam, füüsiliselt võivad kaardid olla väga erinevad: üks võib olla ümmargune trükitud tähega “K”, teine ​​on ruudukujuline, millele on joonistatud “K”. Aga vastavalt probleemi tähendusele isegi sellised kaardid samaks peetud, kuna tingimus küsib tähekombinatsioonide kohta.

Kõik on äärmiselt lihtne - kokku: 11 kaarti, sealhulgas kiri:

K - korratakse 3 korda;
O - korratakse 3 korda;
L - korratakse 2 korda;
b - korratakse 1 kord;
H - korratakse 1 kord;
Ja - kordub 1 kord.

Kontrollige: 3 + 3 + 2 + 1 + 1 + 1 = 11, mida me tahtsime kontrollida.

Vastavalt valemile kordustega permutatsioonide arv:
saab erinevaid tähekombinatsioone. Rohkem kui pool miljonit!

Suure faktoriaalväärtuse kiireks arvutamiseks on mugav kasutada tavalist Exceli funktsiooni: skoori teeme igas lahtris =FAKT(11) ja klõpsake Sisenema.

Praktikas on üsna vastuvõetav üldvalemit mitte üles kirjutada ja lisaks jätta välja ühikfaktoriaalid:

Kuid korduvate kirjade kohta on vajalikud eelnevad kommentaarid!

Vastus: 554400

Teine tüüpiline näide kordustega permutatsioonidest on malenuppude paigutuse probleem, mida võib leida laost valmislahendused vastavas pdf-is. Ja iseseisva lahenduse jaoks pakkusin välja vähem malliülesande:

Ülesanne 13

Aleksei tegeleb spordiga ja 4 päeva nädalas - kergejõustikuga, 2 päeva - jõuharjutused ja 1 puhkepäev. Kui mitmel viisil saab ta oma iganädalasi tunde ajastada?

Valem siin ei tööta, kuna see võtab arvesse kattuvaid permutatsioone (näiteks kui kolmapäevased jõuharjutused asendatakse neljapäevaste jõuharjutustega). Ja veelkord – tegelikult võivad samad 2 jõutreeningut üksteisest vägagi erineda, kuid ülesande kontekstis (graafiku mõttes) käsitletakse neid samade elementidena.

Kaherealine lahendus ja vastus tunni lõpus.

Kombinatsioonid kordustega

Seda tüüpi kombinatsioonide iseloomulik tunnus on see, et valim koostatakse mitmest rühmast, millest igaüks koosneb samadest objektidest.

Kõik tegid täna kõvasti tööd, seega on aeg end värskendada:

14. ülesanne

Tudengikohvikus on müügil taignas vorstid, juustukoogid ja sõõrikud. Mitmel viisil saab osta viit kooki?

Otsus: pöörake kohe tähelepanu kordustega kombinatsioonide tüüpilisele kriteeriumile - vastavalt seisundile mitte objektide komplekt kui selline, vaid erinevat tüüpi esemed; oletatakse, et müügil on vähemalt viis hot dogi, 5 juustukooki ja 5 sõõrikut. Iga grupi pirukad on muidugi erinevad - sest absoluutselt identseid sõõrikuid saab simuleerida ainult arvutis =) Pirukate füüsilised omadused pole aga probleemi tähenduse seisukohalt olulised ja hot dogid / juustukoogid / sõõrikud nende rühmades peetakse samadeks.

Mis võib olla proovis? Esiteks tuleb tähele panna, et proovis on kindlasti identsed pirukad (sest valime 5 tükki ja valikus on 3 sorti). Siin on valikud igale maitsele: 5 hot dogi, 5 juustukooki, 5 sõõrikut, 3 hot dogi + 2 juustukooki, 1 hot dog + 2 + juustukoogid + 2 sõõrikut jne.

Nagu "tavaliste" kombinatsioonide puhul, ei oma pirukate valimise ja paigutuse järjekord valimisse tähtsust - nad valisid lihtsalt 5 tükki ja kõik.

Kasutame valemit kordustega kombinatsioonide arv:
kuidas saab osta 5 pirukat.

Head isu!

Vastus: 21

Millise järelduse saab teha paljudest kombinatoorsetest probleemidest?

Mõnikord on kõige keerulisem seisundist aru saada.

Sarnane näide isetegemise lahendusest:

Ülesanne 15

Rahakotis on üsna palju 1-, 2-, 5- ja 10-rublaseid münte. Mitmel viisil saab kolm münti rahakotist välja võtta?

Enesekontrolli eesmärgil vastake paarile lihtsale küsimusele:

1) Kas kõik proovis olevad mündid võivad olla erinevad?
2) Nimetage "odavaim" ja "kallim" müntide kombinatsioon.

Lahendus ja vastused tunni lõpus.

Oma isiklikust kogemusest võin öelda, et kombinatsioonid kordustega on praktikas kõige haruldasem külaline, mida ei saa öelda järgmist tüüpi kombinatsioonide kohta:

Kordustega paigutused

Elementidest koosnevast komplektist valitakse välja elemendid ning oluline on elementide järjekord igas valimis. Ja kõik oleks hästi, kuid üsna ootamatu nali on see, et me saame valida originaalkomplekti mistahes objekti nii mitu korda kui tahame. Piltlikult öeldes "hulk ei vähene".

Millal see juhtub? Tüüpiline näide on mitme kettaga kombinatsioonlukk, kuid tehnoloogia arengu tõttu on asjakohasem arvestada selle digitaalse järeltulijaga:

Ülesanne 16

Mitu 4-kohalist PIN-koodi on?

Otsus: tegelikult piisab probleemi lahendamiseks ainult kombinatoorika reeglite tundmisest: saate valida PIN-koodi esimese numbri mitmel viisil ja viisid - PIN-koodi teine ​​number ja sama mitmel viisil - kolmandik ja sama palju - neljas. Seega saab kombinatsioonide korrutamise reegli järgi neljakohalise pin-koodi koostada: viisidel.

Ja nüüd valemiga. Tingimuste järgi pakutakse meile numbrite komplekti, mille hulgast numbrid valitakse ja paigutatakse kindlas järjekorras, samas kui proovis olevaid numbreid saab korrata (st algse komplekti mis tahes numbrit saab kasutada suvalise arvu kordi). Kordustega paigutuste arvu valemi järgi:

Vastus: 10000

Mis siinkohal meelde tuleb ... ... kui sularahaautomaat pärast kolmandat ebaõnnestunud PIN-koodi sisestamise katset kaardi "sööb", siis on selle juhusliku kättesaamise võimalus väga illusoorne.

Ja kes ütles, et kombinatoorikas pole praktilist mõtet? Kognitiivne ülesanne kõigile saidi lugejatele:

Probleem 17

Riigistandardi järgi koosneb auto numbrimärk 3 numbrist ja 3 tähest. Sel juhul pole kolme nulliga number lubatud ja tähed valitakse hulgast A, B, E, K, M, H, O, R, C, T, U, X (kasutatakse ainult neid kirillitsa tähti, mille kirjapilt ühtib ladina tähtedega).

Mitu erinevat numbrimärki saab ühe piirkonna jaoks koostada?

Mitte nii, muide, ja palju. Suurtes piirkondades sellest numbrist ei piisa ja seetõttu on nende jaoks kirjas RUS mitu koodi.

Lahendus ja vastus tunni lõpus. Ärge unustage kasutada kombinatoorika reegleid ;-) …tahtsin uhkeldada, et olen eksklusiivne, aga selgus, et see pole eksklusiivne =) Vaatasin Vikipeediat - seal on arvutused, aga ilma kommentaarideta. Kuigi hariduslikel eesmärkidel lahendasid seda ilmselt vähesed.

Meie põnev õppetund on lõppenud ja lõpetuseks tahan öelda, et te ei raisanud oma aega – põhjusel, et kombinatoorika valemid leiavad veel ühe olulise praktilise rakenduse: neid leiab erinevatest ülesannetest. tõenäosusteooria,
ja sisse ülesanded tõenäosuse klassikalise definitsiooni kohta- eriti sageli

Täname kõiki aktiivse osalemise eest ja peatse kohtumiseni!

Lahendused ja vastused:

Ülesanne 2: Otsus: leidke 4 kaardi kõigi võimalike permutatsioonide arv:

Kui nulliga kaart on 1. kohal, muutub number kolmekohaliseks, seega tuleks need kombinatsioonid välistada. Olgu 1. kohal null, siis saab ülejäänud 3 kõige vähemtähtsate numbrite numbrit viisil ümber paigutada.

Märge : sest kaarte on vähe, siin on lihtne loetleda kõik sellised valikud:
0579
0597
0759
0795
0957
0975

Seega saate pakutud komplektist teha:
24 - 6 = 18 neljakohalist numbrit
Vastus : 18

Ülesanne 4: Otsus: 3 kaarti saab valida 36 võimaluse hulgast.
Vastus : 7140

Ülesanne 6: Otsus: viise.
Teine lahendus : viisid, kuidas saate valida rühmast kaks inimest ja ja
2) “Odavaim” komplekt sisaldab 3 rubla münti ja kõige “kallim” komplekt sisaldab 3 kümnerublast münti.

Ülesanne 17: Otsus: viisid, kuidas saate numbrimärgist digitaalse kombinatsiooni teha, samas kui üks neist (000) tuleks välja jätta:.
viisid, kuidas saate autonumbrist tähekombinatsiooni teha.
Kombinatsioonide korrutamise reegli kohaselt saab kõike koostada:
autode numbrid
(iga kombineeritud digitaalne kombinatsioon igaühega tähekombinatsioon).
Vastus : 1726272

Materjalis navigeerimise hõlbustamiseks lisan selle teema sisu:

Sissejuhatus. Komplektid ja valikud.

Selles teemas käsitleme kombinatoorika põhimõisteid: permutatsioonid, kombinatsioonid ja paigutused. Uurime välja nende olemuse ja valemid, mille abil saate nende arvu leida.

Alustuseks vajame taustateavet. Alustame sellisest fundamentaalsest matemaatilisest kontseptsioonist nagu hulk. Täpsemalt kirjeldati hulga mõistet teemas "Hulgu mõiste. Hulkade määramise meetodid" .

Väga lühike lugu rahvahulgast: Näita Peida

Lühidalt öeldes on komplekt esemete kogum. Komplektid on kirjutatud lokkis sulgudes. Elementide kirjutamise järjekord ei oma tähtsust; elementide kordamine ei ole lubatud. Näiteks numbri 11115555999 numbrite komplekt on: $\(1,5,9 \)$. Konsonanttähtede komplekt sõnas "tiigrikutsikas" on järgmine: $\(t, r, r, n, k\)$. Märkus $5\in A$ tähendab, et element 5 kuulub hulka $A=\(1,5,9 \)$. Elementide arvu lõplikus hulgas nimetatakse võimsus sellest komplektist ja on tähistatud $|A|$. Näiteks 3 elementi sisaldava hulga $A=\(1,5,9 \)$ jaoks on meil: $|A|=3$.

Vaatleme mõnda mittetühja lõplikku hulka $U$, mille kardinaalsus on $n$, $|U|=n$ (st. hulgal $U$ on $n$ elemente). Tutvustame sellist mõistet nagu näidis(mõned autorid nimetavad seda korteežiks). $n$ elementide suuruse $k$ valimi all (lühendatult $(n,k)$-valik) peame silmas elementide komplekti $(a_1, a_2,\ldots, a_k)$, kus $a_i\in U$. Valik loetakse tellituks, kui selles on määratud elementide järjekord. Kaks järjestatud näidist, mis erinevad ainult elementide järjestuse poolest, on erinevad. Kui valimi elementide järjekord ei ole oluline, nimetatakse valimit järjestamata.

Pange tähele, et valiku definitsioon ei ütle midagi üksuste korduste kohta. Erinevalt komplektielementidest saab valikuelemente korrata.

Näiteks kaaluge hulka $U=\(a,b,c,d,e\)$. Komplekt $U$ sisaldab 5 elementi, s.o. $|U|=5$. Näidis ilma kordusteta võib olla: $(a,b,c)$. See proov sisaldab 3 elementi, st. selle valimi suurus on 3. Teisisõnu, see on $(5,3)$-valim.

Kordustega näidis võiks olla: $(a,a,a,a,a,c,c,d)$. See sisaldab 8 elementi, st. selle maht on 8. Teisisõnu, see on $(5,8)$-proov.

Mõelge veel kahele $(5,3)$-näidisele: $(a,b,b)$ ja $(b,a,b)$. Kui eeldame, et meie valimid on järjestamata, siis valim $(a,b,b)$ on võrdne valimiga $(b,a,b)$, st. $(a,b,b)=(b,a,b)$. Kui eeldame, et meie proovid on tellitud, siis $(a,b,b)\neq(b,a,b)$.

Vaatame teist näidet, veidi vähem abstraktset :) Oletame, et korvis on kuus kommi ja kõik on erinevad. Kui esimesele kommile on omistatud number 1, teisele kommile number 2 ja nii edasi, siis saab ostukorvis olevate kommidega seostada järgmise komplekti: $U=\(1,2,3,4,5 ,6\)$. Kujutage ette, et paneme juhuslikult käe korvi, et sealt kolm maiustust välja tõmmata. Väljatõmmatud maiustused - see on näidis. Kuna me tõmbame 6-st välja 3 kommi, saame (6,3)-proovi. Kommide peopessa asetamise järjekord on täiesti ebaoluline, seega on see proov järjestamata. No ja kuna kõik kommid on erinevad, siis on proov ilma kordamiseta. Niisiis, antud olukorras räägime järjestamata (6,3)-valikust ilma kordusteta.

Nüüd lähme teiselt poolt. Kujutagem ette, et oleme kommivabrikus ja see tehas toodab nelja tüüpi komme. Komplekt $U$ selles olukorras on järgmine: $U=\(1,2,3,4 \)$ (iga number vastutab isemoodi kommi eest). Kujutage nüüd ette, et kõik maiustused valatakse ühte renni, mille lähedal me seisame. Ja peopesade asemel valime sellest voost 20 maiustust. Kommid peotäis – see on näidis. Kas peotäie kommide järjekord mängib rolli? Loomulikult ei, seega on proov järjestamata. Maiustusi on ainult 4 sorti ja üldisest voolust valime paarkümmend tükki - sortide kordused on paratamatud. Samas võivad näidised olla väga erinevad: meil võivad isegi olla kõik sama sorti kommid. Järelikult on antud olukorras tegemist kordustega järjestamata (4.20)-valikuga.

Vaatame veel paari näidet. Kuubikutele olgu kirjutatud 7 erinevat tähte: k, o, n, f, e, t, a. Need tähed moodustavad hulga $U=\(k,o,n,f,e,t,a\)$. Oletame, et tahame nendest kuubikutest teha 5-tähelisi "sõnu". Nende sõnade tähed (näiteks "confé", "tenko" ja nii edasi) moodustavad (7,5) - valikud: $(k,o,n,f,e)$, $(t,e,n ,k ,o)$ jne. Ilmselgelt on sellises valimis tähtede järjekord oluline. Näiteks sõnad "nokft" ja "kfton" on erinevad (kuigi need koosnevad samadest tähtedest), kuna neil ei ole sama tähtede järjekord. Sellistes “sõnades” pole tähtede kordusi, sest kuubikesi on vaid seitse. Seega on iga sõna tähtede komplekt järjestatud (7,5)-näidis ilma kordusteta.

Veel üks näide: neljakohalistest numbritest 1, 5, 7, 8 valmistame igasuguseid kaheksakohalisi numbreid. Näiteks 11111111, 15518877, 88881111 jne. Komplekt $U$ on järgmine: $U=\(1,5,7,8\)$. Iga koostatud arvu numbrid moodustavad (4,8)-valimi. Tähtis on numbrite järjekord numbris, s.t. proov on tellitud. Lubatud on kordused, seega on siin tegemist järjestatud (4,8)-valikuga kordustega.

Jaotused ilma $n$ elementide kordusteta $k$ võrra

Jaotus ilma $n$ elementide kordusteta $k$ kaupa - järjestatud $(n,k)$-valik ilma kordusteta.

Kuna vaadeldava valimi elemente ei saa korrata, ei saa me valimisse valida rohkem elemente, kui neid on algses komplektis. Seetõttu kehtib selliste valimite puhul järgmine ebavõrdsus: $n≥ k$. Paigutuste arv ilma $n$ elementide kordusteta $k$ võrra määratakse järgmise valemiga:

\begin(võrrand)A_(n)^(k)=\frac(n{(n-k)!} \end{equation} !}

Mida tähendab märk "!"?: Näita Peida

Salvestus "n!" (loe "en faktoriaal") tähistab kõigi arvude korrutist 1-st n-ni, st.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

Definitsiooni järgi eeldatakse, et $0!=1!=1$. Näiteks leiame 5!:

5 $!=1\cpunkt 2\cpunkt 3\cpunkt 4\cpunkt 5=120. $$

Näide nr 1

Tähestik koosneb märkide komplektist $E=\(+,*,0,1,f\)$. Teeme kindlaks selliste kolmekohaliste sõnade arvu selles tähestikus, mis ei sisalda korduvaid tähti.

Kolmekohaliste sõnade all peame silmas selliseid väljendeid nagu "+*0" või "0f1". Komplektis $E$ on viis elementi, seega moodustavad kolmekohaliste sõnade tähed (5,3)-valimised. Esimene küsimus on: kas need näidised on tellitud või mitte? Sõnu, mis erinevad ainult tähtede järjekorra poolest, eeldatakse olevat erinevad, seega on oluline elementide järjekord valimis. Seega on proov tellitud. Teine küsimus: kas kordused on lubatud või mitte? Sellele küsimusele annab vastuse tingimus: sõnad ei tohi sisaldada korduvaid tähti. Kokkuvõte: iga ülesande tingimust rahuldava sõna tähed moodustavad järjestatud (5,3)-valimi ilma kordusteta. Teisisõnu, iga sõna tähed moodustavad paigutuse ilma 5 elemendi 3 kordusteta. Siin on näited selliste paigutuste kohta:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Oleme huvitatud ka nende paigutuste koguarvust. Valemi (1) kohaselt on paigutuste arv ilma 5 elemendi 3 kordamiseta järgmine:

$$ A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

Need. saate teha 60 kolmekohalist sõna, mille tähed ei kordu.

Vastus: 60.

Jaotused $n$ elementide kordustega $k$ võrra

Paigutus $n$ elementide kordustega üle $k$ on järjestatud $(n,k)$-valik kordustega.

Paigutuste arv, mille $n$ elemente korduvad $k$ võrra, määratakse järgmise valemiga:

\begin(võrrand)\bar(A)_(n)^(k)=n^k \end(võrrand)

Näide nr 2

Mitu viiekohalist arvu saab moodustada numbrite hulgast $\(5,7,2\)$?

Sellest numbrikomplektist saate teha viiekohalisi numbreid 55555, 75222 ja nii edasi. Iga sellise arvu numbrid moodustavad (3,5)-näidise: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Küsigem endalt: mis need näidised on? Esiteks saab arvudes olevaid numbreid korrata, seega on tegemist kordustega näidistega. Teiseks on oluline numbrite järjekord numbris. Näiteks 27755 ja 77255 on erinevad numbrid. Seetõttu on meil tegemist järjestatud (3,5)-valikutega koos kordustega. Selliste proovide koguarvu (st nõutavate viiekohaliste arvude koguarvu) saab leida valemi (2) abil:

$$ \bar(A)_(3)^(5)=3^5=243. $$

Seega saab antud numbritest teha 243 viiekohalist arvu.

Vastus: 243.

Permutatsioonid ilma $n$ elementide kordusteta

Permutatsioon ilma $n$ elementide kordusteta on järjestatud $(n,n)$-valik ilma kordusteta.

Tegelikult on kordusteta permutatsioon ilma korduseta paigutuse erijuhtum, kui valimi suurus on võrdne algse komplekti võimsusega. Permutatsioonide arv ilma $n$ elementide kordusteta määratakse järgmise valemiga:

\begin(võrrand)P_(n)=n! \end(võrrand)

Muide, seda valemit on lihtne saada, kui võtta arvesse, et $P_n=A_(n)^(n)$. Siis saame:

$$ P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Näide nr 3

Sügavkülmas on viis portsjonit erinevate firmade jäätist. Kui mitmel viisil saate valida nende söömise järjekorda?

Vastagu number 1 esimesele jäätisele, number 2 teisele ja nii edasi. Saame komplekti $U=\(1,2,3,4,5\)$, mis tähistab sügavkülmiku sisu. Söögijärjekord võib olla $(2,1,3,5,4)$ või $(5,4,3,1,2)$. Iga selline kollektsioon on (5,5)-proov. See on korrapärane ja ilma kordusteta. Teisisõnu, iga selline valim on algse komplekti 5 elemendi permutatsioon. Vastavalt valemile (3) on nende permutatsioonide koguarv:

$$ P_5=5!=120. $$

Seega on 120 toidukorra tellimust.

Vastus: 120.

Permutatsioonid kordustega

Kordustega permutatsioon on järjestatud $(n,k)$-valik kordustega, milles elementi $a_1$ korratakse $k_1$ korda, $a_2$ korratakse $k_2$ korda ja nii edasi kuni viimase elemendini $a_r$, mida korratakse $ k_r$ korda. Lisaks $k_1+k_2+\ldots+k_r=k$.

Kordustega permutatsioonide koguarv saadakse järgmiselt:

\begin(võrrand)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Näide nr 4

Sõnad moodustatakse tähestiku $U=\(a,b,d\)$ alusel. Mitu erinevat seitsmest tähemärgist koosnevat sõna saab koostada, kui täht "a" tuleb nendes sõnades 2 korda korrata; täht "b" - 1 kord ja täht "d" - 4 korda?

Siin on näited otsingusõnadest: "aabdddd", "daddabd" ja nii edasi. Iga sõna tähed moodustavad kordustega (3,7)-näidise: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ ja jne. Iga selline valik koosneb kahest "a" elemendist, ühest "b" elemendist ja neljast "d" elemendist. Teisisõnu $k_1=2$, $k_2=1$, $k_3=4$. Kõigi märkide korduste koguarv on loomulikult võrdne valimi suurusega, st. $k=k_1+k_2+k_3=7$. Asendades need andmed valemisse (4), saame:

$$ P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105. $$ !}

Seetõttu on otsitud sõnade koguarv 105.

Vastus: 105.

Kombinatsioonid ilma $n$ elementide kordusteta $k$ võrra

Kombinatsioon ilma $n$ elementide kordusteta $k$ võrra on järjestamata $(n,k)$-valik ilma kordusteta.

Kombinatsioonide koguarv ilma $n$ elementide kordusteta $k$ võrra määratakse järgmise valemiga:

\begin(võrrand)C_(n)^(k)=\frac(n{(n-k)!\cdot k!} \end{equation} !}

Näide nr 5

Korvis on kaardid, millele on kirjutatud täisarvud 1 kuni 10. Korvist võetakse välja 4 kaarti ja summeeritakse neile kirjutatud numbrid. Mitu erinevat kaardikomplekti saab korvist välja tõmmata?

Seega on selles ülesandes esialgne komplekt järgmine: $U=\(1,2,3,4,5,6,7,8,9,10\)$. Sellest komplektist valime välja neli elementi (st neli kaarti ostukorvist). Väljatõmmatud elementide numbrid moodustavad (10,4)-valimi. Selles proovis ei ole kordused lubatud, kuna kõikide kaartide numbrid on erinevad. Küsimus on selles, kas kaartide valimise järjekord on oluline või mitte? See tähendab, et näiteks kas näidised $(1,2,7,10)$ ja $(10,2,1,7)$ on võrdsed või mitte? Siin peate pöörduma probleemi olukorra poole. Kaardid võetakse välja, et seejärel leida elementide summa. Ja see tähendab, et kaartide järjekord ei ole oluline, kuna summa ei muutu tingimuste kohtade muutmisest. Näiteks näidis $(1,2,7,10)$ ja näidis $(10,2,1,7)$ vastavad samale numbrile $1+2+7+10=10+2+1+7 = 20 dollarit. Järeldus: probleemi olukorrast järeldub, et tegemist on tellimata proovidega. Need. peame leidma järjestamata (10,4) proovide koguarvu ilma kordusteta. Teisisõnu peame leidma 10 elemendi kombinatsioonide arvu 4 võrra. Kasutame selleks valemit (5):

$$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Seetõttu on vajalike komplektide koguarv 210.

Vastus: 210.

Kombinatsioonid $n$ elementide kordustega $k$ võrra

Kombinatsioon $n$ elementide kordustega üle $k$ on järjestamata $(n,k)$-valik kordustega.

Kombinatsioonide koguarv korduste $n$ elementidega üle $k$ määratakse järgmise valemiga:

\begin(võrrand)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!} \end{equation} !}

Näide nr 6

Kujutage ette, et oleme kommivabrikus – otse konveieri kõrval, mida mööda liiguvad nelja sorti kommid. Me paneme oma käed sellesse voolu ja tõmbame neist välja kakskümmend. Mitu erinevat "kommikombinatsiooni" võib peotäies olla?

Kui eeldame, et number 1 vastab esimesele sortimisele, number 2 vastab teisele sortimisele ja nii edasi, siis on meie ülesande alghulk järgmine: $U=\(1,2,3,4\ )$. Sellest komplektist valime välja 20 elementi (st need samad 20 kommi konveierilt). Peotäis maiustusi moodustab (4,20)-proovi. Loomulikult korduvad sordid. Küsimus on selles, kas elementide järjekord valikus mängib rolli või mitte? Ülesande tingimustest järeldub, et elementide järjekord ei oma tähtsust. Meie jaoks ei ole vahet, kas peotäis sisaldab kõigepealt 15 pulgakommi ja seejärel 4 šokolaadi või kõigepealt 4 šokolaadi ja alles siis 15 pulgakommi. Niisiis, meil on tegemist järjestamata (4.20) kordustega valimiga. Nende proovide koguarvu leidmiseks kasutame valemit (6):

$$ \bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Seetõttu on soovitud kombinatsioonide koguarv 1771.

KOMBINAtoorium

Kombinatoorika on matemaatika haru, mis uurib teatud põhihulgast elementide valimise ja järjestamise probleeme vastavalt etteantud reeglitele. Kombinatoorika valemeid ja põhimõtteid kasutatakse tõenäosusteoorias juhuslike sündmuste tõenäosuse arvutamiseks ja vastavalt juhuslike suuruste jaotusseaduste saamiseks. See omakorda võimaldab uurida massiliste juhuslike nähtuste seaduspärasusi, mis on väga oluline looduses ja tehnikas avalduvate statistiliste seaduste õigeks mõistmiseks.

Kombinatoorika liitmise ja korrutamise reeglid

Summereegel. Kui kaks toimingut A ja B on üksteist välistavad ning toimingut A saab sooritada m ja B n viisil, siis saab mis tahes neist toimingutest (kas A või B) sooritada n + m viisil.

Näide 1

Klassis on 16 poissi ja 10 tüdrukut. Mitmel viisil saab ühte saatjat määrata?

Otsus

Valvesse saab määrata kas poisi või tüdruku, s.t. 16 poisist või 10 tüdrukust võib valves olla igaüks.

Vastavalt summareeglile saame, et ühele korrapidajale saab määrata 16+10=26 teed.

Toote reegel. Olgu nõutav k toimingu järjestikuse sooritamine. Kui esimest toimingut saab sooritada n 1 viisil, teist toimingut n 2 viisil, kolmandat n 3 viisil ja nii edasi kuni k-nda toiminguni, mida saab teha n k viisil, siis saab kõiki k toimingut koos teha esines:

viise.

Näide 2

Klassis on 16 poissi ja 10 tüdrukut. Kui mitmel viisil saab määrata kahte saatjat?

Otsus

Esimesena saab valves olla kas poiss või tüdruk. Sest klassis on 16 poissi ja 10 tüdrukut, siis saate määrata esimese korrapidaja 16 + 10 = 26 viisil.

Pärast seda, kui oleme valinud esimese korrapidaja, saame ülejäänud 25 inimese hulgast valida teise, s.o. 25 viisi.

Korrutusteoreemi järgi saab valida kaks saatjat 26*25=650 viisil.

Kombinatsioonid ilma kordusteta. Kombinatsioonid kordustega

Klassikaline kombinatoorika probleem on kordusteta kombinatsioonide arvu probleem, mille sisu saab väljendada küsimusega: kui palju viise saab vali m kaugusel n erinevat eset?

Näide 3

Kingituseks tuleb valida 10 erinevast raamatust 4. Kui mitmel viisil saab seda teha?

Otsus

Peame 10-st raamatust valima 4 ja valiku järjekord ei oma tähtsust. Seega peate leidma 10 elemendi kombinatsioonide arvu 4 võrra:

.

Mõelge kordustega kombinatsioonide arvu probleemile: on olemas r identset objekti, iga n erinevat tüüpi; kui palju viise saab vali m() of need (n*r) üksusi?

.

Näide 4

Kondiitripoes müüdi 4 sorti kooke: napoleonid, ekleerid, purukook ja lehtkook. Kui mitmel viisil saab osta 7 kooki?

Otsus

Sest 7 koogi hulgas võib olla sama sorti kooke, siis määrab 7 koogi ostmise viiside arv kombinatsioonide arvust kordustega 7 kuni 4.

.

Paigutused ilma kordusteta. Kordustega paigutused

Klassikaline kombinatoorika probleem on kordusteta paigutuste arvu probleem, mille sisu saab väljendada küsimusega: kui palju viise saab vali ja koht peal m erinev kohad m kaugusel n erinev esemed?

Näide 5

Mõnes ajalehes on 12 lehekülge. Selle ajalehe lehtedele on vaja paigutada neli fotot. Kui mitmel viisil saab seda teha, kui ühelgi ajalehe leheküljel ei tohi olla rohkem kui üks foto?

Otsus.

Selle ülesande puhul ei vali me lihtsalt fotosid, vaid asetame need ajalehe teatud lehtedele ja igal ajalehe leheküljel ei tohi olla rohkem kui üks foto. Seega taandatakse probleem klassikalisele probleemile, milleks on kordusteta paigutuste arvu määramine 12 elemendist 4 elemendi võrra:

Seega saab 12 leheküljel 4 fotot järjestada 11880 viisil.

Samuti on kombinatoorika klassikaliseks ülesandeks kordustega paigutuste arvu probleem, mille sisu saab väljendada küsimusega: kui palju viise saab sinabarmee ja koht peal m erinev kohad m kaugusel n esetkoosredi mis seal on sama?

Näide 6

Poisil olid lauamängu komplektist kaasas templid numbritega 1, 3 ja 7. Ta otsustas nende templite abil panna kõikidele raamatutele viiekohalised numbrid – koostada kataloog. Mitu erinevat viiekohalist numbrit suudab poiss teha?

Permutatsioonid ilma kordusteta. Permutatsioonid kordustega

Klassikaline kombinatoorika probleem on kordusteta permutatsioonide arvu probleem, mille sisu saab väljendada küsimusega: kui palju viise saab koht n mitmesugused esemed peal n erinev kohad?

Näide 7

Mitu neljatähelist "sõna" saab teha sõna "abielu" tähtedest?

Otsus

Üldine komplekt on 4 sõna "abielu" tähte (b, p, a, k). "Sõnade" arv määratakse nende 4 tähe permutatsioonidega, st.

Juhul, kui valitud n elemendi hulgas on samad (valik tagastusega), saab kordustega permutatsioonide arvu probleemi väljendada küsimusega: Mitmel viisil saab n objekti ümber paigutada n erinevas kohas, kui n objekti hulgas on k erinevat tüüpi (k< n), т. е. есть одинаковые предметы.

Näide 8

Mitu erinevat tähekombinatsiooni saab teha sõna "Mississippi" tähtedest?

Otsus

Seal on 1 täht "m", 4 tähte "i", 3 tähte "c" ja 1 täht "p", kokku 9 tähte. Seetõttu on kordustega permutatsioonide arv

TAUSTKOKKUVÕTE JAOTISE KOMBINAATOORIKA KOHTA