permutasjon

En permutasjon er en ordnet liste av elementer hentet fra en gitt mengde. Ofte brukes begrepet når man ordner alle elementene i mengden, slik at rekkefølgen er viktig. I matematisk sammenheng kobles permutasjoner til symmetriske grupper og til telling av ordnede kombinasjoner.

For en mengde med n distinkte elementer er antallet mulige permutasjoner n!, altså n fakultet. For eksempel gir bokstavene A, B og C seks ulike ordninger: ABC, ACB, BAC, BCA, CAB og CBA. Når man tar ut r elementer fra en mengde på n elementer og rekkefølgen teller, kalles det en permutasjon uten tilbakelegg og antallet er P(n, r) = n!/(n−r)!.

Hvis tilbakelegg er tillatt, dvs. hvert posisjonsvalg kan gjentas uavhengig i de r posisjonene, blir antallet permutasjoner n^r. For eksempel kan hver av tre posisjoner i en tresifret kode velges blant n alternativer, noe som gir n^3 kombinasjoner.

I rund eller sirkulær ordning må man ofte ta hensyn til rotasjoner som ikke utgjør en ny permutasjon. Da er antallet distinct circular permutations for n distinkte elementer (n−1)!, siden alle rotasjoner av samme orden anses like.

Hvis elementene ikke er helt forskjellige (noen like), reduseres antallet permutasjoner ved å dele på multiplikasjonene av fakultetene til like elementer. Dette kalles multiset-permutasjoner og følger formelen n!/(m1! m2! … mk!), der mi er antallet forekomster av hvert like element.

Permutasjoner brukes i telling, kryptering, ordning av data, og i problemer knyttet til arrangement og valg der rekkefølgen er betydningsfull.