Permutari 3o6v4o

Permutari 1.Notiunea de permutare. Fie A o multime finita de „n“ elemente, adica A={1, 2, 3, …, n}. O functie bijectiva σ:AA 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τ :AA 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

j:k =i  σij (k ) = i : k = j k : k ≠ i , j 

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 σ(j). Numarul inversiunilor intr-o permutare se noteaza cu M(σ) <= Cn². 6.Signatura unei permutari. Fie σε Sn. Numarul (σ) =(-1) permutarii σ.

se numeste signatura (semnul)

M (σ ) ε (σ ) = (−1) ε (σ) = 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 2413 4123 σoτ si τoσ. σoτ =1 2 3 4 τoσ =1 2 3 4 3241 1342

2. Sa se determine numarul de inversiuni si signatura pentru fiecare dintre permutarile urmatoare: *123 231 M(σ) =2 => ε (σ) =1 *1234 2413 M(σ)=3 => ε (σ) =-1 *1234 4123 M(σ) =3 => ε (σ) =-1

*12345 53412 M(σ) =8 => ε (σ) =1 3. Fie permutarea σ = 1 2 3 4 5 . Sa se scrie σ ca produs de 31254 transpozitii. Aceeasi problema pentru permutarea τ=1 2 3 4 5 6 . 645321 *(4,5)oσ = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = σ1 12354 31254 31245 (1,3)oσ1 = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = σ2 32145 31245 13245 (2,3)oσ2 = 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 = e 13245 13245 12345  σ = (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 623451 645321 145326 (2,5)oτ1 = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = τ2 153426 145326 142356 (3,4)oτ2 = 1 2 3 4 5 6 o 1 2 3 4 5 6 = 1 2 3 4 5 6 = τ3 124356 142356 132456 (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

ε (σ ) = (−1)n(n −1) / 2 * n = 4k

⇒ ε (σ ) = (−1)4k (4k −1) / 2 =1

* n = 4k + 1

⇒ ε (σ ) = (−1)4k (4k +1) / 2 = 1

* n = 4k + 2

⇒ ε (σ ) = (−1)(4k +1)(4k + 2) / 2 = −1

* n = 4k + 3

⇒ ε (σ ) = (−1)(4k + 2)(4k +3) / 2 = −1

5. Sa se determine numarul inversiunilor permutarii σ. 1234... n n + 1 n + 2 n + 3...2n    2468 ... 2 n 1 3 5 ... 2 n − 1   ...

..........

............

......

.............................

......

............................

.....

M(σ)=1+2+3+4+ … +n = n(n+1)/2 6. Determinati σε S7 astfel incit 1234567  1234567  1234567    oσ o   =   7321654 3127456 5136472       −1 σ 1oσ oσ 2=σ 3 σ1 (σ 1−1 oσ 1) o (σ o σ 2) = σ 1−1 oσ 3 σ o σ 2 = σ 1−1 oσ 3σ 2−1 σ = σ 1−1 o σ 3 o σ 2−1 1234567  1234567  1234567  σ =   o   o   4327651 5136472 2315674       1234567  σ =   4267135  

7. Rezolvati in S5 ecuatia: σoX=Xoσ σ= 1 2 3 4 5 23154 X= 1 2 3 4 5 abcde Xoσ= 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 abcde 23154 bcaed σoX= 1 2 3 4 5 o 1 2 3 4 5 = 1 2 3 4 5 23154 abcde σ(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 => X1 = 1 2 3 4 5 12345 ii) a=2 => σ(2) =b dar σ(2) =3 => b=3 σ(b) =c => σ(3) =c dar σ(3) =1 => c=1 σ(c) =2 => X2 = 1 2 3 4 5 23145 iii) a=3 => σ(3) =b dar σ(3)=1 => b=1 σ(b) =c => σ(1) =c dar σ(1)=2 => c=2

=>X3 =

12345 31245 CAZUL II: d=5 e=4 i) a=1 => X4 = 1 2 3 4 5 12354 ii) a=2 => X5 = 1 2 3 4 5 23154 iii) a=3 => X6 = 1 2 3 4 5 3 1 2 5 4. 8. Fie permutare u = 1 2 3 4 . Sa se arate ca nu exista nici o 3421 permutare X ε S4, astfel incit X² =u. Ɛ(X²) = 1 Ɛ(u) =-1 => nu exista X. 9. Fie permutarea σ = 1 2 3 4 5 6 . Sa se determine i si j astfel 64i 3 j1 incit σ sa fie o permutare para (respectiv impara). i=2 sau i=5 j=5 j=2 *i=2 si j=5 => ε (σ) =-1 => permutarea este impara *i=5 si j=2 => ε (σ) =1 => permutare este para. 10. Se dau numerele reale strict pozitive a1 <…
n 1 Sσ = ∑ i=1 ai ∗ aσ (i ) este maxima. Fie τ =σo (k,j)  1 2 3... k ... j.... n  σ =   σ ( 1 ) σ ( 2 ) σ ( 3 ) ... σ ( k ) ... σ ( j ) ... σ ( n )    1 2 3... k ... j... n  τ =    σ (1n) σ ( 2 ) σ ( 3 )...σ ( j )...σ ( k )...σn  1 S′ = ∑ i=1 ai ∗ aτ (i ) ...

.................

...

...

..................

...

...............

.........

.............

.....

...

..................

.......

.........

.........

....

Sσ − S ′ rel="nofollow"> 0 => Sσ > S ′(aratam ) n n 1 1 Sσ − S ′ = ∑ −∑ i=1 ai ∗ aσ (i ) i =1 ai ∗ aτ (i ) n 1 1 1 Sσ − S ′ = ∑ + + − i=1 ai ∗ aσ (i ) ak ∗ aσ ( k ) aj ∗ aσ ( j ) n 1 1 1 −∑ − − i =1 ai ∗ aτ (i ) ak ∗ aτ ( k ) aj ∗ aτ ( j ) 1 1 1 1 Sσ − S ′ = + − − ak ∗ aσ ( k ) aj ∗ aσ ( j ) ak ∗ aτ ( k ) aj ∗ aτ ( j )

.......... .......... .......... ...

Sσ − S ′ =

1  1 1  1 1 1    +  − −  ak  aσ (k ) aσ ( j )  aj  aσ ( j ) aσ ( k ) 

Sσ − S ′ =

1  aσ ( j ) − aσ (k )  1  aσ (k ) − aσ ( j )   +   ak  aσ ( j ) ∗ aσ (k )  aj  aσ ( j ) ∗ aσ (k ) 

(aσ ( j ) − aσ (k )) ∗ (aj − ak ) >0 ak ∗ aj ∗ aσ (k ) ∗ aσ ( j ) ⇒ aσ ( j ) − aσ (k ) > 0 ⇒ aσ ( j ) > aσ (k ) ⇒ σ = e. ..............................................

=

11. Se dau numerele reale strict pozitive a1 <… =1). τ=σo(k,j) ................

....

2 3... k ... j... n   1 σ =   σ ( 1 ) σ ( 2 ) σ ( 3 )... σ ( k )... σ ( j )... σ ( n )   2 3... k ... j... n  1 τ =   σ ( 1 ) σ ( 2 ) σ ( 3 )... σ ( j )... σ ( k )... σ ( n )   ....

...........................

.........................

....

.....

....................

.................

....

.............................

....

..................

.......................

.................

.................

......................

....

n 1  Pτ = ∏  air + s  aτ (i )  i=1 Pσ > Pτ ( Aratam) n 1   r 1   r 1      ⇒ ∏  air + ∗ + ∗ + aj s   ak s  s  > aσ (i )   aσ (k )   aσ ( j )  i=1 n r 1   r 1   r 1       + ∗ + ∗ + ∏  ai s   ak s   aj s  aσ (i )   aσ ( j )   aσ (k )  i=1 ...............

 1   r 1   r 1   r 1        ⇒  ak r + ∗ + > + ∗ + aj aj s  s   ak s  s  aσ (k )   aσ ( j )   aσ ( j )   aσ (k )   s r s ⇒ air − aj ∗ aσ ( j ) − aσ (i ) ≤ 0 ⇒ σ (i ) < σ ( j ) ⇒ σ = e.

(

) (

)

12. Pentru ce permutare σε Sn suma n 1 Sσ = ∑ i=1 ai ∗ aσ (i ) este minima? Fie τ =σo(k,j)  1 2 3... k ... j.... n  σ =    σ (1) σ ( 2 ) σ ( 3 )...σ ( k )...σ ( j )...σ ( n )   1 2 3... k ... j... n  τ =   σ ( 1 ) σ ( 2 ) σ ( 3 ) ... σ ( j ) ... σ ( k ) ... σ n   ...

.................

...

...

..................

...

...............

.........

.............

.....

...

..................

....

n 1 S′ = ∑ i=1 ai ∗ aτ (i )

.......

.........

.........

Sσ − S ′ > 0 = >Sσ > S ′(aratam) n n 1 1 Sσ − S ′ = ∑ −∑ i=1 ai ∗ aσ (i ) i=1 ai ∗ aτ (i ) n 1 1 1 Sσ − S ′ = ∑ + + − i=1 ai ∗ aσ (i ) ak ∗ aσ (k ) aj ∗ aσ ( j ) n 1 1 1 −∑ − − i=1 ai ∗ aτ (i ) ak ∗ aτ (k ) aj ∗ aτ ( j ) 1 1 1 1 Sσ − S ′ = + − − ak ∗ aσ (k ) aj ∗ aσ ( j ) ak ∗ aτ (k ) aj ∗ aτ ( j )

.................................

Sσ − S ′ =

1  1 1  1 1 1    +  − −  ak  aσ (k ) aσ ( j )  aj  aσ ( j ) aσ (k ) 

Sσ − S ′ =

1  aσ ( j ) − aσ (k )  1  aσ (k ) − aσ ( j )   +   ak  aσ ( j ) ∗ aσ (k )  aj  aσ ( j ) ∗ aσ (k ) 

(aσ ( j ) − aσ (k )) ∗ (aj − ak ) >0 ak ∗ aj ∗ aσ (k ) ∗ aσ ( j ) ⇒ aσ ( j ) − aσ (k ) > 0 ⇒ aσ ( j ) > aσ (k ) ⇒ σ = e. ..............................................

=

3 1 2 σ =   n n −1 n − 2 ................

.....

..........................

......

n  1 

.....................................

.............................

13. Se dau numerele reale a1 < …
Fie τ =σo(k,j)  1 2 3... k ... j.... n  σ =   σ ( 1 ) σ ( 2 ) σ ( 3 ) ... σ ( k ) ... σ ( j ) ... σ ( n )    1 2 3... k ... j... n  τ =   σ ( 1 ) σ ( 2 ) σ ( 3 ) ... σ ( j ) ... σ ( k ) ... σ n   ...

.................

...

...

..................

...

...............

.........

.............

.....

...

..................

.......

.........

.........

....

 Copyright www.ReferateOnline.com Cel mai complet site cu referate n Sτ = ∑ ai ∗aτ(i ) i=1 Sσ − Sτ rel="nofollow"> 0 n n ⇒Sσ − Sτ = ∑ ai ∗aσ(i ) − ∑ ai ∗aτ(i ) i=1 i=1 n ⇒Sσ − Sτ = ∑ ai ∗aσ(i ) + aj ∗aσ( j ) + ak ∗aσ( k ) i=1 n − ∑ ai ∗aτ(i ) − aj ∗aτ( j ) − ak ∗aτ(k ) i=1 ⇒Sσ − Sτ = aj ∗aσ( j ) + ak ∗aσ(k ) − aj ∗aτ( j ) − ak ∗aτ( k ) ⇒Sσ − Sτ = aj ∗aσ( j ) + ak ∗aσ(k ) − aj ∗aσ( k ) − ak ∗aσ( j ) ⇒Sσ − Sτ = aj [ aσ( j ) − aσ( k )] + ak [ aσ( k ) − aσ( j )] ⇒(aj − ak )[ aσ( j ) − aσ( k )] > 0 aj − ak > 0 ⇒aσ( j ) − aσ( k ) > 0 ⇒σ( j ) >σ( k ) ⇒σ = e. .......... .......... .......... .......... .......... .......... .......... .......... ....