Inversiuni și semnul unei permutări

Un program de sortare primește lista $3,1,2$ și trebuie să o aducă la $1,2,3$ schimbând între ele numai elemente vecine. Cu două schimbări reușește: întâi $3$ cu $1$, apoi $3$ cu $2$. Pentru lista $4,3,2,1$ îi trebuie șase schimbări, iar pentru $1,2,3,4$ niciuna. Numărul acesta — câte schimbări de vecini sunt necesare — măsoară cât de „amestecată" este lista, iar el se poate citi direct din listă, fără să faci nicio sortare: numeri perechile aflate în ordine greșită.

Perechile acelea se numesc inversiuni, iar de la ele pornește tot ce urmează. Din numărul lor scoatem un semn, $+1$ sau $-1$, atașat fiecărei permutări — ultima piesă de care avem nevoie ca să scriem determinantul de ordin n ca o sumă cu semne alternante. Ca și în lecția precedentă, Permutări: definiție, notație și compunere, programa cere subiectul strict ca instrument: definim inversiunea, numărăm, luăm semnul și mergem mai departe.

Ce vei învăța

• Vei ști să definești o inversiune a unei permutări și să scrii lista completă a inversiunilor ei.
• Vei ști să numeri inversiunile metodic, fără să pierzi niciuna și fără să numeri de două ori.
• Vei ști să calculezi semnul (signatura) $\epsilon (\sigma )=(-1{)}^{m(\sigma )}$ și să spui dacă o permutare este pară sau impară.
• Vei ști care este numărul maxim de inversiuni al unei permutări de grad $n$ și când se atinge.
• Vei ști cum se schimbă semnul când schimbi între ele două valori ale permutării.
• Vei ști să folosești regula $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\cdot \epsilon (\tau )$ pentru a afla semnul unei compuneri fără să o calculezi.

Hai să descoperim împreună

1. Ce este o inversiune

Într-o permutare, numerele de pe linia a doua sunt, în general, „în dezordine" față de ordinea crescătoare. Măsurăm dezordinea numărând perechile care se contrazic.

Definiție. Fie $\sigma \in S_n$. O pereche $(i,j)$ cu $1\le i<j\le n$ se numește inversiune a permutării $\sigma$ dacă

$$\sigma (i)>\sigma (j).$$

Cu alte cuvinte: pozițiile sunt în ordine crescătoare, dar valorile de pe ele sunt în ordine descrescătoare. Numărul inversiunilor lui $\sigma$ se notează $m(\sigma )$.

Atenție la ce se numără: perechile de poziții, nu valorile și nu numărul de numere „mutate". Într-o permutare de grad $n$ există $\frac{n(n-1)}{2}$ perechi de poziții cu $i<j$, iar fiecare este ori inversiune, ori nu.

Să luăm

$$\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right).$$

Perechile de poziții sunt $(1,2)$, $(1,3)$ și $(2,3)$. Verificăm pe rând: $\sigma (1)=2<3=\sigma (2)$, deci $(1,2)$ nu e inversiune; $\sigma (1)=2>1=\sigma (3)$, deci $(1,3)$ este inversiune; $\sigma (2)=3>1=\sigma (3)$, deci și $(2,3)$ este inversiune. Prin urmare $m(\sigma )=2$.

2. Cum se numără fără greșeală

Verificarea perechilor una câte una funcționează la grad $3$, dar la grad $5$ ar însemna zece verificări. Metoda de lucru este alta, mai rapidă și mai sigură:

Parcurgi linia a doua de la stânga la dreapta și, pentru fiecare număr, numeri câte numere mai mici decât el stau la dreapta lui. Aduni toate aceste numere.

Fiecare pereche este numărată exact o dată — la elementul din stânga ei — deci nu se poate nici sări, nici dubla.

Un exemplu de grad $4$, cu $\alpha$ având pe linia a doua valorile $3,1,4,2$:

• la dreapta lui $3$ stau $1,4,2$; mai mici decât $3$ sunt $1$ și $2$, deci $2$ inversiuni;
• la dreapta lui $1$ stau $4,2$; niciunul mai mic, deci $0$;
• la dreapta lui $4$ stă $2$; mai mic, deci $1$;
• la dreapta lui $2$ nu mai stă nimic, deci $0$.

Total: $m(\alpha )=2+0+1+0=3$. Scrise ca perechi de poziții, inversiunile sunt $(1,2)$, $(1,4)$ și $(3,4)$ — se pot verifica una câte una, ca la punctul anterior.

3. Cele două extreme

Permutarea identică nu are nicio inversiune: valorile sunt deja în ordine crescătoare, deci $m(e)=0$.

La capătul celălalt se află permutarea „răsturnată", cea care are pe linia a doua numerele în ordine descrescătoare, $n,n-1,\dots ,2,1$. La ea orice pereche de poziții este inversiune, deci

$$m({\sigma }_{\max })=\frac{n(n-1)}{2}.$$

Pentru $n=3$ maximul este $3$ (atins de permutarea cu linia a doua $3,2,1$), pentru $n=4$ este $6$ (linia a doua $4,3,2,1$), pentru $n=5$ este $10$. Orice permutare de grad $n$ are deci $0\le m(\sigma )\le \frac{n(n-1)}{2}$ — o verificare rapidă a răspunsului: dacă îți iese $m=8$ la o permutare de grad $4$, ai greșit sigur.

4. Semnul unei permutări

Din numărul de inversiuni scoatem un singur bit de informație: paritatea lui.

Definiție. Semnul (sau signatura) permutării $\sigma \in S_n$ este numărul

$$\epsilon (\sigma )=(-1{)}^{m(\sigma )}\in \{-1,+1\}.$$

Permutarea se numește pară dacă $\epsilon (\sigma )=+1$ (adică $m(\sigma )$ este par) și impară dacă $\epsilon (\sigma )=-1$ (adică $m(\sigma )$ este impar).

Pentru exemplele de mai sus: $m(\sigma )=2$, deci $\epsilon (\sigma )=(-1{)}^2=+1$ și $\sigma$ este pară; $m(\alpha )=3$, deci $\epsilon (\alpha )=-1$ și $\alpha$ este impară. Permutarea identică are $m(e)=0$, deci $\epsilon (e)=+1$: identitatea este întotdeauna pară.

Observă că semnul nu reține cât de amestecată e permutarea, ci doar dacă numărul de inversiuni e par sau impar. Pare puțin, dar exact atât ne trebuie: la determinant, fiecare termen primește semnul $+$ sau $-$, nimic mai mult.

5. Tabelul complet al lui $S_3$

Merită scris o dată în întregime, pentru că îl vei recunoaște, peste două lecții, în cele șase produse ale determinantului de ordin $3$.

Trei permutări pare și trei impare — jumătate-jumătate. Același lucru se întâmplă în $S_4$: dintre cele $24$ de permutări, $12$ sunt pare și $12$ impare. Este o observație pe care o poți verifica prin numărare directă la gradele mici; la clasa a XI-a ne oprim la constatare, pentru că demonstrația generală cere unelte din afara programei.

6. Ce se întâmplă dacă schimbi două valori între ele

Aceasta este proprietatea de care va depinde, peste câteva lecții, întreg comportamentul determinanților la schimbarea a două linii.

Dacă într-o permutare schimbi între ele două valori de pe linia a doua (lăsând restul pe loc), semnul permutării se schimbă.

Verificăm pe permutarea cu linia a doua $2,3,1$, care are $m=2$ și $\epsilon =+1$. Schimbăm între ele valorile de pe pozițiile $1$ și $2$; obținem linia a doua $3,2,1$, cu $m=3$ și $\epsilon =-1$. Semnul s-a schimbat.

Încă un control, pe altă pereche: din $2,3,1$ schimbăm pozițiile $2$ și $3$ și obținem $2,1,3$, cu $m=1$ și $\epsilon =-1$. Din nou semnul s-a schimbat. La fel se întâmplă pentru orice permutare și orice pereche de poziții — se poate verifica exhaustiv la gradul $3$ și la gradul $4$, iar noi o folosim ca atare.

Reține și forma slabă, dar utilă în verificări: schimbând două valori, numărul de inversiuni își schimbă paritatea (poate crește sau scădea, dar niciodată cu un număr par).

7. Semnul unei compuneri și al unei inverse

La compunere, semnele se comportă cum te-ai aștepta de la niște numere $\pm 1$:

$$\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\cdot \epsilon (\tau ),\epsilon ({\sigma }^{-1})=\epsilon (\sigma ).$$

Le verificăm pe exemplul-etalon din lecția precedentă. Fie

$$\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right),\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right),\sigma \circ \tau =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right).$$

Din tabelul de la punctul $5$ citim $m(\sigma )=2$, deci $\epsilon (\sigma )=+1$; $m(\tau )=1$, deci $\epsilon (\tau )=-1$; $m(\sigma \circ \tau )=3$, deci $\epsilon (\sigma \circ \tau )=-1$. Într-adevăr,

$$\epsilon (\sigma \circ \tau )=-1=(+1)\cdot (-1)=\epsilon (\sigma )\cdot \epsilon (\tau ).$$

Pentru inversă: ${\sigma }^{-1}$ are linia a doua $3,1,2$, deci $m({\sigma }^{-1})=2$ și $\epsilon ({\sigma }^{-1})=+1=\epsilon (\sigma )$. Rezultatul are și o explicație simplă: perechile inversate ale lui ${\sigma }^{-1}$ sunt exact perechile inversate ale lui $\sigma$, privite invers, deci numărul lor este același.

O precizare de onestitate matematică: cele două egalități se verifică aici pe exemple și se folosesc ca instrument, așa cum cere programa. Demonstrația lor generală ar cere descompuneri care nu fac parte din materia clasei a XI-a. Utilitatea practică e imediată: ca să afli semnul unei compuneri nu mai trebuie să calculezi compunerea — înmulțești semnele.

8. La ce ne trebuie semnul

Fereastra spre lecțiile următoare, ca să știi de ce ai învățat toate acestea.

Determinantul unei matrice pătratice de ordin $n$ va fi o sumă de $n!$ produse. Fiecare produs ia câte un element din fiecare linie și din fiecare coloană — adică este condus de o permutare $\sigma \in S_n$, care spune din ce coloană se ia elementul liniei $i$. Iar fiecare produs intră în sumă cu semnul $\epsilon (\sigma )$.

Consecința se vede numărând: la ordinul $2$ vor fi $2!=2$ produse, unul cu plus și unul cu minus; la ordinul $3$ vor fi $3!=6$ produse, trei cu plus (permutările pare din tabelul de la punctul $5$) și trei cu minus. Când vei întâlni, la lecția Determinantul de ordinul al treilea: regula lui Sarrus și regula triunghiului, o rețetă cu exact trei produse adunate și trei scăzute, vei ști de unde vine numărul $6$ și de unde vine repartiția semnelor.

Exemple rezolvate

Exemplul 1 — Lista inversiunilor, scrisă complet

Determinați toate inversiunile și numărul $m(\sigma )$ pentru $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 1& 3& 2\end{array}\right)$.

Rezolvare. Parcurgem linia a doua și numărăm, pentru fiecare valoare, câte valori mai mici stau la dreapta ei:

• $4$: la dreapta stau $1,3,2$, toate mai mici — $3$ inversiuni, adică perechile $(1,2)$, $(1,3)$, $(1,4)$;
• $1$: la dreapta stau $3,2$, niciuna mai mică — $0$;
• $3$: la dreapta stă $2$, mai mic — $1$ inversiune, perechea $(3,4)$;
• $2$: nimic la dreapta — $0$.

Deci $m(\sigma )=3+0+1+0=4$, iar inversiunile sunt $(1,2)$, $(1,3)$, $(1,4)$, $(3,4)$. Control: $4\le \frac{4\cdot 3}{2}=6$, deci valoarea e plauzibilă.

Exemplul 2 — Semnul a două permutări de grad 4

Stabiliți dacă permutările cu linia a doua $2,4,1,3$ și $2,1,4,3$ sunt pare sau impare.

Rezolvare. Pentru prima: la dreapta lui $2$ stă $1$ (o inversiune); la dreapta lui $4$ stau $1$ și $3$ (două inversiuni); la dreapta lui $1$ nu e nimic mai mic; la dreapta lui $3$ nici atât. Deci $m=1+2=3$, de unde $\epsilon =(-1{)}^3=-1$: permutarea este impară.

Pentru a doua: la dreapta lui $2$ stă $1$ (o inversiune); la dreapta lui $1$ nimic mai mic; la dreapta lui $4$ stă $3$ (o inversiune); la dreapta lui $3$ nimic. Deci $m=2$ și $\epsilon =+1$: permutarea este pară.

Exemplul 3 — Permutarea răsturnată

Calculați $m(\sigma )$ și $\epsilon (\sigma )$ pentru permutarea de grad $5$ cu linia a doua $5,4,3,2,1$.

Rezolvare. Orice pereche de poziții este inversiune, pentru că valorile scad de la stânga la dreapta. Numărul perechilor este

$$\frac{5\cdot 4}{2}=10,$$

deci $m(\sigma )=10$ și $\epsilon (\sigma )=(-1{)}^{10}=+1$: permutarea este pară.

Merită observat că $\epsilon$ depinde de grad: permutarea răsturnată de grad $4$ are $m=6$, deci e tot pară, dar cea de grad $3$ are $m=3$ și e impară. Nu există o regulă „răsturnata e mereu pară".

Exemplul 4 — Semnul unei compuneri, fără a calcula compunerea

Fie $u$ și $v$ permutările de grad $4$ cu liniile a doua $3,1,4,2$, respectiv $2,4,1,3$. Stabiliți semnul lui $u\circ v$ fără a calcula compunerea, apoi verificați rezultatul calculând-o.

Rezolvare. Numărăm inversiunile fiecăreia. Pentru $u$ (linia a doua $3,1,4,2$): $3$ are la dreapta pe $1$ și $2$ (două inversiuni), $1$ are $0$, $4$ îl are pe $2$ (una), $2$ are $0$; deci $m(u)=3$ și $\epsilon (u)=-1$. Pentru $v$ (linia a doua $2,4,1,3$): $2$ îl are pe $1$ (una), $4$ îi are pe $1$ și $3$ (două), restul $0$; deci $m(v)=3$ și $\epsilon (v)=-1$.

Prin urmare $\epsilon (u\circ v)=(-1)\cdot (-1)=+1$: compunerea este pară.

Verificare. $(u\circ v)(1)=u(2)=1$; $(u\circ v)(2)=u(4)=2$; $(u\circ v)(3)=u(1)=3$; $(u\circ v)(4)=u(3)=4$. Deci $u\circ v=e$, care are $m=0$ și $\epsilon =+1$. ✓ (Cele două permutări sunt, de fapt, una inversa celeilalte.)

Exemplul 5 — Schimbarea a două valori

Permutarea $\sigma$ de grad $4$ are linia a doua $1,4,2,3$. Calculați $\epsilon (\sigma )$, apoi schimbați între ele valorile de pe pozițiile $1$ și $3$ și calculați semnul noii permutări.

Rezolvare. Pentru $\sigma$: $1$ nu are nimic mai mic la dreapta; $4$ îi are pe $2$ și $3$ (două inversiuni); $2$ are $0$; $3$ are $0$. Deci $m(\sigma )=2$ și $\epsilon (\sigma )=+1$.

Schimbând valorile de pe pozițiile $1$ și $3$ obținem linia a doua $2,4,1,3$. Pentru ea: $2$ îl are pe $1$ (una); $4$ îi are pe $1$ și $3$ (două); restul $0$. Deci $m=3$ și $\epsilon =-1$.

Semnul s-a schimbat, așa cum spune regula de la punctul $6$ — deși numărul de inversiuni a crescut doar cu $1$. Ce contează nu e cu cât se schimbă $m$, ci că paritatea lui se schimbă întotdeauna.

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră permutările $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$ și $\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 4& 3\end{array}\right)$ din $S_4$. a) Calculați $m(\sigma )$ și $m(\tau )$ și stabiliți paritatea fiecăreia. b) Determinați $\epsilon (\sigma \circ \tau )$ folosind proprietatea semnului. c) Calculați $\sigma \circ \tau$ și verificați rezultatul de la punctul b) numărând direct inversiunile.

Rezolvare. a) Pentru $\sigma$ (linia a doua $2,3,4,1$): fiecare dintre $2$, $3$, $4$ îl are pe $1$ la dreapta, deci $m(\sigma )=3$ și $\sigma$ este impară, $\epsilon (\sigma )=-1$. Pentru $\tau$ (linia a doua $2,1,4,3$): $2$ îl are pe $1$, $4$ îl are pe $3$, deci $m(\tau )=2$ și $\tau$ este pară, $\epsilon (\tau )=+1$.

b) $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\cdot \epsilon (\tau )=(-1)\cdot (+1)=-1$, deci compunerea este impară.

c) Calculăm compunerea (întâi $\tau$, apoi $\sigma$):

$$(\sigma \circ \tau )(1)=\sigma (2)=3,(\sigma \circ \tau )(2)=\sigma (1)=2,(\sigma \circ \tau )(3)=\sigma (4)=1,(\sigma \circ \tau )(4)=\sigma (3)=4,$$

deci $\sigma \circ \tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 1& 4\end{array}\right)$. Numărăm inversiunile: $3$ îi are la dreapta pe $2$ și $1$ (două); $2$ îl are pe $1$ (una); $1$ și $4$ nu aduc nimic. Deci $m(\sigma \circ \tau )=3$ și $\epsilon (\sigma \circ \tau )=-1$ — exact valoarea prezisă la b). ✓

Să exersăm

La fiecare exercițiu, scrie lista inversiunilor, nu doar numărul lor: așa se vede unde ai greșit, dacă ai greșit. Verifică apoi că $m(\sigma )\le \frac{n(n-1)}{2}$.

1. Determină inversiunile și $m(\sigma )$ pentru permutarea de grad $3$ cu linia a doua $1,3,2$. Este pară sau impară?

2. Aceeași cerință pentru permutarea de grad $3$ cu linia a doua $3,2,1$.

3. Determină $m(\sigma )$ și $\epsilon (\sigma )$ pentru permutarea de grad $4$ cu linia a doua $3,1,4,2$.

4. Determină $m(\sigma )$ și $\epsilon (\sigma )$ pentru permutarea de grad $4$ cu linia a doua $1,4,3,2$.

5. (Adevărat/Fals cu motivare.) „Dacă $m(\sigma )=0$, atunci $\sigma$ este permutarea identică."

6. Care este numărul maxim de inversiuni ale unei permutări de grad $6$? Ce permutare îl atinge și ce semn are ea?

7. Determină $\epsilon (\sigma )$ pentru permutarea de grad $4$ cu linia a doua $4,3,2,1$, apoi pentru cea de grad $3$ cu linia a doua $3,2,1$. Compară rezultatele.

8. Fie $u$ și $v$ permutările de grad $4$ cu liniile a doua $3,4,1,2$, respectiv $1,3,2,4$. Calculează $\epsilon (u)$, $\epsilon (v)$ și deduce $\epsilon (u\circ v)$.

9. Verifică rezultatul exercițiului precedent calculând efectiv $u\circ v$ și numărând inversiunile.

10. (Adevărat/Fals cu motivare.) „Dacă $\sigma$ este pară, atunci ${\sigma }^{-1}$ este impară."

11. Permutarea de grad $4$ are linia a doua $2,3,4,1$. Schimbă între ele valorile de pe pozițiile $2$ și $4$ și compară semnele celor două permutări.

12. (Problemă aplicată.) Cinci concurenți au intrat în sală în ordinea numerelor lor de concurs $2,3,1,5,4$, deși ar fi trebuit să intre în ordinea $1,2,3,4,5$. Câte perechi de concurenți sunt „în ordine greșită"? Câte schimbări între vecini sunt necesare, cel puțin, pentru a-i pune în ordine?

13. Câte permutări din $S_3$ sunt pare? Scrie-le pe toate.

14. Fie $\sigma \in S_4$ cu linia a doua $4,2,1,3$. Determină $m(\sigma )$, $\epsilon (\sigma )$, apoi determină ${\sigma }^{-1}$ și verifică pe el egalitatea $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$.

15. (Exercițiu tip Bacalaureat M1.) Se consideră $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 1& 2& 3\end{array}\right)$ și $\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 3& 4\end{array}\right)$. a) Calculați $m(\sigma )$ și $m(\tau )$. b) Determinați $\epsilon (\sigma \circ \tau )$ fără a calcula compunerea. c) Calculați $\sigma \circ \tau$ și verificați.

16. Arată că, pentru orice $\sigma \in S_n$, permutarea $\sigma$ și permutarea obținută din ea schimbând între ele valorile de pe pozițiile $1$ și $2$ au semne opuse. Verifică afirmația pe două permutări de grad $4$ alese de tine.

17. Câte permutări de grad $4$ au exact $2$ inversiuni? (Indicație: scrie-le sistematic, în ordine de dicționar după linia a doua.)

18. (Provocare.) Pentru permutarea de grad $4$ cu linia a doua $3,1,4,2$, sortează efectiv lista schimbând numai elemente vecine și numără câte schimbări ai făcut. Compară numărul obținut cu $m(\sigma )$. Explică, în două-trei fraze, de ce fiecare schimbare de vecini modifică numărul de inversiuni cu exact $1$.

Răspunsuri și explicații

1. Singura pereche inversată este $(2,3)$, pentru că $3>2$. Deci $m(\sigma )=1$, $\epsilon (\sigma )=-1$: permutarea este impară.

2. Toate cele trei perechi sunt inversiuni: $(1,2)$ cu $3>2$, $(1,3)$ cu $3>1$, $(2,3)$ cu $2>1$. Deci $m(\sigma )=3$ și $\epsilon (\sigma )=-1$: impară.

3. $3$ îi are la dreapta pe $1$ și $2$ (perechile $(1,2)$ și $(1,4)$); $1$ nu are nimic mai mic; $4$ îl are pe $2$ (perechea $(3,4)$). Deci $m(\sigma )=3$ și $\epsilon (\sigma )=-1$: impară.

4. $1$ nu aduce nimic; $4$ îi are la dreapta pe $3$ și $2$ (perechile $(2,3)$ și $(2,4)$); $3$ îl are pe $2$ (perechea $(3,4)$). Deci $m(\sigma )=3$ și $\epsilon (\sigma )=-1$: impară.

5. Adevărat. Dacă nu există nicio pereche $(i,j)$ cu $i<j$ și $\sigma (i)>\sigma (j)$, atunci valorile de pe linia a doua cresc de la stânga la dreapta. Singurul șir crescător format din numerele $1,2,\dots ,n$ este chiar $1,2,\dots ,n$, deci $\sigma =e$.

6. Maximul este $\frac{6\cdot 5}{2}=15$, atins de permutarea cu linia a doua $6,5,4,3,2,1$. Cum $15$ este impar, $\epsilon =(-1{)}^{15}=-1$: permutarea este impară.

7. Pentru gradul $4$: $m=\frac{4\cdot 3}{2}=6$, deci $\epsilon =+1$ (pară). Pentru gradul $3$: $m=3$, deci $\epsilon =-1$ (impară). Concluzia: paritatea permutării răsturnate depinde de grad, prin paritatea numărului $\frac{n(n-1)}{2}$.

8. Pentru $u$ (linia a doua $3,4,1,2$): $3$ îi are pe $1$ și $2$ (două), $4$ îi are pe $1$ și $2$ (două), deci $m(u)=4$ și $\epsilon (u)=+1$. Pentru $v$ (linia a doua $1,3,2,4$): doar perechea $(2,3)$, deci $m(v)=1$ și $\epsilon (v)=-1$. Prin urmare $\epsilon (u\circ v)=(+1)(-1)=-1$.

9. $(u\circ v)(1)=u(1)=3$; $(u\circ v)(2)=u(3)=1$; $(u\circ v)(3)=u(2)=4$; $(u\circ v)(4)=u(4)=2$. Linia a doua a compunerii este $3,1,4,2$, cu $m=3$ (calculat la exercițiul $3$), deci $\epsilon =-1$ ✓ — aceeași valoare ca la exercițiul $8$.

10. Fals. Regula este $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$: inversa are același semn, nu semnul opus. De exemplu, permutarea cu linia a doua $2,3,1$ are $m=2$ și e pară, iar inversa ei, cu linia a doua $3,1,2$, are tot $m=2$ și e tot pară.

11. Permutarea inițială are linia a doua $2,3,4,1$, cu $m=3$ și $\epsilon =-1$. După schimbarea valorilor de pe pozițiile $2$ și $4$, linia a doua devine $2,1,4,3$, cu inversiunile $(1,2)$ și $(3,4)$, deci $m=2$ și $\epsilon =+1$. Semnul s-a schimbat, conform regulii.

12. Perechile în ordine greșită sunt inversiunile permutării cu linia a doua $2,3,1,5,4$: $2$ îl are pe $1$ la dreapta, $3$ îl are pe $1$, iar $5$ îl are pe $4$. Deci sunt $3$ perechi „în ordine greșită", $m=3$, iar numărul minim de schimbări între vecini este tot $3$ (fiecare schimbare de vecini repară exact o pereche).

13. Sunt trei permutări pare în $S_3$: cea identică (linia a doua $1,2,3$, cu $m=0$), cea cu linia a doua $2,3,1$ ($m=2$) și cea cu linia a doua $3,1,2$ ($m=2$). Celelalte trei sunt impare.

14. Pentru $\sigma$ (linia a doua $4,2,1,3$): $4$ îi are pe $2,1,3$ (trei inversiuni), $2$ îl are pe $1$ (una), restul $0$; deci $m(\sigma )=4$ și $\epsilon (\sigma )=+1$. Inversa: din $\sigma (3)=1$, $\sigma (2)=2$, $\sigma (4)=3$, $\sigma (1)=4$ rezultă că ${\sigma }^{-1}$ are linia a doua $3,2,4,1$. Inversiunile ei: $3$ îi are pe $2$ și $1$ (două), $2$ îl are pe $1$ (una), $4$ îl are pe $1$ (una), deci $m({\sigma }^{-1})=4$ și $\epsilon ({\sigma }^{-1})=+1=\epsilon (\sigma )$ ✓.

15. a) Pentru $\sigma$ (linia a doua $4,1,2,3$): $4$ îi are la dreapta pe $1,2,3$, deci $m(\sigma )=3$ și $\epsilon (\sigma )=-1$. Pentru $\tau$ (linia a doua $2,1,3,4$): doar perechea $(1,2)$, deci $m(\tau )=1$ și $\epsilon (\tau )=-1$. b) $\epsilon (\sigma \circ \tau )=(-1)(-1)=+1$. c) $(\sigma \circ \tau )(1)=\sigma (2)=1$; $(\sigma \circ \tau )(2)=\sigma (1)=4$; $(\sigma \circ \tau )(3)=\sigma (3)=2$; $(\sigma \circ \tau )(4)=\sigma (4)=3$, deci linia a doua a compunerii este $1,4,2,3$, cu inversiunile $(2,3)$ și $(2,4)$, adică $m=2$ și $\epsilon =+1$ ✓.

16. Fie $\sigma$ cu $\sigma (1)=a$ și $\sigma (2)=b$, iar ${\sigma }^{\prime }$ permutarea obținută schimbându-le. Perechile care nu conțin pozițiile $1$ și $2$ nu se schimbă deloc. Perechea $(1,2)$ trece din inversiune în neinversiune sau invers, deci contribuie cu $\pm 1$. Pentru orice altă poziție $k>2$, perechile $(1,k)$ și $(2,k)$ își schimbă rolurile între ele, deci suma contribuțiilor lor rămâne aceeași. În total, $m$ se modifică cu un număr impar, deci semnul se schimbă. Verificare pe două exemple: $2,3,4,1\to 3,2,4,1$ dă $m=3\to m=4$ (semnul se schimbă); $1,4,3,2\to 4,1,3,2$ dă $m=3\to m=4$ (la fel).

17. Sunt cinci: permutările cu liniile a doua $1,3,4,2$; $1,4,2,3$; $2,1,4,3$; $2,3,1,4$; $3,1,2,4$. Se obțin scriind în ordine de dicționar toate cele $24$ de permutări și numărând inversiunile fiecăreia; pentru control, distribuția completă în $S_4$ este $1,3,5,6,5,3,1$ permutări cu $0,1,2,3,4,5,6$ inversiuni, iar suma lor este $24$.

18. Ai calculat deja $m(\sigma )=3$ la exercițiul $3$. O sortare posibilă a listei $3,1,4,2$ prin schimbări de vecini: $3,1,4,2\to 1,3,4,2\to 1,3,2,4\to 1,2,3,4$ — exact trei schimbări. Motivul general: o schimbare între două elemente vecine afectează o singură pereche de poziții, cea formată din ele, și nu atinge nicio altă pereche; deci $m$ scade sau crește cu exact $1$. Cum pornești de la $m(\sigma )$ și trebuie să ajungi la $0$, îți trebuie cel puțin $m(\sigma )$ schimbări, iar cu o sortare care repară de fiecare dată o inversiune se atinge exact acest număr.

De reținut

• Inversiunea este o pereche de poziții $(i,j)$ cu $i<j$ și $\sigma (i)>\sigma (j)$; numărul lor se notează $m(\sigma )$.
• Metoda de numărare: pentru fiecare valoare de pe linia a doua, numeri câte valori mai mici stau la dreapta ei, apoi aduni. Nicio pereche nu se pierde și niciuna nu se numără de două ori.
• Semnul: $\epsilon (\sigma )=(-1{)}^{m(\sigma )}$; permutarea e pară dacă $\epsilon =+1$ și impară dacă $\epsilon =-1$. Identitatea este pară.
• Marginile: $0\le m(\sigma )\le \frac{n(n-1)}{2}$, minimul fiind atins de $e$, iar maximul de permutarea răsturnată.
• Regulile de calcul: $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\epsilon (\tau )$ și $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$; schimbând între ele două valori, semnul se schimbă.

Greșeli frecvente

• Numărarea valorilor în loc de perechi. $m(\sigma )$ nu este „câte numere nu sunt la locul lor", ci câte perechi de poziții sunt inversate. Pentru linia a doua $2,1$ răspunsul e $1$, nu $2$.
• Condiția scrisă pe jumătate. Inversiunea cere și $i<j$, și $\sigma (i)>\sigma (j)$. Cine verifică doar a doua condiție numără fiecare pereche de două ori și obține un $m$ dublu.
• Confuzia dintre semn și număr. $\epsilon (\sigma )$ este $+1$ sau $-1$, niciodată $2$ sau $-3$. Dacă răspunsul tău la semn e alt număr, ai scris $m$ în loc de $\epsilon$.
• Presupunerea că inversa are semn opus. Regula corectă e $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$: aceeași paritate, nu opusă. Greșeala vine din analogia falsă cu inversul unui număr.
• Depășirea maximului. Un rezultat $m=7$ pentru o permutare de grad $4$ este imposibil, pentru că maximul e $6$. Verifică întotdeauna încadrarea în $\frac{n(n-1)}{2}$ înainte de a trece mai departe.

Aplică acasă

1. Coada de la casă. Notează ordinea în care intră cinci persoane într-un rând față de ordinea în care ar fi trebuit să intre și numără perechile inversate. Apoi pune-le în ordine schimbând numai vecini și verifică dacă numărul de schimbări coincide cu numărul de inversiuni.

2. Tabelul lui $S_4$. Scrie toate cele $24$ de permutări de grad $4$, în ordine de dicționar după linia a doua, și calculează pentru fiecare $m$ și $\epsilon$. Numără câte sunt pare și câte impare — vei obține $12$ și $12$.

3. Testul de multiplicativitate. Alege trei perechi de permutări de grad $4$ și verifică, pentru fiecare, egalitatea $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\epsilon (\tau )$, calculând ambii membri independent.

Pentru părinți și profesori

Lecția închide partea de permutări și livrează instrumentul cerut de programă: signatura. Este o lecție de numărare disciplinată, în care greșelile nu vin din concept, ci din procedură — de aceea metoda de numărare („câte valori mai mici stau la dreapta") merită impusă ca standard, în locul verificării haotice a perechilor.

De verificat în caiet: (1) inversiunile sunt scrise ca perechi de poziții, nu ca valori; (2) $m$ se încadrează între $0$ și $\frac{n(n-1)}{2}$; (3) $\epsilon$ este $\pm 1$ și nu se confundă cu $m$; (4) la compuneri se folosește înmulțirea semnelor, cu verificare independentă cel puțin o dată. Întrebări de control: „Ce este o inversiune?"; „Câte inversiuni are cel mult o permutare de grad $5$?"; „Ce semn are permutarea identică?"; „Cum afli semnul unei compuneri fără să o calculezi?".

La BAC M1 semnul unei permutări apare de regulă ca prim punct al unui subiect de algebră, urmat de o compunere sau de trecerea la determinanți. Semn că elevul a înțeles: numără inversiunile unei permutări de grad $4$ în mai puțin de un minut și își verifică rezultatul cu marginea $\frac{n(n-1)}{2}$.

Întrebări frecvente

Ce este o inversiune a unei permutări? Este o pereche de poziții $(i,j)$ cu $i<j$ pentru care valorile sunt în ordine inversă, adică $\sigma (i)>\sigma (j)$. Se numără perechile de poziții, nu numerele.

Cum se numără repede inversiunile? Parcurgi linia a doua de la stânga la dreapta și, pentru fiecare valoare, numeri câte valori mai mici stau la dreapta ei. Suma acestor numere este $m(\sigma )$.

Ce înseamnă semnul unei permutări? Semnul, sau signatura, este $\epsilon (\sigma )=(-1{)}^{m(\sigma )}$. Este $+1$ dacă numărul de inversiuni e par (permutare pară) și $-1$ dacă e impar (permutare impară).

Care este numărul maxim de inversiuni al unei permutări de grad n? Este $\frac{n(n-1)}{2}$, adică numărul tuturor perechilor de poziții. Se atinge la permutarea care are pe linia a doua numerele în ordine descrescătoare.

Ce semn are permutarea identică? Are $m(e)=0$ inversiuni, deci $\epsilon (e)=(-1{)}^0=+1$: permutarea identică este întotdeauna pară, indiferent de grad.

Cum aflu semnul unei compuneri de permutări? Înmulțești semnele: $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\cdot \epsilon (\tau )$. Nu e nevoie să calculezi compunerea, deși e o verificare bună să o faci și să numeri inversiunile rezultatului.

Inversa unei permutări are același semn? Da: $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$. Perechile inversate ale inversei sunt aceleași ca ale permutării inițiale, citite invers, deci numărul lor nu se schimbă.

De ce am nevoie de semnul unei permutări la determinanți? Pentru că fiecare termen al determinantului de ordin $n$ corespunde unei permutări și intră în sumă cu semnul acesteia. Așa se explică de ce, la ordinul $3$, trei produse se adună și trei se scad: $S_3$ are exact trei permutări pare și trei impare.