Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Meseria se fura, ingineria se invata.Telecomunicatii, comunicatiile la distanta, Retele de, telefonie, VOIP, TV, satelit




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
PERMUTARI - Notiunea de permutare, Proprietati ale compunerii permutarilor, Transpozitii


PERMUTARI - Notiunea de permutare, Proprietati ale compunerii permutarilor, Transpozitii


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)










Politica de confidentialitate





Copyright © 2023 - Toate drepturile rezervate