MateExamene

Profesor de Matematică - Elena Micu

Liceu › Clasa a XI-a › Algebră › Capitolul I. Permutări › Lecția 3
📄 Versiune PDF
CAPITOLUL I. PERMUTĂRI

Lecția 3. Inversiunile și semnul unei permutări.
Permutări pare, permutări impare

Inversiunile unei permutări

Fie $n \in \mathbb{N}^*$, $n \geq 2$, și mulțimea $S_n$ a tuturor permutărilor de gradul $n$. Considerăm o permutare $\sigma \in S_n$, reprezentată sub formă tabelară prin:

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & \dots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \dots & \sigma(n) \end{pmatrix}$$
Definiție (Inversiune)

Fie $\sigma \in S_n$ și perechea de indici $(i, j)$ cu $i, j \in \{1, 2, \dots, n\}$ astfel încât $i < j$. Perechea $(i, j)$ se numește inversiune a permutării $\boldsymbol{\sigma}$ dacă:

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

Numărul total al inversiunilor permutării $\sigma$ se notează cu $m(\sigma)$.

Interpretare intuitivă și metodică

Din punct de vedere intuitiv, o inversiune reprezintă o dereglare a ordinii naturale a numerelor. Dacă numărul mai mic $i$ se află înaintea numărului mai mare $j$ $(i < j)$, dar imaginile lor prin permutare sunt inversate $\big(\sigma(i) > \sigma(j)\big)$, atunci perechea $(i, j)$ creează o „încrucișare”. În reprezentarea grafică a unei permutări prin fire ce unesc rândul superior cu cel inferior, numărul total de încrucișări ale firelor este exact egal cu numărul inversiunilor $m(\sigma)$.

1 2 3 4 5 1 2 3 4 5
Permutarea $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 2 & 1 & 4 \end{pmatrix}$ reprezentată prin fire: fiecare element $k$ de sus este unit cu imaginea sa $\sigma(k)$ de jos. Firele se încrucișează de $6$ ori, adică exact $m(\sigma) = 6$.
Exemplu

Fie permutarea de gradul 5:

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 2 & 1 & 4 \end{pmatrix} \in S_5.$$

Să determinăm toate inversiunile permutării $\sigma$ și să calculăm $m(\sigma)$.

Rezolvare

Căutăm toate perechile $(i, j)$ cu $1 \leq i < j \leq 5$ pentru care $\sigma(i) > \sigma(j)$:

Pentru $i = 1$, cu $\sigma(1) = 3$:

Pentru $i = 2$, cu $\sigma(2) = 5$:

Pentru $i = 3$, cu $\sigma(3) = 2$:

Pentru $i = 4$, cu $\sigma(4) = 1$: avem $\sigma(5) = 4 > 1$, deci nu există alte inversiuni.

Mulțimea inversiunilor este $\operatorname{Inv}(\sigma) = \{(1,3), (1,4), (2,3), (2,4), (2,5), (3,4)\}$.

Prin urmare, numărul total de inversiuni este $m(\sigma) = 6$.

Semnul (signatura) unei permutări
Definiții

1.   Se numește semnul (sau signatura) permutării $\sigma \in S_n$ numărul notat cu $\varepsilon(\sigma)$ sau $\operatorname{sgn}(\sigma)$, definit prin:

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

2.   Permutarea $\sigma$ se numește permutare pară dacă numărul inversiunilor sale $m(\sigma)$ este par, adică $\varepsilon(\sigma) = +1$.

3.   Permutarea $\sigma$ se numește permutare impară dacă numărul inversiunilor sale $m(\sigma)$ este impar, adică $\varepsilon(\sigma) = -1$.

Bibliografie

Burtea, M., & Burtea, G. (2006). Matematică: Manual pentru clasa a XI-a: Trunchi comun + curriculum diferențiat: M1. Editura Carminis.