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)

loading... ECoduri.com - Coduri postale - adresa, caen, cor Politica de confidentialitate