Paridad e Inversa de Permutaciones (impar y Par)

Question

Quiero una explicación sobre cómo saber si una permutación es impar o par. Por ejemplo, tengo unas cuantas permutaciones de [9] que necesito que me expliquen la paridad, la inversa y el número de inversiones si es posible.

1. 987654321
2. 135792468
3. 259148637

Necesito saber cómo llegar. (Puedes añadir más ejemplos si es necesario, sólo he elegido estos ya que forman parte de un texto)

Answer 1

La paridad y el número de inversiones van juntos: si el número de inversiones es par, también lo es la paridad, y si el número de inversiones es impar, también lo es la paridad. Por tanto, ambos se reducen a contar las inversiones. Cada vez que un número mayor precede a un número menor en una permutación, se tiene una inversión.

Veamos tu tercer ejemplo, $259148637$ . El $2$ precede a $5,9,1,4,8,6,3$ y $7$ el único de ellos que es más pequeño que $2$ es $1$ , por lo que el par $(2,1)$ es la única inversión que implica el $2$ . Ir a la $5$ : precede a $9,1,4,8,6,3$ y $7$ de estos, $1,4$ y $3$ son menores que $5$ así que tenemos otras tres inversiones: $(5,1),(5,4)$ y $(5,3)$ . Continúe de la misma manera: el $9$ es mayor que los seis números que le siguen, por lo que aporta seis inversiones; el $1$ no es mayor que ninguno de los números posteriores, por lo que no aporta ninguno. Y así sucesivamente: el $4$ contribuye con uno, $(4,3)$ La $8$ aporta tres, ya que es mayor que los tres números posteriores; el $6$ contribuye con uno, $(6,3)$ ; y eso es todo, ya que el $3$ y $7$ no aportan nada.. El total general es, por tanto, de $$1+3+6+0+1+3+1+0+0= 15\;,$$ si no he contado mal. Concluimos que la permutación $259148637$ tiene $15$ inversiones, y como $15$ es impar, es una permutación de impar.

Encontrar la inversa es otra cosa. Para ello, lo más fácil es escribir la permutación en notación de dos líneas, así: $$\matrix{1&2&3&4&5&6&7&8&9\\2&5&9&1&4&8&6&3&7}\tag{1}$$ Esto es básicamente una visualización tabular de la permutación como función Uno que lleva cada número de la fila superior al número de abajo. Si llamo a la permutación $\pi$ Puedo pensar en ella como la función tal que $\pi(1)=2,\pi(2)=5,\pi(3)=9,\dots,\pi(9)=7$ . La función inversa simplemente invierte todos estos pares: $\pi^{-1}(2)=1,\pi^{-1}(5)=2,\pi^{-1}(9)=3,\dots,\pi^{-1}(7)=9$ . En forma de tabla, esto es sólo girar $(1)$ al revés: $$\matrix{2&5&9&1&4&8&6&3&7\\1&2&3&4&5&6&7&8&9}\tag{2}$$

Ahora $(2)$ es un poco difícil de usar, porque la fila superior (o "de entrada") está desordenada. Para solucionarlo, basta con reordenar las columnas para que la fila superior esté en orden numérico: $$\matrix{1&2&3&4&5&6&7&8&9\\4&1&8&5&2&7&9&6&3}\tag{3}$$ Para conseguir $(3)$ de $(2)$ Acabo de mover las columnas como unidades: la cuarta columna de $(2)$ se convierte en la primera columna de $(3)$ la primera columna de $(2)$ se convierte en la segunda columna de $(3)$ la octava columna de $(2)$ se convierte en la tercera columna de $(3)$ y así sucesivamente, hasta la tercera columna de $(2)$ que $-$ ya que tiene el $9$ en la fila superior $-$ se convierte en la última columna de $(3)$ .

Ahora sólo hay que leer la fila inferior de $(3)$ : $418527963$ es la inversa de la permutación original. Prueba este procedimiento con los demás, y comprueba si tienes alguna duda.

Answer 2

Una forma es escribir la permutación como un producto de ciclos disjuntos (si no sabes cómo hacerlo, pregunta y alguien te responderá). Es incluso si hay un número par de $n$ -ciclos con $n$ incluso; si no, es impar.