• Referate Anatomie
• Referate Astronomie
• Referate Automatica
• Referate Biologie
• Referate Chimie
• Referate Diverse
• Referate Drept
• Referate Economie
• Referate Engleza
• Referate Filosofie
• Referate Fizica
• Referate Franceza
• Referate Geografie
• Referate Germana
• Referate Informatica
• Referate Istorie
• Referate Marketing
• Matematica
• Referate Medicina
• Referate Muzica
• Referate Psihologie
• Referate Religie
• Referate Romana

Link sponsorizat :

Permutari

1. Notiunea de permutare.
Fie A o multime finita de „n" elemente, adica A={1, 2, 3, …, n}.
O functie bijectiva ó: AA 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ô: AA 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 ó.
(ó) = 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 (ó) = Ð (ó (i)- ó (j))/(i-j).
Teorema 3. Daca ó, ô å Sn atunci (ó oô) = (ó) o (ô).
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 => (ó) =1
* 1 2 3 4
2 4 1 3
M(ó)=3 => (ó) =-1
* 1 2 3 4
4 1 2 3
M(ó) =3 => (ó) =-1
* 1 2 3 4 5
5 3 4 1 2
M(ó) =8 => (ó) =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 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
ð ô = (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 ó å 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
=...

Nota: Textul de mai sus reprezinta doar un extras din referat. Pentru versiunea completa a documentului apasa butonul Download.