permutasjon

Generelt gjelder at n forskjellige objekter kan permuteres på n! (n-fakultet), ulike måter, det vil si 1·2·3·4···(n–1)·n måter.

Hvis to av elementene er like, vil det være likegyldig i hvilken orden disse to elementene opptrer, og antallet av permutasjoner må divideres på 2. Hvis α av elementene er like, må man dividere med α!.

Generelt er det slik at hvis de n elementene faller i grupper av like elementer med α, β, .... elementer i hver gruppe, så er antallet av permutasjoner lik \[\frac{n!}{\alpha!\beta!\dotsc}\]

Spesielt kan nevnes at mengden av alle permutasjoner av n elementer danner en gruppe; den kalles den symmetriske gruppe av orden n, betegnes S_n og har n! elementer.

De ti bokstavene i ordet Hammerfest kan ombyttes på \(\frac{10!}{2!2!} = 907200\) måter.

Når elementene a, b, c, d ved en permutasjon ordnes til rekkefølgen c, d, a, b, så skrives det ofte i formen av en substitusjon \(\begin{pmatrix}a & b & c & d \\ c & d & a & b\end{pmatrix}\) hvor nedre linje angir hva det tilsvarende element i første linje skal erstattes med. Når én permutasjon anvendes først, og deretter en annen på den nye ordningen, så er resultatet også en permutasjon som kalles produktet av de to permutasjonene.

Blant de mange spesielle permutasjoner kan nevnes de sykliske permutasjonene, også kalt sirkelpermutasjoner. Her erstattes i rekken a, b, ..., n hvert element med det følgende og det siste med det første i sirkelorden.

• kombinatorikk
• algebra