(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).
(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.