www.matematikk.org
LærerstudenterLærerstudenter

Permutasjoner

Et stafettlag består av tre personer som skal gjennomføre hver sin etappe etter hverandre. Hvor mange muligheter har vi til å organisere laget? Spørsmålet kan formuleres slik: Hvor mange rekkefølger kan vi finne for tre bokstaver a, b og c?

Vi prøver og ser at det blir seks forskjellige måter (rekkefølger): abc, acb, bac, bca, cab, cba. En slik kombinasjon, en rekkefølge av de tre bokstavene, for eksempel abc, kalles en permutasjon. I dette tilfellet er det enkelt å sette opp alle permutasjonene og telle dem. Men i andre tilfeller er det ikke alltid like lett. Vi vil derfor finne en systematisk metode som gir riktig antall permutasjoner ved hjelp av litt regning.

La oss igjen se på de tre bokstavene a, b og c. Det er 3 forskjellige bokstaver, a, b eller c, som kan settes opp på den første plassen. Når vi har valgt en av de tre til å stå på første plass, kan denne kombineres med de to gjenværende på plass nummer 2. Der er det da to muligheter. Til slutt er det bare én bokstav igjen som kan stå på den siste plassen. Det er med andre ord  321=6  forskjellige måter å stille opp de tre bokstavene på.

Tenk nå at vi skal sette opp de fem bokstavene a, b, c, d og f i alle mulige rekkefølger. Hvor mange måter kan vi gjøre dette på?

Det er fem forskjellige bokstaver å velge mellom på den første plassen, deretter fire, så tre osv. Derfor er det 54321=120 forskjellige rekkefølger vi kan sette sammen bokstavene i. Eller kanskje lettere å huske: Fem forskjellige bokstaver kan vi plasseres i 12345 forskjellige rekkefølger.

Vi generaliserer dette, og tenker oss at vi har et uspesifisert antall bokstaver eller andre objekter. Da vil vi finne 123...n mulige rekkefølger, eller permutasjoner av disse. Altså: Vi ganger alle tallene fra 1 til n med hverandre, der n er et eller annet naturlig tall. Det finnes et eget symbol for dette produktet. Vi skriver det n!. Utropstegnet leses fakultet, så n! leses ”n fakultet”.

n!=123...n.

Permutasjoner med klasser av like objekter


I eksemplene over er objektene som sorteres, forskjellige. Hva om vi prøver å telle opp alle kombinasjoner av bokstavene i ordet PAPPA? Her er det tre P-er og to A-er. Dersom vi later som om de tre P-ene er forskjellige fra hverandre, og det samme for de to A-ene, skal vi ordne fem forskjellige bokstaver på vanlig måte. Da er antall muligheter:

5!=12345=120.

Altså 120 forskjellige kombinasjoner av bokstaver. Men mange av disse er jo like, for hvis vi for eksempel bytter om på to P-er eller to A-er, endrer ikke det på ordet. Tenk for eksempel på PAAPP som ett av de mulige ordene. Vi må finne ut hvor mange ganger vi kan vi permutere P-er og A-er her uten at ordet endres. De tre P-ene kan permuteres på 3! = 6 forskjellige måter. For hver av de seks kombinasjonene av P-er, kan vi permutere de to A-ene på 2! = 2 forskjellige måter. Det betyr at antallet 120 er 3!2!=62=12 ganger for stort. Vi har med andre ord telt hver av kombinasjonene 12 ganger. Det vil si at antallet permutasjoner vi har til sammen, dersom vi tenker på P-ene og A-ene som innbyrdes like, er 12 ganger for stort. Derfor må vi dele antallet kombinasjoner på 12, for å få riktig antall forskjellige ordkombinasjoner. Resultatet blir at antall måter å organisere bokstavene i ordet PAPPA er:

5!3!2!=12012=10.   

Vi kan altså lage 10 forskjellige ord av bokstavene i ordet PAPPA. Prøv å finne dem og skrive dem opp!

Generelt, hvis vi har en mengde med totalt n objekter, og k1,k2,...,km er antallene like objekter i mengden, er antall ulike mulige kombinasjoner av disse n objektene

n!k1!k2!...km!

Det var 3 P-er og 2 A-er i PAPPA, og da fikk vi i nevneren 3! ganget med 2!. Så da var k-ene henholdsvis lik 3 og 2, og n=5 og m=2, for tilfellet PAPPA.

Eksempel 2


I et billøp er det 9 deltakende biler: 4 er av merket Porsche, 3 Ferrari og 2 Jaguar. Hvor mange rekkefølger kan det bli på resultatlistene når vi bare tenker på bilmerkene? Vi setter inn i formelen:

Antall permutasjoner  9!4!3!2!=123456789123412312=1260.

Det er altså 1260 mulige rekkefølger av resultater mellom disse tre bilmerkene, fordelt på denne måten mellom 9 biler.

Publisert: 01.04.2008 Endret: 30.09.2015