See artikkel keskendub matemaatika eriosale, mida nimetatakse kombinatoorikaks. Valemid, reeglid, probleemide lahendamise näited – kõik see leiad siit, lugedes artikli 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. Kui suur on näiteks kaartide mängimise 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? Seda tüüpi ülesannete jaoks peame teadma vähem alt 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 formuleerimiseks, vaid ka erinevate kombinatoorsete ülesannete lahendamiseks. Selliste mudelite näited on:
- paigutus;
- permutatsioon;
- kombinatsioon;
- numbrite koosseis;
- number jagatud.
Esimesest kolmest räägime lähem alt 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. Ja jagamine on järjestamata summa.
Jaotised
Enne kui asume otse kombinatoorika valemite ja ülesannete käsitlemise juurde, tasub tähelepanu pöörata asjaolule, et kombinatoorikal, nagu ka teistel matemaatika osadel, on oma alajaotised. Nende hulka kuuluvad:
- loenduv;
- struktuurne;
- äärmuslik;
- Ramsey teooria;
- tõenäoline;
- 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, kordamise võ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 see, mis 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äosuslikkombinatoorika suudab vastata küsimusele – kui suur on tõenäosus, et antud hulgal on mingi 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 puhul.
Lisamise reegel
Kombinatoorika valemite hulgast võib leida üsna lihtsaid, millega oleme juba 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.
Teoorias on sellest üsna raske aru saada, proovime lihtsa näitega kogu mõtte edasi anda. 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 on ainult kakskümmend viis viisimäärake tänaseks töötund.
Korrutamisreegel
Korrutamise reegel kuulub ka kombinatoorika põhivalemite hulka. 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 c1c2c3…ca.
Jällegi, teoreetiliselt pole midagi selget, liigume edasi korrutamisreegli rakendamise lihtsa näite juurde. 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 allesjää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. Saime selle arvu kahekümne viie ja kahekümne nelja korrutamisel.
Vaheta
Nüüd käsitleme veel üht kombinatoorika valemit. Artikli selles osas meRää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 järjestatud komplekti tegemiseks.
Alustame, kui meil pole palle, siis on meil ka nullpaigutusvõimalused. 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 Р2=2. Kolm palli saab paigutada kuuel viisil (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Ja kui selliseid kuule 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=nP(n-1). Kui proovime valemit lihtsustada, saame: Pn=n (n - 1) … 21. Ja see on esimeste naturaalarvude korrutis. Sellist arvu nimetatakse faktoriaaliks ja seda tähistatakse kui n!
Mõtleme probleemi üle. 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 meieMeil on ainult kaheksateist õppeainet. 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 lihts alt leidma soovitud tõenäosuse: (18!3!) / 20! Mis on ligikaudu 0,016. Kui teisendada protsendiks, on see vaid 1,6%.
Majutus
Nüüd käsitleme teist väga olulist ja vajalikku kombinatoorika valemit. Majutus on meie järgmine number, mida soovitame käsitleda artikli selles osas. Me 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 arvestame n üksuse permutatsioone m võrra.
Kombinatoorika põhivalemeid ei tohiks lihts alt 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=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 käsitlenud peaaegu kõiki kombinatoorika põhivalemeid koos näidetega. Liigume nüüd kombinatoorika algkursuse käsitlemise 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 eikaaluge järjekorda. Sellest järjestamata komplektist saab kombinatsioon.
Sisestage kohe tähis: C. Võtame m palli paigutused n-st. 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 valimiseks paar 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 üksuste valimisel on võimalik saavutada maksimaalne kombinatsioonide arv.
Kuidas valida ülesande 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:
- Küsige end alt: kas elementide järjekorda on ülesande tekstis arvesse võetud?
- Kui vastus on eitav, siis kasutage kombinatsiooni valemit (C=n! / (m!(n - m)!)).
- Kui vastus on eitav, peate vastama veel ühele küsimusele: kas kõik elemendid on kombinatsioonis?
- Kui vastus on jah, siis kasutage permutatsiooni valemit (P=n!).
- Kui vastus on eitav, siis kasutage jaotusvalemit (A=n! / (n - m)!).
Näide
Oleme kaalunud kombinatoorika elemente, valemeid ja mõnda muud küsimust. Liigume nüüd edasiarvestades tõelist probleemi. 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 võimalust.
Teine 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.
Kolmas küsimus: mitmel viisil saab kahte puuvilja valida? 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
Neljas 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.
Viies küsimus: mitmel viisil saate valida vähem alt ühe puuvilja? See tingimus tähendab, et võime võtta ühe, kaks või kõik kolm vilja. Seetõttu lisame C1 + C2 + C3=3 + 3 + 1=7. See tähendab, et meil on seitse võimalust võtta lau alt vähem alt üks puuvili.
