Utente:Grasso Luigi/sandbox4/Inversione

In informatica e matematica discreta, il termine inversione in una successione è una coppia di elementi che non sono nel loro ordine naturale.

Consideriamo una permutazione nella notazione 1-linea

${\displaystyle \pi \ =\ \pi (1)\pi (2)\cdots \pi (i)\cdots \pi (j)\cdots \pi (n)}$

dell'insieme ${\displaystyle X\ =\ \{1,2,\cdots ,i\cdots ,j\cdots ,n\}}$. Diciamo inversione di ${\displaystyle \pi }$ tra ${\displaystyle i}$ e ${\displaystyle j}$ se ${\displaystyle i<j}$ e ${\displaystyle \pi (i)>\pi (j)}$. L'inversione viene denotata o dalla coppia delle due posizioni ${\displaystyle (i,j)}$^[1][2] o dalla coppia degli elementi ${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$.^[3][4][5]

Dicesi insieme inversione l'insieme di tutte le inversioni e si denota ${\displaystyle \operatorname {inv} (\pi )}$. Quindi in notazione posizione-elementi si ha:

${\displaystyle \operatorname {inv} (\pi )=\{\ (i,j)\ \mid \pi (i)>\pi (j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi \in S_{n}\}}$

o in maniera equivalente nella notazione valore-elementi:

${\displaystyle \operatorname {inv} (\pi )=\{\ (\pi (i),\pi (j))\ \mid \pi (i)>\pi (j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi \in S_{n}\}}$

Nel caso di notazione posizione-elemento di una permutazione l'insieme è uguale a quello della permutazione inversa con la notazione valore-elemento con la coppia di elementi scambiata, cioè ${\displaystyle (\pi ^{-1}(j),\ \pi ^{-1}(i))}$:

${\displaystyle {\begin{aligned}\operatorname {inv} (\pi )&=\{\ (i,j)\ \mid \pi (i)>\pi (j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi \in S_{n}\}\\&=\{\ (\pi ^{-1}(j),\pi ^{-1}(i))\ \mid \pi ^{-1}(i)>\pi ^{-1}(j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi ^{-1}\in S_{n}\}\\\end{aligned}}}$

Allo stesso modo, l'insieme inversione di una permutazione usando la notazione valore-elemento è uguale a quello della permutazione inversa con la notazione posizione-elemento con i due indici scambiati, quindi ${\displaystyle (j,\ i)}$.^[6]

${\displaystyle {\begin{aligned}\operatorname {inv} (\pi )&=\{\ (\pi (i),\pi (j))\ \mid \pi (i)>\pi (j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi \in S_{n}\}\\&=\{\ (j,i)\ \mid \pi ^{-1}(i)>\pi ^{-1}(j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi ^{-1}\in S_{n}\}\\\end{aligned}}}$

per cui, noto l'insieme inversione di una permutazione, è facile trovare quello della sua inversa in notazione posizione-elemento:

${\displaystyle \operatorname {inv} (\pi ^{-1})\ =\ \{\ (\pi (j),\pi (i))\ \mid \pi (i)>\pi (j),\quad i=1,\ldots ,n\quad j=i+1,\dots ,n;\ \pi \in S_{n}\}}$

Le inversioni di solito si definiscono per le permutazioni, ma possono anche definirsi per le successioni:
Sia ${\displaystyle S}$ una successione (o permutazione multiinsieme^[7]). Se ${\displaystyle i<j}$ e ${\displaystyle S(i)>S(j)}$, sia la coppia delle posizioni ${\displaystyle (i,j)}$^[8][9] o la coppia di elementi ${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$^[10] viene detta inversione di ${\displaystyle S}$.

Per le successioni, la definizione d'inversione usando gli elementi non è unica, infatti differenti coppie di posizioni possono avere la stessa coppia di valori.

Il numero inversione con notazione ${\displaystyle {\mathtt {inv}}(X)}$^[11] di una successione di numeri

${\displaystyle X\ =\ \langle x_{1},x_{2},\dots ,x_{n}\rangle }$

rappresenta la cardinalità dell'insieme inversione. È una misura comune dell'ordinamento (a volte chiamato preordinamento) di una permutazione^[12] o successione.^[13] Il campo di valori è:

${\displaystyle 0\leqslant {\mathtt {inv}}(X)\leqslant {\frac {n(n-1)}{2}}}$.

Nel caso di permutazioni si usa pure il simbolo ${\displaystyle |\operatorname {inv} (\pi )|}$, inoltre una permutazione e la sua inversa hanno lo stesso numero inversione, cioè:

${\displaystyle |\operatorname {inv} (\pi )|\ =\ |\operatorname {inv} (\pi ^{-1})|}$

Ad esempio ${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0}$ in quanto la successione è ordinata. Inoltre, quando ${\displaystyle n=2m}$ cioè un numero pari, ${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}}$ (infatti ogni coppia ${\displaystyle (1\leq i\leq m<j\leq 2m)}$ è un'inversione). Quest'ultimo esempio mostra che un insieme intuitivamente quasi ordinato può ancora avere un numero quadratico di inversioni.

Il numero di inversione è il numero di incroci nel diagramma a freccia di una permutazione,^[14] oppure è la distanza tau di Kendall della permutazione da quella identica (${\displaystyle \pi _{I}=123\cdots n}$) ed è anche la somma di ciascuno dei vettori correlati all'inversione definiti di seguito.

Altre misure di ordinamento includono il numero minimo di elementi che possono essere eliminati dalla sequenza per produrre una sequenza completamente ordinata, the number and lengths of sorted "runs" within the sequence, the Spearman footrule (somma delle distanze di ogni elemento dalla sua posizione ordinata), ed è il più piccolo numero di scambi necessari per avere una successione ordinata.Template:Sfn Gli algoritmi di ordinamento comparativi standard si possono adattare per calcolare il numero di inversione nel tempo ${\displaystyle O(n\ log\ n)}$.^[15]

Consideriamo una permutazione nella notazione 1-linea e utilizziamo due indici diversi ${\displaystyle i,\ j}$ per la posizione

${\displaystyle \pi \ =\ \pi (1)\pi (2)\cdots \pi (i)\cdots \pi (j)\cdots \pi (n)}$

e la sua inversa nella stessa notazione

${\displaystyle \pi ^{-1}\ =\ \pi ^{-1}(1)\pi ^{-1}(2)\cdots \pi ^{-1}(i)\cdots \pi ^{-1}(j)\cdots \pi ^{-1}(n)}$.

Possiamo associare dei vettori tra loro analoghi per rappresentare le inversioni di una permutazione in insiemi di componenti che le determinano univocamente. Viene usato il termine vettore inversione seguito da un modo specifico di operare nel calcolo delle possibili inversioni. (A list of sources is found here.)

In questa definizione usiamo i seguenti termini

vettore inversione destro dell'inversa ${\displaystyle \mathbf {v} \ =\ \operatorname {I} (\pi ^{-1})}$

vettore inversione sinistro dell'inversa ${\displaystyle \mathbf {v'} \ =\ \operatorname {I'} (\pi ^{-1})}$.

vettore inversione sinistro ${\displaystyle \mathbf {l} \ =\ \operatorname {L'} (\pi )}$

vettore inversione destro o vettore di Lehmer ${\displaystyle \mathbf {r} \ =\ \operatorname {L} (\pi )}$.

dove i simboli ${\displaystyle \mathbf {v} ,\mathbf {v'} ,\mathbf {l} ,\mathbf {r} }$ sono utilizzati dal programma Mathematica nel linguaggio Wolfram.^[16] Se ogni componente del vettore viene interpretata come un numero in base fattoriale allora il conteggio delle inversioni a sinistra fornisce l'indice colessicografico inverso (rev-Colex) ,^[17] e il conteggio delle inversioni a destra fornisce l'indice lessicografico (Lex).

Vettori inversione destro, sinistro di π^-1: v, v'

Definiamo il vettore inversione destro nella notazione vettoriale e nella notazione fattoriale

${\displaystyle \mathbf {v} \ =\ \operatorname {I} (\pi ^{-1})\ =\ (\ 0,\ I_{2},\cdots ,\ I_{i},\cdots ,I_{n}\ )\ =\ {I_{n}I_{n-1}\cdots I_{i}\cdots I_{2}\ 0}_{(!)}}$

e prima componente sempre nulla. Nella definizione della componente ${\displaystyle I_{i}}$ indichiamo il numero d'inversioni il cui componente più piccolo è nella posizione ${\displaystyle i}$.Template:Sfn. Per il suo calcolo occorre trovare il numero di elementi ${\displaystyle \pi ^{-1}(j)}$ in ${\displaystyle \pi }$ che stanno a destra di ${\displaystyle \pi ^{-1}(i)}$ e sono minori di esso. In notazioni equivalenti:

${\displaystyle \mathbf {v_{i}} \ =\ I_{i}(\pi ^{-1})~~=~~\#\left\{j\mid i<j~\land ~\pi ^{-1}(i)>\pi ^{-1}(j)\right\}\ =\ |\left\{(i,j)\mid i<j~\land ~\pi ^{-1}(i)>\pi ^{-1}(j),\quad i=1,2,\ldots ,n\quad j=i+1,i+2,\ldots ,n\right\}|}$

analogamente possiamo definire il vettore sinistro nelle due notazioni viste prima

${\displaystyle \mathbf {v'} \ =\ \operatorname {I'} (\pi ^{-1})\ =\ (\ 0,\ I'_{2},\ \cdots ,\ I'_{j},\cdots ,I'_{n}\ )\ =\ {0\ I'_{2}\cdots I'_{j}\cdots I'_{n-1}I'_{n}}_{(!)}}$

e prima componente nulla. Il calcolo delle sue componenti:

${\displaystyle \mathbf {v'_{j}} \ =\ I'_{j}(\pi ^{-1})~~=~~\#\{i\mid i<j~\land ~\pi ^{-1}(i)>\pi ^{-1}(j)\}=|\{(i,j)\mid i<j~\land ~\pi ^{-1}(i)>\pi ^{-1}(j),\quad j=1,2,\ldots ,n\quad i=1,2,\ldots ,j-1\}|}$

Vettore inversione sinistro, destro di π: l, r

Definiamo il vettore inversione sinistro nella notazione vettoriale e nella notazione fattoriale

${\displaystyle \mathbf {l} \ =\ \operatorname {L'} (\pi )\ =\ (\ L'_{1},\ L'_{2},\ \cdots ,\ L'_{j},\cdots ,L'_{n}\ )\ =\ {0\ L'_{2}\cdots L'_{j}\cdots L'_{n-1}L'_{n}}_{(!)}}$

la prima componente è sempre nulla. In notazione posizionale ${\displaystyle l_{j}\ =\ L'_{j}(\pi )}$ indica il numero d'inversioni la cui componente più grande (a destra) è ${\displaystyle j}$. Per il suo calcolo fissiamo un elemento ${\displaystyle \pi (j)}$, e contiamo il numero elementi del tipo ${\displaystyle \pi (i)}$ maggiori di ${\displaystyle \pi (j)}$ che stanno a sinistra di quello fissato ${\displaystyle \pi (j)}$. In notazioni equivalenti:

${\displaystyle \mathbf {l_{j}} \ =\ L'_{j}(\pi )~~=~~\#\left\{i\mid i<j~\land ~\pi (i)>\pi (j)\right\}\ =\ |\left\{(i,j)\mid i<j~\land ~\pi (i)>\pi (j),\quad j=1,2,\ldots ,n\quad i=1,2,\ldots ,j-1\right\}|}$

e definiamo il vettore inversione destro nelle due solite notazioni

${\displaystyle \mathbf {r} \ =\ \operatorname {L} (\pi )\ =\ (\ L_{1},\ L_{2},\ \cdots ,\ L_{i},\cdots ,L_{n}\ )\ =\ {L_{n}L_{n-1}\cdots L_{i}\cdots L_{2}\ 0}_{(!)}}$

con prima componente nulla e spesso detto codice di Lehmer. Definiamo in notazione posizionale ${\displaystyle r_{i}\ =\ L_{i}(\pi )}$ come il numero d'inversioni la cui componente più piccola (sinistra) è ${\displaystyle i}$. Per il suo calcolo fissiamo un elemento ${\displaystyle \pi (i)}$, e contiamo il numero elementi del tipo ${\displaystyle \pi (j)}$ minori di ${\displaystyle \pi (i)}$ che stanno a destra di quello fissato ${\displaystyle \pi (i)}$. In notazioni equivalenti:

${\displaystyle \mathbf {r_{i}} \ =\ L_{i}(\pi )~~=~~\#\left\{j\mid i<j~\land ~\pi (i)>\pi (j)\right\}\ =\ |\left\{(i,j)\mid i<j~\land ~\pi (i)>\pi (j),\quad i=1,2,\ldots ,n\quad j=i+1,i+2,\ldots ,n\right\}|}$

Sia ${\displaystyle v=\operatorname {I} (\pi ^{-1})}$ che ${\displaystyle r=\operatorname {L} (\pi )}$ si possono rappresentare con il diagramma di Rothe, cioè una matrice di permutazione con gli elementi ${\displaystyle (i,\ \pi (i))}$ rappresentati da puntini, e un'inversione (spesso indicata con una crocetta), utilizzando le definizioni viste, in ogni posizione ${\displaystyle (i,\ \pi (j))}$ quando si effettua il calcolo del vettore inversione destro di ${\displaystyle \pi }$ detto anche vettore codice Lehmer, in questo caso le colonne rappresentano i valori ${\displaystyle \pi (j)}$. Il valore di ${\displaystyle r_{i}\ =\ L_{i}(\pi )}$ si ottiene come somma delle inversioni della ${\displaystyle i}$-esima riga del diagramma, mentre ${\displaystyle v_{i}\ =\ I_{i}(\pi ^{-1})}$ si ottiene come somma delle inversioni nella ${\displaystyle i}$-esima colonna. Il diagramma della permutazione inversa si ottiene per trasposizione, per cui ${\displaystyle v}$ di una permutazione diventa ${\displaystyle r}$ della sua inversa, e viceversa.

Infine è da notare che esistono delle relazioni tra i vettori d'inversione destri e quelli sinistri. Conoscendo i vettori L, L' si ottengono I',I tramite ${\displaystyle \pi ^{-1}}$:

${\displaystyle \operatorname {L} (\pi )=(\ L_{1},\cdots ,\ L_{j},\cdots ,L_{n})\quad \operatorname {L'} (\pi )=(\ L'_{1},\cdots ,\ L'_{j},\cdots ,L'_{n}\ )\longrightarrow \operatorname {I'} (\pi ^{-1})=(\ 0,L_{\pi ^{-1}(2)},\cdots ,L_{\pi ^{-1}(n)}\ )\quad \operatorname {I} (\pi ^{-1})=(\ L'_{\pi ^{-1}(1)},L'_{\pi ^{-1}(2)},\cdots ,\ L'_{\pi ^{-1}(n-1)},0\ )}$

o in forma indiciale

${\displaystyle {\begin{aligned}\operatorname {I'} _{i}&=\operatorname {L} _{j=\pi ^{-1}(i)};&&\operatorname {I'} _{1}=0&&0\leqslant \operatorname {I'} _{i}<i&i=1,2\ldots ,n\\\operatorname {I} _{i}&=\operatorname {L'} _{j=\pi ^{-1}(i)};&&\operatorname {I} _{n}=0&&0\leqslant \operatorname {I} _{i}\leqslant n-i&i=1,2\ldots ,n\\\end{aligned}}}$

oppure dai vettori I, I' si ottengono L', L tramite ${\displaystyle \pi }$:

${\displaystyle \operatorname {I} (\pi ^{-1})=(\ I_{1},\cdots ,\ I_{i},\cdots ,I_{n}\ )\quad \operatorname {I'} (\pi ^{-1})=(\ I'_{1},\cdots ,\ I'_{i},\cdots ,I'_{n}\ )\longrightarrow \operatorname {L'} (\pi )=(\ 0,L'_{\pi (2)},\cdots ,L'_{\pi (n)}\ )\quad \operatorname {L} (\pi )=(\ L_{\pi (1)},L_{\pi (2)},\cdots ,\ L_{\pi (n-1)},0\ )}$

ad esempio dalla permutazione π=254631 si ha:

${\displaystyle \operatorname {L} (\pi )=(1,3,2,2,1,0)\quad \operatorname {L'} (\pi )=(0,0,1,0,3,5)\longrightarrow \operatorname {I'} (\pi )=(L_{6},L_{1},L_{5},L_{3},L_{2},L_{4})=(0,1,1,2,3,2)\quad \operatorname {I} (\pi )=(L'_{6},L'_{1},L'_{5},L'_{3},L'_{2},L'_{4})=(5,0,3,1,0,0)}$

Consideriamo la seguente permutazione di 6 elementi:

${\displaystyle S_{6}\ni \pi ={\begin{pmatrix}1&2&3&4&5&6\\2&5&4&6&3&1\\\end{pmatrix}}=(125346)=254631=(612534)}$

che ammette inversa

${\displaystyle S_{6}\ni \pi ^{-1}={\begin{pmatrix}1&2&3&4&5&6\\6&1&5&3&2&4\\\end{pmatrix}}=(643521)=615324}$

Possiamo calcolare i vettori d'inversione per il diagramma di Rothe accanto

Le tabelle ordinabili mostrano le 6 permutazioni di tre elementi e le 24 permutazioni di 4 elementi con le colonne seguenti:

1. ${\displaystyle \operatorname {L} (\pi )_{(10)}}$: il valore in base 10 del vettore inversione destro di ${\displaystyle \pi }$ o vettore di Lehmer. Le permutazioni involutive (${\textstyle \pi =\pi ^{-1}}$) sono contraddistinte con il colore verde.
2. ${\displaystyle M_{\pi }}$: visualizza la matrice di permutazione associata.
3. ${\displaystyle \pi _{1-l}}$: la permutazione in notazione 1-linea.
4. p-b (cioè place-based): rappresentazione in un triangolo formato dal numero ${\displaystyle |\operatorname {inv} (\pi )|}$ di coppie (i,j) nella notazione posizionale dell'insieme d'inversione.
5. ${\displaystyle \operatorname {I} (\pi )_{(!)}}$: vettore inversione destro della permutazione inversa ${\displaystyle \pi _{1-l}^{-1}}$.
6. ${\displaystyle \operatorname {L} (\pi )_{(!)}}$: vettore inversione destro della permutazione ${\displaystyle \pi _{1-l}}$.
7. ${\displaystyle |\operatorname {inv} (\pi )|}$ oppure ${\displaystyle \operatorname {\#} }$: numero d'inversioni. Da notare che ${\textstyle \sum _{i=1}^{n}\operatorname {I} _{i}=\sum _{i=1}^{n}\operatorname {L} _{i}=|\operatorname {inv} (\pi )|}$. Inoltre le inversioni dispari (numeri in nero) hanno segno della permutazione ${\textstyle \epsilon (\pi )=-1}$ e quelle pari (numeri in rosso) hanno segno +1.

Le componenti dei vettori inversione destri nel sistema numerico fattoriale sono espressi con le cifre in colore rosso con quella meno significativa opaca, ad esempio

${\displaystyle \operatorname {L} (\pi )\ =}$ 1000
	indica nel sistema numerico fattoriale
${\displaystyle \operatorname {L} (\pi )_{(10)}=1\ 3!\ +0\ 2!\ +0\ 1!\ +0\ 0!}$

Proprietà

• I vettori inversione sx e dx di ${\displaystyle \pi }$ sono in relazione con l'insieme d'inversione che è contenuto nell'insieme delle possibili coppie rappresentate da un triangolo p-b (place-based). I valori non nulli del vettore inversione sinistro ${\displaystyle \operatorname {L'} (\pi )_{(!)}=0L'_{2}\cdots L'_{j}\cdots L'_{n}}$ sono le somme delle coppie delle diagonali discendenti o principali del triangolo p-b, mentre quelle del vettore inversione destro ${\displaystyle \operatorname {L} (\pi )_{(!)}=L_{n}L_{n-1}\cdots L_{i}\cdots 0}$ sono le somme delle coppie delle diagonali ascendenti o secondarie. (Dalla figura accanto per n=4, le coppie nelle diagonali discendenti hanno in comune la posizione j=2,3,4; mentre le coppie nelle diagonali ascendenti hanno in comune la componente i=1,2,3.)
• I vettori inversione ${\displaystyle v}$ ed ${\displaystyle l}$ hanno le stesse cifre, lo stesso per ${\displaystyle v'}$ ed ${\displaystyle r}$. Ad esempio per n=3 si ha:

  ${\displaystyle \pi }$	v	r	v'	l
  123	000	000	000	000
  213	100	100	010	010
  132	010	010	001	001
  312	110	200	002	011
  231	200	110	011	002
  321	210	210	012	012
• L'ordine rev-colex di ${\displaystyle \pi }$, è lo stesso come l'ordine colex del vettore ${\displaystyle l}$. L'ordine lex di ${\displaystyle \pi }$ è lo stesso ordine per il vettore ${\displaystyle r}$. L'ordine colex si ottiene da quello lex per inversione delle singole sequenze 1-linea. Ad esempio per n=3 si ha:

  ${\displaystyle 123{\overset {~~\operatorname {lex} }{<}}\ 132<213<231<312<321\qquad 321{\overset {~~\operatorname {colex} }{<}}\ 231<312<132<213<123}$

  infine se invertiamo l'ordine otteniamo rev-lex e rev-colex, cioè

  ${\displaystyle 321{\overset {~~\operatorname {rev-lex} }{<}}\ 312<231<213<132<123\qquad 123{\overset {~~\operatorname {rev-colex} }{<}}\ 213<132<312<231<321}$

  per i vettori inversione nell'ordine lex di ${\displaystyle \pi }$ si hanno

  ${\displaystyle \operatorname {L} (\pi )_{(!)}:\quad 000{\overset {~~\operatorname {lex} }{<}}\ 010<100<110<200<210}$

  ${\displaystyle \operatorname {I} (\pi ^{-1})_{(!)}:\quad 000{\overset {~~\operatorname {lex} }{<}}\ 010<100<200<110<210}$

  e invertendo le singole sequenze si ottiene

  ${\displaystyle \operatorname {L'} (\pi )_{(!)}:\quad 000{\overset {~~\operatorname {colex} }{<}}\ 010<001<011<002<012}$

  ${\displaystyle \operatorname {I'} (\pi ^{-1})_{(!)}:\quad 000{\overset {~~\operatorname {colex} }{<}}\ 010<001<002<011<012}$

  che corrispondono ai vettori inversione nell'ordine rev-colex di ${\displaystyle \pi }$.

Il gruppo simmetrico n=3 ammette 4 elementi simmetrici (celle verdi prima colonna).

Il gruppo simmetrico n=4 ammette 10 elementi simmetrici.

The set of permutations on n items can be given the structure of a partial order, called the weak order of permutations, which forms a lattice.

The Hasse diagram of the inversion sets ordered by the subset relation forms the skeleton of a permutohedron.

If a permutation is assigned to each inversion set using the place-based definition, the resulting order of permutations is that of the permutohedron, where an edge corresponds to the swapping of two elements with consecutive values. This is the weak order of permutations. The identity is its minimum, and the permutation formed by reversing the identity is its maximum.

If a permutation were assigned to each inversion set using the element-based definition, the resulting order of permutations would be that of a Cayley graph, where an edge corresponds to the swapping of two elements on consecutive places. This Cayley graph of the symmetric group is similar to its permutohedron, but with each permutation replaced by its inverse.

• (EN) Aigner Martin, Word Representation, in A course in enumeration, Berlin, New York, Springer, 2007, DOI:978-3642072536Controllare il valore del parametro doi (aiuto).
• (EN) Wilhelm Barth; Petra Mutzel, Simple and Efficient Bilayer Cross Counting, in J. Graph Algorithms Appl., vol. 8, n. 2, 2004, pp. 179–194, DOI:10.7155/jgaa.00088.
• (EN) Bóna Miklós, 2.2 Inversions in Permutations of Multisets, in Boca Raton, FL, CRC Press, 2012, ISBN 978-1439850510.
• (EN) Comtet Louis, 6.4 Inversions of a permutation of [n], in Advanced combinatorics; the art of finite and infinite expansions, Dordrecht, Boston, D. Reidel Pub. Co, 1974, ISBN 9027704414.
• (EN) Thomas H. Cormen; Charles E. Leiserson; Rivest Ronald L.; Clifford Stein, Introduzione agli algoritmi, 2ª ed., MIT Press and McGraw-Hill, 2001, ISBN 0-262-53196-8.
• (EN) George Grätzer, 7-2 Basic objects, in Lattice theory. special topics and applications, Cham, Switzerland, Birkhäuser, 2016, ISBN 978-3319442358.
• (EN) Kleinberg Jon; Tardos Éva, Algorithm Design, 1ª ed., Londra, UK, Pearson, 2005, ISBN 0-321-29535-8.
• (EN) Knuth Donald, 5.1.1 Inversions, in The Art of Computer Programming, Addison-Wesley Pub. Co, 1973, ISBN 0201896850.
• (EN) Hosam M. Mahmoud, Sorting Nonrandom Data, in Sorting: a distribution theory, Wiley-Interscience series in discrete mathematics and optimization Vol.54, Wiley-IEEE, 2000.
• (EN) Sriram V. Pemmaraju; Steven S. Skiena, Permutations and combinations, in Computational discrete mathematics: combinatorics and graph theory with Mathematica, CUP, 2003, ISBN 978-0-521-80686-2.
• (EN) J.S. Vitter; Ph. Flajolet; Jan van Leeuwen, Average-Case Analysis of Algorithms and Data Structures, in Algorithms and Complexity, 2ª ed., Elsevier, 1990, ISBN 978-0-444-88071-0.

• (EN) Barbara H. Margolius, Permutations with Inversions, in J. Integer Seq., vol. 4, n. 2, 2001, pp. Art. 01.2.4, p.13.
• (EN) Heikki Mannila, Measures of presortedness and optimal sorting algorithms, in IEEE Trans. Comput., C-34, n. 4, 1985, pp. 318–325, DOI:10.1109/tc.1985.5009382.
• (EN) Vladimir Estivill-Castro; Derick Wood, A new measure of presortedness, in Inf. Comput., vol. 83, n. 1, 1989, pp. 111–119, DOI:10.1016/0890-5401(89)90050-3.
• (EN) Steven S. Skiena, Encroaching lists as a measure of presortedness, in BIT Numer. Math., vol. 28, n. 4, 1988, pp. 755–784, DOI:10.1007/bf01954897.

Template:'''wikiversity'''

• Sistema numerico fattoriale
• Permutation graph
• Transpositions, simple transpositions, inversions and sorting
• Damerau–Levenshtein distance
• Parità di una permutazione

Successioni di OEIS:

• Successioni relative al sistema numerico fattoriale
• Numeri fattoriali: A007623, A108731
• Numeri inversioni: A034968
• Insiemi inversioni come numeri binari: A211362   (permutazioni correlate: A211363)
• Permutazioni che hanno solo 0 e 1 nei vettori inversioni: A059590   (insiemi inversioni: A211364)
• Numero permutazioni di n elementi con k inversioni; numeri Mahoniani: A008302   (massimi per riga o numeri Kendall-Mann: A000140)
• Numero di grafi connessi con n archi ed n nodi: A057500