Se consideră permutările $$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}$$ și $$\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4 \end{pmatrix}$$ din $$S_4$$. Cât este $$\sigma \circ \tau$$?

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$$

Care este inversa permutării $$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}$$?

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}$$

Ce sunt permutările și cum se notează?

Lecția pe scurt · clasa a XI-a · Permutări: definiție și compunere

O permutare de grad $n$ reașază între ele numerele $1, 2, \dots, n$ ; riguros spus, este o bijecție a mulțimii ${1, 2, \dots, n}$ pe ea însăși. Se notează pe două linii: sus argumentele în ordine, jos valorile lor. De pildă $σ = (132132)$ trimite $1$ în $3$ , $2$ în $1$ și $3$ în $2$ . Toate permutările de grad $n$ formează mulțimea $S_{n}$ , care are $n!$ elemente.

La clasa a 11-a, o permutare de grad $n$ nu mai este o așezare, ca la combinatorică, ci o funcție bijectivă $σ : {1, 2, \dots, n} \to {1, 2, \dots, n}$ . Mulțimea tuturor acestor funcții se notează $S_{n}$ și are $card S_{n} = n!$ elemente — același număr ca $P_{n}$ , semn că cele două priviri descriu același obiect.

Se scrie pe două rânduri: sus argumentele în ordine crescătoare, jos imaginile lor. Tabloul este valabil doar dacă linia de jos conține fiecare număr de la $1$ la $n$ exact o dată. Atenție, tabloul acesta nu este o matrice: nu se adună, nu se înmulțește cu un scalar și nu are determinant.

Singura operație de care avem nevoie este compunerea, cu ordinea fixată o dată pentru totdeauna: $(σ \circ τ) (k) = σ (τ (k))$ , adică întâi $τ$ , apoi $σ$ ; se citește de la dreapta la stânga. Compunerea nu este comutativă, deci în general $σ \circ τ \neq = τ \circ σ$ .

Permutarea identică $e$ lasă totul pe loc și joacă rolul lui $1$ de la înmulțire: $σ \circ e = e \circ σ = σ$ . Fiind bijectivă, orice permutare are o inversă $σ^{- 1}$ , obținută schimbând cele două linii și reordonând apoi coloanele; ea verifică $σ \circ σ^{- 1} = σ^{- 1} \circ σ = e$ , iar la un produs ordinea se răstoarnă: $(σ \circ τ)^{- 1} = τ^{- 1} \circ σ^{- 1}$ .

De aici ies ecuațiile din subiectele de Bacalaureat M1: din $σ \circ x = τ$ obții $x = σ^{- 1} \circ τ$ , iar din $x \circ σ = τ$ obții $x = τ \circ σ^{- 1}$ — două rezultate, de regulă, diferite. Tot acest instrumentar servește la definiția determinantului de ordin $n$ .

De reținut

Permutare de grad $n$ = funcție bijectivă pe ${1, 2, \dots, n}$
$∣ S_{n} ∣ = n!$ ; elementul neutru este permutarea identică $e$
$(σ \circ τ) (x) = σ (τ (x))$ — se lucrează dinspre dreapta

Greșeala tipică

Compunerea se face de la stânga la dreapta, ca la o citire obișnuită. Fiind vorba de funcții, se aplică întâi permutarea din dreapta, iar inversarea ordinii schimbă rezultatul, fiindcă operația nu este comutativă.

Exerciții din această mini-lecție

Se consideră permutările $σ = (13243241)$ și $τ = (12233144)$ din $S_{4}$ . Cât este $σ \circ τ$ ?
- a) $(11243342)$
- b) $(14223341)$
- c) $(13213442)$
- d) $(12233441)$
Vezi răspunsul

Răspuns corect: b) $(14223341)$

Se aplică întâi $τ$ , apoi $σ$ : $(σ \circ τ) (1) = σ (2) = 4$ , $(σ \circ τ) (2) = σ (3) = 2$ , $(σ \circ τ) (3) = σ (1) = 3$ , $(σ \circ τ) (4) = σ (4) = 1$ . Varianta a) este $τ \circ σ$ , adică rezultatul obținut dacă citești compunerea de la stânga la dreapta — greșeala numărul unu la acest tip de exercițiu.
Câte permutări $σ \in S_{5}$ au proprietatea $σ (2) = 5$ ?
- a) $5$
- b) $120$
- c) $4$
- d) $24$
Vezi răspunsul

Răspuns corect: d) $24$

Valoarea lui $σ (2)$ fiind fixată, rămân de repartizat numerele $1, 2, 3, 4$ pe pozițiile $1, 3, 4, 5$ , în orice ordine: $4! = 24$ posibilități. Varianta b) este $card S_{5} = 5! = 120$ , adică numărul tuturor permutărilor, fără nicio condiție.
Care este inversa permutării $σ = (14233142)$ ?
- a) $(13243241)$
- b) $(14233142)$
- c) $(12213344)$
- d) $(12213443)$
Vezi răspunsul

Răspuns corect: a) $(13243241)$

Din $σ (3) = 1$ rezultă $σ^{- 1} (1) = 3$ ; din $σ (4) = 2$ , $σ^{- 1} (2) = 4$ ; din $σ (2) = 3$ , $σ^{- 1} (3) = 2$ ; din $σ (1) = 4$ , $σ^{- 1} (4) = 1$ . Varianta b) este $σ$ însăși (ea nu este propria inversă), iar varianta d) este $σ \circ σ$ . Controlul obligatoriu: $σ \circ σ^{- 1} = e$ .

Întrebări conexe

Cum aflu ordinul unei permutări?

Compui permutarea cu ea însăși până când reapare identitatea, iar numărul de pași făcuți este ordinul căutat. Pentru $σ = (132132)$ ies $σ^{2} \neq = e$ și $σ^{3} = e$ , deci ordinul este $3$ . Ordinul împarte întotdeauna numărul total de elemente ale mulțimii $S_{n}$ .

Ce este o transpoziție?

O permutare care schimbă între ele doar două elemente și le lasă pe toate celelalte pe loc. Se notează $(i j)$ , iar compusă cu ea însăși dă identitatea, deci este propria ei inversă.

Cum descompun o permutare în transpoziții?

Aduci elementele la locul lor unul câte unul, notând fiecare schimb făcut. Descompunerea nu este singura posibilă, dar paritatea numărului de transpoziții rămâne aceeași, indiferent de drumul ales.

Ce este un ciclu la permutări?

Un lanț închis de elemente care se împing unul în locul celuilalt, iar restul rămân neatinse. Se scrie $(132)$ și se citește: $1$ merge în $3$ , $3$ merge în $2$ , iar $2$ se întoarce în $1$ .

Cum calculez sigma la puterea a treia pentru o permutare dată?

Aplici permutarea de trei ori la rând fiecărui element, urmărind drumul lui. Este mai rapid decât să faci două compuneri complete, mai ales când permutarea se descompune în cicluri scurte.

De ce se compun permutările de la dreapta la stânga?

Pentru că sunt funcții, iar $(σ \circ τ) (x)$ înseamnă $σ (τ (x))$ : lucrează întâi cea din dreapta. Citirea în ordine inversă este cea mai frecventă sursă de rezultate greșite la compunere.

Oamenii mai întreabă și: ce este o permutare de grad n · cum se scrie o permutare pe două linii · mulțimea S n a permutărilor · permutări la liceu, notație