Acest site foloseste cookies. Prin navigarea pe acest site, va exprimati acordul asupra folosirii cookie-urilor. Citeste mai mult... X
Referatele si lucrarile oferite de Clopotel.ro au scop educativ si orientativ pentru cercetare academica.

Permutari

Materie: Matematica
Accesari: 22.551
Download-uri: 2.191
Nota: 5.92 (777 note)
Am probleme cu acest referat!

1 2 3
4 5 6
7 8 9


Download Referat - Permutari
Publicitate:

Trimis de
din 12 Noiembrie 2002

PERMUTARI



1.Notiunea de permutare.
Fie A o multime finita de n elemente, adica A={1, 2, 3, , n}.
O functie bijectiva s:AA se numeste permutare (substitutie)
de gradul n.

P:Numarul tuturor permutarilor de ordin n este egal cu n! .

2.Produsul (compunerea) permutarilor.
Fie s si t doua permutari de acelasi grad n.
Prin compunerea celor doua permutari se intelege o noua
permutare s ot :AA cu prop. (s ot)(k)=s(t(k)).

3.Proprietati ale compunerii permutarilor.
P1: Asociativitatea compunerii
(sot)of=so(tof), oricare ar fi s;t;f e Sn.
P2: Compunerea permutarilor nu este comutativa
sot=tos
P3: Element neutru
so?=?os oricare ar fi s e Sn
?(i)=i permutarea identica



P4: Element simetrizabil
sos=sos=?


4.Transpozitii.
Se numeste transpozitie o permutare de forma s(i,j) sau (i,j) cu proprietatea
Proprietati:
P1: sij =e
P2: sij = sij
P3: sij = sji
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 s o pereche de elemente (i,j) i<j cu proprietatea ca s(i)> s(j).

Numarul inversiunilor intr-o permutare se noteaza cu M(s) <= Cn.

6.Signatura unei permutari.
Fie se Sn. Numarul e(s) =(-1) se numeste signatura (semnul) permutarii s.


e (s) = 1 daca M(s) este par
-1 daca M(s) este impar
*s se numeste permutare para daca are un numar par de
inversiuni.
*s se numeste permutare impara daca are un numar impar de
inversiuni.

Teorema 1. Orice transpozitie este o permutare impara.
Teorema 2. Daca s e Sn atunci e (s) = ? ( s(i)- s(j) )/(i-j).
Teorema 3. Daca s,t eSn atunci e (sot) =e (s) o e (t).
Teorema 4. Daca s eSn este o permutare atunci s poate fi descompusa ca produs de transpozitii.

Obs: Daca s 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 s=1 2 3 4 si t=1 2 3 4 . Sa se calculeze
2 4 1 3 4 1 2 3
sot si tos.
sot =1 2 3 4 tos =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(s) =2 => e (s) =1
* 1 2 3 4
2 4 1 3
M(s)=3 => e (s) =-1
* 1 2 3 4
4 1 2 3
M(s) =3 => e (s) =-1
* 1 2 3 4 5
5 3 4 1 2
M(s) =8 => e (s) =1

3. Fie permutarea s = 1 2 3 4 5 . Sa se scrie s ca produs de
3 1 2 5 4
transpozitii. Aceeasi problema pentru permutarea
t=1 2 3 4 5 6 .
6 4 5 3 2 1
*(4,5)os = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = s1
1 2 3 5 4 3 1 2 5 4 3 1 2 4 5
(1,3)os1 = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = s2
3 2 1 4 5 3 1 2 4 5 1 3 2 4 5
(2,3)os2 = 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
s = (4,5)o(1,3)o(2,3)


*(1,6)ot = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = t1
6 2 3 4 5 1 6 4 5 3 2 1 1 4 5 3 2 6
(2,5)ot1 = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = t2
1 5 3 4 2 6 1 4 5 3 2 6 1 4 2 3 5 6
(3,4)ot2 = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = t3
1 2 4 3 5 6 1 4 2 3 5 6 1 3 2 4 5 6
(2,3)ot3 = e
t = (1,6)o(2,5)o(3,4)o(2,3).

4. Fie permutarea se S2n
s = 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 s.
Sa se determine n astfel incit s sa fie para (respectiv impara).
M(s)=1+2+3++ n-1=n(n-1)/2


5. Sa se determine numarul inversiunilor permutarii s.

M(s)=1+2+3+4+ +n = n(n+1)/2

6. Determinati se S7 astfel incit

7. Rezolvati in S5 ecuatia:
soX=Xos s= 1 2 3 4 5
2 3 1 5 4
X= 1 2 3 4 5
a b c d e

Xos= 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

soX= 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 s(a) s(b) s(c) s(d) s(e)
=> s(a) =b
s(b) =c
s(c) =a
s(d) =e
s(e) =d => d,e e {4,5}
CAZUL I: d=4
e=5
=> s(a) =b
s(b) =c
s(c) =a
i) a=1 => s(1) =b dar s(1) =2 => b=2
s(b) =c => s(2) =c dar s(2) =3 => c=3
s(c) =1
=> X1 = 1 2 3 4 5
...

Atentie : Textul de mai sus este doar un preview al referatului, pentru a vedea daca continutul acestui referat te poate ajuta. Pentru varianta printabila care poate sa contina imagini sau tabele apasa butonul de 'download' !!!
Download Referat - Permutari