|
PermutareaPermutari 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. 29985sun24loy6k
P:Numarul tuturor permutarilor de ordin n este egal cu n! . 2.Produsul (compunerea) permutarilor. Fie σ si τ doua permutari de acelasi grad n. uo985s9224looy 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<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) se numeste signatura (semnul) permutarii σ. e (σ) = 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 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 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 => 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 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
*(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
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 => X1 = 1 2 3 4 5 1 2 3 4 5 ii) a=2 => σ(2) =b dar σ(2) =3 => b=3 σ(b) =c => σ(3) =c dar σ(3) =1 => c=1 σ(c) =2 => X2 = 1 2 3 4 5 2 3 1 4 5 iii) a=3 => σ(3) =b dar σ(3)=1 => b=1 σ(b) =c => σ(1) =c dar σ(1)=2 => c=2
=>X3 = 1 2 3 4 5 3 1 2 4 5 CAZUL II: d=5 e=4 i) a=1 => X4 = 1 2 3 4 5 1 2 3 5 4 ii) a=2 => X5 = 1 2 3 4 5 2 3 1 5 4 iii) a=3 => X6 = 1 2 3 4 5 3 1 2 5 4.
8. Fie permutare u = 1 2 3 4 . Sa se arate ca nu exista nici o 3 4 2 1 permutare X ε S4, astfel incit X² =u. Ɛ(X²) = 1 Ɛ(u) =-1 => nu exista X. 9. Fie permutarea σ = 1 2 3 4 5 6 . Sa se determine i si j astfel 6 4 i 3 j 1 incit σ sa fie o permutare para (respectiv impara). i=2 sau i=5 j=5 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. Pentru ce permutare σε Sn suma
este maxima. Fie τ =σo (k,j)
11. Se dau numerele reale strict pozitive a1<a2<…<an. Pentru ce 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)
|
