Se consideră permutarea de grad $$7$$ cu linia a doua $$7, 6, 5, 4, 3, 2, 1$$. Care afirmație este adevărată?

$$m(\sigma) = 21$$ și $$\sigma$$ este impară

$$m(\sigma) = 21$$ și $$\sigma$$ este pară

$$m(\sigma) = 42$$ și $$\sigma$$ este pară

$$m(\sigma) = 28$$ și $$\sigma$$ este impară

Cum aflu semnul unei permutări?

Lecția pe scurt · clasa a XI-a · Inversiuni și semnul unei permutări

Numeri perechile așezate în ordine greșită pe linia de jos: fiecare pereche $i < j$ cu $σ (i) > σ (j)$ este o inversiune. Dacă numărul lor este $m$ , semnul este $ε (σ) = (- 1)^{m}$ . La $σ = (132132)$ perechile greșite sunt $(1, 2)$ și $(1, 3)$ , deci $m = 2$ și semnul iese $+ 1$ . Un număr par de inversiuni dă permutare pară, unul impar dă permutare impară.

O pereche de poziții $(i, j)$ cu $i < j$ se numește inversiune a permutării $σ$ dacă valorile de pe ele stau invers, adică $σ (i) > σ (j)$ . Numărul inversiunilor se notează $m (σ)$ și se numără fără greșeală așa: parcurgi linia a doua de la stânga la dreapta și, pentru fiecare valoare, numeri câte valori mai mici stau la dreapta ei; apoi aduni. Fiecare pereche este numărată exact o dată.

Se numără perechi de poziții, nu numere „mutate din loc". De aici și marginile: $0 \leq m (σ) \leq \frac{n ( n - 1 )}{2}$ , minimul fiind atins de permutarea identică, iar maximul de cea răsturnată, cu linia a doua scrisă descrescător. Un rezultat în afara acestui interval este, sigur, o greșeală de numărare.

Din numărul de inversiuni păstrăm un singur bit: paritatea. Semnul, sau signatura, este $ε (σ) = (- 1)^{m (σ)} \in {- 1, + 1}$ ; permutarea se numește pară când $ε (σ) = + 1$ și impară când $ε (σ) = - 1$ . Identitatea este mereu pară. Nu confunda $m$ cu $ε$ : al doilea este întotdeauna $\pm 1$ .

Trei reguli de calcul îți scurtează munca la Bacalaureat M1: dacă schimbi între ele două valori, semnul se schimbă; $ε (σ \circ τ) = ε (σ) \cdot ε (τ)$ , deci afli semnul unei compuneri fără să o calculezi; și $ε (σ^{- 1}) = ε (σ)$ , adică inversa are același semn, nu semnul opus.

Semnul este ultima piesă necesară determinantului de ordin $n$ : fiecare dintre cele $n!$ produse intră în sumă cu semnul permutării care îl conduce.

De reținut

Inversiune: pereche $i < j$ cu $σ (i) > σ (j)$
$ε (σ) = (- 1)^{m}$ , unde $m$ este numărul de inversiuni
O transpoziție schimbă semnul; $ε (σ τ) = ε (σ) ε (τ)$

Greșeala tipică

Se numără doar perechile de valori vecine, nu toate perechile de poziții. O permutare de grad $4$ are $6$ perechi de comparat, iar sărirea celor depărtate schimbă paritatea și, cu ea, semnul.

Exerciții din această mini-lecție

Câte inversiuni are permutarea de grad $5$ cu linia a doua $3, 5, 1, 4, 2$ ?
- a) $4$
- b) $5$
- c) $6$
- d) $10$
Vezi răspunsul

Răspuns corect: c) $6$

Numărăm, pentru fiecare valoare, câte valori mai mici stau la dreapta ei: $3$ are $1$ și $2$ (două), $5$ are $1$ , $4$ și $2$ (trei), $1$ are zero, $4$ îl are pe $2$ (una), $2$ are zero. Deci $m (σ) = 2 + 3 + 0 + 1 + 0 = 6$ . Varianta d) este maximul posibil la gradul $5$ , $\frac{5 \cdot 4}{2} = 10$ , atins doar de permutarea răsturnată.
Se știe că $σ, τ \in S_{5}$ au $m (σ) = 7$ și $m (τ) = 4$ . Cât este $ε (σ \circ τ)$ ?
- a) $- 1$
- b) $+ 1$
- c) $28$
- d) $11$
Vezi răspunsul

Răspuns corect: a) $- 1$

$ε (σ) = (- 1)^{7} = - 1$ și $ε (τ) = (- 1)^{4} = + 1$ , iar semnele se înmulțesc: $ε (σ \circ τ) = (- 1) \cdot (+ 1) = - 1$ . Variantele c) și d) vin din confuzia dintre $m$ și $ε$ : signatura este întotdeauna $- 1$ sau $+ 1$ , niciodată alt număr.
Se consideră permutarea de grad $7$ cu linia a doua $7, 6, 5, 4, 3, 2, 1$ . Care afirmație este adevărată?
- a) $m (σ) = 21$ și $σ$ este pară
- b) $m (σ) = 42$ și $σ$ este pară
- c) $m (σ) = 28$ și $σ$ este impară
- d) $m (σ) = 21$ și $σ$ este impară
Vezi răspunsul

Răspuns corect: d) $m (σ) = 21$ și $σ$ este impară

La permutarea răsturnată orice pereche de poziții este inversiune, deci $m (σ) = \frac{7 \cdot 6}{2} = 21$ . Cum $21$ este impar, $ε (σ) = (- 1)^{21} = - 1$ , adică permutarea este impară. Varianta b) numără perechile ordonate, uitând împărțirea la $2$ .

Întrebări conexe

Câte permutări pare de grad n există?

Exact jumătate din total, adică $\frac{n !}{2}$ pentru $n \geq 2$ . Împerecherea se face compunând fiecare permutare pară cu o transpoziție fixă, ceea ce dă o corespondență între cele două familii.

Cum se schimbă semnul dacă schimb două elemente între ele?

Semnul se inversează, fiindcă o transpoziție schimbă paritatea numărului de inversiuni. De aceea o permutare scrisă ca produs de $k$ transpoziții are semnul $(- 1)^{k}$ , indiferent de descompunerea aleasă.

Ce semn are o permutare scrisă ca produs de trei transpoziții?

Semnul $- 1$ , deci este impară, fiindcă fiecare transpoziție răstoarnă paritatea, iar trei răsturnări lasă rezultatul pe partea opusă celei de pornire. Numărul de inversiuni al ei va ieși, așadar, impar.

Ce semn are un ciclu de lungime k?

Este $(- 1)^{k - 1}$ , pentru că un ciclu se desface în $k - 1$ transpoziții. Ciclurile de lungime impară sunt pare, iar cele de lungime pară sunt impare — o inversare de vocabular care încurcă des.

De ce semnul nu depinde de descompunerea aleasă?

Fiindcă orice două descompuneri ale aceleiași permutări au numere de transpoziții cu aceeași paritate. Numărul de factori poate diferi, dar diferența este întotdeauna pară, deci $(- 1)^{k}$ rămâne același.

Cum verific că am numărat corect inversiunile?

Refaci numărătoarea pe coloane: iei pe rând fiecare număr de jos și socotești câte numere mai mici îl urmează. Totalul trebuie să iasă același ca la prima trecere; o diferență arată că ai sărit o pereche.

Oamenii mai întreabă și: semnul unei permutări · signatura unei permutări · cum număr inversiunile unei permutări · permutare pară sau impară