Inversiuni și semnul unei permutări — lecție clasa a 11-a: teorie, exemple, exerciții

În această lecție înveți să numeri inversiunile unei permutări și să afli semnul ei: o permutare este pară dacă are un număr par de inversiuni și impară în caz contrar. Semnul se înmulțește la compunere, $\epsilon (\sigma \tau )=\epsilon (\sigma )\epsilon (\tau )$, iar cu el se definește determinantul de ordinul $n$.

Teorie

Inversiuni

Fie $\sigma \in S_n$. O pereche $(i,j)$, cu $1\le i<j\le n$, se numește inversiune a lui $\sigma$ dacă $\sigma (i)>\sigma (j)$, adică ordinea se „strică”: numărul mai mic are imaginea mai mare. Numărul inversiunilor se notează $m(\sigma )$.

Cum le numeri repede: în linia a doua a permutării, pentru fiecare număr numeri câte numere mai mici decât el se află la dreapta lui, apoi aduni.

Pentru orice $\sigma \in S_n$: $0\le m(\sigma )\le \frac{n(n-1)}{2}$. Valoarea 0 o are doar $e$, iar valoarea maximă doar permutarea $\left(\begin{array}{cccc}1& 2& \dots & n\\ n& n-1& \dots & 1\end{array}\right)$, la care toate cele $C_n^2=\frac{n(n-1)}{2}$ perechi sunt inversiuni.

Semnul (signatura) unei permutări

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

Permutarea este pară dacă $\epsilon (\sigma )=1$ (număr par de inversiuni) și impară dacă $\epsilon (\sigma )=-1$. Semnul se poate scrie și ca un produs:

$$\epsilon (\sigma )=\prod _{1\le i<j\le n}\frac{\sigma (j)-\sigma (i)}{j-i}.$$

De ce? Când perechea $\{i,j\}$ parcurge toate perechile din $\{1,\dots ,n\}$, și $\{\sigma (i),\sigma (j)\}$ le parcurge pe toate ($\sigma$ este bijectivă), deci numărătorii și numitorii au aceleași valori absolute și produsul este $\pm 1$. Un factor este negativ exact când $\sigma (i)>\sigma (j)$, adică pentru fiecare inversiune, deci semnul produsului este $(-1{)}^{m(\sigma )}$.

Teorema: semnul compunerii

Pentru orice $\sigma ,\tau \in S_n$:

$$\epsilon (\sigma \tau )=\epsilon (\sigma )\cdot \epsilon (\tau ).$$

Demonstrație. Scrii fiecare factor din produsul pentru $\sigma \tau$ ca

$$\frac{\sigma (\tau (j))-\sigma (\tau (i))}{j-i}=\frac{\sigma (\tau (j))-\sigma (\tau (i))}{\tau (j)-\tau (i)}\cdot \frac{\tau (j)-\tau (i)}{j-i}.$$

Produsul ultimelor fracții este $\epsilon (\tau )$. În primele fracții, $\{\tau (i),\tau (j)\}$ parcurge toate perechile, iar fracția nu se schimbă dacă inversezi ordinea celor două numere, deci produsul lor este $\epsilon (\sigma )$. $◼$

Consecințe:

• $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$, pentru că $\epsilon (\sigma )\epsilon ({\sigma }^{-1})=\epsilon (e)=1$;
• $\epsilon ({\sigma }^k)=\epsilon (\sigma {)}^k$: o putere impară a unei permutări impare este impară;
• orice transpoziție $(ij)$, $i<j$, este impară: are $2(j-i)-1$ inversiuni (perechea $(i,j)$ și câte două pentru fiecare număr dintre $i$ și $j$);
• dacă schimbi între ele două valori din linia a doua, semnul se schimbă (compui cu o transpoziție);
• pentru $n\ge 2$, $S_n$ are $\frac{n!}{2}$ permutări pare și $\frac{n!}{2}$ impare: funcția $\sigma \mapsto (12)\sigma$ duce bijectiv permutările pare în cele impare.

Legătura cu determinanții

Determinantul unei matrice pătratice de ordinul $n$ se definește cu ajutorul semnului:

$$detA=\sum _{\sigma \in S_n}\epsilon (\sigma )a_{1\sigma (1)}{a}_{2\sigma (2)}\cdots a_{n\sigma (n)}.$$

Pentru $n=3$: permutările pare $e$, $\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$ dau cei trei termeni cu „+” din regula lui Sarrus, iar cele trei transpoziții dau termenii cu „−”.

De reținut

• Inversiune: $i<j$ și $\sigma (i)>\sigma (j)$; $0\le m(\sigma )\le \frac{n(n-1)}{2}$.
• $\epsilon (\sigma )=(-1{)}^{m(\sigma )}$; $\epsilon (e)=1$.
• $\epsilon (\sigma \tau )=\epsilon (\sigma )\epsilon (\tau )$, $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$, $\epsilon ({\sigma }^k)=\epsilon (\sigma {)}^k$.
• Transpozițiile sunt impare; o schimbare de două valori schimbă paritatea.
• Pentru $n\ge 2$: jumătate din permutările lui $S_n$ sunt pare.

Exemple rezolvate

Exemplul 1. Află inversiunile și semnul permutării $\sigma =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 5& 1& 4& 2\end{array}\right)$.

Vezi rezolvarea

1. Linia a doua este 3, 5, 1, 4, 2. La dreapta lui 3 sunt mai mici: 1, 2 (2 inversiuni); la dreapta lui 5: 1, 4, 2 (3); la dreapta lui 1: niciunul; la dreapta lui 4: 2 (1).
2. Inversiunile, ca perechi de poziții: $(1,3)$, $(1,5)$, $(2,3)$, $(2,4)$, $(2,5)$, $(4,5)$.
3. $m(\sigma )=2+3+0+1=6$, deci $\epsilon (\sigma )=(-1{)}^6=1$.

Răspuns: 6 inversiuni, $\sigma$ este pară

Exemplul 2. Scrie toate permutările din $S_3$, cu numărul de inversiuni și semnul fiecăreia.

Vezi rezolvarea

linia a doua	inversiuni	$m(\sigma )$	semn
1 2 3	—	0	pară
1 3 2	(2, 3)	1	impară
2 1 3	(1, 2)	1	impară
2 3 1	(1, 3), (2, 3)	2	pară
3 1 2	(1, 2), (1, 3)	2	pară
3 2 1	(1, 2), (1, 3), (2, 3)	3	impară

Răspuns: 3 permutări pare și 3 impare, adică $\frac{3!}{2}=3$ de fiecare fel

Exemplul 3. Fie $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right)$. Află semnul permutărilor ${\sigma }^{2027}$ și ${\sigma }^{-1}$, fără să le calculezi.

Vezi rezolvarea

1. Inversiunile lui $\sigma$: la dreapta lui 2 este 1 (1); la dreapta lui 4 sunt 1, 3 (2); la dreapta lui 1 niciunul. $m(\sigma )=3$, deci $\epsilon (\sigma )=-1$.
2. $\epsilon ({\sigma }^{2027})=\epsilon (\sigma {)}^{2027}=(-1{)}^{2027}=-1$.
3. $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )=-1$.

Răspuns: ambele sunt impare

Exemplul 4. Determină $x,y$ astfel încât $\sigma =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& x& 5& y& 1\end{array}\right)$ să fie o permutare pară.

Vezi rezolvarea

1. Linia a doua trebuie să conțină toate numerele 1, …, 5, deci $\{x,y\}=\{3,4\}$.
2. Pentru $x=3$, $y=4$: 2, 3, 5, 4, 1 are inversiunile $1+1+2+1=5$, deci este impară.
3. Pentru $x=4$, $y=3$ (am schimbat două valori, deci paritatea se schimbă): 2, 4, 5, 3, 1 are $1+2+2+1=6$ inversiuni, deci este pară.

Răspuns: $x=4$, $y=3$

Exemplul 5. Fie $\sigma \in S_n$, $\sigma (k)=n+1-k$ (linia a doua este $n,n-1,\dots ,1$). Calculează $m(\sigma )$ pentru $n=10$ și află pentru ce valori $n\le 10$ permutarea este pară.

Vezi rezolvarea

1. Orice pereche $i<j$ este inversiune, pentru că $n+1-i>n+1-j$. Deci $m(\sigma )=C_n^2=\frac{n(n-1)}{2}$.
2. Pentru $n=10$: $m(\sigma )=45$, impar, deci $\sigma$ este impară.
3. Pentru $n=2,3,\dots ,10$ obții $1,3,6,10,15,21,28,36,45$; numerele pare apar pentru $n=4,5,8,9$ (iar pentru $n=1$, $\sigma =e$).

Răspuns: $m(\sigma )=45$ pentru $n=10$; $\sigma$ este pară pentru $n\in \{1,4,5,8,9\}$

Exemplul 6 (nivel Bacalaureat). Arată că ecuația $x^2=\tau$, unde $\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 3& 4\end{array}\right)$, nu are soluții în $S_4$.

Vezi rezolvarea

1. $\tau$ are o singură inversiune, $(1,2)$, deci $\epsilon (\tau )=-1$.
2. Pentru orice $x\in S_4$, $\epsilon (x^2)=\epsilon (x)\cdot \epsilon (x)=\epsilon (x{)}^2=1$, deci $x^2$ este pară.
3. O permutare pară nu poate fi egală cu una impară, deci $x^2\ne \tau$ pentru orice $x$.

Răspuns: ecuația nu are soluții, pentru că pătratul oricărei permutări este par, iar $\tau$ este impară

Greșeli frecvente

• Numeri doar perechile vecine: în 3, 5, 1, 4, 2, perechea (3, 2) este inversiune deși numerele nu sunt alăturate. Se compară fiecare număr cu toate numerele de la dreapta lui.
• Numeri și numerele mai mari: la dreapta lui 3 în 3, 5, 1, 4, 2 se numără doar 1 și 2 (mai mici), nu și 5 sau 4.
• Aduni semnele în loc să le înmulțești: $\epsilon (\sigma \tau )=\epsilon (\sigma )\epsilon (\tau )$; două permutări impare au compusul par, nu „de două ori impar”.
• Calculezi inutil puteri mari: semnul lui ${\sigma }^{2027}$ este $\epsilon (\sigma {)}^{2027}$; nu trebuie să afli ${\sigma }^{2027}$.

Verifică-te

Exersează

• Lecția anterioară: permutări: compunere, inversă.
• Unde folosești semnul: determinanți (definiția cu permutări, regula lui Sarrus) și matrice și determinanți la Bacalaureat.
• În clasa a XII-a: fișă de lucru despre grupuri (grupul permutărilor) și grup abelian ($S_n$, $n\ge 3$, este un exemplu de grup necomutativ).

Inversiunile și semnul unei permutări sunt în programa de Bacalaureat M1 (clasa a XI-a), dar în subiectele de Bac M1 din 2020–2026 nu a apărut niciun item despre ele. Lecția este doar pentru profilul mate-info (M1); nu face parte din programa M2.

Întrebări frecvente

Ce este o inversiune a unei permutări? Este o pereche de poziții $i<j$ pentru care $\sigma (i)>\sigma (j)$. În linia a doua a permutării, o inversiune înseamnă un număr urmat (nu neapărat imediat) de un număr mai mic.

Cum aflu dacă o permutare este pară sau impară? Numeri inversiunile: pentru fiecare număr din linia a doua numeri câte numere mai mici sunt la dreapta lui și aduni. Dacă totalul este par, permutarea este pară (semn $+1$); dacă este impar, este impară (semn $-1$).

Câte permutări pare are S_n? Pentru $n\ge 2$, exact jumătate: $\frac{n!}{2}$. De exemplu $S_3$ are 3 permutări pare, iar $S_4$ are 12.