Considere a permutação
\pi=\left(\begin{array}{lllll} 1 & 2 & 3 & 4 & 5 \\\\ 2 & 4 & 5 & 1 & 3 \end{array}\right)
(a) Escreva a decomposição cíclica de \pi e determine sua paridade.
(b) Conte o número de inversões de \pi, isto é, o número de pares de inteiros que estão fora de sua ordem natural na segunda linha de \pi; por exemplo, 2 e 4 estão em sua ordem natural, mas 2 e 1 não. Esse número é par ou ímpar?
(c) Compare a paridade dos números em (a) e (b).

Passo 1

O enunciado dá a permutação
\pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\[4pt] 2 & 4 & 5 & 1 & 3 \end{pmatrix}
e pede três coisas:
  • (a) escrever a decomposição cíclica de \pi e determinar sua paridade;
  • (b) contar o número de inversões da sequência (2,4,5,1,3) (a segunda linha) e dizer se esse número é par ou ímpar;
  • (c) comparar a paridade obtida em (a) com a de (b).
Informações relevantes:
  • A segunda linha da permutação, que é a imagem de 1,2,3,4,5 pela aplicação \pi, é a sequência \bigl(2,4,5,1,3\bigr).
  • Um ciclo k-uplo (um k-ciclo) pode ser escrito como produto de k-1 transposições; isso será usado para avaliar a paridade.]

Passo 2

Vamos construir a decomposição em ciclos de \pi passo a passo (método prático):
  • Começo pelo menor elemento que ainda não apareceu num ciclo, isto é 1.
  • Aplico \pi: 1\mapsto 2. Então sigo com 2.
  • Aplico \pi em 2: 2\mapsto 4. Sigo com 4.
  • Aplico \pi em 4: 4\mapsto 1. Voltei a 1, então fecho o ciclo encontrado: (1\\\ 2\\\ 4).
Agora pego o menor elemento não usado ainda: 3.
  • 3\mapsto 5.
  • 5\mapsto 3. Voltei a 3, então o ciclo é (3\\\ 5).
Não restam elementos não usados (os elementos 1,2,3,4,5 estão todos nos ciclos). Portanto a decomposição em ciclos disjuntos é
\pi=(1\\\ 2\\\ 4)(3\\\ 5).
(Observação: ciclos de tamanho 1 costumam ser omitidos.)

Passo 3

Agora determinar a paridade a partir da decomposição cíclica:
  • Um k-ciclo pode ser escrito como produto de k-1 transposições. Logo:
    • (1\\\ 2\\\ 4) é um 3-ciclo e equivale a 3-1=2 transposições (par).
    • (3\\\ 5) é um 2-ciclo (transposição) e equivale a 2-1=1 transposição (ímpar).
  • O número total de transposições na decomposição (somando os k-1 de cada ciclo) é 2+1=3, que é ímpar.
Conclusão: \pi é uma permutação ímpar.

Passo 4

Definição e método para contar inversões:
  • Dado um arranjo da sequência a_1,a_2,\dots,a_n, uma inversão é um par (i,j) com i<j e a_i>a_j.
  • Aqui a sequência é \bigl(a_1,a_2,a_3,a_4,a_5\bigr)=(2,4,5,1,3). Vou verificar todos os pares i<j:
Compare a_1=2 com os à direita 4,5,1,3:
  • 2>4? não.
  • 2>5? não.
  • 2>1? sim → inversão: (1,4).
  • 2>3? não.
    Total a partir de a_1: 1 inversão.
Compare a_2=4 com os à direita 5,1,3:
  • 4>5? não.
  • 4>1? sim → inversão: (2,4).
  • 4>3? sim → inversão: (2,5).
    Total a partir de a_2: 2 inversões (acumula 3).
Compare a_3=5 com os à direita 1,3:
  • 5>1? sim → inversão: (3,4).
  • 5>3? sim → inversão: (3,5).
    Total a partir de a_3: 2 inversões (acumula 5).
Compare a_4=1 com o à direita 3:
  • 1>3? não.
    Total a partir de a_4: 0.
a_5 não tem elementos à direita.
Somando: 1+2+2+0=5 inversões no total.
Portanto o número de inversões é 5, que é ímpar.

Passo 5

Comparação das paridades e explicação intuitiva do porquê elas coincidem:
  • Encontramos na parte (a) que \pi é ímpar (decomposta em 3 transposições no total).
  • Encontramos na parte (b) que o número de inversões é 5, ímpar.
  • Essas duas paridades coincidem: ambas ímpares.
Por que isso ocorre (intuição curta): cada transposição (troca de duas entradas) altera o número de inversões por um valor ímpar, então o número total de transposições (paridade da decomposição) e a paridade do número de inversões concordam. Assim a definição de permutação par/ímpar via produto de transposições coincide com a paridade do número de inversões.

Resposta

(a) \pi=(1\\\ 2\\\ 4)(3\\\ 5); \pi é ímpar.
(b) Número de inversões =5; esse número é ímpar.
(c) As paridades coincidem: ambas são ímpares.

Exercícios relacionados