Inversión (matemáticas discretas)

Dejar${\displaystyle \pi }$sea ​​una permutación . Hay una inversión de${\displaystyle \pi }$entre${\displaystyle i}$y${\displaystyle j}$si${\displaystyle i<j}$y${\displaystyle \pi (i)>\pi (j)}$La inversión se indica mediante un par ordenado que contiene cualquiera de los lugares .${\displaystyle (i,j)}$^{[ 1 ] [ 2 ]} o los elementos${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$. ^{[ 3 ] [ 4 ] [ 5 ]}

El conjunto de inversión es el conjunto de todas las inversiones. El conjunto de inversión de una permutación que utiliza notación basada en la posición es el mismo que el conjunto de inversión de la permutación inversa que utiliza notación basada en los elementos, con los dos componentes de cada par ordenado intercambiados. De igual modo, el conjunto de inversión de una permutación que utiliza notación basada en los elementos es el mismo que el conjunto de inversión de la permutación inversa que utiliza notación basada en la posición, con los dos componentes de cada par ordenado intercambiados. ^{[ 6 ]}

Las inversiones se definen generalmente para permutaciones, pero también pueden definirse para secuencias: Sea${\displaystyle S}$ser una secuencia (o permutación de multiconjuntos ^{[ 7 ]} ). Si${\displaystyle i<j}$y${\displaystyle S(i)>S(j)}$ya sea el par de lugares${\displaystyle (i,j)}$^{[ 7 ] [ 8 ]} o el par de elementos${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$^{[ 9 ]} se denomina una inversión de${\displaystyle S}$.

En el caso de las secuencias, las inversiones según la definición basada en elementos no son únicas, ya que diferentes pares de posiciones pueden tener el mismo par de valores.

El número de inversión${\displaystyle {\mathtt {inv}}(X)}$^{[ 10 ]} de una secuencia${\displaystyle X=\langle x_{1},\dots,x_{n}\rangle }$, es la cardinalidad del conjunto de inversión. Es una medida común de ordenamiento (a veces llamada preordenamiento) de una permutación ^{[ 5 ]} o secuencia. ^{[ 9 ]} El número de inversión está entre 0 y${\displaystyle {\frac {n(n-1)}{2}}}$inclusivo. Una permutación y su inversa tienen el mismo número de inversión.

Por ejemplo${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots,n\rangle )=0}$ya que la secuencia está ordenada. Además, cuando${\displaystyle n=2m}$es par,${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}}$(porque cada par${\displaystyle (1\leq i\leq m<j\leq 2m)}$es una inversión). Este último ejemplo muestra que un conjunto que intuitivamente está "casi ordenado" aún puede tener un número cuadrático de inversiones.

El número de inversión es el número de cruces en el diagrama de flechas de la permutación, ^{[ 6 ]} la distancia tau de Kendall de la permutación con respecto a la permutación identidad y la suma de cada uno de los vectores relacionados con la inversión definidos a continuación.

Otras medidas de ordenamiento incluyen el número mínimo de elementos que se pueden eliminar de la secuencia para obtener una secuencia completamente ordenada, el número y la longitud de las "rachas" ordenadas dentro de la secuencia, la regla de Spearman (suma de las distancias de cada elemento a su posición ordenada) y el número mínimo de intercambios necesarios para ordenar la secuencia. ^{[ 11 ]} Los algoritmos de ordenamiento por comparación estándar se pueden adaptar para calcular el número de inversión en tiempo O( n log n ) . ^{[ 12 ]}

Se utilizan tres vectores similares que condensan las inversiones de una permutación en un vector que la determina de forma única. A menudo se les denomina vector de inversión o código de Lehmer . ( Aquí se puede encontrar una lista de fuentes ).

Este artículo utiliza el término vector de inversión (${\displaystyle v}$) como Wolfram . ^{[ 13 ]} Los dos vectores restantes a veces se denominan vector de inversión izquierda y derecha , pero para evitar confusiones con el vector de inversión, este artículo los denomina recuento de inversión izquierda (${\displaystyle l}$) y recuento de inversión derecha (${\displaystyle r}$). Interpretado como un número factorial , el recuento de inversión izquierda da las permutaciones colexicográficas inversas, ^{[ 14 ]} y el recuento de inversión derecha da el índice lexicográfico.

Vector de inversión${\displaystyle v}$: Con la definición basada en elementos${\displaystyle v(i)}$es el número de inversiones cuyo componente menor (derecho) es${\displaystyle i}$. ^{[ 3 ]}

${\displaystyle v(i)}$es el número de elementos en${\displaystyle \pi }$más que${\displaystyle i}$antes${\displaystyle i}$.

${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}}$

Recuento de inversión izquierda${\displaystyle l}$: Con la definición basada en el lugar${\displaystyle l(i)}$es el número de inversiones cuyo componente mayor (derecho) es${\displaystyle i}$.

${\displaystyle l(i)}$es el número de elementos en${\displaystyle \pi }$más que${\displaystyle \pi (i)}$antes${\displaystyle \pi (i)}$.

${\displaystyle l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}}$

Recuento de inversión derecha${\displaystyle r}$, a menudo llamado código Lehmer : Con la definición basada en el lugar${\displaystyle r(i)}$es el número de inversiones cuyo componente más pequeño (izquierdo) es${\displaystyle i}$.

${\displaystyle r(i)}$es el número de elementos en${\displaystyle \pi }$más pequeño que${\displaystyle \pi (i)}$después${\displaystyle \pi (i)}$.

${\displaystyle r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}}$

Ambos${\displaystyle v}$y${\displaystyle r}$Se puede encontrar con la ayuda de un diagrama de Rothe , que es una matriz de permutación donde los 1 están representados por puntos y hay una inversión (a menudo representada por una cruz) en cada posición que tiene un punto a su derecha y debajo.${\displaystyle r(i)}$es la suma de las inversiones en la fila${\displaystyle i}$del diagrama de Rothe, mientras que${\displaystyle v(i)}$es la suma de las inversiones en la columna${\displaystyle i}$. La matriz de permutación de la inversa es la transpuesta , por lo tanto${\displaystyle v}$de una permutación es${\displaystyle r}$de su inverso, y viceversa.