Tämä artikkeli keskittyy matematiikan erityisosaan, jota kutsutaan kombinatoriikaksi. Kaavat, säännöt, esimerkkejä ongelmanratkaisusta - kaiken tämän löydät täältä lukemalla artikkelin loppuun asti.
Joten, mikä tämä osio on? Kombinatoriikka käsittelee kysymystä minkä tahansa objektin laskemisesta. Mutta tässä tapauksessa esineet eivät ole luumuja, päärynöitä tai omenoita, vaan jotain muuta. Kombinatoriikka auttaa meitä löytämään tapahtuman todennäköisyyden. Millä todennäköisyydellä vastustajalla on v alttikortti esimerkiksi korttia pelatessa? Tai tällainen esimerkki - millä todennäköisyydellä saat täsmälleen valkoisen kahdenkymmenen pallon pussista? Juuri tällaisia tehtäviä varten meidän on tiedettävä ainakin tämän matematiikan perusteet.
Kombinatoriset kokoonpanot
Kun otetaan huomioon kysymys kombinatoriikan peruskäsitteistä ja kaavoista, emme voi muuta kuin kiinnittää huomiota kombinatorisiin konfiguraatioihin. Niitä ei käytetä vain formulointiin, vaan myös erilaisten kombinatoristen ongelmien ratkaisemiseen. Esimerkkejä tällaisista malleista ovat:
- sijoittelu;
- permutaatio;
- yhdistelmä;
- numerokokoonpano;
- jaettu numero.
Puhumme kolmesta ensimmäisestä tarkemmin myöhemmin, mutta kiinnitämme huomiota sävellykseen ja jakamiseen tässä osiossa. Kun he puhuvat tietyn luvun koostumuksesta (esim. a), he tarkoittavat luvun a esittämistä joidenkin positiivisten lukujen järjestetynä summana. Ja jako on järjestämätön summa.
Osat
Ennen kuin siirrytään suoraan kombinatoriikan kaavoihin ja tehtävien tarkasteluun, on syytä kiinnittää huomiota siihen, että kombinatoriikassa, kuten muillakin matematiikan osioilla, on omat alajaksonsa. Näitä ovat:
- enumeratiivinen;
- rakenteellinen;
- äärimmäinen;
- Ramseyn teoria;
- todennäköisyys;
- topologinen;
- ääretön.
Ensimmäisessä tapauksessa puhumme numeratiivisesta kombinatoriikasta, ongelmat käsittelevät joukkojen elementtien muodostamien erilaisten konfiguraatioiden luetteloimista tai laskemista. Pääsääntöisesti näille sarjoille asetetaan joitain rajoituksia (erotettavuus, erottamattomuus, toistomahdollisuus ja niin edelleen). Ja näiden kokoonpanojen lukumäärä lasketaan käyttämällä yhteen- tai kertolaskua, josta puhumme hieman myöhemmin. Rakenteellinen kombinatoriikka sisältää graafien ja matroidien teoriat. Esimerkki äärimmäisestä kombinatorisesta ongelmasta on, mikä on graafin suurin ulottuvuus, joka täyttää seuraavat ominaisuudet… Neljännessä kappaleessa mainittiin Ramseyn teoria, joka tutkii säännöllisten rakenteiden esiintymistä satunnaisissa kokoonpanoissa. Todennäköisyyskombinatoriikka osaa vastata kysymykseen - millä todennäköisyydellä tietyllä joukolla on tietty ominaisuus. Kuten arvata saattaa, topologinen kombinatoriikka soveltaa menetelmiä topologiassa. Ja lopuksi seitsemäs kohta – ääretön kombinatoriikka tutkii kombinatoriikan menetelmien soveltamista äärettömiin joukoihin.
Lisäyssääntö
Kombinatoriikan kaavoista löytyy varsin yksinkertaisia, jotka ovat olleet tuttuja jo pitkään. Esimerkki on summasääntö. Oletetaan, että meille annetaan kaksi toimenpidettä (C ja E), jos ne ovat toisensa poissulkevia, toiminto C voidaan tehdä useilla tavoilla (esim. a) ja toiminto E voidaan tehdä b-tavoilla, niin mikä tahansa niistä (C tai E) voidaan tehdä a + b tavoilla.
Teoriassa tämä on melko vaikea ymmärtää, yritämme välittää koko asian yksinkertaisella esimerkillä. Otetaan yhden luokan oppilaiden keskimääräinen lukumäärä - oletetaan, että se on kaksikymmentäviisi. Heidän joukossaan on viisitoista tyttöä ja kymmenen poikaa. Kurssille määrätään päivittäin yksi hoitaja. Kuinka monella tapaa luokanhoitajan nimeämiseen on nykyään? Ratkaisu ongelmaan on melko yksinkertainen, turvaudumme lisäyssääntöön. Tehtävän tekstissä ei sanota, että vain pojat tai vain tytöt voivat olla päivystyksessä. Siksi se voi olla mikä tahansa viidestätoista tytöstä tai mikä tahansa kymmenestä pojasta. Summa-sääntöä sovellettaessa saamme melko yksinkertaisen esimerkin, josta alakoululainen selviää helposti: 15 + 10. Laskettuaan saamme vastauksen: kaksikymmentäviisi. Eli tapaa on vain kaksikymmentäviisimääritä päivystysluokka tälle päivälle.
Kertokertasääntö
Kertolasääntö kuuluu myös kombinatoriikan peruskaavoihin. Aloitetaan teoriasta. Oletetaan, että meidän on suoritettava useita toimintoja (a): ensimmäinen toiminto suoritetaan yhdellä tavalla, toinen - kahdella tavalla, kolmas - kolmella tavalla ja niin edelleen, kunnes viimeinen a-toiminto suoritetaan samalla tavalla. Sitten kaikki nämä toiminnot (joita meillä on yhteensä) voidaan suorittaa N tavalla. Kuinka laskea tuntematon N? Kaava auttaa meitä tässä: N \u003d c1c2c3…ca.
Taaskaan, teoriassa mikään ei ole selvää, siirrytään yksinkertaiseen esimerkkiin kertolaskusäännön soveltamisesta. Otetaan sama 25 hengen luokka, jossa opiskelee viisitoista tyttöä ja kymmenen poikaa. Vain tällä kertaa meidän on valittava kaksi hoitajaa. He voivat olla joko vain poikia tai tyttöjä tai poikia tytön kanssa. Siirrymme ongelman perusratkaisuun. Valitsemme ensimmäisen hoitajan, kuten viimeisessä kappaleessa päätimme, saamme kaksikymmentäviisi mahdollista vaihtoehtoa. Toinen päivystävä henkilö voi olla kuka tahansa jäljellä olevista henkilöistä. Meillä oli kaksikymmentäviisi opiskelijaa, valitsimme yhden, mikä tarkoittaa, että kuka tahansa jäljellä olevista 24 henkilöstä voi olla toinen päivystävä. Lopuksi sovellamme kertolasääntöä ja huomaamme, että kaksi hoitajaa voidaan valita kuudellasadalla tavalla. Saimme tämän luvun kertomalla kaksikymmentäviisi ja kaksikymmentäneljä.
Vaihda
Nyt tarkastelemme vielä yhtä kombinatorista kaavaa. Tässä artikkelin osassa mePuhutaan permutaatioista. Harkitse ongelmaa välittömästi esimerkin avulla. Otetaan biljardipalloja, niitä on n:s määrä. Meidän on laskettava: kuinka monta vaihtoehtoa on järjestää ne peräkkäin, eli tehdä tilattu sarja.
Aloitetaan, jos meillä ei ole palloja, niin meillä on myös nolla sijoitusvaihtoehtoa. Ja jos meillä on yksi pallo, niin järjestely on myös sama (matemaattisesti tämä voidaan kirjoittaa seuraavasti: Р1=1). Kaksi palloa voidaan järjestää kahdella eri tavalla: 1, 2 ja 2, 1. Siksi Р2=2. Kolme palloa voidaan järjestää kuudella tavalla (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Ja jos tällaisia palloja ei ole kolme, vaan kymmenen tai viisitoista? Kaikkien mahdollisten vaihtoehtojen luettelointi on hyvin pitkä, niin kombinatoriikka tulee avuksemme. Permutaatiokaava auttaa meitä löytämään vastauksen kysymykseemme. Pn=nP(n-1). Jos yritämme yksinkertaistaa kaavaa, saamme: Pn=n (n - 1) … 21. Ja tämä on ensimmäisten luonnollisten lukujen tulo. Tällaista lukua kutsutaan kertoimeksi ja se merkitään n!
Mietitään ongelmaa. Johtaja rakentaa joka aamu osastonsa jonoon (kaksikymmentä henkilöä). Ryhmässä on kolme parasta ystävää - Kostya, Sasha ja Lesha. Millä todennäköisyydellä ne ovat vierekkäin? Löytääksesi vastauksen kysymykseen, sinun on jaettava "hyvän" tuloksen todennäköisyys tulosten kokonaismäärällä. Permutaatioiden kokonaismäärä on 20!=2,5 kvintiljoonaa. Kuinka laskea "hyvien" tulosten lukumäärä? Oletetaan, että Kostya, Sasha ja Lesha ovat yksi supermies. Sitten meMeillä on vain kahdeksantoista aihetta. Permutaatioiden lukumäärä tässä tapauksessa on 18=6,5 kvadriljoonaa. Kaiken tämän myötä Kostya, Sasha ja Lesha voivat mieliv altaisesti liikkua keskenään jakamattomassa kolmiossa, ja tämä on vielä 3!=6 vaihtoehtoa. Meillä on siis yhteensä 18 "hyvää" tähtikuviota!3! Meidän on vain löydettävä haluttu todennäköisyys: (18!3!) / 20! Mikä on noin 0,016. Prosentteiksi muutettuna se on vain 1,6%.
Majoitus
Nyt tarkastelemme toista erittäin tärkeää ja tarpeellista kombinatoriikan kaavaa. Majoitus on seuraava numeromme, jota suosittelemme harkitsemaan artikkelin tässä osassa. Meistä tulee monimutkaisempia. Oletetaan, että haluamme harkita mahdollisia permutaatioita, ei vain koko joukosta (n), vaan pienemmästä (m). Toisin sanoen tarkastelemme n kohteen permutaatioita m:llä.
Kombinatoriikan peruskaavoja ei pidä vain opetella ulkoa, vaan myös ymmärtää. Huolimatta siitä, että niistä tulee monimutkaisempia, koska meillä ei ole yhtä parametria, vaan kaksi. Oletetaan, että m \u003d 1, sitten A \u003d 1, m \u003d 2, sitten A=n(n - 1). Jos yksinkertaistamme kaavaa entisestään ja siirrymme merkintään kertoimia käyttämällä, saadaan melko ytimekäs kaava: A \u003d n! / (n - m)!
Yhdistelmä
Olemme tarkastelleet lähes kaikkia kombinatoriikan peruskaavoja esimerkein. Siirrytään nyt kombinatoriikan peruskurssin pohdinnan viimeiseen vaiheeseen - yhdistelmään tutustumiseen. Nyt valitsemme m kohdetta n:stä, joka meillä on, samalla kun valitsemme ne kaikki kaikilla mahdollisilla tavoilla. Miten tämä sitten eroaa majoituksesta? Emmeharkita järjestystä. Tämä tilaamaton sarja on yhdistelmä.
Ota heti käyttöön merkintä: C. Otetaan m pallon sijoittelut n:stä. Lakkaamme kiinnittämästä huomiota järjestykseen ja saamme toistuvia yhdistelmiä. Yhdistelmien lukumäärän saamiseksi meidän on jaettava sijoittelujen määrä m:llä! (m faktoriaalinen). Eli C \u003d A / m! Näin ollen on olemassa muutamia tapoja valita n pallosta, mikä vastaa suunnilleen sitä, kuinka monta valita melkein kaikki. Tälle on looginen ilmaus: vähän valita on sama kuin melkein kaiken heittäminen pois. Tässä vaiheessa on myös tärkeää mainita, että maksimimäärä yhdistelmiä voidaan saavuttaa, kun yritetään valita puolet kohteista.
Kuinka valita kaava ongelman ratkaisemiseksi?
Olemme tutkineet yksityiskohtaisesti kombinatoriikan peruskaavat: sijoittelu, permutaatio ja yhdistelmä. Nyt tehtävämme on helpottaa tarvittavan kaavan valintaa ongelman ratkaisemiseksi kombinatoriikassa. Voit käyttää seuraavaa melko yksinkertaista mallia:
- Kysy itseltäsi: onko elementtien järjestys otettu huomioon tehtävän tekstissä?
- Jos vastaus on ei, käytä yhdistelmäkaavaa (C=n! / (m!(n - m)!)).
- Jos vastaus on ei, sinun on vastattava vielä yhteen kysymykseen: ovatko kaikki elementit mukana yhdistelmässä?
- Jos vastaus on kyllä, käytä permutaatiokaavaa (P=n!).
- Jos vastaus on ei, käytä allokointikaavaa (A=n! / (n - m)!).
Esimerkki
Olemme pohtineet kombinatoriikan elementtejä, kaavoja ja joitain muita asioita. Nyt siirrytään asiaantodellista ongelmaa harkiten. Kuvittele, että sinulla on edessäsi kiivi, appelsiini ja banaani.
Kysymys yksi: kuinka monella tavalla ne voidaan järjestää uudelleen? Tätä varten käytämme permutaatiokaavaa: P=3!=6 tapaa.
Kysymys kaksi: kuinka monella tavalla yksi hedelmä voidaan valita? Tämä on ilmeistä, meillä on vain kolme vaihtoehtoa - valitse kiivi, appelsiini tai banaani, mutta käytämme yhdistelmäkaavaa: C \u003d 3! / (2!1!)=3.
Kysymys kolme: kuinka monella tavalla voidaan valita kaksi hedelmää? Mitä vaihtoehtoja meillä on? Kiivi ja appelsiini; kiivi ja banaani; appelsiini ja banaani. Eli kolme vaihtoehtoa, mutta tämä on helppo tarkistaa yhdistelmäkaavalla: C \u003d 3! / (1!2!)=3
Kysymys neljä: kuinka monella tavalla kolme hedelmää voidaan valita? Kuten näet, on vain yksi tapa valita kolme hedelmää: ota kiivi, appelsiini ja banaani. C=3! / (0!3!)=1.
Kysymys viisi: kuinka monella tavalla voit valita ainakin yhden hedelmän? Tämä ehto tarkoittaa, että voimme ottaa yhden, kaksi tai kaikki kolme hedelmää. Siksi lisäämme C1 + C2 + C3=3 + 3 + 1=7. Eli meillä on seitsemän tapaa ottaa ainakin yksi hedelmä pöydältä.
