Kombinatoorika- See on matemaatika haru, mille põhiülesanne on loendada antud olukorras tekkivate valikute arv. Klassikalise tõenäosuse definitsiooni abil ülesandeid lahendades vajame mõningaid kombinatoorika valemeid.

Majutuskohad.

Definitsioon 1. Pannes ilma kordamiseta n elemendid poolt k mida iganes kutsutakse korrastatud antud hulga alamhulk M = (a 1 , a 2 , ¼, a n ), sisaldab k elementi.

Pange tähele, et definitsioonist tuleneb kohe, et esiteks on kõik elemendid paigutuses ilma kordusteta erinevad (muidu on kaks identset elementi), ja teiseks, k £ n, kolmandaks erinevad ka kaks erinevat paigutust ilma kordusteta koostis nende koostisosad või korras nende asukoht. See tähendab, et järjekord on oluline.

1. teoreem. Erinevate paigutuste arv ilma n elemendi kordusteta by k (k £ n) võrdub

Tõestus.

Lase M={a 1,a 2,¼,a n). On vaja kindlaks määrata vormi erinevate stringide arv ( x 1,x 2,¼,x k), kus kõik elemendid x 1,x 2,0,x k ОM ja erinev. Esimene element x 1 saab valida n viise. Kui a x 1 juba valitud, seejärel valimiseks x 2 vasakut n-1 elementi. Samamoodi x 3 saab valida n-2 viisi jne. Viimane element x k saab valida n-k+1 viise. Korrutades need arvud, saame valemi (4) Teoreem on tõestatud.

Näide 1 Klassis on 12 ainet ja esmaspäeval 5 erinevat tundi. Kui mitmel viisil saab esmaspäeva tunniplaani kokku panna?

Võimalike ajakavavalikute arv on ilmselgelt erinevate paigutuste arv 12 elemendist 5, see on

Oluline erijuhtum on juhtum, kui n=k, st kui stringis ( x1,x2,¼,xn) kaasatud on kõik komplekti elemendid M. Kordusteta stringid, mis koosnevad hulga n elemendist M nimetatakse n elemendi permutatsioonideks. Tuletame meelde, et matemaatikas läbi n! tähistage kõigi naturaalarvude korrutist 1-st n-ni, see tähendab ¼, ja arvestage definitsiooni järgi, et 0!=1.

Järeldus 1. Kasutades valemit (4), leiame, et erinevate permutatsioonide arv P n alates n elemendid on võrdsed P n = n!.

2. definitsioon. Paigutus kordustega n elemendid k on mis tahes järjestatud string k seada elemendid M = (a 1 , a 2 , ¼, a n ), millest mõnda võib korrata.

Näiteks sõna "ema" on paigutus kahe elemendi kordusega M=(m, a) 4 korda.

2. teoreem. Erinevate paigutuste arv kordustega alates n elemendid poolt k

Tõestus.

Esimene element stringis alates küksusi saab valida n viisidel, sest |M|=n. Samamoodi saab 2., 3., ...,k-ndat elementi valida n viisil. Korrutades need arvud, saame

küks kord

Teoreem on tõestatud.

Näide 2 Mitu erinevat kahekohalist arvu saab arvudest 1, 2, 3, 4, 5 teha?

Selles ülesandes M=(1, 2, 3, 4, 5), n=5, k = 2. Seetõttu on vastuseks arv

Näide 3 Kui mitmel viisil saab k reisijat jaotada n auto vahel, kui iga reisija jaoks on oluline ainult auto arv, mitte koht, mille ta autos hõivab?

Nummerdage kõik reisijad ümber. Lase x 1 - esimese reisija valitud vaguni number, x 2 - teise reisija auto number, ..., x k- vaguni number k-reisija. rida ( x 1,x 2,¼,x k) iseloomustab täielikult sõitjate jaotust autode vahel. Iga number x 1,x 2,¼,x k võib võtta mis tahes täisarvu vahemikus 1 kuni n. Nii et selles näites

M=(1, 2,…,n) ja autode vahel on nii palju erinevaid jaotusi, kui palju on ridu pikkusega k, mida saab komplekti elementidest koostada M, see on

Märgime veel kord, et kordustega ja ilma kordusteta paigutustes on oluline elementide järjekord. Kui elementide järjekord ei ole oluline, siis antud juhul räägitakse kombinatsioonidest.

Kombinatsioonid(ilma kordamiseta).

3. määratlus. Lase M=(a1,a2,0,an). Mis tahes alamhulk X komplektid M sisaldavad k elemente nimetatakse kombinatsioon k elementi n-st.

Märgime kohe, et selles määratluses on hulga elementide järjekord X tähtsusetu ja see k£n, sest k = ½ X½, n = ½ M½ ja XOM.

3. teoreem. Erinevate kombinatsioonide arv k elemendid alates n võrdub

. (6)

Tõestus.

Iga kombinatsioon k elemendid n-st genereerib k! erinevad paigutused ilma kordusteta n-st k-ni erinevate permutatsioonide abil (vt Järeldus 1). Seega kõik kombinatsioonid k elemendist n-st pärast erinevaid k! permutatsioonid genereerivad kõik paigutused ilma kordusteta n peal k. Sellepärast . Järelikult

Kombinatoorikas uuritakse küsimusi, kui palju saab antud objektidest (elementidest) teha teatud tüüpi kombinatsioone.

Kombinatoorika kui lõigu sünd on seotud B. Pascali ja P. Fermat’ hasartmänguteooria töödega. Suure panuse kombinatoorsete meetodite arendamisse andis G.V. Leibniz, J. Bernoulli ja L. Euler.

Prantsuse filosoof, kirjanik, matemaatik ja füüsik Blaise Pascal (1623–1662) näitas varakult oma silmapaistvaid matemaatilisi võimeid. Pascali matemaatiliste huvide ring oli väga mitmekesine. Pascal tõestas ühte
projektiivse geomeetria põhiteoreemidest (Pascali teoreem), konstrueeris summeerimismasina (Pascali liitmismasin), andis meetodi binoomkoefitsientide arvutamiseks (Pascali kolmnurk), defineeris esmakordselt täpselt ja rakendas tõestamiseks matemaatilise induktsiooni meetodit, tegi olulise sammu lõpmatu väikese analüüsi arengus, mängis olulist rolli tõenäosusteooria sünnis. Hüdrostaatikas kehtestas Pascal oma põhiseaduse (Pascali seaduse). Pascali kirjad provintsiaalile oli prantsuse klassikalise proosa meistriteos.

Gottfried Wilhelm Leibniz (1646–1716) oli saksa filosoof, matemaatik, füüsik ja leiutaja, jurist, ajaloolane ja keeleteadlane. Matemaatikas töötas ta koos I. Newtoniga välja diferentsiaal- ja integraalarvutuse. Ta andis olulise panuse kombinatoorikasse. Eelkõige on tema nimega seotud arvuteoreetilisi probleeme.

Gottfried Wilhelm Leibniz oli pisut muljetavaldav välimus ja jättis seetõttu üsna ebamäärase inimese mulje. Kord Pariisis astus ta raamatupoodi lootuses osta oma tuttava filosoofi raamat. Kui külastaja selle raamatu kohta küsis, vastas raamatumüüja teda pealaest jalatallani uurinud pilkavalt: “Milleks sul seda vaja on? Kas sa oled võimeline selliseid raamatuid lugema? Enne kui teadlane jõudis vastata, sisenes poodi raamatu autor ise sõnadega: "Tervitused ja lugupidamine suurele Leibnizile!" Müüja ei saanud aru, et tal on tõesti kuulus Leibniz, kelle raamatud olid teadlaste seas väga nõutud.

Tulevikus mängib olulist rolli järgmine.

Lemma. Laske sisse elementide komplekt ja komplektis - elemendid. Siis kõigi erinevate paaride arv, kus on võrdne .

Tõestus. Tõepoolest, ühe hulga elemendiga saame teha nii erinevaid paare, kuid ainult elementide komplektis.

Paigutused, permutatsioonid, kombinatsioonid

Oletame, et meil on kolmest elemendist koosnev komplekt. Kuidas saame neist elementidest kaks valida? .

Definitsioon. Erinevate elementide hulga paigutused elementide kaupa on kombinatsioonid, mis koosnevad antud elementidest > elementide kaupa ja erinevad kas elementide endi või elementide järjestuse poolest.

Elementide kogumi kõigi paigutuste arv elementide kaupa tähistatakse (prantsuse sõna "arrangement" algustähest, mis tähendab paigutust), kus ja .

Teoreem. Elementide komplekti paigutuste arv elementide kaupa on võrdne

Tõestus. Oletame, et meil on elemente. Olgu võimalikud paigutused. Ehitame need paigutused järjestikku. Esmalt määratleme esimese paigutuse elemendi. Antud elementide komplektist saab seda valida mitmel viisil. Pärast esimese elemendi valimist teise elemendi jaoks on valikuvõimalusi jne. Kuna iga selline valik annab uue asukoha, saab kõiki neid valikuid omavahel vabalt kombineerida. Seetõttu on meil:

Näide. Kui mitmel viisil saab lippu kokku panna kolmest erinevat värvi horisontaalsest triibust, kui on olemas viievärviline materjal?

Lahendus. Soovitud arv kolmetriibulisi lippe:

Definitsioon. Elementide hulga permutatsioon on elementide paigutus kindlas järjekorras.

Seega on kolmest elemendist koosneva hulga kõik erinevad permutatsioonid

Märgitud on elementide kõigi permutatsioonide arv (prantsuse sõna "permutation" algustähest, mis tähendab "permutatsiooni", "liikumist"). Seetõttu arvutatakse kõigi erinevate permutatsioonide arv valemiga

Näide. Mitmel viisil saab vankrit malelauale asetada, et nad üksteist ei ründaks?

Lahendus. Nõutav arv vankri paigutusi

Definitsiooni järgi!

Definitsioon. Erinevate elementide kombinatsioonid elementide kaupa on kombinatsioonid, mis koosnevad etteantud elementidest elementide kaupa ja erinevad vähemalt ühe elemendi poolest (teisisõnu antud elementide komplekti -elemendi alamhulgad).

Nagu näete, ei võeta kombinatsioonides erinevalt paigutustest arvesse elementide järjekorda. Märgitakse kõigi elementide kombinatsioonide arv igas elemendis (prantsuse sõna "kombinatsioon", mis tähendab "kombinatsiooni" algustähest).

Numbrid

Kõik kombinatsioonid komplektist kaks - .

Numbriomadused (\sf C)_n^k

Tõepoolest, antud elementide hulga iga -element alamhulk vastab sama hulga ühele ja ainult ühele -elemendi alamhulgale.

Tõepoolest, elementide alamhulki saame valida järgmiselt: fikseerime ühe elemendi; seda elementi sisaldavate elementide alamhulkade arv on ; elementide alamhulkade arv, mis seda elementi ei sisalda, on .

Pascali kolmnurk

Selles kolmnurgas on iga rea ​​äärmuslikud arvud võrdsed 1-ga ja iga mitteäärmuslik arv on võrdne selle kohal oleva eelmise rea kahe arvu summaga. Seega võimaldab see kolmnurk arvutada numbreid.

Teoreem.

Tõestus. Vaatleme elementide kogumit ja lahendame järgmise ülesande kahel viisil: mitu jada võib koosneda antud elementidest
hulgad, milles ükski element ei esine kaks korda?

1 viis. Valime jada esimese liikme, seejärel teise, kolmanda ja nii edasi. liige

2 viis. Esmalt valime antud komplektist elemendid ja seejärel järjestame need mingis järjekorras

Korrutage selle murru lugeja ja nimetaja arvuga:

Näide. Mitmel viisil saab Sportloto mängus valida 5 numbrit 36-st?

Soovitud viiside arv

Ülesanded.

1. Autode numbrid koosnevad 3 vene tähestiku tähest (33 tähte) ja 4 numbrist. Mitu erinevat auto numbrit on?
2. Klaveril on 88 klahvi. Mitmel viisil saab järjestikku tekitada 6 heli?
3. Mitu kuuekohalist arvu jagub 5-ga?
4. Mitmel viisil saab 7 erinevat münti kolme taskusse panna?
5. Mitu 5-kohalist arvu saab moodustada, mis sisaldavad kümnendkohas vähemalt korra numbrit 5?
6. Kui mitut moodi saab ümmarguse laua taha istuda 20 inimest, arvestades võimalusi ühesugusteks, kui neid saab üksteiselt ringi liikudes?
7. Mitu viiekohalist arvu, mis jaguvad 5-ga, ei sisalda ühesuguseid numbreid?
8. Ruudulisele paberile, mille lahtri pool on 1 cm, joonistatakse 100 cm raadiusega ring, mis ei läbi lahtrite ülaosasid ega puuduta lahtrite külgi. Mitu ruutu võib see ring lõikuda?
9. Mitmel viisil saab numbreid ritta paigutada nii, et numbrid seisaksid kõrvuti ja pealegi tõusvas järjekorras?
10. Mitu viiekohalist arvu saab numbritest teha, kui iga numbrit saab kasutada ainult üks kord?
11. Sõnast ROT saab tähti ümber paigutades ka järgmised sõnad: TOR, ORT, OTR, TRO, RTO. Neid nimetatakse anagrammideks. Mitu anagrammi saate LOGARITHiga teha?
12. Helistame poolitamine naturaalarv on selle esitus naturaalarvude summana. Siin on näiteks kõik numbri partitsioonid:

Sektsioonid loetakse erinevateks, kui need erinevad kas arvult või liitmiste järjestuse poolest.

Mitu erinevat arvu partitsiooni on?
13. Kui palju on mittekasvavaid 3-kohalisi arve?
14. Kui palju on mittekasvavaid 4-kohalisi arve?
15. Mitu moodi saab 17 inimest järjest istuda nii, et nad on kõrvuti?
16. tüdrukud ja poisid istuvad juhuslikult kohtade reas. Kui mitmel viisil saab neid istutada nii, et kaks tüdrukut ei istuks kõrvuti?
17. tüdrukud ja poisid istuvad juhuslikult kohtade reas. Kui mitmel viisil saab neid istutada nii, et kõik tüdrukud istuvad kõrvuti?

Kombinatsioonid. Majutuskohad. Permutatsioonid

Permutatsioonid nimetatakse kombinatsioonideks, mis koosnevad samast n erinevad elemendid ja erinevad ainult nende paigutuse järjekorras. Kõigi võimalike permutatsioonide arv

Kaaluge näidet: mitu kolmekohalist arvu saab teha numbritest 1,2,3, kui iga number sisaldub numbri kujutises ainult üks kord?

Lahendus:

Või niimoodi näiteks. Seitse osalejat õpilaskonverentsil esinemise järjekord määratakse loosi teel. Mitu erinevat loosi varianti on võimalik?

Lahendus: iga loosi versioon erineb ainult osalejate järjestuse poolest, see tähendab, et tegemist on 7 elemendi permutatsiooniga. Nende arv on

Näide. Kassa poole pöördus korraga 4 inimest, et raha kätte saada. Kui mitmel viisil saavad nad rivistuda?

Lahendus: järjekord koosneb 4 erinevast isikust, mistõttu iga järjekorda seadmise meetodi puhul arvestatakse nende asukoha järjekorda. Seega on nelja inimese permutatsioonid, nende arv on võrdne

Paigutused n erinevad elemendid vastavalt m elemendid, mis erinevad kas oma järjestuse või elementide koostise poolest.

Arvutatakse välja kõigi võimalike paigutuste arv

Näide: mitu signaali saab teha 6 erinevat värvi lipust, mis võetakse kahekaupa?

Lahendus:

Näide:Ühe päeva kava koosneb viiest õppetunnist. Määrake ajakava valikute arv, kui valite 11 eriala hulgast.

Lahendus: iga ajakavavalik esindab 5 distsipliini komplekti 11-st, mis erineb teistest valikutest nii erialade koostise kui ka nende järgnemise järjekorra poolest, see tähendab, et tegemist on 11 elemendi paigutusega 5 kaupa. Ajakava arv valikud leitakse valemiga

Kombinatsioonid nimetatakse kombinatsioonideks, mis koosnevad n erinevad elemendid vastavalt m elemendid, mis erinevad vähemalt ühe elemendi poolest. Kombinatsioonide arv

Näide: Mitmel viisil saab 10 eset sisaldavast kastist valida 2 eset?

Lahendus:

Näide: Maleturniiril osaleb 16 inimest. Mitu mängu peab turniiril mängima, kui üks mäng toimub kahe osaleja vahel?

Lahendus: iga mängu mängib kaks osalejat 16-st ja see erineb ainult osalejapaaride koosseisust, see tähendab, et see on kombinatsioon 16 elemendist kahest

Näide: Seal on 6 bakteritüve. Nende kasvukiiruse määramiseks tuleb valida kolm tüve. Kui mitmel viisil saab seda teha?

Lahendus: valikumeetodeid peetakse erinevateks, kui iga valitud tüvi erineb vähemalt ühe elemendi poolest. See number

See tähendab, et on 20 viisi.

Rõhutame, et paigutuste, permutatsioonide ja kombinatsioonide arv on seotud võrdsusega

Ülesannete lahendamisel kasutab kombinatoorika järgmisi reegleid.

Summereegel: kui mõni vastu A saab valida objektide hulgast m viisid ja teine ​​objekt AT saab valida n viise, siis valige üks neist AGA, või AT võimalikud viisid.

Toote reegel: kui objekt AGA saab valida objektide hulgast m viisid ja iga sellise valiku järel objekt AT saab valida n viise, seejärel paar objekti ( A, B) selles järjekorras saab valida erinevatel viisidel.

See artikkel keskendub matemaatika eriharule, mida nimetatakse kombinatoorikaks. Valemid, reeglid, probleemide lahendamise näited - kõik selle leiate siit, lugedes artiklit lõpuni.

Mis see jaotis siis on? Kombinatoorika käsitleb mis tahes objektide loendamise küsimust. Kuid antud juhul pole objektideks ploomid, pirnid või õunad, vaid midagi muud. Kombinatoorika aitab meil leida sündmuse tõenäosust. Näiteks kaarte mängides - kui suur on tõenäosus, et vastasel on trump? Või selline näide - kui suur on tõenäosus, et saad paarikümnest pallist kotist täpselt valge? Just seda tüüpi ülesannete jaoks peame teadma vähemalt selle matemaatika osa põhitõdesid.

Kombinatoorsed konfiguratsioonid

Arvestades kombinatoorika põhimõistete ja valemite küsimust, ei saa me tähelepanu pöörata kombinatoorsetele konfiguratsioonidele. Neid kasutatakse mitte ainult selliste mudelite koostamiseks, vaid ka lahendamiseks:

• majutus;
• permutatsioon;
• kombinatsioon;
• numbrite koosseis;
• numbri poolitamine.

Esimesest kolmest räägime lähemalt hiljem, kuid selles osas pöörame tähelepanu kompositsioonile ja jagamisele. Kui nad räägivad teatud arvu (näiteks a) koostisest, peavad nad silmas arvu a esitamist mõne positiivse arvu järjestatud summana. Jaotus on järjestamata summa.

Sektsioonid

Enne kui asume otse kombinatoorika valemite ja probleemide käsitlemise juurde, tasub tähelepanu pöörata asjaolule, et kombinatoorikal, nagu ka teistel matemaatikaharudel, on oma alajaotised. Need sisaldavad:

• loendav;
• struktuurne;
• äärmuslik;
• Ramsey teooria;
• tõenäosuslik;
• topoloogiline;
• lõpmatu.

Esimesel juhul räägime loendavast kombinatoorikast, ülesanded käsitlevad erinevate konfiguratsioonide loendamist või loendamist, mis on moodustatud hulkade elementidest. Reeglina seatakse nendele komplektidele teatud piirangud (eristatavus, eristamatus, kordusvõimalus jne). Ja nende konfiguratsioonide arv arvutatakse liitmise või korrutamise reegli abil, millest räägime veidi hiljem. Struktuurikombinatoorika hõlmab graafikute ja matroidide teooriaid. Ekstreemkombinatoorika probleemi näide on, milline on graafi suurim mõõde, mis rahuldab järgmisi omadusi... Neljandas lõigus mainisime Ramsey teooriat, mis uurib regulaarsete struktuuride olemasolu juhuslikes konfiguratsioonides. Tõenäosuslik kombinatoorika suudab vastata küsimusele – kui suur on tõenäosus, et antud hulgal on teatud omadus. Nagu võite arvata, rakendab topoloogiline kombinatoorika topoloogias meetodeid. Ja lõpuks seitsmes punkt – lõpmatu kombinatoorika uurib kombinatoorika meetodite rakendamist lõpmatute hulkade suhtes.

Lisamise reegel

Kombinatoorika valemite hulgast leiab ka üsna lihtsaid, millega oleme ammu tuttavad. Näiteks on summa reegel. Oletame, et meile on antud kaks tegevust (C ja E), kui need on üksteist välistavad, saab toimingut C teha mitmel viisil (näiteks a) ja tegevust E saab teha b-viisidel, siis ükskõik milline neist (C või E) saab teha a + b viisil .

Teoreetiliselt on sellest üsna raske aru saada, proovime kogu mõtte edasi anda lihtsa näitega. Võtame ühe klassi õpilaste keskmise arvu – oletame, et see on kakskümmend viis. Nende hulgas on viisteist tüdrukut ja kümme poissi. Iga päev määratakse klassile üks saatja. Mitu võimalust on tänapäeval klassiteenindaja määramiseks? Probleemi lahendus on üsna lihtne, kasutame lisamise reeglit. Ülesande tekst ei ütle, et valves võivad olla ainult poisid või ainult tüdrukud. Seetõttu võib see olla ükskõik milline viieteistkümnest tüdrukust või ükskõik milline kümnest poisist. Summareeglit rakendades saame üsna lihtsa näite, millega algklassiõpilane saab hõlpsasti hakkama: 15 + 10. Arvutanud, saame vastuseks: kakskümmend viis. See tähendab, et tänaseks valveklassi määramiseks on ainult kakskümmend viis võimalust.

korrutamisreegel

Kombinatoorika põhivalemite hulka kuulub ka korrutamise reegel. Alustame teooriaga. Oletame, et peame sooritama mitu toimingut (a): esimene toiming sooritatakse ühel viisil, teine ​​- kahel viisil, kolmas - kolmel viisil ja nii edasi, kuni viimane a-toiming sooritatakse samal viisil. Siis saab kõiki neid toiminguid (mida meil on kokku) teha N viisil. Kuidas arvutada tundmatut N? Valem aitab meid selles: N \u003d c1 * c2 * c3 * ... * ca.

Jällegi, teoreetiliselt pole miski selge, liigume edasi lihtsa näite juurde korrutamisreegli rakendamisest. Võtame sama kahekümne viie inimese klassi, kus õpib viisteist tüdrukut ja kümme poissi. Ainult seekord peame valima kaks saatjat. Nad võivad olla ainult poisid või tüdrukud või poiss koos tüdrukuga. Pöördume ülesande elementaarse lahenduse poole. Valime esimese saatja, nagu viimases lõigus otsustasime, saame kakskümmend viis võimalikku varianti. Teiseks valves olevaks isikuks võib olla ükskõik milline ülejäänud inimestest. Meil oli kakskümmend viis õpilast, valisime ühe, mis tähendab, et ülejäänud kahekümne neljast inimesest võib igaüks olla teine ​​valves. Lõpuks rakendame korrutusreeglit ja leiame, et kahte saatjat saab valida kuuesajal viisil. Selle arvu saime korrutades kahekümne viie ja kahekümne neljaga.

permutatsioon

Nüüd käsitleme veel üht kombinatoorika valemit. Artikli selles osas räägime permutatsioonidest. Mõelge probleemile kohe näite abil. Võtame piljardipallid, meil on neid n-s arv. Peame arvutama: mitu võimalust on nende järjestamiseks, st tellitud komplekti tegemiseks.

Alustame, kui meil pole palle, siis on meil ka null paigutusvõimalust. Ja kui meil on üks pall, siis on ka paigutus sama (matemaatiliselt saab selle kirjutada järgmiselt: Р1 = 1). Kaks palli saab paigutada kahel erineval viisil: 1.2 ja 2.1. Seetõttu P2 = 2. Kolm palli saab paigutada kuuel viisil (P3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3.2.1; 3,1,2. Ja kui selliseid palle pole mitte kolm, vaid kümme või viisteist? Kõigi võimalike valikute loetlemine on väga pikk, siis tuleb meile appi kombinatoorika. Permutatsioonivalem aitab meil oma küsimusele vastuse leida. Pn = n*P(n-1). Kui proovime valemit lihtsustada, saame: Pn = n* (n - 1) *…* 2 * 1. Ja see on esimeste naturaalarvude korrutis. Sellist arvu nimetatakse faktoriaaliks ja seda tähistatakse kui n!

Vaatleme ülesannet. Juht ehitab igal hommikul oma salga rivisse (kakskümmend inimest). Üksuses on kolm parimat sõpra - Kostja, Sasha ja Lesha. Kui suur on tõenäosus, et nad on kõrvuti? Küsimusele vastuse leidmiseks peate jagama "hea" tulemuse tõenäosuse tulemuste koguarvuga. Permutatsioonide koguarv on 20! = 2,5 kvintiljonit. Kuidas lugeda "heade" tulemuste arvu? Oletame, et Kostja, Sasha ja Lesha on üks superinimene. Siis on meil ainult kaheksateist ainet. Permutatsioonide arv on sel juhul 18 = 6,5 kvadriljonit. Kõige selle juures saavad Kostja, Sasha ja Lesha oma jagamatus kolmikus meelevaldselt omavahel liikuda ja see on veel 3! = 6 valikut. Seega on meil kokku 18 “head” tähtkuju! * 3! Peame lihtsalt leidma soovitud tõenäosuse: (18! * 3!) / 20! Mis on ligikaudu 0,016. Kui tõlkida protsentidesse, siis on see vaid 1,6%.

Majutus

Nüüd käsitleme veel ühte väga olulist ja vajalikku kombinatoorika valemit. Majutus on meie järgmine number, mida soovitame käsitleda artikli selles osas. Läheme keerulisemaks. Oletame, et me tahame arvestada võimalike permutatsioonidega, ainult mitte kogu hulgast (n), vaid väiksemast (m). See tähendab, et me käsitleme n üksuse permutatsioone m võrra.

Kombinatoorika põhivalemeid ei tohiks lihtsalt pähe õppida, vaid ka mõista. Isegi hoolimata asjaolust, et need muutuvad keerulisemaks, kuna meil pole mitte üks parameeter, vaid kaks. Oletame, et m \u003d 1, siis A \u003d 1, m \u003d 2, siis A = n * (n - 1). Kui lihtsustame valemit veelgi ja läheme faktoriaalide abil üle tähistusele, saame üsna kokkuvõtliku valemi: A \u003d n! / (n - m)!

Kombinatsioon

Oleme näidetega käsitlenud peaaegu kõiki kombinatoorika põhivalemeid. Liigume nüüd kombinatoorika algkursuse kaalumise viimasesse etappi – kombinatsiooni tundmaõppimisse. Nüüd valime olemasoleva n hulgast m üksust, samas kui me valime need kõik kõigil võimalikel viisidel. Mille poolest see siis majutusest erineb? Me ei arvesta korda. Sellest tellimata komplektist saab kombinatsioon.

Kohe tutvustame tähistust: C. Võtame m palli paigutused alates n. Lõpetame järjestusele tähelepanu pööramise ja saame korduvaid kombinatsioone. Kombinatsioonide arvu saamiseks peame paigutuste arvu jagama m-ga! (m faktoriaal). See tähendab, C \u003d A / m! Seega on n palli hulgast valida mitu võimalust, mis on ligikaudu võrdne sellega, kui palju valida peaaegu kõike. Selle jaoks on loogiline väljend: natukene valida on sama, mis peaaegu kõik ära visata. Siinkohal on oluline ka mainida, et poolte esemete valimisel on võimalik saavutada maksimaalne kombinatsioonide arv.

Kuidas valida probleemi lahendamiseks valemit?

Oleme üksikasjalikult uurinud kombinatoorika põhivalemeid: paigutus, permutatsioon ja kombinatsioon. Nüüd on meie ülesandeks hõlbustada kombinatoorika ülesande lahendamiseks vajaliku valemi valikut. Võite kasutada järgmist üsna lihtsat skeemi:

1. Esitage endale küsimus: kas ülesande tekstis on elementide järjekorda arvestatud?
2. Kui vastus on eitav, kasutage kombinatsiooni valemit (C \u003d n! / (m! * (n - m))).
3. Kui vastus on eitav, siis tuleb vastata veel ühele küsimusele: kas kombinatsioonis on kõik elemendid?
4. Kui vastus on jah, siis kasuta permutatsiooni valemit (P = n!).
5. Kui vastus on eitav, kasutage paigutusvalemit (A = n! / (n - m)!).

Näide

Oleme kaalunud kombinatoorika elemente, valemeid ja mõnda muud küsimust. Liigume nüüd tegeliku probleemi juurde. Kujutage ette, et teie ees on kiivi, apelsin ja banaan.

Esimene küsimus: mitmel viisil saab neid ümber korraldada? Selleks kasutame permutatsiooni valemit: P = 3! = 6 viisi.

2. küsimus: mitmel viisil saab ühte puuvilja valida? See on ilmne, meil on ainult kolm võimalust - vali kiivi, apelsin või banaan, kuid kasutame kombinatsioonivalemit: C \u003d 3! / (2! * 1!) = 3.

3. küsimus: mitmel viisil saab valida kahte puuvilja? Millised võimalused meil on? Kiivi ja apelsin; kiivi ja banaan; apelsin ja banaan. See tähendab, et kolm võimalust, kuid seda on lihtne kontrollida kombineeritud valemi abil: C \u003d 3! / (1! * 2!) = 3

4. küsimus: mitmel viisil saab valida kolme puuvilja? Nagu näete, on kolme puuvilja valimiseks ainult üks võimalus: võtke kiivi, apelsin ja banaan. C=3! / (0! * 3!) = 1.

5. küsimus: mitmel viisil saate valida vähemalt ühe puuvilja? See tingimus tähendab, et võime võtta ühe, kaks või kõik kolm vilja. Seetõttu liidame C1 + C2 + C3 = 3 + 3 + 1 = 7. See tähendab, et meil on seitse võimalust võtta laualt vähemalt üks puuvili.

Teema kokkuvõte:

Lõpetanud 10. klassi "B" õpilane

keskkool nr 53

Gluhhov Mihhail Aleksandrovitš

Naberežnõje Tšelnõi

2002. aasta
Sisu

Kombinatoorika ajaloost _______________________________________________________	3
Summarieegel _________________________________________________________	4
	-
Tootereegel __________________________________________________	4
Näited ülesannetest _________________________________________________________________	-
Lõikuvad hulgad ___________________________________________________	5
Näited ülesannetest _________________________________________________________________	-
Euleri ringid __________________________________________________________	-
Paigutused ilma kordusteta __________________________________________________	6
Näited ülesannetest _________________________________________________________________	-
Permutatsioonid ilma kordusteta ______________________________________________	7
Näited ülesannetest _________________________________________________________________	-
Kombinatsioonid ilma kordusteta __________________________________________________	8
Näited ülesannetest _________________________________________________________________	-
Paigutused ja kombinatsioonid ilma kordusteta ______________________________	9
Näited ülesannetest _________________________________________________________________	-
Permutatsioonid kordustega	9
Näited ülesannetest _________________________________________________________________	-
Iseseisva lahenduse ülesanded ___________________________________	10
Bibliograafia____________________________________	11

Kombinatoorika ajaloost

Kombinatoorika käsitleb erinevat tüüpi ühendeid, mida saab moodustada lõpliku hulga elementidest. Mõned kombinatoorika elemendid olid Indias tuntud juba 2. sajandil eKr. eKr e. Nidlased oskasid arvutada numbreid, mida nüüd nimetatakse "kombinatsioonideks". XII sajandil. Bhaskara arvutas välja teatud tüüpi kombinatsioonid ja permutatsioonid. Eeldatakse, et India teadlased uurisid ühendeid seoses nende kasutamisega poeetikas, värsi ehituse teaduses ja poeetilistes teostes. Näiteks seoses n-silbise jala rõhulise (pika) ja rõhutu (lühike) silpide võimalike kombinatsioonide arvutamisega. Teadusliku distsipliinina kujunes kombinatoorika 17. sajandil. Raamatus "Aritmeetika teooria ja praktika" (1656) pühendab prantsuse autor A. ka terve peatüki kombinatsioonidele ja permutatsioonidele.
B. Pascal selgitas "Traktates aritmeetilisest kolmnurgast" ja "Traktaadis numbrilistest järjekordadest" (1665) binoomkoefitsientide doktriini. P. Fermat teadis matemaatiliste ruutude ja kujundlike arvude seostest ühendite teooriaga. Mõistet "kombinatoorika" hakati kasutama pärast Leibnizi 1665. aastal avaldatud teost "Discourse on kombinatorial art", milles esmakordselt anti teaduslik põhjendus kombinatsioonide ja permutatsioonide teooriale. J. Bernoulli uuris esimesena paigutusi oma raamatu "Ars conjectandi" (ennustuskunst) teises osas aastal 1713. Kombinatsioonide kaasaegse sümboolika pakkusid välja erinevad õppekäsiraamatute autorid alles 19. sajandil.

Kogu erinevaid kombinatoorseid valemeid saab tuletada kahest lõplikku hulka käsitlevast põhiväitest – summareegel ja korrutisreegel.

Summereegel

Kui lõplikud hulgad ei ristu, siis elementide arv X U Y (või) võrdub hulga X elementide arvu ja hulga Y elementide arvu summaga.

See tähendab, et kui esimesel riiulil on X raamatut ja teisel Y raamatut, saate valida raamatu esimeselt või teiselt riiulilt X + Y viisil.

Ülesannete näited

Õpilane peab sooritama praktilise töö matemaatikas. Talle pakuti algebras valida 17 ja geomeetrias 13 teemat. Kui mitmel viisil saab ta valida ühe teema praktiliseks tööks?

Lahendus: X=17, Y=13

Vastavalt summareeglile X U Y=17+13=30 teemat.

Valikus on 5 sularaha ja riiete loteriipiletit, 6 spordiloterii piletit ja 10 autoloterii piletit. Mitmel viisil saab spordiloteriist või autoloteriist valida ühe pileti?

Lahendus: Kuna raha ja riiete loterii valikus ei osale, on valikuid ainult 6 + 10 = 16.

toote reegel

Kui elementi X saab valida k viisil ja elementi Y m viisil, siis paari (X,Y) saab valida k*m viisil.

See tähendab, et kui esimesel riiulil on 5 ja teisel 10 raamatut, saate valida ühe raamatu esimeselt riiulilt ja ühe raamatu teiselt 5 * 10 = 50 viisil.

Ülesannete näited

Köitja peab köitma 12 erinevat punases, rohelises ja pruunis köites raamatut. Kui mitmel viisil saab ta seda teha?

Lahendus: Raamatuid on 12 ja värvid 3, seega on tootereegli järgi võimalikud 12 * 3 = 36 köitmisvõimalust.

Kui palju on viiekohalisi numbreid, mis loevad sama vasakult paremale ja paremalt vasakule?

Lahendus: sellistes numbrites on viimane number sama, mis esimene ja eelviimane - nagu teine. Kolmas number on mis tahes. Seda saab kujutada kui XYZYX, kus Y ja Z on suvalised numbrid ja X ei ole null. Seega on tootereegli kohaselt nii vasakult paremale kui ka paremalt vasakule võrdselt loetavate numbrite arv 9 * 10 * 10 = 900 valikut.

Kattuvad komplektid

Kuid juhtub, et hulgad X ja Y lõikuvad, siis kasutavad nad valemit

, kus X ja Y on hulgad ja on ristumisala. Ülesannete näited

20 inimest oskab inglise ja 10 - saksa keelt, neist 5 nii inglise kui saksa keelt. Mitu inimest kokku?

Vastus: 10+20-5=25 inimest.

Probleemi visuaalseks lahendamiseks kasutatakse sageli ka Euleri ringe. Näiteks:

100 välisreisile suunduvast turistist räägib saksa keelt 30, inglise keelt 28, prantsuse keelt 42. inglise ja saksa keelt räägib korraga 8 inimest, inglise ja prantsuse keelt 10, saksa ja prantsuse keelt 5, kõiki kolme keelt 3 .turistid ei räägi ühtegi keelt?

Lahendus: Väljendagem selle probleemi seisukorda graafiliselt. Määrakem ring neile, kes oskavad inglise keelt, teine ​​ring neile, kes oskavad prantsuse keelt ja kolmas ring neile, kes oskavad saksa keelt.

Kolm turisti räägivad kõiki kolme keelt, mis tähendab, et ringide ühisosas sisestame numbri 3. Inglise ja prantsuse keelt räägib 10 inimest ning 3 neist ka saksa keelt. Seetõttu räägib ainult inglise ja prantsuse keelt 10-3=7 inimest.

Samamoodi saame, et ainult inglise ja saksa keelt räägib 8-3=5 inimest ning saksa ja prantsuse keelt 5-3=2 turisti. Sisestame need andmed vastavatesse osadesse.

Teeme nüüd kindlaks, kui palju inimesi räägib ainult ühte loetletud keeltest. Saksa keelt oskab 30 inimest, aga 5+3+2=10 neist räägivad ka muid keeli, seega ainult 20 inimest oskab saksa keelt. Samamoodi saame, et 13 inimest räägivad ühte inglise keelt ja 30 inimest räägivad ühte prantsuse keelt.

Vastavalt probleemi seisukorrale on turiste vaid 100. 20 + 13 + 30 + 5 + 7 + 2 + 3 = 80 turisti oskab vähemalt ühte keelt, seega 20 inimest ei räägi ühtegi neist keeltest.

Paigutused ilma kordusteta.

Mitu telefoninumbrit võib koosneda 6 numbrist, et kõik numbrid oleksid erinevad?

See on näide paigutusprobleemist, kus ei esine kordusi. Siia on paigutatud 10 numbrit 6. Ja valikuid, milles samad numbrid on erinevas järjekorras, peetakse erinevateks.

Kui n-st elemendist koosnevat X-hulka m≤n, siis m elementi sisaldavat järjestatud hulka X nimetatakse järjestatud hulgaks X, mis sisaldab m elementi.

Kõigi n elemendi paigutuste arv m-ga on tähistatud

n! - n-faktoriaal (inglise faktor) naturaalarvude korrutis 1-st mis tahes arvuni n

n!=1*2*3*...*n 0!=1

Seega on vastus ülaltoodud probleemile

Ülesanne

Kui mitmel viisil saavad 4 poissi kuuest tüdrukust neljal tantsima kutsuda?

Lahendus: Kaks poissi ei saa sama tüdrukut korraga kutsuda. Ja valikuid, kus samad tüdrukud tantsivad erinevate poistega, peetakse erinevateks, seetõttu:

Võimalik on 360 valikut.

Permutatsioonid ilma kordusteta

Juhul, kui n=m (vt kordusteta paigutusi) n elementi m võrra, nimetatakse hulga x permutatsiooniks.

Kõigi n elemendi permutatsioonide arv on tähistatud P n-ga.

Kehtib n=m korral:

Ülesannete näited

Mitu erinevat kuuekohalist arvu saab numbritest 0, 1, 2, 3, 4,5 teha, kui numbrid arvus ei kordu?

1) Leidke nende arvude kõigi permutatsioonide arv: P 6 =6!=720

2) 0 ei saa olla arvu ees, seega tuleb sellest arvust lahutada nende permutatsioonide arv, milles 0 on ees. Ja see on P 5 = 5! = 120.

P 6 -P 5 \u003d 720-120 \u003d 600

ulakas ahv

Jah, lampjalgsus Mishka

Hakkas mängima kvartetti

Lõpetage, vennad, lõpetage! -

Ahv karjub, - oota!

Kuidas muusika läheb?

Sa ei istu nii...

Ja nii, ja nii siirdatud - jälle muusika ei lähe hästi.