Permutasjoner

Spør vi oss hvor mange måter vi kan organisere tallene 1 og 2 på, er det lett å innse at svaret er to. Vi kan ha sekvensene 1-2 og 2-1. Men tar vi med tallet 3 også, blir det mer komplisert. Vi kan ha 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 og 3-2-1. Totalt seks sekvenser. Tar vi også med tallet 4, kan vi ha 24 sekvenser. Slike sekvenser kalles permutasjoner.

Fakultet

Antallet forskjellige permutasjoner er lett å beregne. La oss si at vi har tre elementer. Da kan tre elementer velges til å stå først, blant de gjenstående kan to velges til å stå som nummer to, og så er det bare ett element igjen som kan stå sist. Totalt 3 · 2 · 1 = 6 sekvenser. Med fire elementer får vi 4 · 3 · 2 · 1 = 24 sekvenser. Generelt, med n elementer, får vi n · (n−1) · (n−2) · … · 1 sekvenser.

Produktet n · (n−1) · (n−2) · … · 1 har et eget navn, fakultet, og betegnes med et utropstegn:

$\fbox{Fakultet: $n! = n \cdot (n−1) \cdot (n−2) \cdot \; \dots \; \cdot 1$}$

Her er n et positivt heltall. Det er også definert at

$\fbox{$0! = 1$}$

Vi skal senere se hvorfor dette er nyttig.

Eksempel 1:

Vi skal beregne 5! og får 5 · 4 · 3 · 2 · 1 = 120.

Eksempel 2:

Vi har en klasse med 20 elever, og skal beregne hvor mange forskjellige måter de kan sette seg ved pultene på. Første elev kan velge blant 20 pulter, andre blant 19, og så videre, så totalt blir det 20! ≈ 2,4 · 10¹⁸ muligheter. Et enormt tall. Hvis elevene byttet plass hvert 5. sekund døgnet rundt, ville det ta nesten 400 milliarder år å komme gjennom alle variantene.

Vi skjønner at n! blir et stort tall, selv for lave n. 59! ≈ 1,4 · 10⁸⁰ er for eksempel et tall større enn antall atomer i det observerbare universet.

Det er sjelden vi beregner fakultetet for hånd. Litt avanserte kalkulatorer og dataprogrammer har egne funksjoner for dette. I Excel bruker vi funksjonen fakultet, for eksempel skriver vi =fakultet(10) for å beregne 10!. I GeoGebra skriver vi bare et tall med et utropstegn etter i inntastingsfeltet eller CAS. For eksempel 10!.

På grunn av de store tallene er det begrenset hvor høye fakulteter dataprogrammer kan beregne. Excel og GeoGebra stopper på 170!. En del kalkulatorer stopper på 69!, fordi høyere fakulteter er større enn 10¹⁰⁰, og kalkulatorene bare kan vise eksponenter med maksimalt to sifre.

Oppgave 1:

En skoleklasse på 30 elever stiller opp på rekke. Hvor mange måter kan rekka organiseres på? Bruk kalkulator eller dataprogram til beregningen.

Se løsningsforslag

k-permutasjoner av n

Det finnes altså n! mulige sekvenser med n elementer, for eksempel 5! = 120. Men hva om vi ikke vil ha med alle elementene, og spør om hvor mange sekvenser vi kan lage av k av totalt n elementer? Det er ikke så vanskelig å resonnere seg fram til. Første element kan velges på n måter, andre element på n−1 måter, tredje element på n−2 måter, og så videre til vi har tatt med k elementer, altså n · (n−1) · (n−2) · … · (n−k+1).

Slike sekvenser kaller vi k-permutasjoner av n.

Eksempel 3:

Vi vil lage sekvenser med 4 elementer fra en mengde på 10. Her er n = 10 og k = 4. Så antall sekvenser blir
n · (n−1) · (n−2) · … · (n−k+1) = 10 · (10−1) · (10−2) · (10−3) = 10 · 9 · 8 · 7 = 5040.

Det finnes 5040 mulige sekvenser med 4 av 10 elementer på. Antall 4-permutasjoner av 10 er altså 5040.

Excel har en egen funksjon, permuter, til å beregne antall k-permutasjoner, der permuter(n; k) gir antall k-permutasjoner av n. Vi skriver for eksempel =permuter(10; 4) for å gjøre beregningen i eksempel 3. I GeoGebra skriver vi nPr(n, k) i inntastingsfeltet eller CAS. Vi skriver for eksempel nPr(10, 4) for å gjøre beregningen i eksempel 3.

Men har vi ikke Excel eller GeoGebra tilgjengelig, vil det være arbeidskrevende å utføre multiplikasjonene én for én. Vi skal derfor regne om uttrykket n · (n−1) · (n−2) · … · (n−k+1) ved hjelp av et lite regnetriks, og multipliserer med en brøk med (n − k)!, det vil si (n − k) · (n − k − 1) · (n − k − 2) · … · 1 i teller og nevner:

$n \cdot (n − 1) \cdot (n − 2) \cdot \; \dots \; \cdot (n − k + 1) =$

$n \cdot (n − 1) \cdot (n − 2) \cdot \; \dots \; \cdot (n − k + 1) \cdot \frac{\displaystyle (n − k) \cdot (n − k − 1) \cdot (n − k − 2) \cdot \; \dots \; \cdot 1}{\displaystyle (n − k) \cdot (n − k − 1) \cdot (n − k − 2) \cdot \; \dots \; \cdot 1} =$

$\frac{\displaystyle n \cdot (n − 1) \cdot (n − 2) \cdot \; \dots \; \cdot 1}{\displaystyle (n − k) \cdot (n − k − 1) \cdot (n − k − 2) \cdot \; \dots \; \cdot 1} =$

$\frac{\displaystyle n!}{\displaystyle (n − k)!}$

Her har vi kommet fram til en form som bare involverer fakulteter, og derfor enkelt kan beregnes på en kalkulator med fakultetsfunksjon.

Vi har altså:

$\fbox{Antall $k$-permutasjoner av $n$: $\frac{\displaystyle n!}{\displaystyle (n − k)!}$}$

Eksempel 4:

Vi skal finne antall 2-permutasjoner av 3, det vil si hvor mange sekvenser av to elementer vi kan lage av totalt tre. Vi bruker formelen over, og får ${\large \frac{3!}{(3 − 2)!}} = {\large \frac{6}{1}} = 6$.
Med så få elementer kan vi kontrollere dette ved å telle permutasjonene. La oss si at de 3 elementene heter a, b og c. Da kan vi lage sekvensene a–b, a–c, b–a, b–c, c–a og c–b. Totalt 6 stykker, slik vi kom fram til ved hjelp av formelen.

Oppgave 2:

Beregn antall 4-permutasjoner av 10 ved å bruke formelen for antall k-permutasjoner av n. Gjør også utregningen i Excel og GeoGebra.

​Se løsningsforslag

​Eksempel 5:

Vi skal finne antall 5-permutasjoner av 5. Vi bruker formelen for antall k-permutasjoner av n, og får ${\large \frac{5!}{(5 − 5)!}} = {\large \frac{5!}{0!}} = {\large \frac{120}{1}} = 120$.

Her fikk vi 0! = 1 i nevneren. Hadde vi ikke hatt spesialdefinisjonen av 0!, ville vi ikke kunnet bruke formelen i dette tilfellet.

Men utregningen er tungvint, for en n-permutasjon av n betyr bare n!, så vi kunne nøyd oss med å regne ut 5! = 120.

​​Eksempel 6:

Vi skal finne antall 0-permutasjoner av n. Vi bruker formelen for antall k-permutasjoner av n, og får ${\large \frac{n!}{(n − 0)!}} = {\large \frac{n!}{n!}} = 1$.

Vi kan altså lage én sekvens med 0 elementer uavhengig av hvor mange elementer vi har til rådighet totalt.

Se filmen «Permutasjoner»
 

Kilder

• • Hinna, K.R.C., Rinvold, R.A., Gustavsen, TS. (2011). QED 5-10, bind 1. Høyskoleforlaget
  • Hagen, Per C. (2000). Innføring i sannsynlighetsregning og statistikk. Cappelen akademisk
  • Birkeland, P.A., Breiteig, B., Venheim, R. (2012). Matematikk for lærere 2. Universitetsforlaget