Inversión (matemáticas)

En informática e matemáticas discretas, unha inversión nunha secuencia é un par de elementos que están fóra da súa orde natural.

 Definicións 

 Inversión 
Sexa  unha permutación. Hai unha inversión de  entre  e  se  e . A inversión indícase mediante un par ordenado que contén calquera dos lugares    ou os elementos .  

O conxunto de inversión é o conxunto de todas as inversións. O conxunto de inversión dunha permutación que usa a notación baseada no lugar é o mesmo que o conxunto de inversión da permutación inversa usando a notación baseada en elementos cos dous compoñentes de cada par ordenado intercambiados. Do mesmo xeito, o conxunto de inversión dunha permutación que usa a notación baseada en elementos é o mesmo que o conxunto de inversión da permutación inversa usando a notación baseada no lugar cos dous compoñentes de cada par ordenado intercambiados.

As inversións adoitan definirse para as permutacións, mais tamén se poden definir para as secuencias:Sexa   unha secuencia, se  e , ben o par de lugares    ou o par de elementos   chámase inversión de .

Para as secuencias, as inversións segundo a definición baseada en elementos non son únicas, porque diferentes pares de lugares poden ter o mesmo par de valores.

 Número da inversión 
O número da inversión   dunha secuencia , é a cardinalidade do conxunto de inversión. É unha medida común de ordenación (ás veces chamada preclasificación) dunha permutación ou secuencia.  O número de inversión está entre 0 e  inclusive. Unha permutación e a súa inversa teñen o mesmo número de inversión.

Por exemplo  xa que a secuencia está ordenada. Ademais, cando  é par,  (porque cada parella  é unha inversión). Este último exemplo mostra que un conxunto intuitivamente "case ordenado" aínda pode ter un número cadrático de inversións.

O número de inversión é o número de cruzamentos no esquema de frecha da permutation,[6] a distancia tau de Kendall  da permutación desde a identidade, e a suma de cada un dos vectores de inversión relacionados definidos abaixo.

Outras medidas de ordenación inclúen o número mínimo de elementos que se poden eliminar da secuencia para obter unha secuencia totalmente ordenada, a regra de pé de Spearman (suma das distancias de cada elemento dende a súa  posición ordenada), e o menor número de trocos necesarios para ordenar a secuencia.  Os algoritmos estándar de ordenación por comparación pódense adaptar para calcular o número de inversión nun tempo . 

 Vectores relacionados coa inversión 
Están en uso tres vectores similares que condensan as inversións dunha permutación nun vector que a determina de forma única. Adoitan chamarse vector de inversión ou código de Lehmer. (Atópase aquí unha lista de fontes).

Este artigo usa o termo vector de inversión () como as páxinas de Wolfram Mathematica.Weisstein, Eric W. "Inversion Vector" From MathWorld--A Wolfram Web Resource Os dous vectores restantes ás veces chámanse vector de inversión pola esquerda e pola dereita, mais para evitar confusións co vector de inversión, este artigo chámaos conta de inversión pola esquerda () e conta de inversión pola dereita (). Interpretado como un sistema de numeración factorial, a conta de inversión pola esquerda dá as permutacións colexicográficas inversas, Reverse colex order of finitary permutations  e a conta de inversión pola dereita dá o índice lexicográfico.
miniatura| Diagrama de Rothe
Vector de inversión :Coa definición baseada en elementos  é o número de inversións cuxo compoñente menor (dereito) é . 

  é o número de elementos en  máis grande cá  en posición anterior a .


Conta de inversión pola esquerda  :Coa definición baseada no lugar  é o número de inversións cuxo compoñente (dereito) maior é  .

  é o número de elementos en  máis grande cá  en posición anterior a .


Conta de inversións pola dereita , a miúdo chamado código de Lehmer :Coa definición baseada no lugar  é o número de inversións cuxa compoñente menor (esquerda) é  .

  é o número de elementos en  menor que  posteriores a  .


Ambos os  e  pódense atopar coa axuda dun diagrama de Rothe, que é unha matriz de permutación cos 1 representados por puntos, e unha inversión (a miúdo representada por unha cruz) en cada posición que teña un punto á dereita e debaixo dela.  é a suma das inversións na fila  do diagrama de Rothe, mentres que  é a suma das inversións na columna . A matriz de permutación da inversa é a transposta, polo tanto o  dunha permutación é o  da súa inversa, e viceversa.

 Exemplo: todas as permutacións de catro elementos 
miniatura| As seis posibles inversións dunha permutación de 4 elementos
A seguinte táboa ordenada mostra as 24 permutacións de catro elementos (na columna ) cos seus conxuntos de inversión baseados no lugar (na columna p-b), os vectores relacionados coa inversión (nas columnas , , e ) e os números de inversión (na columna #). (As columnas con letra máis pequena e sen título son reflexos das columnas situadas ao lado, e pódense usar para ordenar por orde colexicográfica).

Pódese ver que  e  sempre teñen os mesmos díxitos, e que tano  como  están relacionados co conxunto de inversión baseado no lugar. Os elementos non triviais de  son as sumas das diagonais descendentes do triángulo mostrado e os de  son as sumas das diagonais ascendentes. (Os pares en diagonais descendentes teñen en común as compoñentes dereitas 2, 3, 4, mentres que os pares en diagonais ascendentes teñen en común as compoñentes esquerdas 1, 2, 3).

A orde predeterminada da táboa é a orde "colex" inversa por , que é o mesmo que a orde colex por . A orde "lex" por  é o mesmo que a orde "lex" por .
Permutacións de 3 elementos para comparación 011

 Orde feble de permutacións 
miniatura| Permutoedro do grupo simétrico S4
Ao conxunto de permutacións de n elementos pódeselle dar a estrutura dunha orde parcial, chamada orde feble de permutacións, que forma unha retícula.

O diagrama de Hasse dos conxuntos de inversión ordenados pola relación de subconxuntos forma o esqueleto dun permutoedro.

Se se asignase unha permutación a cada conxunto de inversión usando a definición baseada en elementos, a orde resultante das permutacións sería a dun grafo de Cayley, onde unha aresta corresponde ao troco de dous elementos en lugares consecutivos. Este grafo de Cayley do grupo simétrico é semellante ao seu permutoedro, mais con cada permutación substituída pola súa inversa.
 Notas 


 Véxase tamén 

 Bibliografía 












 Outros artigos 
 Paridade dunha permutación.
 Sistema de numeración factorial.
 Permutación.
 Grupo das permutacións.

Categoría:Matemática discreta
Categoría:Combinatoria
Categoría:Teoría da orde
Categoría:Teoría de grupos