Tässä artikkelissa opit Permutaatioiden ja yhdistelmien ongelmista: Määritelmä, kaavat, ratkaistuja esimerkkejä ja tietokilpailu harjoituskysymyksineen.

Permutaatiot

Määritelmä

Permutaatiot ovat erilaisia tapoja, joilla kokoelma kohteita voidaan järjestää.

Esimerkiksi:

Erilaiset tavat, joilla aakkoset A, B ja C voidaan ryhmitellä yhteen, kun otetaan kaikki kerrallaan, ovat: ABC, ACB, BCA, BCA, CBA, CAB, BAC.

Huomaa, että ABC ja CBA eivät ole samoja, koska järjestysjärjestys on eri. Sama sääntö pätee, kun ratkaistaan mitä tahansa permutaatioiden ongelmaa.

Tapojen lukumäärä, joilla n asiaa voidaan järjestää, kun otetaan kaikki kerrallaan, on nPn = n!, kutsutaan ’n faktoriaaliksi.’

Faktoriaalikaava

Luvun n faktoriaali määritellään kaikkien n:n ja 1:n välisten lukujen tulona.

Esimerkiksi 5:n faktoriaali, 5! = 5*4*3*2*1 = 120.

Siten 3 kirjaimen järjestämistapojen lukumäärä, kun otetaan kaikki kerrallaan, on 3! = 3*2*1 = 6 tapaa.

N asioiden permutaatioiden lukumäärä, kun otetaan r kerrallaan, merkitään:

nPr = n! / (n-r)!

Esimerkiksi:

Kolme kirjainta, joita otetaan kaksi kerrallaan, voidaan järjestää eri tavoin: 3!/(3-2)! = 3!/1! = 6 tapaa.

Tärkeitä permutaatiokaavoja

1! = 1

0! = 1
Katsotaanpa muutamia esimerkkejä:

Tehtävä 1: Löydä niiden sanojen määrä, merkitykseltään tai merkityksettömyydeltään, jotka voidaan muodostaa sanan ’TUOLI’ kirjaimilla.

Ratkaisu:

’TUOLI’ sisältää 5 kirjainta.

Siten niiden sanojen lukumäärä, jotka voidaan muodostaa näillä 5 kirjaimella = 5! = 5*4*3*2*1 = 120.

Tehtävä 2: Löydä niiden sanojen lukumäärä, merkityssisällön kanssa tai sitä vailla, jotka voidaan muodostaa sanan ’INDIA’ kirjaimilla.

Ratkaisu:

Sanassa ’INDIA’ on 5 kirjainta ja ’I’ esiintyy kahdesti.

Kun kirjain esiintyy sanassa useammin kuin kerran, jaetaan sanan kaikkien kirjainten lukumäärän faktoriluku kunkin kirjaimen esiintymien lukumäärällä.

Siten sanan ’INDIA’ muodostamien sanojen lukumäärä = 5!/2! = 60.

Tehtävä 3: Etsi niiden sanojen lukumäärä, joilla on tai joilla ei ole merkitystä, jotka voidaan muodostaa sanan ’UIMA’ kirjaimista?

Ratkaisu:

Sanassa ’UIMA’ on 8 kirjainta. Joista I esiintyy kahdesti ja M esiintyy kahdesti.

Siten tästä sanasta muodostettavien sanojen lukumäärä = 8! / (2!*2!) = 10080.

Ongelma 4: Kuinka monta erilaista sanaa voidaan muodostaa sanan ’SUPER’ kirjaimista siten, että vokaalit tulevat aina yhteen?

Ratkaisu:

Sana ’SUPER’ sisältää 5 kirjainta.

Etsitään niiden permutaatioiden lukumäärä, jotka voidaan muodostaa, kun kaksi vokaalia U ja E tulevat yhteen.

Tällöin ryhmitellään ne kirjaimet, joiden pitäisi tulla yhteen, ja pidetään tätä ryhmää yhtenä kirjaimena.

Kirjaimet ovat siis S,P,R, (UE). Nyt sanojen lukumäärä on 4.

Siten niiden tapojen lukumäärä, joilla 4 kirjainta voidaan järjestää, on 4!

U:n ja E:n kohdalla niiden tapojen lukumäärä, joilla U ja E voidaan järjestää, on 2!

Siten niiden tapojen lukumäärä, joilla ’SUPER’-sanan kirjaimet voidaan järjestää siten, että vokaalit ovat aina yhdessä, on yhteensä 4! * 2! = 48 tapaa.

Ongelma 5: Etsi kuinka monta erilaista sanaa voidaan muodostaa sanan ’BUTTER’ kirjaimista niin, että vokaalit ovat aina yhdessä.

Ratkaisu:

Sanassa ’BUTTER’ on 6 kirjainta.

Kirjainten U ja E pitäisi olla aina yhdessä. Kirjaimet ovat siis B, T, T, R, (UE).

Tapojen määrä, joilla yllä olevat kirjaimet voidaan järjestää = 5!/2! = 60 (koska kirjain ’T’ toistuu kahdesti).

Tapojen määrä, joilla U ja E voidaan järjestää = 2! = 2 tapaa

Siten mahdollisten permutaatioiden kokonaismäärä = 60*2 = 120 tapaa.
Tehtävä 6: Etsi sanan ’JÄLJELLÄ’ kirjainten permutaatioiden lukumäärä siten, että vokaalit esiintyvät aina parittomilla paikoilla.

Ratkaisu:

Sanassa ’REMAINS’ on 7 kirjainta.

Sanassa on 4 konsonanttia ja 3 vokaalia.

Kirjoittaminen seuraavalla tavalla helpottaa tämän tyyppisten kysymysten ratkaisemista.

(1) (2) (3) (4) (5) (6) (7)

Tapojen määrä, joilla 3 vokaalia voi esiintyä neljässä eri paikassa = 4P3 = 24 tapaa.

Kun 3 vokaalia on kolmessa paikassa, tapojen määrä, joilla 4 konsonanttia voi olla neljässä paikassa = 4P4 = 4! = 24 tapaa.

Siten mahdollisten permutaatioiden kokonaismäärä = 24*24 = 576 tapaa.

Kombinaatiot Määritelmä Erilaisia valintoja, jotka ovat mahdollisia joukosta kohteita, kutsutaan kombinaatioiksi.

Esimerkiksi:

Aakkosista A, B, C mahdolliset erilaiset valinnat, kun otetaan 2 kappaletta kerrallaan, ovat AB, BC ja CA.

Ei ole väliä, valitsemmeko A:n B:n jälkeen vai B:n A:n jälkeen. Valintajärjestyksellä ei ole merkitystä yhdistelmissä.

Voidaksemme löytää yhdistelmien lukumäärän, joka on mahdollinen tietystä ryhmästä n, joka otetaan r kerrallaan, kaava, jota merkitään nCr:llä, on

nCr = n! /

Ylläolevan esimerkin todentamiseksi voidaan esimerkiksi todeta, että aakkosista A, B, C mahdolliset eri valinnat, joita on kaksi kerrallaan, ovat

3C2 = 3! / (2! * (3-2)!) = 3 mahdollista valintaa (esim, AB, BC, CA)

Tärkeitä yhdistelmäkaavoja

nCn = 1

nC0 = 1

nC1 = n

nCr = nC(n-r)

Mahdollisten valintojen määrä, kun A, B, C otetaan kaikki kerrallaan, on 3C3 = 1 (ts. ABC)

Ratkaistuja esimerkkejä yhdistelmästä

Katsotaanpa muutamia esimerkkejä, jotta ymmärtäisimme, miten yhdistelmät toimivat:

Tehtävä 1: Kuinka monella tavalla voidaan muodostaa 1 miehen ja 3 naisen muodostama komitea 3 miehen ja 4 naisen ryhmästä?

Ratkaisu:

Tapojen määrä, joilla 1 mies voidaan valita 3 miehen ryhmästä = 3C1 = 3! / 1!*(3-1)! = 3 tapaa.

Tapojen määrä, joilla 3 naista voidaan valita 4 naisen ryhmästä = 4C3 = 4! / (3!*1!) = 4 tapaa.

Tehtävä 2: Kuinka monella tavalla voidaan valita 5 mustan ja 3 punaisen pallon joukosta 5 palloa siten, että vähintään 3 niistä on mustia palloja.

Ratkaisu:

5 mustan pallon joukosta 5 mustan pallon kokonaisvalinnassa voidaan valita vähintään 3 mustaa palloa

3 B- ja 2 R-palloa

4 B- ja 1 R-palloa ja

5 B- ja 0 R-palloa.

Siten ratkaisulausekkeemme näyttää seuraavalta.
5C3 * 3C2 + 5C4 * 3C1 + 5C5 * 3C0 = 46 tapaa .

Ongelma 3: Kuinka monta 10:llä jaettavaa 4-numeroista lukua voidaan muodostaa luvuista 3, 5, 7, 8, 9, 0 siten, että yksikään luku ei toistu?

Ratkaisu:

Jos luku on jaollinen 10:llä, sen yksikköpaikan pitäisi sisältää 0.
_ _ _ 0

Kun 0 on sijoitettu yksikköpaikkaan, kymppipaikka voidaan täyttää millä tahansa muulla 5:stä numerosta.

Valitsemalla yhden numeron 5:stä numerosta voidaan valita 5C1 = 5 tapaa.

Kymppipaikan täyttämisen jälkeen jäljelle jää 4 numeroa. Yhden numeron valitseminen neljästä numerosta voidaan tehdä 4C1 = 4 tapaa.

Satasen paikan täyttämisen jälkeen tuhansien paikka voidaan täyttää 3C1 = 3 tapaa.

Siten kaikkien mahdollisten yhdistelmien kokonaismäärä = 5*4*3 = 60.

Permutaatiot ja yhdistelmät tietokilpailu

Kokeile näitä harjoitustehtäviä.

.