Inversiunile unei permutări. Semnul unei permutări

Știm deja că o permutare de grad n este o funcție bijectivă sigma definită pe mulțimea a cu valori în mulțimea a,

unde mulțimea a este formată din elementele 1, 2, n, iar yes n este mulțimea permutărilor de grad n.

Ne vom concentra în acest videoclip asupra unui concept important în studiul permutărilor și anume paritatea unei permutări.

O utilizare a acestui concept o vom regăsi în definirea determinanților, dar este de mare ajutor în analiza solvabilității unei probleme.

Avem următorul șild de numere 1, 2, 3, 4, 5 și ne propunem să scriem aceste numere în următoarea ordine 5, 4, 2, 3, 1, respectând următoarea regulă.

Se pot schimba doar două numere în același timp. Cum voi proceda?

Am plecat de la șirul 1, 2, 3, 4, 5, voi schimba numărul 1 cu numărul 5, voi obține șirul 5, 2, 3, 4, 1.

Voi schimba acum numărul 4 cu numărul 2 și obțin șirul 5, 4, 3, 2, 1 și mai avem de făcut o singură schimbare și anume pe 3 cu 2 obținând șirul 5, 4, 2, 3, 1.

Te întreb dacă ai putea obține șirul cerut, deci plecând de la acest șir 1, 2, 3, 4, 5, să ajungi la șirul 5, 4, 2, 3, 1 în exact patru schimbări.

Sau dacă poți să faci acest lucru în cinci schimbări.

Te aștept cu rezolvarea problemei în secțiunea comentarii.

Fie o permutare sigma de grad ien, iar i și j, două elemente ale mulțimii 1, 2, ien cu i mai mic decât j.

Perechea ie-j poartă numele de inversiune a permutării sigma dacă sigma de i este mai mare decât sigma de j.

Numărul acestor perechi se notează cu m de sigma.

Să considerăm acum o permutare de grad 4, care are reprezentarea 1, 2, 3, 4, 4, 3, 1, 2.

Perechea 1, 2 este inversiune deoarece sigma de 1 este 4, sigma de 2 este 3.

Deci sigma de 1 e mai mare decât sigma de 2.

Perechea 1, 3 este și ea o inversiune pentru că sigma de 1 este 4, iar sigma de 3 este 1.

Sigma de 1 e mai mare decât sigma de 3.

Perechea 1, 4 este inversiune pentru că sigma de 1 este 4, iar sigma de 4 este egal cu 2.

Sigma de 1 e mai mare decât sigma de 4.

Perechea 2, 3 este și ea o inversiune pentru că sigma de 2 este egal cu 3, iar sigma de 3 este egal cu 1.

Așadar, sigma de 2 este mai mare decât sigma de 3.

Perechea 2, 4 este inversiune pentru că sigma de 2 este egal cu 3, iar sigma de 4 este egal cu 2.

Așadar, sigma de 2 este mai mare decât sigma de 4.

În total, numărul inversiunilor este, așa cum vedeți, 5.

Deci, în această situație, m de sigma este egal cu 5.

Care credeți că este permutarea cu numărul minim de inversiuni?

Nu poate fi vorba decât de permutarea identică care are reprezentarea 1, 2, n.

Pentru această permutare, numărul de inversiuni este 0.

Dar permutarea cu numărul maxim de inversiuni?

Va fi acea permutare în care elementelor 1, 2, n le corespund aceleași elemente, dar în ordine descrescătoare, adică n, n-1, respectiv 1.

Să calculăm numărul de inversiuni.

Elementul 1 formează cu toate celelalte elemente inversiuni, pentru că toate celelalte imagini sunt mai mici decât n.

Deci, perechea 1, 2 este inversiune ca și perechea 1, 3 ca și perechea 1, n.

Adică, în total, avem n-1 inversiuni.

2 va face cu toate elementele mai mari decât el inversiuni.

Adică, avem perechele 2, 3, 2, 4, respectiv 2, n.

Obținem așadar n-2 inversiuni.

Și așa mai departe.

Ultima inversiune este cea făcută de elementele n-1, respectiv n.

Deci, ultima inversiune este n-1, n, adică o inversiune.

Să însumăm aceste inversiuni.

Deci, m de sigma este egal cu n-1 plus n-2 plus puncte puncte plus 1.

Păi, regăsim în această sumă suma lui Gauss.

Și, în concluzie, m de sigma este n-1 înmulțit cu consecutivul lui, adică n, totusupra 2.

Păi, rezultatul acesta nu reprezintă altceva decât combinări de n luate câte 2.

Ce am obținut?

Am obținut că numărul de inversiuni poate să ia valoarea minimă 0 sau valoarea maximă combinări de n luate câte 2.

Adică 0 este mai mic sau egal decât m de sigma, care e mai mic sau egal decât combinări de n luate câte 2,

oricare ar fi sigma o permutare de gradient.

Cu ajutorul noțiunei de inversiune, vom defini noțiunea de semn sau signatură a unei permutări.

Fie sigma, permutare de gradient.

Numim semnul sau signatura permutării sigma numărul epsilon de sigma egal cu minus 1 totul la puterea m de sigma.

O permutare se numește permutare pară dacă signatura este egală cu 1,

iar permutarea sigma se numește permutare impară dacă signatura este egală cu minus 1.

Să considerăm acum permutarea sigma de gradul al patrulea 1, 2, 3, 4 cu imaginile 4, 3, 1, 2.

Este exemplul precedent.

Ne amintim că m de sigma l-am determinat ca fiind egal cu 5, dar să revedem aceste lucruri.

Avem inversiunea 1, 2, 1, 3, 1, 4, 2, 3 și 2, 4.

3, 4 nu formează o inversiune.

Atunci epsilon de sigma este egal cu minus 1 totul la puterea 5, adică minus 1.

Și în concluzie, permutarea sigma este o permutare impară.

Dacă vom considera acum o permutare delta cu reprezentarea 1, 2, 3, 4, 1, 4, 2, 3,

numarul de inversiuni îl calculăm astfel.

1 nu formează inversiune cu niciun element, cu niciun alt element, pentru că toate imaginile sunt mai mari decât 1.

2 formează două inversiuni, 2 cu 3, respectiv 2 cu 4.

3, de asemenea, nu formează inversiune cu 4, pentru că 2 este mai mic decât 3.

Epsilon de delta este egal cu minus 1 totul la puterea 2, adică 1.

Deci delta este o permutare impară.

Am văzut că permutarea identică are 0 inversiuni.

Signatura permutării identice este minus 1 la puterea 0, adică 1.

Permutarea identică este o permutare impară, dar o are transpoziția?

Ce paritate ar avea?

Dacă vom considera o transpoziție IJ cu reprezentarea 1, 2, I minus 1, I, I plus 1, K, J minus 1, J, N,

cu imaginele 1, 2, I minus 1, J, I plus 1, K, J minus 1, I, N,

niciunul dintre elementele de la 1 până la I minus 1 nu formează inversiune cu elementele mai mari decât ele.

Cum I este mai mic decât J, obținem că I va forma inversiune cu toate elementele I plus 1 până la J inclusiv.

Deci avem inversiunile I, I plus 1, I, I plus 2, I, K, I, J minus 1, I, J.

Numărul acestor inversiuni este egal cu J minus I.

De asemenea, elementele I plus 1 până la J minus 1 inclusiv vor forma inversiuni cu elementul J, adică mai avem inversiunile I plus 1, J,

I plus 2, J, iar ultimul ar fi J minus 1, J.

În total, aceste inversiuni sunt în număr de J minus I minus 1.

Adică numărul de inversiuni al acestei transpoziții este J minus I plus J minus I minus 1, adică 2 pe lângă J minus I minus 1.

Signatura transpoziției I, J este minus 1 la puterea m de sigma, adică minus 1, deoarece m de sigma este un număr impar.

Orice transpoziție este o permutare impară.