Permutationer

En permutation er et specialtilfælde af ordnet udvælgelse, hvor vi har en mængde af størrelse n og vil finde antallet af alle forskellige n-tupler.

Formel

Lad os først repetere ordnet udvælgelse. Lad os have mængden af cifre {1, 2, 3, 4, 5}. Hvor mange trecifrede tal kan vi sammensætte af dem, hvis intet ciffer må gentages? Det er et typisk eksempel på ordnet udvælgelse, som kan løses med den kendte formel

$$P(n,r)=\frac{n!}{(n-r)!}=\frac{5!}{(5-3)!}=60.$$

Hvor mange femcifrede tal kunne vi sammensætte?

$$P(n,r)=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

Vi kan bemærke, at hvis vi har en mængde med fem elementer og søger antallet af alle forskellige femtupler, er resultatet lig med 5!. Det kan vi generalisere og sige, at hvis vi har en mængde med n elementer, findes der i alt n! forskellige n-tupler. Dermed er vi nået frem til begrebet permutation.

Hvad er en permutation

Hvis vi har en mængde M af størrelse n, så er en permutation et vilkårligt n-tupel sammensat af elementer fra mængden M, hvor intet element må gentages. Eksempel: hvis vi har mængden M = {a, b, c, d}, så er en permutation fx (a, b, d, c) eller (d, b, a, c). Antallet af alle forskellige permutationer er lig med

$$P(n)=P(n,n)=n!$$

Løste eksempler

1. Du har i alt seks bøger og vil stille dem på en hylde i en eller anden rækkefølge. Hvor mange forskellige rækkefølger findes der? Vi har seks bøger, vi permuterer altid alle bøgerne, så resultatet er lig med P(6) = 6! = 720.

2. Til dine 6 danske bøger fra det forrige eksempel er der kommet 4 bøger skrevet på latin. Hvor mange forskellige måder kan du stille de 10 bøger på hylden, hvis du vil have alle de danske bøger samlet og alle de latinske bøger samlet?

   Hvilke muligheder har vi for at stille bøgerne? Vi kan først stille de seks danske bøger og derefter de fire latinske eller omvendt — først de fire latinske og så de seks danske. Samtidig gælder, at der er 6! måder at stille de danske bøger på og 4! måder at stille de latinske bøger på. Vi bruger multiplikationsprincippet og ganger disse resultater: 6! · 4! = 17.280. Fordi der er to muligheder for, hvordan bøgerne kan stå (danske, så latinske og omvendt), skal vi gange tallet med to. Det samlede resultat er 17.280 · 2 = 34.560.