O que é decomposição cíclica e como vamos proceder (explicação didática):
Um ciclo (a_1\\ a_2\\ \dots\\ a_k) representa a permutação que envia a_1\mapsto a_2, a_2\mapsto a_3, \dots, a_{k-1}\mapsto a_k, a_k\mapsto a_1.
Para decompor uma permutação dada em duas linhas, procedemos pegando um elemento não ainda colocado em algum ciclo, seguimos sua imagem, depois a imagem dessa imagem, etc., até voltarmos ao elemento inicial — isso forma um ciclo. Repetimos com o menor elemento restante até cobrir todos.
Vou usar essa estratégia passo a passo, mostrando cada imagem explicitamente, para você poder replicar isso na prova sem erro.
Passo 3
Começo pelo menor elemento 1 (a técnica usual: pegar o menor ainda não usado).
\;1\mapsto4 (pegado da tabela).
\;4\mapsto9.
\;9\mapsto6.
\;6\mapsto2.
\;2\mapsto1, que nos traz de volta ao início.
Portanto os elementos visitados formam o ciclo
(1\\\ 4\\\ 9\\\ 6\\\ 2).
Isto significa exatamente: 1\mapsto4,\;4\mapsto9,\;9\mapsto6,\;6\mapsto2,\;2\mapsto1.
Passo 4
Agora escolho o menor elemento que ainda não apareceu no ciclo anterior: 3.
\;3\mapsto8.
\;8\mapsto5.
\;5\mapsto10.
\;10\mapsto3, volta ao início.
Portanto obtemos o ciclo
(3\\\ 8\\\ 5\\\ 10).
Passo 5
Restam os elementos 7 e 11 (a maioria já foi usada). Pegando 7:
\;7\mapsto11.
\;11\mapsto7, voltamos ao início.
Isso forma o ciclo
(7\\\ 11).
Passo 6
Temos agora ciclos disjuntos que cobrem todos os elementos 1 a 11:
Como são disjuntos, a permutação é o produto (composição) desses ciclos; a ordem entre ciclos disjuntos não importa.
Passo 7
Agora a paridade — explicação didática:
Qualquer ciclo de comprimento k pode ser escrito como produto de k-1 transposições (transposição = troca de dois elementos). Por exemplo, um 4‑ciclo tem a identidade
(a\\ b\\ c\\ d)=(a\\ d)(a\\ c)(a\\ b),
ou seja, 4-ciclo = 3 transposições.
Assim, se escrevemos a permutação como produto de ciclos disjuntos, o número total de transposições necessário é a soma de (k-1) sobre todos os ciclos de comprimento k.
A permutação é par se esse número total for par, e ímpar se for ímpar.
Passo 8
Aplicando isso aos nossos ciclos:
O ciclo (1\\\ 4\\\ 9\\\ 6\\\ 2) tem comprimento 5, contribui com 5-1=4 transposições.
O ciclo (3\\\ 8\\\ 5\\\ 10) tem comprimento 4, contribui com 4-1=3 transposições.
O ciclo (7\\\ 11) tem comprimento 2, contribui com 2-1=1 transposição.
Somando:
4+3+1=8.
O número total de transposições é 8, que é par. Portanto a permutação é par.