Operații cu permutări

În acest videoclip, vom studia operațiile cu permutări de gradient și proprietățile acestora.

Pentru început, să ne reamintim câteva noțiuni necesare pentru înțelegerea acestor operații, respectiv proprietăți.

Ne vom reaminti cum realizăm compunerea funcților, care sunt proprietățile compunerii funcților,

ce înțelegem prin funcție inversă și ce este o permutare de gradient.

Dacă avem o funcție f definită pe o mulțime a cu valori într-o mulțime b și o funcție g definită pe mulțimea b cu valori în mulțimea c,

compus a funcției g cu funcție a f se notează așa și reprezintă o funcție definită pe mulțimea a cu valori în mulțimea c.

Dată prin relația g compus cu f de x este egal cu g de f de x pentru orice x aparținând mulțimea a.

Astfel, oricărui element din mulțimea a îi corresponde prin funcție f un unic element în mulțimea b,

iar fiecărui element din mulțimea b îi corespunde prin funcție g un unic element în mulțimea c.

În concluzie, fiecărui element din mulțimea a îi corresponde prin funcția g compus cu f un unic moment în mulțimea c.

O primă proprietate a compunerii funcțiilor este asociativitatea.

Astfel, pentru oricare trei funcții, h definită pe a cu valorin b, g definită pe b cu valorin c, f definită pe c cu valorin d,

f compus cu g totul compus cu h este egal cu f compus cu rezultatul compunerii lui g cu h.

Compunerea funcțiilor are și un element neutru.

Astfel, pentru orice funcție f definită pe mulțimea a cu valorin mulțimea b, există funcția identică 1a definită pe a cu valorin a

și funcția identică 1b definită pe b cu valorin b, astfel încât f compus cu 1a este egal cu f, iar 1b compus cu f este egal tot cu f.

Atenție! Compunerea funcțiilor nu este o operație comutativă.

O funcție f definită pe mulțimea a cu valori într-o mulțime b este inversabilă dacă există o altă funcție g definită pe b cu valorin a,

astfel încât f compus cu g să fie egal cu funcția identică definită pe b, iar g compus cu f să fie funcția identică definită pe mulțimea a.

Această funcție g nu este altceva decât inversa funcției f.

Ea se notează f la minus 1, dar atenție! Nu este egal cu 1 supra f.

O funcție este inversabilă dacă și numai dacă ea este bijectivă.

Numim permutare de grad n o funcție bijectivă definită pe mulțimea a cu valori în mulțimea a, unde mulțimea a este o mulțime formată din elementele 1, 2, respectiv n.

Mulțimea tuturor permutărilor de grad n se notează cu yes indice n.

Fie mulțimea a formată din elementele 1, 2, 3, respectiv n.

Sigma și delta, două permutări de grad n.

Asta înseamnă că sigma și delta sunt definite pe mulțimea a cu valori în mulțimea a, adică cele două funcții au același domeniu respectiv codomeniu, ceea ce permite compunerea lor.

Rezulta astfel funcția sigma compus cu delta definită pe mulțimea a cu valori în mulțimea a, dar și delta compus cu sigma definită pe mulțimea a cu valori în mulțimea a.

Sigma și delta sunt permutări, așadar sunt funcții bijective.

Compunerea a două funcții bijective este tot o funcție bijectivă, ceea ce ne permite să concluzionăm că rezultatul compunerii a două permutări de grad n este tot o permutare de grad n.

Așadar, sigma compus cu delta, dar și delta compus cu sigma aparțin lui yes n.

Compunerea a două permutări sau produsul a două permutări sigma și delta din yes n este tot o permutare.

Deci, sigma compus cu delta este tot o permutare de același grad, adică sigma compus cu delta este definită pe mulțimea a cu valori în mulțimea a

și este dată de relația sigma compus cu delta de k este egal cu sigma de delta de k, oricare ar fi k aparținând mulțimii a.

Pentru a ne ușura scrierea, utilizăm în loc de sigma compus cu delta, sigma ori delta.

Dacă permutarea sigma are reprezentarea 1, 2, respectiv n, cu imaginele sigma de 1, sigma de 2, respectiv sigma de n,

iar permutarea delta are reprezentarea 1, 2, respectiv n, cu imaginele delta de 1, delta de 2, delta de n,

sigma delta este o permutare cu reprezentarea 1, 2, respectiv n, cu imaginele sigma de delta de 1, sigma de delta de 2, respectiv sigma de delta de n.

Să considerăm acum, spre exemplu, două permutări, sigma și delta din S3.

Astfel, sigma are reprezentarea 1, 2, 3 cu imaginele 2, 1, 3.

Delta are reprezentarea 1, 2, 3 cu imaginele 3, 2, 1.

Sigma ori delta are reprezentarea 1, 2, 3 cu imaginele sigma de delta de 1, sigma de delta de 2, sigma de delta de 3.

Adică permutarea cu următoarele imagine.

Păi, cu delta de 1, delta de 1 este 3, adică vom avea sigma de 3.

Delta de 2, pe delta de 2 este tot 2 și atunci vom obține sigma de 2.

Iar lui 3, delta de 3, pe delta de 3 este 1, ceea ce înseamnă că vom avea aici sigma de 1.

Adică obținem permutarea cu reprezentarea 1, 2, 3 cu imaginele sigma de 3.

Sigma de 3 este 3, deci 3.

Sigma de 2, pe sigma de 2 este 1.

Sigma de 1, sigma de 1 este 2, adică 2.

Analog, delta compus cu sigma are reprezentarea 1, 2, 3 cu imaginele delta de sigma de 1, delta de sigma de 2, delta de sigma de 3.

Adică permutarea 1, 2, 3 cu imaginele sigma de 1, sigma de 1 este 2, deci delta de 2.

Sigma de 2, pe sigma de 2 este 1, deci delta de 1.

Sigma de 3, pe sigma de 3 este 3, deci delta de 3.

Adică permutarea 1, 2, 3 cu imaginele delta de 2, delta de 2 este 2, deci lui 1 îi corespunde 2.

Delta de 1, pe delta de 1 este 3, deci lui 2 va corespunde 3.

Delta de 3, pe delta de 3 este 1, deci lui 3 îi corespunde 1.

Observați cum permutarea sigma compus cu delta este diferită de delta compus cu sigma.

Dacă urmărim doar corespondențele, pentru compunerea permutării sigma cu delta putem proceda astfel.

Lui 1 îi corespunde 3, lui 3 îi corespunde 3, în consecință lui 1 va corespunde 3.

Lui 2 îi corespunde 2, lui 2 îi corespunde 1, în consecință lui 2 îi corespunde 1.

Lui 3 îi corespunde 1, lui 1 îi corespunde 2, astfel lui 3 îi corespunde 2.

Sau dacă vom calcula permutarea delta ori sigma, așezăm cele două permutări una lângă cealaltă

și urmărim corespondențele.

Adică, lui 1 îi corespunde 2, lui 2 îi corespunde 2, în consecință lui 1 îi corespunde 2.

Lui 2 îi corespunde 1, lui 1 îi corespunde 3, așadar lui 2 îi corespunde 3.

Lui 3 îi corespunde 3, iar lui 3 îi corespunde 1.

În concluzie, lui 3 îi corespunde 1.

Proprietățile compunerii permutărilor de gradient derivă din proprietățile compunerii funcțiilor.

Cum compunerea funcțiilor este o operație asociativă și compunerea permutărilor este o operație asociativă,

astfel, oricare ar fi sigma, delta și teta aparținându-i SN,

sigma ori delta, totul înmulțit cu teta, este egal cu sigma înmulțit cu rezultatul produsului lui delta cu teta.

Cum compunerea funcțiilor admite element neutru, funcția identică,

și compunerea permutărilor admite element neutru, permutarea identică.

Așadar, există permutarea identică E aparținându-i SN,

astfel încât, pentru orice permutare sigma aparținându-i SN,

sigma ori E este egal cu E ori sigma și este egal cu sigma.

Permutările sunt funcții bijective, în consecință inversabile.

Astfel, oricare ar fi permutarea sigma aparținându-i SN,

există sigma la minus 1 aparținându-i SN,

astfel încât, sigma ori sigma la minus 1 este egal cu sigma la minus 1 ori sigma și este egal cu E.

Iată cum putem determina inversa.

Pentru o permutare sigma de gradul N,

reprezentarea acestea este 1, 2, N

cu imaginile sigma de 1, sigma de 2, sigma de N.

Sigma la minus 1 se construiește astfel.

Sigma de 1, sigma de 2, sigma de N

cu imaginile 1, 2, N

și ordonăm apoi linia 1.

Luând acum o permutare sigma din S4,

sigma are următoarea reprezentare.

1, 2, 3, 4

cu imaginile 3, 1, 4, 2.

Sigma la minus 1 are următoarea reprezentare.

Luăm imaginile și le așezăm pe prima linie,

3, 1, 4, 2

cu imaginile 1, 2, 3, 4.

Adică, ordonând acum prima linie,

1, 2, 3, 4,

lui 1 îi corespunde 2.

Deci 2.

Lui 2 îi corespunde 4.

Deci 4.

3 îi corespunde 1,

iar lui 4 îi corespunde 3.

Aceasta este permutarea inversă.

Sau putem face și ordonarea în același timp.

Fie acum o permutare sigma din S5,

sigma are reprezentarea.

1, 2, 3, 4, 5

cu imaginile 3, 5, 2, 1, 4.

Sigma la minus 1 o determinăm astfel.

1, 2, 3, 4, 5

cu imaginile lui 1 îi corespunde 4.

Lui 2 îi corespunde 3.

Lui 3 îi corespunde 1.

Lui 4 îi corespunde 5.

Iar lui 5 îi corespunde 2.

Atenție!

Compunerea funcțiilor nu este o operație comutativă.

În consecință,

nici compunerea permutărilor nu este o operație comutativă.

Fie sigma

o permutare din Yesian.

Considerăm că sigma la 0

este permutare identică.

Sigma la puterea 1 este sigma.

Sigma la puterea 2

este sigma

ori sigma.

Atunci, deducem că puterea a iena

a permutării sigma

reprezintă

produsul permutării sigma

cu ea însăși

de ienori.

Oricare ar fi ien

un număr natural.

Să vedem acum cum calculăm

produsul a două puteri.

Sigma la m

înmulțit cu sigma la n

reprezintă sigma

înmulțit cu sigma

de m ori

înmulțit cu sigma

înmulțit cu sigma

de n ori.

Adică

avem m factor

înmulțit cu n factor

în total m plus n factor.

În concluzie,

sigma la puterea m plus n.

Deducem așadar

relația

sigma la m

înmulțit cu sigma la n

reprezintă sigma

la puterea m plus n

oricare ar fi

m și n

numere naturale.

Pentru calculul lui

sigma la m totul

la puterea n

scriem această putere

ca sigma la m

înmulțit cu

sigma la m

de n ori.

Obținem

sigma la puterea m

plus m

plus m

de n ori.

Și în final

sigma la puterea m

ori n.

Am obținut următoarea formulă

sigma la m totul

la puterea n este egal cu

sigma la puterea m

ori n oricare ar fi

m și n

numere naturale.

În următorul videoclip

vom vorbi despre transpoziție.

Imaginați-vă cum ar fi să componeți

două coduri Cesar.

Să zicem cu pasul 2

respectiv cu pasul 3.

Ce credeți că s-ar întâmpla?