Permutari

1. Notiunea de permutare. 
Fie A o multime finita de „n" elemente, adica A={1, 2, 3, …, n}. 
O functie bijectiva ó: AA 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ô: AA cu prop. (ó oô)(k)=ó (ô (k)). 
3. Proprietati ale compunerii permutarilor. 
P1: Asociativitatea compunerii
(ó oô)oö =ó o(ô oö), oricare ar fi ó; ô; ö å 

1.    Robot pe Marte

2.   Ce să mai citim?

3. Tatăl fondator al Uniunii Europene.            

4. Colonizarea de pe Marte !

5.   Ne pregătim pentru Marte

6. Colonizarea Marte poate determina umanitatea să-și modifice ADN-ul ?

7. Cine mai urăște să poarte mască?

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< j< n. 
5. Inversiunile unei permutari. 

Se numeste inversiune intr-o permutare ó o pereche de elemente (i, j) i< j cu proprietatea ca ó (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 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = ô 2
1 5 3 4 2 6 1 4 5 3 2 6 1 4 2 3 5 6
(3, 4)oô 2 = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = ô 3
1 2 4 3 5 6 1 4 2 3 5 6 1 3 2 4 5 6
(2, 3)oô 3 = e
ð ô = (1, 6)o(2, 5)o(3, 4)o(2, 3). 
4. Fie permutarea ó å S2n
ó = 1 2 3 4… n n+1 n+2… 2n
1 3 5 7… 2n-1 2 4 … 2n. 
Sa se determine numarul inversiunilor permutarii ó. 
Sa se determine „n" astfel incit ó sa fie para (respectiv impara). 
M(ó)=1+2+3+…+ n-1=n(n-1)/2
5. Sa se determine numarul inversiunilor permutarii ó. 
M(ó)=1+2+3+4+ … +n = n(n+1)/2
6. Determinati ó å S7 astfel incit
7. Rezolvati in S5 ecuatia: 
ó oX=Xoó ó = 1 2 3 4 5
2 3 1 5 4
X= 1 2 3 4 5
a b c d e
Xoó = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5
a b c d e 2 3 1 5 4 b c a e d
ó oX= 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5
2 3 1 5 4 a b c d e ó (a) ó (b) ó (c) ó (d) ó (e)
=> ó (a) =b
ó (b) =c
ó (c) =a
ó (d) =e
ó (e) =d => d, e å {4, 5}
CAZUL I: d=4
e=5
=> ó (a) =b
ó (b) =c
ó (c) =a
i) a=1 => ó (1) =b dar ó (1) =2 => b=2
ó (b) =c => ó (2) =c dar ó (2) =3 => c=3
ó (c) =1