Kombinatoriikka – permutaatiot ja kombinaatiot
Kombinatoriikka on matematiikan haara, joka tutkii erilaisten järjestelyjen ja valintojen lukumääriä. Kombinatoriikka käsittelee permutaatioita (järjestelyjä) ja kombinaatioita (valintoja ilman järjestystä). Kombinatoriikkaa tarvitaan todennäköisyyslaskennassa, kun lasketaan suotuisien tapahtumien lukumääriä. Tämä aihe kuuluu lukion matematiikan opetussuunnitelmaan (LOPS21) ja käsitellään kursseilla MAA8: Tilastot ja todennäköisyys ja MAA12. Tällä sivulla opit permutaatioiden ja kombinaatioiden laskemisen sekä niiden käytön todennäköisyyslaskennassa.
Kaavat
Kertoma
Kertoma laskee kuinka monella tavalla alkiota voidaan järjestää peräkkäin. Määritelmän mukaan , jotta permutaatio- ja kombinaatiokaavat toimivat (esim. ).
- Kertoma (n alenevien kokonaislukujen tulo)
- Määritellään $0! = 1$
Permutaatio
Permutaatio vastaa kysymykseen: kuinka monella tavalla valitaan alkiota :stä ja järjestetään ne? Järjestys merkitsee — eri järjestykset ovat eri tapauksia. Kun , .
- Alkioiden kokonaismäärä
- Valittavien ja järjestettävien alkioiden määrä
Kombinaatio
Kombinaatio vastaa: kuinka monella tavalla valitaan k alkiota n:stä ilman että järjestys merkitsee? Sama joukko = yksi tapaus. Jakaja k! poistaa järjestyksen.
- Binomikerroin (n yli k)
- n = alkioiden määrä, k = valittavien määrä
Kombinaation symmetria
Valita k alkiota n:stä on sama asia kuin jättää n−k pois; tapojen lukumäärä on sama. Käytä laskennan helpottamiseen kun k on suuri.
- Valita $n-k$ alkiota = jättää $k$ pois
Pascalin kolmio
Jokainen binomikerroin = ylävasemmalla + yläoikealla. Rekursio: valitsetko :nnen alkion mukaan (sitten yli ) vai et (sitten yli )? Rivi antaa kertoimet .
- Ylävasen luku
- Yläoikea luku
Säännöt
Kertoma
ja
Kertoma on luvun alenevien kokonaislukujen tulo; määritellään .
Permutaatio
(järjestys merkitsee)
Valitaan k alkiota n:stä ja järjestetään ne – järjestys merkitsee.
Kombinaatio
(järjestys ei merkitse)
Valitaan k alkiota n:stä ilman järjestystä; binomikerroin (n yli k).
Kombinaation symmetria
K alkiota valitaan sama kuin jättää n-k pois.
Pascalin kolmio
Rekursio: valitsetko :nnen (sitten yli ) vai et (sitten yli )?
Esimerkit
Esimerkki 1: Kertoma
HelppoLaske .
- Käytä kertoman määritelmää: .Kertoma on kaikkien positiivisten kokonaislukujen tulo :stä :ään.
- Laske: .Kertoma on .
Esimerkki 2: Permutaatio
HelppoKuinka monella tavalla voidaan järjestää kirjaa hyllyyn?
- Tunnista, että järjestys merkitsee, joten käytetään permutaatiota.Koska kirjat järjestetään hyllyyn, järjestys merkitsee. Tämä on permutaatio.
- Käytä permutaation kaavaa: .Kun kaikki alkiota järjestetään, permutaatio on .
- Vastaus: erilaista tapaa järjestää kirjaa hyllyyn.Voidaan myös ajatella: ensimmäiselle paikalle vaihtoehtoa, toiselle , kolmannelle ja neljännelle , eli .
Esimerkki 3: Permutaatio (osajoukko)
KeskitasoKuinka monella tavalla voidaan valita ja järjestää henkilöä :sta henkilöstä palkintosijalle?
- Tunnista, että sekä valinta että järjestys merkitsevät, joten käytetään permutaatiota.Koska henkilöt valitaan ja järjestetään palkintosijalle, järjestys merkitsee. Tämä on permutaatio.
- Käytä permutaation kaavaa: .Permutaatio lasketaan kaavalla .
- Vastaus: erilaista tapaa valita ja järjestää henkilöä :sta.Voidaan myös ajatella: ensimmäiselle sijalle vaihtoehtoa, toiselle ja kolmannelle , eli .
Esimerkki 4: Kombinaatio
KeskitasoKuinka monella tavalla voidaan valita korttia kortin pakasta?
- Tunnista, että järjestys ei merkitse, joten käytetään kombinaatiota.Koska kortit valitaan pakasta ilman järjestystä, järjestys ei merkitse. Tämä on kombinaatio.
- Käytä kombinaation kaavaa: .Kombinaatio lasketaan kaavalla .
- Yksinkertaista: .Kombinaatio voidaan laskea suoraan kertomalla ja jakamalla ilman kertomien täyttä laskemista.
- Vastaus: erilaista tapaa valita korttia kortin pakasta.Tämä on tyypillinen pokerikäsi, jossa järjestys ei merkitse.
Esimerkki 5: Kombinaation symmetria
HelppoLaske käyttämällä symmetriaa.
- Käytä kombinaation symmetriaa: .Kombinaation symmetrian mukaan .
- Laske .Symmetriaa käyttäen laskeminen on helpompaa, koska on pienempi kuin .
- Vastaus: .Symmetriaa käyttäen voidaan välttää suurten kertomien laskeminen.
Esimerkki 6: Monimutkainen kombinatoriikka
VaikeaRyhmässä on opiskelijaa: tyttöä ja poikaa. Kuinka monella tavalla voidaan valita henkilöä ryhmästä siten, että joukossa on vähintään tyttöä?
- Jaa ongelma osiin: "vähintään tyttöä" tarkoittaa , tai tyttöä.Monimutkaiset ongelmat jaetaan usein osiin, joissa jokainen osa on helpompi laskea.
- Tapaus 1: Tarkalleen tyttöä ja poikaa: .Valitaan tyttöä :stä ja poikaa :stä. Kertolasku, koska valinnat ovat riippumattomia.
- Tapaus 2: Tarkalleen tyttöä ja poika: .Valitaan tyttöä :stä ja poika :stä.
- Tapaus 3: Tarkalleen tyttöä: .Valitaan tyttöä :stä. Poikia ei valita.
- Laske yhteensä: .Koska tapaukset ovat erillisiä, lasketaan summa.
- Vastaus: erilaista tapaa valita henkilöä siten, että joukossa on vähintään tyttöä.Yhteensä erilaista tapaa.
Esimerkki
Kuinka monella tavalla voidaan valita henkilöä :stä henkilöstä?
- Tunnista, että järjestys ei merkitse, joten käytetään kombinaatiota.
- Käytä kombinaation kaavaa: .
- Yksinkertaista: .
- Vastaus: erilaista tapaa valita henkilöä :stä.
Sovellukset
- Todennäköisyyslaskennassa kombinatoriikkaa käytetään laskemaan suotuisien tapahtumien lukumääriä. Esimerkiksi korttipeleissä kombinaatioita käytetään laskemaan, kuinka monella tavalla voidaan saada tietty käsi.
- Tietojenkäsittelytieteessä kombinatoriikkaa käytetään algoritmien suunnittelussa ja optimoinnissa. Esimerkiksi hajautustaulut ja hakualgoritmit perustuvat kombinatoriikkaan.
- Genetiikassa kombinatoriikkaa käytetään laskemaan erilaisten geeniyhdistelmien määriä. Esimerkiksi perinnöllisyystutkimuksessa lasketaan, kuinka monella tavalla geenejä voidaan periyttää.
- Salakirjoituksessa kombinatoriikkaa käytetään laskemaan mahdollisten salausavainten määriä. Mitä enemmän mahdollisia avaimia, sitä turvallisempi salaus on.
Yleisiä virheitä
Permutaation ja kombinaation sekoittaminen
Monet sekoittavat permutaation ja kombinaation. He käyttävät väärää kaavaa tai eivät tunnista, merkitseekö järjestys.
Oikein: Permutaatiota käytetään, kun järjestys merkitsee (esimerkiksi palkintosijat, järjestys). Kombinaatiota käytetään, kun järjestys ei merkitse (esimerkiksi korttikädet, joukkueen valinta). Muista: permutaatio = järjestys merkitsee, kombinaatio = järjestys ei merkitse.
Kertoman laskeminen väärin
Monet unohtavat, että tai laskevat kertoman väärin. He saattavat saada tai laskea kertoman väärin.
Oikein: Muista, että . Kertoma lasketaan kaavalla . Esimerkiksi .
Kombinaation kaavan unohtaminen
Monet unohtavat, että kombinaatiossa täytyy jakaa myös :lla, koska järjestys ei merkitse. He saattavat käyttää permutaation kaavaa kombinaation sijaan.
Oikein: Kombinaation kaava on . Huomaa, että jakaja sisältää sekä että . Permutaation kaava on (ei jakajassa).
Symmetrian unohtaminen
Monet eivät käytä kombinaation symmetriaa, vaikka se helpottaisi laskemista. He laskevat suoraan sen sijaan, että käyttäisivät .
Oikein: Käytä kombinaation symmetriaa: . Tämä helpottaa laskemista, kun on suuri. Esimerkiksi , koska on lähellä :tä.
Usein kysyttyä
- Mikä ero on permutaatiolla ja kombinaatiolla?
- Permutaatiossa järjestys merkitsee, kombinaatiossa järjestys ei merkitse. Esimerkiksi, jos valitaan henkilöä :stä palkintosijalle, järjestys merkitsee (kuka on ensimmäinen, toinen, kolmas), joten käytetään permutaatiota. Jos valitaan henkilöä :stä joukkueeseen, järjestys ei merkitse, joten käytetään kombinaatiota.
- Mikä on kertoma?
- Kertoma on kaikkien positiivisten kokonaislukujen tulo :stä :ään: . Määritelmän mukaan . Esimerkiksi .
- Miten lasken permutaation?
- Permutaatio lasketaan kaavalla , missä on alkioiden kokonaismäärä ja on valittavien alkioiden määrä. Esimerkiksi .
- Miten lasken kombinaation?
- Kombinaatio lasketaan kaavalla , missä on alkioiden kokonaismäärä ja on valittavien alkioiden määrä. Esimerkiksi .
- Miksi ?
- Kertoman määritelmän mukaan . Tämä on määritelty näin, koska se tekee kombinatoriikan kaavoista yhdenmukaisia. Esimerkiksi , mikä on loogista: on yksi tapa valita alkiota :stä (ei valita mitään).
- Mikä on kombinaation symmetria?
- Kombinaation symmetria tarkoittaa, että . Tämä tarkoittaa, että valita alkiota :stä on sama kuin jättää alkiota valitsematta. Esimerkiksi , koska valita alkiota :stä on sama kuin jättää alkiota valitsematta.
- Milloin käytän permutaatiota ja milloin kombinaatiota?
- Käytä permutaatiota, kun järjestys merkitsee (esimerkiksi palkintosijat, järjestys, koodit). Käytä kombinaatiota, kun järjestys ei merkitse (esimerkiksi korttikädet, joukkueen valinta, osajoukot). Kysy itseltäsi: "Jos vaihdan alkioiden järjestystä, saanko eri tuloksen?" Jos vastaus on kyllä, käytä permutaatiota. Jos vastaus on ei, käytä kombinaatiota.
- Mikä on Pascalin kolmio?
- Pascalin kolmio on taulukko, jossa jokainen luku on kahden yläpuolella olevan luvun summa. Pascalin kolmion :s rivi sisältää kombinaatiot . Pascalin kolmio noudattaa kaavaa .
- Miten lasken monimutkaisia kombinatoriikkaongelmia?
- Monimutkaiset kombinatoriikkaongelmat jaetaan usein osiin. Jokainen osa lasketaan erikseen, ja sitten osat yhdistetään (joko summa tai tulo riippuen tilanteesta). Esimerkiksi "vähintään " jaetaan tapauksiin "tarkalleen ", "tarkalleen ", jne.
- Voiko kombinatoriikkaa käyttää todennäköisyyslaskennassa?
- Kyllä. Kombinatoriikkaa käytetään laajasti todennäköisyyslaskennassa laskemaan suotuisien tapahtumien lukumääriä. Esimerkiksi korttipeleissä kombinaatioita käytetään laskemaan, kuinka monella tavalla voidaan saada tietty käsi. Todennäköisyys lasketaan sitten kaavalla , missä on suotuisien tapahtumien lukumäärä (kombinatoriikka) ja on kaikkien mahdollisten tapahtumien lukumäärä.
Lähteet ja lisämateriaali
- LOPS21: MAA8 ja MAA12 Tilastot ja todennäköisyys
Lukion matematiikan kurssit (LOPS21): MAA8 ja MAA12 käsittelevät kombinatoriikkaa, permutaatioita ja kombinaatioita. Osa lukion opetussuunnitelmaa.
- Ylioppilaskokeiden tehtävät
Aiemmat ylioppilaskokeiden tehtävät ja malliratkaisut kombinatoriikasta.
- TIM - Pitkän matematiikan kertauskurssi
Jyväskylän yliopiston kertauskurssi, joka sisältää harjoitustehtäviä ja teoriaa kombinatoriikasta.
- Ylen Abitreenit: Kombinatoriikka
Ylen Abitreenit-sivuston materiaali kombinatoriikasta.