PERMUTARI

1.Notiunea de permutare.

Fie A o multime finita de "n" elemente, adica A=.

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<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 σ.

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 11 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

σ = (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 61 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 61 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-12 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 4b 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 4a b c d e σ(a) σ(b) σ(c) σ(d) σ(e)

=> σ(a) =b

σ(b) =c

σ(c) =a

σ(d) =e

σ(e) =d => d,e ε

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)