Mostra la font per a Paritat d'una permutació

En [[matemàtiques]], les [[permutació|permutacions]] (és a dir, les bijeccions en els conjunts finits) es poden descompondre en un producte de [[Permutació#permutacions particulars|transposicions]], és a dir en una successió d'intercanvis d'elements dos a dos.
* Una '''permutació parella''' és una permutació que es pot expressar com el producte d'un nombre parell de transposicions;
* Una '''permutació senar''' és una permutació que es pot expressar com el producte d'un nombre senar de transposicions.

El '''signe''' d'una permutació val 1 si és parella i -1 si és senar. L'aplicació signe constitueix un [[homomorfisme|morfisme de grups]]. Intervé en [[àlgebra multilineal]], sobretot per al càlcul de [[Determinant (matemàtiques)|determinants]].

== Definició de la paritat ==
Sigui una permutació <math>\sigma</math>. La definició tradicional de la paritat de <math>\sigma</math> es fa pel recompte de les inversions.

;Definició

Siguin ''i<j'' dos elements diferents compresos entre 1 i ''n''. Es diu que la parella ''{i,j}'' queda '''invertida'' per <math>\sigma</math> quan <math>\sigma(i)>\sigma(j)</math>.

Una permutació s'anomena '''parella''' quan presenta un nombre parell d'inversions, senar si no.

; Exemple
: Sigui la permutació
::<math>\begin{pmatrix} 1&2&3&4&5\\1&3&5&4&2\end{pmatrix}</math>
:La parella {1,2} no està en inversió ja que les imatges de 1 i 2 estan conserven el mateix [[ordre]]. Tampoc ho estan 1 i 3. La llista de les parelles en inversió és {2,5}, {3,4}, {3,5}, {4,5}. N'hi ha quatre, per tant la permutació és parella.

Per definició, el signe d'una permutació parella és 1, la d'una permutació senar és -1.

=== Una transposició és senar ===
Tota [[Permutació#permutacions particulars|transposició]] és una permutació senar. En efecte notant ''i'' i ''j'', ''i<j'', els termes intercanviats per la transposició, aquesta s'escriu
:<math>\begin{pmatrix} 1&\dots&i-1&i&i+1&\dots &j-1&j&j+1&\dots\; n\\
1&\dots & i-1&j&i+1&\dots &j-1&i&j+1&\dots\; n\end{pmatrix}</math>

Els parells en inversió són els parells de la forma ''{i,k}'' amb ''k'' comprès entre ''i+1'' i ''j'' i les de la forma ''{k,j}'' amb ''k'' comprès entre ''i+1'' i ''j-1''. En total, hi ha un nombre senar d'inversions, i d'aquí se'n desprèn que la permutació és senar.

=== Una fórmula per a calcular el signe ===
Es nota <math>{\mathcal P}</math> el conjunt dels parells d'elements compresos entre 1 i ''n'' (n'hi ha ''n(n-1)/2''). Una permutació σ té per signe
:<math>\varepsilon(\sigma)=\prod\limits_{i<j} \frac{\sigma(i)-\sigma(j)}{i-j}
=\prod\limits_{\{i,j\}\in {\mathcal P}} \frac{\sigma(i)-\sigma(j)}{i-j}</math>

:''Demostració''
:Dient ''P'' aquest producte. Examinar totes les parelles ''(i,j)'' amb ''i<j'' porta a examinar tots els parells ''{i,j}''. Per a cadascuna d'elles, el terme que es troba al producte té un signe negatiu si el parell és en inversió, positiu si no. Això mostra que el signe de ''P'' és el de la permutació. Finalment, per bijectivitat de σ, els termes ''σ(i)-σ(j)'' del numerador són, tret del signe, els mateixos que els ''i-j'' del denominador. Això mostra que el [[valor absolut]] de ''P'' és 1 i permet concloure.

Aquesta fórmula té un cert interès algebraic però no permet un càlcul eficaç del signe a la pràctica. En efecte, respecte al senzill recompte de les inversions s'afegeix la multiplicació i la divisió per un cert nombre d'enters.

== Signe d'un producte ==
Les permutacions verifiquen una regla dels signes per al producte: el producte de dues permutacions parelles és parell, de dues permutacions senars és parell, el producte d'una permutació parella i d'una senar és senar. Utilitzant el signe, això es resumeix per la fórmula
:<math>\varepsilon(\sigma\circ\tau)=\varepsilon(\sigma).\varepsilon(\tau)</math>

:''Demostració''
:<math>\varepsilon(\sigma\circ \tau)=\prod\limits_{\{i,j\}\in {\mathcal P}} \frac{\sigma(\tau(i))-\sigma(\tau(j))}{\tau(i)-\tau(j)}
\prod\limits_{\{i,j\}\in {\mathcal P}} \frac{\tau(i)-\tau(j)}{i-j}</math>
:En el segon factor del segon membre, es reconeix directament un signe. Per al primer, cal prèviament reindexar posant ''{i',j'}={τ(i),τ(j)}'', on es reconeix llavors igualment un signe.

En termes algebraics: el signe és un [[morfisme]] de grups del [[grup simètric]] <math>(\mathfrak S_n,\circ)</math> en <math>\left(\{-1,1\},\times\right)</math>. El conjunt de les permutacions parelles forma el [[grup alternat]], nucli d'aquest morfisme. Finalment la permutació inversa de σ té el mateix signe que σ.

=== Càlcul del signe ===
Com a corol·lari dels resultats precedents,
* una permutació és parella [[si i només si]] es pot expressar com el producte d'un nombre parell de transposicions;
* una permutació és senar si i només si es pot expressar com el producte d'un nombre senar de transposicions

i aquests dos casos s'exclouen mútuament.

El càlcul del signe per la descomposició en producte de transposicions és molt més eficaç que l'aplicació de la definició inicial; en efecte per a una permutació de <math>{\mathfrak S}_n</math> aquesta descomposició demanda com a màxim ''n-1'' operacions, contra ''n(n-1)/2'' per a la definició.

; Exemples
: la identitat és una permutació parella;
: una transposició és una permutació senar;
: una [[permutació circular]] és parella si el nombre d'elements és senar; és senar si el nombre d'elements és parell.

== Vegeu també ==
* [[Permutació]]
* [[Grup simètric]]


{{ORDENA:Paritat D'Una Permutacio}}
[[Categoria:Combinatòria]]
[[Categoria:Teoria de grups]]