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.
22929cge62jhe7e
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 gh929c2262jhhe 22929cge62jhe7e
permutare σ oτ :AàA cu prop. (σ oτ)(k)=σ(τ(k)).
3.Proprietati ale compunerii permutarilor.
P1: Asociativitatea compunerii
22929cge62jhe7e 22929cge62jhe7e (σoτ)oφ=σo(τoφ), oricare ar fi σ;τ;φ ε Sn.
P2: Compunerea permutarilor nu este comutativa
22929cge62jhe7e 22929cge62jhe7e σoτ=τoσ
P3: Element neutru
22929cge62jhe7e 22929cge62jhe7e σoе=еoσ oricare ar fi σ ε Sn
22929cge62jhe7e 22929cge62jhe7e е(i)=i àpermutarea identica
P4: Element simetrizabil
22929cge62jhe7e 22929cge62jhe7e σoσ=σoσ=е
22929cge62jhe7e 22929cge62jhe7e
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 e(σ) =(-1) 22929cge62jhe7e se numeste signatura (semnul) 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e permutarii σ.
e (σ) = 1 daca M(σ) este par
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e -1 daca M(σ) este impar
*σ se numeste permutare para daca are un numar par de
22929cge62jhe7e inversiuni.
*σ se numeste permutare impara daca are un numar impar de
22929cge62jhe7e inversiuni.
Teorema 1. Orice transpozitie este o permutare impara.
Teorema 2. Daca σ ε Sn atunci e (σ) = Π ( σ(i)- σ(j) )/(i-j).
Teorema 3. Daca σ,τ εSn atunci e (σoτ) =e (σ) o e (τ).
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
22929cge62jhe7e 22929cge62jhe7e transpozitii si daca este impara ea poate fi descompusa ca 22929cge62jhe7e 22929cge62jhe7e
22929cge62jhe7e 22929cge62jhe7e produs impar de transpozitii.
Aplicatii.
1. Fie permutarile σ=1 2 3 4 si τ=1 2 3 4 . Sa se calculeze
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 2 4 1 3 22929cge62jhe7e 22929cge62jhe7e 4 1 2 3
σoτ si τoσ.
σoτ =1 2 3 4 22929cge62jhe7e τoσ =1 2 3 4
22929cge62jhe7e 22929cge62jhe7e 3 2 4 1 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 3 4 2
2. Sa se determine numarul de inversiuni si signatura pentru 22929cge62jhe7e
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e fiecare dintre permutarile urmatoare:
* 1 2 3
2 3 1
M(σ) =2 => e (σ) =1
* 1 2 3 4
2 4 1 3
M(σ)=3 => e (σ) =-1
* 1 2 3 4
4 1 2 3
M(σ) =3 => e (σ) =-1
* 1 2 3 4 5
5 3 4 1 2
M(σ) =8 => e (σ) =1
3. Fie permutarea σ = 1 2 3 4 5 . Sa se scrie σ ca produs de
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 3 1 2 5 4
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e transpozitii. Aceeasi problema pentru permutarea 22929cge62jhe7e
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e τ=1 2 3 4 5 6 .
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 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
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 2 3 5 4 22929cge62jhe7e 3 1 2 5 4 22929cge62jhe7e 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
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 3 2 1 4 5 22929cge62jhe7e 3 1 2 4 5 22929cge62jhe7e 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
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 3 2 4 5 22929cge62jhe7e 1 3 2 4 5 22929cge62jhe7e 1 2 3 4 5
*(1,6)oτ = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = τ1
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 6 2 3 4 5 1 22929cge62jhe7e 6 4 5 3 2 1 22929cge62jhe7e 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
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 5 3 4 2 6 22929cge62jhe7e 1 4 5 3 2 6 22929cge62jhe7e 22929cge62jhe7e 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
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 2 4 3 5 6 22929cge62jhe7e 1 4 2 3 5 6 22929cge62jhe7e 22929cge62jhe7e 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
22929cge62jhe7e σ = 1 2 3 4… 22929cge62jhe7e n 22929cge62jhe7e n+1 n+2… 2n
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 3 5 7… 2n-1 22929cge62jhe7e 2 22929cge62jhe7e 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 σ.
22929cge62jhe7e
22929cge62jhe7e M(σ)=1+2+3+4+ … +n = n(n+1)/2
6. Determinati σε S7 astfel incit
7. Rezolvati in S5 ecuatia:
σoX=Xoσ 22929cge62jhe7e σ= 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 2 3 1 5 4
22929cge62jhe7e X= 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e a b c d e
22929cge62jhe7e
Xoσ= 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e a b c d e 22929cge62jhe7e 2 3 1 5 4 22929cge62jhe7e 22929cge62jhe7e b c a e d
σoX= 1 2 3 4 5 o 1 2 3 4 5 = 22929cge62jhe7e 1 22929cge62jhe7e 2 22929cge62jhe7e 3 22929cge62jhe7e 4 22929cge62jhe7e 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 2 3 1 5 4 22929cge62jhe7e 22929cge62jhe7e a b c d e 22929cge62jhe7e 22929cge62jhe7e σ(a) σ(b) σ(c) σ(d) σ(e)
=> σ(a) =b
22929cge62jhe7e σ(b) =c
22929cge62jhe7e σ(c) =a
22929cge62jhe7e σ(d) =e
22929cge62jhe7e σ(e) =d => d,e ε {4,5}
CAZUL I: d=4
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e e=5
=> σ(a) =b
22929cge62jhe7e σ(b) =c
22929cge62jhe7e σ(c) =a
i) a=1 => σ(1) =b dar σ(1) =2 => b=2
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e σ(b) =c 22929cge62jhe7e => σ(2) =c dar σ(2) =3 => c=3
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e σ(c) =1
=> X1 = 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 2 3 4 5
ii) a=2 => σ(2) =b dar σ(2) =3 => b=3
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e σ(b) =c => σ(3) =c dar σ(3) =1 => c=1
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e σ(c) =2
=> X2 = 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 2 3 1 4 5
iii) a=3 => σ(3) =b dar σ(3)=1 => b=1
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e σ(b) =c => σ(1) =c dar σ(1)=2 => c=2
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e
=>X3 = 22929cge62jhe7e 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 3 1 2 4 5
CAZUL II: d=5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e e=4
i) a=1
=> X4 = 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 1 2 3 5 4
ii) a=2
=> X5 = 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 2 3 1 5 4
iii) a=3
22929cge62jhe7e => X6 = 1 2 3 4 5
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 3 1 2 5 4.
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e
8. Fie permutare u = 1 2 3 4 . Sa se arate ca nu exista nici o
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 3 4 2 1
22929cge62jhe7e permutare X ε S4, astfel incit X² =u.
22929cge62jhe7e Ɛ(X²) = 1
22929cge62jhe7e Ɛ(u) =-1 => nu exista X.
9. Fie permutarea σ = 1 2 3 4 5 6 . Sa se determine i si j astfel
22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 6 4 i 3 j 1
22929cge62jhe7e incit σ sa fie o permutare para (respectiv impara). 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e 22929cge62jhe7e
22929cge62jhe7e i=2 sau i=5
22929cge62jhe7e j=5 22929cge62jhe7e 22929cge62jhe7e j=2
*i=2 si j=5
=> e (σ) =-1 => permutarea este impara
*i=5 si j=2
=> e (σ) =1 => permutare este para.
10. Se dau numerele reale strict pozitive a1<a2<…<an.
22929cge62jhe7e Pentru ce permutare σε Sn suma
22929cge62jhe7e
22929cge62jhe7e este maxima.
22929cge62jhe7e Fie τ =σo (k,j)
22929cge62jhe7e 22929cge62jhe7e
11. Se dau numerele reale strict pozitive a1<a2<…<an. Pentru ce 22929cge62jhe7e 22929cge62jhe7e permutare σε Sn produsul
(r se s sunt doua numere naturale >=1).
τ=σo(k,j)
12. Pentru ce permutare σε Sn suma
este minima?
Fie τ =σo(k,j)
13. Se dau numerele reale a1<a2< … <an.
Pentru ce permurare σε Sn suma
este maxima?
Fie τ =σo(k,j)
