Caro João Carlos:
Uma explicação simplista seria a seguinte:
Considere o conjunto In = {1,2,3,...,n}
Uma permutação de In nada mais é do que uma bijeção de In em In. No entanto,
do ponto de vista notacional, é conveniente representar uma permutação como
sendo uma matriz 2 x n, onde a primeira linha é:
1 2 3 4 ... n-1 n
e a segunda linha, a permutação desejada dos elementos de In, tal como por
exemplo:
2 3 1 4 ... n-1 n
(ou seja, uma permutação que leva 1 em 2, 2 em 3, 3 em 1, e fixa os demais
elementos de In)
A fim de verificar a paridade da permutação, você só precisa "ligar pontos",
ou seja, traçar n linhas ligando números iguais nas linhas superior e
inferior (de forma que no máximo duas das linhas traçadas se interceptem num
mesmo ponto). Se o número de pontos de interseção for par, a permutação será
par, caso contrário será ímpar.
Assim, a permutação do exemplo é par (2 pontos de interseçao: 1-1 com 2-2, e
1-1 com 3-3).
Outros exemplos (em I5):
1 2 3 4 5
5 4 3 2 1 ==> 10 pontos de interseção ==> PAR
1 2 3 4 5
2 3 1 5 4 ==> 3 pontos de interseção ==> ÍMPAR
1 2 3 4 5
5 1 2 4 3 ==> 5 pontos de interseção ==> ÍMPAR
Uma explicação mais detalhada deverá envolver alguns conceitos simples tais
como ciclos e transposições.
Por exemplo, você pode dar uma olhada em
http://www.fc.up.pt/mp/clomp/chapter4.pdf - um arquivo pdf que trata disso
tudo. Existem várias outras referências on-line, mas são em inglês. Se você
quiser eu posso te indicar.
Espero ter ajudado.
Um abraço,
Claudio.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================