Permutation
- För den juridiska termen, se Permutation (juridik).
Inom matematiken används termen permutation i flera besläktade betydelser, nämligen som en funktion, en omordning, eller som ett urval.
Olika betydelser
[redigera | redigera wikitext]Den vanligaste betydelsen är att en permutation av mängden M är en bijektiv funktion från M till sig själv. Mängden av permutationer på M bildar en grupp med operatorn funktionssammansättning, vilken kallas den symmetriska gruppen på M. Begreppet permutation används i denna betydelse allmänt inom de flesta grenar av matematiken, bland annat inom sannolikhetsteori, algebra och talteori.
Antalet olika permutationer av en mängd innehållande n stycken element är n!, där och utläses "n-fakultet". Detta kan förklaras med att det för det första elementet, finns n möjliga alternativ. För nästa element finns n-1 element kvar att välja mellan, för det tredje elementet n-2 element, och så vidare till och med det sista elementet, där således inga andra alternativ finns.
Mängden kan alltså permuteras på 3! = 6 sätt: abc, acb, bac, bca, cab, cba.
Om man ur en mängd med n element skulle välja ut r av dessa och sedan permutera urvalet, finns det permutationer av dessa. För detta har man infört skrivsätten P(n, r), och .
Detta gäller självklart också i specialfallet n = r, eftersom , vilket gäller eftersom är en tom produkt, som per definition är lika med 1.
Ibland används i stället termen permutation för att beteckna en omordning av en ordnad uppsättning element. Med detta synsätt är exempelvis (1,4,2,3) en permutation av (1,2,3,4). Detta ligger mycket nära uppfattningen av en permutation som en bijektion; exemplet motsvaras av
Den "naturliga" sammansättningen av omordningar är dock inte densamma som funktionssammansättningen. Uppfattar man permutationer som omordningar, så låter man därför oftast fg betyda g°f i stället för f°g.
Slutligen används också ibland permutation som synonym till ordnat urval utan upprepning av element i en mängd. Ofta kontrasteras då permutationer mot oordnade urval utan upprepning, som då kan kallas kombinationer. De förra tar alltså hänsyn till i vilken ordning elementen i urvalet kommer. abc och bca är således i denna mening inte samma permutation, men samma kombination, ur mängden {a,b,c,d,e}.
I resten av denna artikel kommer permutation främst att användas i den förstnämnda betydelsen.
Notation, produkter och inverser av permutationer
[redigera | redigera wikitext]En permutation
Man kan även ange permutationer på enradsform, då man bara ger den nedre raden.
Inom gruppteori behandlas ofta permutationer av mängden X = {1, 2, ..., n} då man ofta använder cykelnotation, där man börjar med 1, sedan
- .
Dock är inte alla permutationer en stor cykel utan flera mindre, då man skriver (tvåradsform respektive cykelnotation):
En produkt av två permutationer
Cykelstruktur, jämna och udda permutationer
[redigera | redigera wikitext]En permutation
och resten av elementen i 1, 2, ..., n är fixpunkter till
Två permutationer är disjunkta om varje element som flyttas av den ena permutationen är fixpunkt till den andra. Disjunkta permutationer kommuterar och alla permutationer är en produkt av disjunkta cykler, cykler själva är en produkt med en faktor. En fullständig faktorisering av en permutation är en faktorisering av permutationen i disjunkta cykler, inklusive cykler av längd 1 för element som fixeras av permutationen.[1].
Om en permutation
Varje permutation kan även skrivas som en produkt av transpositioner (inte nödvändigtvis disjunkta). En permutation kallas jämn respektive udda om den är en produkt av ett jämnt respektive udda antal transpositioner.
Fixpunkter och banor
[redigera | redigera wikitext]Låt
Om
Oavsett om x är en fixpunkt eller inte, så är ju
där Z är mängden av heltal. Mängden av alla banor (med avseende på den givna permutationen) utgör en partition av M.
Stabilisator
[redigera | redigera wikitext]Alla permutationer som avbildar x på sig själv sägs tillhöra stabilisatorn för x.
Referenser
[redigera | redigera wikitext]- Rotman, Joseph (1995). An Introduction to the Theory of Groups. Springer Verlag. ISBN 0-387-94285-8
- https://web.archive.org/web/20140201194043/http://www.mittag-leffler.se/pdf/specialarbeten/lindstr2.pdf
Noter
[redigera | redigera wikitext]- ^ Rotman, sid. 6