Inversión (matemáticas discretas)

Par de posiciones en una secuencia donde dos elementos están fuera de orden

Permutación con una de sus inversiones resaltada. Una inversión puede denotarse por el par de lugares (2, 4) o el par de elementos (5, 2). Las inversiones de esta permutación que utilizan la notación basada en elementos son: (3, 1), (3, 2), (5, 1), (5, 2) y (5, 4).

En informática y matemáticas discretas , una inversión en una secuencia es un par de elementos que están fuera de su orden natural .

Definiciones

Inversión

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

El conjunto de inversión es el conjunto de todas las inversiones. El conjunto de inversión de una permutación que utiliza una notación basada en el lugar es el mismo que el conjunto de inversión de la permutación inversa que utiliza una notación basada en los elementos con los dos componentes de cada par ordenado intercambiados. De la misma manera, el conjunto de inversión de una permutación que utiliza una notación basada en los elementos es el mismo que el conjunto de inversión de la permutación inversa que utiliza una notación basada en el lugar 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 una secuencia (o permutación multiconjunto ^[7] ). Si y , el par de lugares ^{[7] [8]} o el par de elementos ^[9] se denomina inversión de . ${\displaystyle S}$ ${\displaystyle i<j}$ ${\displaystyle S(i)>S(j)}$ ${\displaystyle (i,j)}$ ${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$ ${\displaystyle S}$

Para las secuencias, las inversiones según la definición basada en elementos no son únicas, porque diferentes pares de lugares pueden tener el mismo par de valores.

Número de inversión

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

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

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 desde 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 ordenación 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 las longitudes de las "ejecuciones" ordenadas dentro de la secuencia, la regla de Spearman (suma de las distancias de cada elemento desde su posición ordenada) y el número más pequeño de intercambios necesarios para ordenar la secuencia. ^{[11] Los algoritmos} de ordenación por comparación estándar se pueden adaptar para calcular el número de inversión en el tiempo O( n log n ) . ^[12]

Vectores relacionados con la inversión

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 los denomina vector de inversión o código de Lehmer . (Aquí se encuentra una lista de fuentes).

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

Diagrama de Rothe

Vector de inversión : ${\displaystyle v}$
con la definición basada en elementos , es el número de inversiones cuyo componente más pequeño (derecho) es . ^[3] ${\displaystyle v(i)}$ ${\displaystyle i}$

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

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

Recuento de inversiones a la izquierda : ${\displaystyle l}$
con la definición basada en el lugar , es el número de inversiones cuyo componente más grande (derecho) es . ${\displaystyle l(i)}$ ${\displaystyle i}$

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

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

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

${\displaystyle r(i)}$es el número de elementos en menor que después de . ${\displaystyle \pi }$ ${\displaystyle \pi (i)}$ ${\displaystyle \pi (i)}$

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

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

Ejemplo: Todas las permutaciones de cuatro elementos

Las seis posibles inversiones de una permutación de 4 elementos

La siguiente tabla ordenable muestra las 24 permutaciones de cuatro elementos (en la columna) con sus conjuntos de inversión basados ​​en el lugar (en la columna pb), vectores relacionados con la inversión (en las columnas , y ) y números de inversión (en la columna #). (Las columnas con letra más pequeña y sin encabezado son reflejos de las columnas que se encuentran junto a ellas y se pueden usar para ordenarlas en orden colexicográfico ). ${\displaystyle \pi }$ ${\displaystyle v}$ ${\displaystyle l}$ ${\displaystyle r}$

Se puede observar que y siempre tienen los mismos dígitos, y que y ambos están relacionados con el conjunto de inversión basado en el lugar. Los elementos no triviales de son las sumas de las diagonales descendentes del triángulo mostrado, y los de son las sumas de las diagonales ascendentes. (Los pares en diagonales descendentes tienen los componentes derechos 2, 3, 4 en común, mientras que los pares en diagonales ascendentes tienen los componentes izquierdos 1, 2, 3 en común). ${\displaystyle v}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle l}$ ${\displaystyle r}$

El orden predeterminado de la tabla es el orden colex inverso por , que es el mismo que el orden colex por . El orden lex por es el mismo que el orden lex por . ${\displaystyle \pi }$ ${\displaystyle l}$ ${\displaystyle \pi }$ ${\displaystyle r}$

Orden débil de permutaciones

Permutoedro del grupo simétrico S ₄

Al conjunto de permutaciones de n elementos se le puede dar la estructura de un orden parcial , llamado orden débil de permutaciones , que forma una red .

El diagrama de Hasse de los conjuntos de inversión ordenados por la relación de subconjunto forma el esqueleto de un permutoedro .

Si se asigna una permutación a cada conjunto de inversión utilizando la definición basada en el lugar, el orden de permutaciones resultante es el del permutoedro, donde una arista corresponde al intercambio de dos elementos con valores consecutivos. Este es el orden débil de permutaciones. La identidad es su mínimo y la permutación formada al invertir la identidad es su máximo.

Si se asignara una permutación a cada conjunto de inversión utilizando la definición basada en elementos, el orden resultante de las permutaciones sería el de un grafo de Cayley , donde una arista corresponde al intercambio de dos elementos en lugares consecutivos. Este grafo de Cayley del grupo simétrico es similar a su permutoedro, pero con cada permutación reemplazada por su inverso.

Véase también

• Sistema de numeración factorial
• Gráfico de permutación
• Transposiciones, transposiciones simples, inversiones y clasificación.
• Distancia Damerau-Levenshtein
• Paridad de una permutación

Secuencias en la OEIS :

• Secuencias relacionadas con la representación de la base factorial
• Números factoriales: A007623 y A108731
• Números de inversión: A034968
• Conjuntos de inversión de permutaciones finitas interpretadas como números binarios: A211362 (permutación relacionada: A211363)
• Permutaciones finitas que solo tienen 0 y 1 en sus vectores de inversión: A059590 (sus conjuntos de inversión: A211364)
• Número de permutaciones de n elementos con k inversiones; números mahonianos: A008302 (sus máximos de fila; números de Kendall-Mann: A000140)
• Número de gráficos etiquetados conectados con n aristas y n nodos: A057500

Referencias

1. Aigner 2007, págs. 27.
2. Comtet 1974, págs. 237.
3. Knuth 1973, págs. 11.
4. Pemmaraju y Skiena 2003, págs.69.
5. Vitter y Flajolet 1990, págs.459.
6. Gratzer 2016, págs. 221.
7. Bóna 2012, págs. 57.
8. Cormen et al. 2001, págs. 39.
9. Barth y Mutzel 2004, págs. 183.
10. Mannila 1985.
11. Mahmoud 2000, págs. 284.
12. Kleinberg y Tardos 2005, págs.225.
13. Weisstein, Eric W. "Vector de inversión" de MathWorld --Un recurso web de Wolfram
14. Orden colex inverso de permutaciones finitarias (secuencia A055089 en la OEIS )

Bibliografía de fuentes

• Aigner, Martin (2007). "Representación de palabras". Un curso de enumeración . Berlín, Nueva York: Springer. ISBN 978-3642072536.
• Barth, Wilhelm; Mutzel, Petra (2004). "Conteo cruzado de dos capas simple y eficiente". Revista de algoritmos y aplicaciones de grafos . 8 (2): 179–194. doi : 10.7155/jgaa.00088 .
• Bóna, Miklós (2012). "2.2 Inversiones en permutaciones de multiconjuntos". Combinatoria de permutaciones . Boca Ratón, FL: CRC Press. ISBN 978-1439850510.
• Comtet, Louis (1974). "6.4 Inversiones de una permutación de [n]". Combinatoria avanzada; el arte de las expansiones finitas e infinitas. Dordrecht, Boston: D. Reidel Pub. Co. ISBN 9027704414.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-53196-8.
• Gratzer, George (2016). "7-2 Objetos básicos". Teoría de retículos. Temas especiales y aplicaciones . Cham, Suiza: Birkhäuser. ISBN 978-3319442358.
• Kleinberg, Jon; Tardos, Éva (2005). Diseño de algoritmos . ISBN 0-321-29535-8.
• Knuth, Donald (1973). "5.1.1 Inversiones". El arte de la programación informática . Addison-Wesley Pub. Co. ISBN 0201896850.
• Mahmoud, Hosam Mahmoud (2000). "Ordenación de datos no aleatorios". Ordenación: una teoría de distribución . Serie Wiley-Interscience sobre matemáticas discretas y optimización. Vol. 54. Wiley-IEEE. ISBN 978-0-471-32710-3.
• Pemmaraju, Sriram V.; Skiena, Steven S. (2003). "Permutaciones y combinaciones". Matemáticas computacionales discretas: combinatoria y teoría de grafos con Mathematica . Cambridge University Press. ISBN 978-0-521-80686-2.
• Vitter, JS; Flajolet, Ph. (1990). "Análisis de casos promedio de algoritmos y estructuras de datos". En van Leeuwen, Jan (ed.). Algoritmos y complejidad . Vol. 1 (2.ª ed.). Elsevier. ISBN 978-0-444-88071-0.

Lectura adicional

• Margolius, Barbara H. (2001). "Permutaciones con inversiones". Journal of Integer Sequences . 4 .

Medidas de preclasificación

• Mannila, Heikki (abril de 1985). "Medidas de clasificación previa y algoritmos de ordenamiento óptimos". IEEE Transactions on Computers . C-34 (4): 318–325. doi :10.1109/tc.1985.5009382.
• Estivill-Castro, Vladimir; Wood, Derick (1989). "Una nueva medida de clasificación previa". Información y Computación . 83 (1): 111–119. doi : 10.1016/0890-5401(89)90050-3 .
• Skiena, Steven S. (1988). "Listas invasivas como medida de clasificación previa". BIT . 28 (4): 755–784. doi :10.1007/bf01954897. S2CID  33967672.