Post on 20-Jan-2016
description
PERMUTPERMUTĂRI
PrezentareaPrezentarea noţiunilor teoretice
Definiţie:
:{1,2,….,n} {1,2,….,n}
funcţie bijectivă , poartă denumirea de permutare de ordin n.
Se notează: =
Ex: :{1,2,3} {1,2,3} cu (1)=2, (2)=3, (3)=1
=
)()....2()1(
...........21
n
n
132
321
Noţiunea de permutare identică, Sn
Noţiunea de transpoziţie
e = se numeşte permutare identică
Se defineşte Sn, mulţimea tuturor permutărilor de ordin n.
card Sn =n!
Transpoziţii = (i,j)
n
n
...........21
...........21
nij
nji
...........21
...........21 notatie
Compunerea permutărilor
( )(k)= ( (k)) Exemplu:
= =
= =
=
Observaţii: 1. Nu se compun decât permutări de acelaşi ordin
2. În general, compunerea a două permutări nu este comutativă.
3214
4321
2413
4321
3214
4321
2413
4321
1342
4321
2413
4321
3214
4321 =
4132
4321
Proprietăţi ale compunerii permutărilor
Asociativitatea compunerii permutărilor
, , Sn avem
Compunerea permutărilor admite element neutru Există e Sn astfel încât Sn să avem
)( )()(
)(
ee
Orice permutare admite inversă
ar fi Sn, există ar fi
Exemplu: = =
= =
= =
)( )( 1 Sn astfel încât e 11
42135
543211
15243
54321
1
42135
54321
15243
54321
54321
54321
1
15243
54321
42135
54321
54321
54321
Descompunerea unei permutări ca produs de transpoziţii
Exemplu:
= =(1,5) =
=(2,3) =
=(3,5) =
=(4,5) =
42135
543211
42531
54321
2
3
4
43521
54321
45321
54321
54321
54321
)5,1()3,2()5,3()5,4(
1
2
3
Inversiunea unei permutări
=
Spunem că avem o inversiune cu (i,j), cu i<j <
Exemplu:
=
Inversiunile sunt: 1,3 2,3 3,4 1,4 2,4 1,5 2,5 Permutarea are 7 inversiuni.
Numărul de inversiuni ale unei permutări se notează cu
)()....()..()..2()1(
............................21
nji
nji
)(i )( j
31254
54321
m
Signatura unei permutări Signatura (semnul permutării) este
Dacă =1 avem permutare pară.
Dacă = -1 avem permutare impară.
O altă metodă de stabilire a signaturii este =
Proprietate:
Observaţie: O transpoziţie este întotdeauna impară.
=
m)1(
nji ij
ij
1
)()(
42135
54321
)(
1)1())5,4(())5,3(())5,2(())5,1(()( 4