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.

En av inversionerna i en permutation

Definitioner

Permutationen (4,1,5,2,6,3) har inversionsvektorn ([0,]1,0,2,0,3) och inversionsmängden {(1,2),(1,4),(3,4),(1,6),(3,6),(5,6)}. I triangeln visas de möjliga paren så att elementet med den lägre positionen (1-5) representeras av en kolumn, och det med den högre (2-6) av en rad. Elementen i inversionsmängden utgörs av de rödmarkerade paren i triangeln och antalet par längs en diagonal ger elementen i inversionsvektorn. Inversionsvektorn kan unikt uttryckas som 373 i ett decimalt faktoriellt numreringssystem.

Inversionsmängden för permutationen
(0,15, 14,1, 13,2, 3,12,
11,4, 5,10, 6,9, 8,7)
uppvisar mönstret för
Thue–Morse-sekvensen

Låt $A=(A(1),\ldots ,A(n))$ vara en följd av $n$ distinkta tal. Om $i<j$ och $A(i)>A(j)$ så utgör paret $(i,j)$ en inversion i $A$.

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 ${\text{inv}}(A)=|\{(A(i),A(j))\mid i<j{\text{ och }}A(i)>A(j)\}|$, 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 $V[i]=\left\vert \{k\mid k<i{\text{ och }}A(k)>A(i)\}\right\vert$. 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

Cayleygrafen av ordning 4. Den ordnade sekvensen (1,2,3,4) återfinns längst ner, genom translokationer av konsekutiva (intilliggande) element kan vi klättra runt längs kanterna och nå det största elementet (4,3,2,1) längst upp. Färgerna markerar vilka intilliggande tal vi translokerar.

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

• Margolius, Barbara H. (2001). ”Permutations with Inversions”. Journal of Integer Sequences 4. 

Mått på sorteringsgrad

• Mannila, Heikki (1984). ”Measures of presortedness and optimal sorting algorithms”. Lecture Notes in Computer Science 172: sid. 324–336. doi:10.1007/3-540-13345-3_29. 
• Estivill-Castro, Vladimir; Wood, Derick (1989). ”A new measure of presortedness”. Information and Computation 83 (1): sid. 111–119. doi:10.1016/0890-5401(89)90050-3. 
• Skiena, Steven S. (1988). ”Encroaching lists as a measure of presortedness”. BIT 28 (4): sid. 755–784. doi:10.1007/bf01954897.