Permutation
Der er for få eller ingen kildehenvisninger i denne artikel, hvilket er et problem. Du kan hjælpe ved at angive troværdige kilder til de påstande, som fremføres i artiklen.
Inden for matematikken er en permutation en (typisk specificeret) ombytning af rækkefølgen af en række elementer (teknisk set en bijektiv afbildning af en ordnet mængde på sig selv). Ordet permutation anvendes også om resultatet af en ombytning; man taler således både om at "A er en permutation af B" og at "A fremkommer ved anvendelse af permutationen P på B".
Som eksempel på permutation kan man tænke på et spil kort. Blander man kortene, står man med de samme kort i en anden rækkefølge. Et andet eksempel er anagrammer, der er permutationer af et ord eller en sætning. 15-spillet består af en række permutationer, idet hvert enkelt deltrin er en ombytning af den tomme plads med en af dens nabobrikker.
Permutationer anvendes bl.a. inden for kombinatorik og kryptografiske algoritmer, hvor permutation af tegn eller tegngrupper sammen med substitution spiller en afgørende rolle i sidstnævnte.
Operationer og specielle permutationer
[redigér | rediger kildetekst]Den permutation der afbilder alle elementer på sig selv kaldes enhedspermutationen, den identiske permutation, eller identitetspermutationen, og reserveres normal symbolet I. Om end denne ikke umiddelbart kan synes vigtig nok til at få sit eget navn, er den vigtig som reference.
Kombinationen af to permutationer er i sig selv en permutation; man taler om "produktet" af to permutationer. Til enhver permutation P kan man desuden finde en permutation P-1 der, når den kombineres P giver enhedspermutationen I. P-1 kaldes P's omvendte permutation eller inverse permutation. Man kan tænke på dette som "division", altså det omvendte af "multiplikation".
Et specialtilfælde af permutationer er cykliske permutationer. En cyklisk permutation er en permutation hvor alle elementer rykkes et antal pladser frem eller tilbage i rækkefølgen. De elementer der derved "skubbes ud" af rækken flyttes til starten, hhv. slutningen. Kombinationen af to cykliske permutationer er selv en cyklisk permutation.
Permutationer kan deles i lige og ulige permutationer. En lige permutation er en permutation af en mængde der kan fremkomme ved et lige antal ombytninger af to elementer (transpositioner). Tilsvarende er en ulige permutation en der fremkommer ved et ulige antal ombytninger. Enhver permutation er enten lige eller ulige, men kan ikke være begge dele.