Permutari













1.Notiunea de permutare.
Fie A o multime finita de „n“ elemente, adica A={1, 2, 3, …, n}.
O functie bijectiva ?:A(A se numeste permutare (substitutie)
de gradul n.

P:Numarul tuturor permutarilor de ordin n este egal cu n! .

2.Produsul (compunerea) permutarilor.
Fie ? si ? doua permutari de acelasi grad n.
Prin compunerea celor doua permutari se intelege o noua
permutare ? o? :A(A cu prop. (? o?)(k)=?(?(k)).

3.Proprietati ale compunerii permutarilor.
P1: Asociativitatea compunerii
(?o?)o?=?o(?o?), oricare ar fi ?;?;? ? Sn.
P2: Compunerea permutarilor nu este comutativa
?o?=?o?
P3: Element neutru
?o?=?o? oricare ar fi ? ? Sn
?(i)=i (permutarea identica



P4: Element simetrizabil
?o?=?o?=?


4.Transpozitii.
Se numeste transpozitie o permutare de forma ?(i,j) sau (i,j) cu proprietatea
 Proprietati:
P1: ?²ij =e
P2: ?ij = ?ij
P3: ?ij = ?ji
Numarul tuturor transpozitiilor de ordin n este egal cu Cn².
Numarul tuturor transpozitiilor de ordin n este egal cu numarul perechilor (i,j) cu proprietatea ca i
5.Inversiunile unei permutari.
Se numeste inversiune intr-o permutare ? o pereche de elemente (i,j) i ?(j).

Numarul inversiunilor intr-o permutare se noteaza cu M(?) <= Cn².

6.Signatura unei permutari.
Fie ?? Sn. Numarul ?(?) =(-1) se numeste signatura (semnul) permutarii ?.


( (?) = 1 daca M(?) este par
-1 daca M(?) este impar
*? se numeste permutare para daca are un numar par de
inversiuni.
*? se numeste permutare impara daca are un numar impar de
inversiuni.

Teorema 1. Orice transpozitie este o permutare impara.
Teorema 2. Daca ? ? Sn atunci ( (?) = ? ( ?(i)- ?(j) )/(i-j).
Teorema 3. Daca ?,? ?Sn atunci ( (?o?) =( (?) o ( (?).
Teorema 4. Daca ? ?Sn este o permutare atunci ? poate fi descompusa ca produs de transpozitii.

Obs: Daca ? este para ea poate fi descompusa ca produs par de
transpozitii si daca este impara ea poate fi descompusa ca
produs impar de transpozitii.


Aplicatii.
1. Fie permutarile ?=1 2 3 4 si ?=1 2 3 4 . Sa se calculeze
2 4 1 3 4 1 2 3
?o? si ?o?.
?o? =1 2 3 4 ?o? =1 2 3 4
3 2 4 1 1 3 4 2







2. Sa se determine numarul de inversiuni si signatura pentru
fiecare dintre permutarile urmatoare:

* 1 2 3
2 3 1
M(?) =2 => ( (?) =1
* 1 2 3 4
2 4 1 3
M(?)=3 => ( (?) =-1
* 1 2 3 4
4 1 2 3
M(?) =3 => ( (?) =-1
* 1 2 3 4 5
5 3 4 1 2
M(?) =8 => ( (?) =1

3. Fie permutarea ? = 1 2 3 4 5 . Sa se scrie ? ca produs de
3 1 2 5 4
transpozitii. Aceeasi problema pentru permutarea
?=1 2 3 4 5 6 .
6 4 5 3 2 1
*(4,5)o? = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = ?1
1 2 3 5 4 3 1 2 5 4 3 1 2 4 5
(1,3)o?1 = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = ?2
3 2 1 4 5 3 1 2 4 5 1 3 2 4 5
(2,3)o?2 = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = e
1 3 2 4 5 1 3 2 4 5 1 2 3 4 5
? = (4,5)o(1,3)o(2,3)



*(1,6)o? = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = ?1
6 2 3 4 5 1 6 4 5 3 2 1 1 4 5 3 2 6
(2,5)o?1 = 1 2 3 4 5...