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