Inversión (matemáticas discretas) - Inversion (discrete mathematics)

Permutación con una de sus inversiones resaltada

Se puede denotar por el par de lugares (2, 4) o el par de elementos (5, 2).

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 . Si y , el par de lugares o el par de elementos se llama inversión de . ${\ Displaystyle \ pi}$${\ Displaystyle i <j}$${\ Displaystyle \ pi (i)> \ pi (j)}$${\ Displaystyle (i, j)}$${\ Displaystyle {\ bigl (} \ pi (i), \ pi (j) {\ bigr)}}$${\ Displaystyle \ pi}$

La inversión generalmente se define para permutaciones, pero también puede definirse para secuencias:
Sea una secuencia (o permutación de múltiples conjuntos ). Si y , el par de lugares o el par de elementos se llama 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 de acuerdo con la definición basada en elementos no son únicas, porque diferentes pares de lugares pueden tener el mismo par de valores.

El conjunto de inversión es el conjunto de todas las inversiones. El conjunto de inversión de una permutación de acuerdo con la definición basada en el lugar es el del conjunto de inversión de la permutación inversa de acuerdo con la definición basada en elementos, y viceversa, solo con los elementos de los pares intercambiados.

Número de inversión

El número de inversión de una secuencia es la cardinalidad del conjunto de inversión. Es una medida común de (pre) ordenación de una permutación o secuencia. Este valor está comprendido entre 0 e incluido. ${\ 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. Además, como cada pareja es una inversión. Este último ejemplo muestra que un tipo que se ordena intuitivamente todavía puede tener un número cuadrático de inversiones. ${\ displaystyle {\ mathtt {inv}} (\ langle 1,2, \ dots, n \ rangle) = 0}$${\ Displaystyle {\ mathtt {inv}} (\ langle n + 1, n + 2, \ dots, 2n, 1,2, \ dots, n \ rangle) = n ^ {2}}$${\ Displaystyle (1 \ leq i \ leq n <j \ leq 2n)}$

Es el número de cruces en el diagrama de flechas de la permutación, su distancia de Kendall tau desde la permutación de identidad y la suma de cada uno de los vectores relacionados con la inversión definidos a continuación.

No importa si se usa la definición de inversión basada en lugares o en elementos para definir el número de inversión, porque una permutación y su inversa tienen el mismo número de inversiones.

Otras medidas de (pre) ordenación incluyen el número mínimo de elementos que se pueden eliminar de la secuencia para producir una secuencia completamente ordenada, el número y longitudes de "corridas" ordenadas dentro de la secuencia, la regla de Spearman (suma de distancias de cada elemento desde su posición ordenada), y el menor número de intercambios necesarios para ordenar la secuencia. Los algoritmos de clasificación por comparación estándar se pueden adaptar para calcular el número de inversión en el tiempo O ( n log n ) .

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 les llama vector de inversión o código de Lehmer . ( Aquí encontrará una lista de fuentes ).

Este artículo utiliza el término vector de inversión ( ) como Wolfram . 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 de la izquierda da las permutaciones colexicográficas inversas, y el recuento de inversión de la derecha 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 (derecha) es . ${\ 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 . ${\ Displaystyle \ pi}$${\ Displaystyle \ pi (i)}$${\ Displaystyle \ pi (i)}$

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

Ambos 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. 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 clasificable muestra las 24 permutaciones de cuatro elementos con sus conjuntos de inversión basados ​​en el lugar, vectores relacionados con la inversión y números de inversión. (Las columnas pequeñas son reflejos de las columnas contiguas y se pueden usar para clasificarlas en orden colexicográfico ).

Se puede observar que y siempre tienen los mismos dígitos, y que y están ambos relacionados con el conjunto de la inversión basada 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 . Lex order by es el mismo que lex order by . ${\ Displaystyle \ pi}$${\ Displaystyle l}$${\ Displaystyle \ pi}$${\ Displaystyle r}$

Permutaciones de 3 elementos para comparar
0 1 2 3 4 5 ${\ Displaystyle \ pi}$ ${\ Displaystyle v}$ ${\ Displaystyle l}$ pb ${\ Displaystyle r}$ # 0 123 321 00 0 0 00 00 0 0 00 00 0 0 00 0 1 213 312 10 0 0 01 01 0 0 10 10 0 0 01 1 2 132 231 01 0 0 10 10 0 0 01 01 0 0 10 1 3 312 213 11 0 0 11 11 0 0 11 20 0 0 02 2 4 231 132 20 0 0 02 20 0 0 02 11 0 0 11 2 5 321 123 21 0 0 12 21 0 0 12 21 0 0 12 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23

${\ Displaystyle \ pi}$ ${\ Displaystyle v}$ ${\ Displaystyle l}$ pb ${\ Displaystyle r}$ # 0 1234 4321 000 0 0 000 000 0 0 000 000 0 0 000 0 1 2134 4312 100 0 0 001 001 0 0 100 100 0 0 001 1 2 1324 4231 010 0 0 010 010 0 0 010 010 0 0 010 1 3 3124 4213 110 0 0 011 011 0 0 110 200 0 0 002 2 4 2314 4132 200 0 0 002 020 0 0 020 110 0 0 011 2 5 3214 4123 210 0 0 012 021 0 0 120 210 0 0 012 3 6 1243 3421 001 0 0 100 100 0 0 001 001 0 0 100 1 7 2143 3412 101 0 0 101 101 0 0 101 101 0 0 101 2 8 1423 3241 011 0 0 110 110 0 0 011 020 0 0 020 2 9 4123 3214 111 0 0 111 111 0 0 111 300 0 0 003 3 10 2413 3142 201 0 0 102 120 0 0 021 120 0 0 021 3 11 4213 3124 211 0 0 112 121 0 0 121 310 0 0 013 4 12 1342 2431 020 0 0 020 200 0 0 002 011 0 0 110 2 13 3142 2413 120 0 0 021 201 0 0 102 201 0 0 102 3 14 1432 2341 021 0 0 120 210 0 0 012 021 0 0 120 3 15 4132 2314 121 0 0 121 211 0 0 112 301 0 0 103 4 dieciséis 3412 2143 220 0 0 022 220 0 0 022 220 0 0 022 4 17 4312 2134 221 0 0 122 221 0 0 122 320 0 0 023 5 18 2341 1432 300 0 0 003 300 0 0 003 111 0 0 111 3 19 3241 1423 310 0 0 013 301 0 0 103 211 0 0 112 4 20 2431 1342 301 0 0 103 310 0 0 013 121 0 0 121 4 21 4231 1324 311 0 0 113 311 0 0 113 311 0 0 113 5 22 3421 1243 320 0 0 023 320 0 0 023 221 0 0 122 5 23 4321 1234 321 0 0 123 321 0 0 123 321 0 0 123 6

Orden débil de permutaciones

Permutoedro del grupo simétrico S ₄

Al conjunto de permutaciones en n elementos se le puede dar la estructura de un orden parcial , llamado orden débil de permutaciones , que forma un retículo .

El diagrama de Hasse de los conjuntos de inversión ordenados por la relación de subconjuntos 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 resultante de las permutaciones es el del permutoedro, donde un borde 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 gráfico de Cayley , donde un borde corresponde al intercambio de dos elementos en lugares consecutivos. Esta gráfica de Cayley del grupo simétrico es similar a su permutoedro, pero con cada permutación reemplazada por su inversa.

Ver también

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

Secuencias en la OEIS :

• Secuencias relacionadas con la representación de 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 tienen solo 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 mahónicos: A008302   (sus máximos de fila; números de Kendall-Mann: A000140 )
• Número de gráficos etiquetados conectados con n bordes y n nodos: A057500

Referencias

Bibliografía fuente

Otras lecturas

Medidas de clasificación previa