En permutation i kombinatorik är en ordnad mängd utan upprepningar av siffror , vanligtvis behandlad som en bijektion på mängden , som associerar numret med det -th elementet från mängden. Numret kallas permutationens längd [1] .
I gruppteorin betyder en permutation av en godtycklig mängd en bijektion av denna uppsättning på sig själv. Som en synonym för ordet "permutation" i denna mening använder vissa författare ordet substitution . (Andra författare kallar substitution för ett visuellt sätt att skriva en permutation. Den större skillnaden är att en substitution är en funktion i sig, medan en permutation är resultatet av att den funktionen appliceras på elementen i en sekvens.)
Termen "permutation" uppstod eftersom föremål först togs, på något sätt arrangerades, och andra sätt att ordna krävde omarrangering av dessa föremål. [2] .
En permutation är en uppsättning som består av samma antal element, som bara skiljer sig i ordningen på elementen. [3]
Antalet alla permutationer av element är lika med antalet placeringar av by , det vill säga den faktoriella [4] [5] [6] [7] :
.Sammansättning definierar produktens funktion på permutationer av samma längd: Med avseende på denna operation bildar uppsättningen av permutationer av element en grupp , som kallas symmetrisk och vanligtvis betecknas .
Varje ändlig grupp av element är isomorf till någon undergrupp av den symmetriska gruppen ( Cayleys teorem ). I det här fallet är varje element associerat med en permutation som definieras på elementen av identiteten där är en gruppoperation i .
Bäraren för en permutation är en delmängd av den uppsättningsom definieras som
En fast punkt i en permutationär vilken fast punkt som helst i mappningen, det vill säga ett element i mängdenUppsättningen av alla fasta punkter i en permutationär komplementet till dess bärare i.
En inversion i en permutationär vilket par av indexså attoch. Pariteten för antalet inversioner i en permutation bestämmer permutationens paritet .
En permutation av en uppsättning kan skrivas som en substitution , till exempel:
var och .
Varje permutation kan sönderdelas till en produkt ( sammansättning ) av osammanhängande cykler av längd , och på ett unikt sätt upp till ordningen av cyklerna i produkten. Till exempel:
Det antas också ofta att de fasta punkterna för en permutation är oberoende cykler av längd 1, och de kompletterar permutationens cykelexpansion med dem. För exemplet ovan skulle en sådan utökad sönderdelning vara . Antalet cykler av olika längd, nämligen uppsättningen av siffror , där är antalet cykler av längd , bestämmer permutationens cykliska struktur . I det här fallet är värdet lika med längden på permutationen och värdet är lika med det totala antalet cykler. Antalet permutationer av element med cykler ges av det osignerade stirlingtalet av det första slaget .
Vilken cykel som helst kan brytas ned till en produkt av (inte nödvändigtvis osammanhängande) transpositioner . I det här fallet kan en cykel av längd 1 (som i huvudsak är en identisk permutation ) representeras som en tom produkt av transpositioner eller, till exempel, som en kvadrat av vilken transponering som helst: En längdcykel kan dekomponeras till en produkt av införlivningar enligt följande:
Det bör noteras att nedbrytningen av cykler till en produkt av transponeringar inte är unik:
Således kan vilken permutation som helst brytas upp till en produkt av transponeringar. Även om detta kan göras på många sätt, är pariteten för antalet transpositioner densamma i alla sådana nedbrytningar. Detta gör att tecknet för en permutation ( permutationsparitet eller permutationssignatur ) kan definieras som:
var är antalet införlivningar i någon expansion av . I det här fallet kallar de en jämn permutation om , och en udda permutation om .
På motsvarande sätt bestäms tecknet för en permutation av dess cykelstruktur: tecknet för en permutation av element, bestående av cykler, är lika med
.Tecknet på permutationen kan också bestämmas i termer av antalet inversioner i :
.Betrakta element av olika typer, och i varje typ är alla element desamma. Sedan kallas permutationerna av alla dessa element, upp till ordningen av samma typ av element, permutationer med upprepning . Om är antalet element av den e typen, då är antalet möjliga permutationer med upprepningar lika med den multinomiala koefficienten
En permutation med upprepningar kan också ses som en kardinalitet multiset permutation .
En slumpmässig permutation är en slumpmässig vektor, vars alla element tar naturliga värden från 1 till och sannolikheten för att två element matchar är 0.
En oberoende slumpmässig permutation är en sådan slumpmässig permutation , för vilken:
för vissa sådana att:
Om samtidigt inte är beroende av , då kallas permutationen jämnt fördelad . Om det inte finns något beroende av , det vill säga det kallas homogen .