Inversion (kombinatorik)

Inom kombinatorik avser en inversion ett par av element i en sekvens som står i omvänd naturlig ordning. En inversion kan också beskrivas som en omkastning av den inbördes ordningen för ett par av element vid en permutation.

Definitioner

Låt  vara en följd av  distinkta tal. Om  och  så utgör paret  en inversion i .
Exempel: I sekvensen A=(1,2,4,3,5), om den naturliga ordningen är (1,2,3,4,5), utgör paret (3,4) den enda inversionen (det är det enda paret där det "större" elementet står längre till vänster än det "lägre"), medan i B=(1,2,4,5,3) finns två inversioner: (3,4) och (3,5).

Inversionsmängden för en sekvens är mängden av inversioner i sekvensen. I sekvensen B i exemplet ovan är inversionsmängden alltså {(3,4), (3,5)}.

Inversionstalet för en sekvens är ett vanligt mått på hur välsorterad den är. Formellt definieras inversionstalet som antalet inversioner i sekvensen, det vill säga , eller inversionsmängdens kardinalitet. Inversionstalet anger hur många transpositioner av intilliggande element som en permutation motsvarar, så om inversionstalet är jämnt är permutationens paritet jämn, är det udda är pariteten udda. 

Inversionsvektorn V(i) för sekvensen definieras för i = 2,  , ..., n som . Detta innebär att vektorns element anger hur många "större" element som "står före" motsvarande element i sekvensen. Observera att en sekvens inversionsvektor ofta anges med ett element mindre än sekvensen, eftersom inga element kan stå före det första (vektorns första element skulle i så fall alltid vara noll, och kan således strykas). Varje permutation har en unik inversionsvektor och det är möjligt att konstruera varje given permutation utifrån (den fullt sorterade) sekvensen och permutationens inversionsvektor.

Exempel: Inversionsvektorn för exempelmängden B ovan är (0,0,0,2) eller (0,0,0,0,2), eftersom 3 är det enda tal som har större tal till vänster om sig (och två stycken sådana), medan C=(2,5,4,1,3) har inversionvektorn ([0],0,1,3,2). Från sekvensen (1,2,3,4,5) och inversionsvektorn kan C återskapas: Sista talet i vektorn är två, vilket innebär att det sista talet i sekvensen skall ha två tal som är större till vänster om sig, alltså är det sista talet en trea eftersom det finns två tal som är större än tre (och alla tal måste ju stå till vänster om det sista). Näst sista talet skall ha tre större tal, och räknar vi bakifrån bland den sorterade sekvensens kvarvarande tal (5-4-2-1) finner vi att det näst sista i vår permutation är en etta. Tredje talet skall ha ett tal som är större till vänster (alltså fem), vilket innebär att tredje talet bakifrån är fyra. Sedan följer det största kvarvarande talet, d.v.s. fem, eftersom vektorns element är en nolla. Återstår nu bara tvåan, som skall stå först.

En partiell ordning för permutationer

Mängden av permutationer av n element kan ges en partiell ordning som bildar ett gitter.

För att skapa denna "ordning", anta att elementen som skall permuteras är talen från 1 till n och låt Inv(u) beteckna inversionsmängden för permutationen u på den naturliga ordningen för elementen. Det vill säga att Inv(u) är mängden ordnade par (i,j) sådana att 1 ≤ i < j ≤ n och u(i) > u(j). Vi definierar u ≤ v för två permutationer närhelst Inv(u) ⊆ Inv(v).

Kanterna på ett Hassediagram över den partiella ordningen ges av permutationerna u och v så att u < v och så att v erhålles från u genom att byta plats på två konsekutiva element i u. Dessa kanter bildar en Cayleygraf för permutationsgruppen som är isomorf med en permutoeders skelett.

Identitetspermutationen än ordningens minsta element och den inversa ordingen dess största.

Referenser

Vidare läsning

Mått på sorteringsgrad 
 
 
 

Kombinatorik
Permutationer