Permutari referat






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

3 2 4 1 1 3 4 2








2. Sa se determine numarul de inversiuni si signatura pentru   

fiecare dintre permutarile urmatoare:



2 3 1

M( ) =2 => e


2 4 1 3

M( => e


4 1 2 3

M( ) =3 => e


5 3 4 1 2

M( ) =8 => e


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 2 3 5 4 3 1 2 5 4 3 1 2 4 5

(1,3)o = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 =

3 2 1 4 5 3 1 2 4 5 1 3 2 4 5

(2,3)o = 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 =

6 2 3 4 5 1 6 4 5 3 2 1 1 4 5 3 2 6

(2,5)o = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 =

1 5 3 4 2 6 1 4 5 3 2 6 1 4 2 3 5 6

(3,4)o = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 =

1 2 4 3 5 6 1 4 2 3 5 6 1 3 2 4 5 6

(2,3)o = 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-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 S astfel incit


7. Rezolvati in S 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

CAZUL I: d=4

e=5

=> a =b

σ(b =c

σ(c =a

i) a=1 => =b dar (1) =2 => b=2

σ(b =c => (2) =c dar (2) =3 => c=3

σ(c

=> X = 1 2 3 4 5

1 2 3 4 5

ii) a=2  => =b dar (2) =3 => b=3

σ(b =c => (3) =c dar (3) =1 => c=1

σ(c

=> X = 1 2 3 4 5

2 3 1 4 5

iii) a=3 => =b dar (3)=1 => b=1

σ(b =c => (1) =c dar (1)=2 => c=2


=>X = 1 2 3 4 5

3 1 2 4 5

CAZUL II: d=5

e=4

i) a=1

=> X = 1 2 3 4 5

1 2 3 5 4

ii) a=2

=> X = 1 2 3 4 5

2 3 1 5 4

iii) a=3

=> X = 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 S , 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 a <a <…<an

Pentru ce permutare Sn suma


este maxima.


Fie o (k,j)






11. Se dau numerele reale strict pozitive a <a <…<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)














loading...









Copyright © Contact | Trimite referat


Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu














loading...



Scriitori romani