Trimite referat
Referatele si lucrarile oferite de Clopotel.ro au scop educativ si orientativ pentru cercetare academica.

Permutari

Materie: Matematica
Accesari: 25.446
Download-uri: 2.269
Nota: 6.00 (986 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
X

Raporteaza-ne problema !

Te rugam sa ne spui ce problema ai intampinat cu acest referat. Prin contributia ta acest site va deveni cea mai tare resursa de referate online din Romania. Iti multumim pentru sprijinul acordat!





Acest site foloseste cookies. Prin navigarea pe acest site, va exprimati acordul asupra folosirii cookie-urilor. Detalii aici OK