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 σ = (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 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)
