Permutări: definiție, notație și compunere

Ia o tablă de șah mică, de $3\times 3$, și pune pe ea trei turnuri, astfel încât să nu se atace între ele: câte unul pe fiecare linie și câte unul pe fiecare coloană. Câte așezări diferite există? Pe prima linie ai trei coloane la dispoziție; pe a doua îți rămân două; pe a treia, una singură. Deci $3\cdot 2\cdot 1=6$ așezări. Fiecare dintre ele este, de fapt, o regulă care asociază fiecărei linii exact o coloană — și nu oricum, ci fără repetiții.

Regula aceasta are un nume: se numește permutare, iar obiectul o să-ți fie de folos imediat. În lecțiile următoare vei calcula determinanți, iar determinantul unei matrice pătratice este exact o sumă de produse, în care fiecare produs ia câte un element din fiecare linie și din fiecare coloană — adică o așezare de turnuri care nu se atacă. Programa cere permutările doar ca instrument pentru definiția determinantului de ordin $n$, așa că lecția aceasta construiește exact atât: obiectul, notația lui și singura operație de care avem nevoie, compunerea. La lecția următoare adăugăm semnul, iar la Determinantul de ordin n: definiția cu permutări unealta intră în funcțiune.

Ce vei învăța

• Vei ști să definești o permutare de grad $n$ ca funcție bijectivă de la $\{1,2,\dots ,n\}$ la ea însăși și să deosebești noțiunea de „permutarea" din combinatorică.
• Vei ști să scrii o permutare în notația cu două linii și să citești din ea imaginea oricărui element.
• Vei ști câte elemente are mulțimea $S_n$ și de ce.
• Vei ști să compui două permutări în ordinea corectă și să arăți, pe exemplu, că rezultatul depinde de ordine.
• Vei ști să recunoști permutarea identică și să determini inversa unei permutări date.
• Vei ști să rezolvi ecuații simple de forma $\sigma \circ x=\tau$ și $x\circ \sigma =\tau$ în $S_n$.

Hai să descoperim împreună

1. Un cuvânt cunoscut, un obiect nou

În clasa a X-a, la Permutări: definiție și formulă, ai învățat că o permutare a unei mulțimi cu $n$ elemente este o așezare a tuturor elementelor într-o anumită ordine, iar numărul lor este $P_n=n!$. Acum privim același lucru din alt unghi, mai potrivit pentru calcule: în loc să spunem „am așezat elementele în ordinea $2,3,1$", spunem „am construit o funcție care duce locul $1$ în valoarea $2$, locul $2$ în valoarea $3$ și locul $3$ în valoarea $1$".

Cele două descrieri conțin aceeași informație, dar a doua se poate compune: dacă amesteci de două ori, efectul total este tot o funcție, obținută prin compunerea celor două. Tocmai de asta avem nevoie.

Definiție. Fie $n\in {\mathbb{N}}^{\ast }$ și fie mulțimea $A=\{1,2,\dots ,n\}$. Se numește permutare de grad $n$ orice funcție bijectivă $\sigma :A\to A$. Mulțimea tuturor permutărilor de grad $n$ se notează $S_n$.

Cerința de bijectivitate este esențială și o cunoști din Funcții injective, surjective, bijective: funcția trebuie să fie și injectivă (două locuri diferite nu pot primi aceeași valoare — două turnuri nu stau pe aceeași coloană), și surjectivă (fiecare valoare este folosită o dată — nicio coloană nu rămâne liberă). Pentru o funcție de la o mulțime finită la ea însăși, cele două condiții sunt echivalente, deci e destul să verifici că valorile sunt distincte două câte două.

2. Notația cu două linii

O permutare se scrie pe două rânduri, între paranteze rotunde: sus, argumentele $1,2,\dots ,n$ în ordine crescătoare; jos, imaginile lor, fiecare sub argumentul ei.

$$\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)\text{ıˆnseamna˘}\sigma (1)=2,\sigma (2)=3,\sigma (3)=1.$$

Citirea e mecanică: cauți numărul pe linia de sus și cobori. Verificarea că ai scris o permutare validă e la fel de mecanică: pe linia de jos trebuie să apară toate numerele de la $1$ la $n$, fiecare exact o dată.

Atenție la o capcană de scriere: în notația aceasta, linia de sus nu aduce nicio informație nouă (e mereu $1,2,\dots ,n$), dar nu se omite — ea e cea care spune sub ce argument stă fiecare imagine. Iar tabloul acesta cu două linii nu este o matrice: nu se adună, nu se înmulțește cu un scalar, nu are determinant. Împrumută doar parantezele.

3. Câte permutări de grad $n$ există

Pentru a construi o permutare alegem pe rând imaginile: pentru $\sigma (1)$ avem $n$ posibilități; pentru $\sigma (2)$ rămân $n-1$ (valoarea folosită nu se repetă); și tot așa, până la $\sigma (n)$, pentru care rămâne o singură posibilitate. Prin urmare

$$\mathrm{card}{S}_n=n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1=n!.$$

Este exact numărul $P_n$ din combinatorică — semn că cele două descrieri ale permutării vorbesc despre același lucru, numărat în același fel.

Creșterea este dramatică, iar asta explică o decizie de mai târziu: definiția determinantului de ordin $n$ va conține $n!$ produse, deci nu se folosește niciodată ca metodă de calcul pentru $n\ge 4$ — la ordinul $4$ ar însemna $24$ de produse de câte patru factori. Definiția e pentru înțeles; pentru calculat există dezvoltarea după o linie.

Iată toate cele șase permutări din $S_3$, scrise ordonat după linia a doua:

$$\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right),\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right),\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right),\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),\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right).$$

Scrierea lor în ordine „de dicționar" (după prima cifră a liniei de jos, apoi după a doua) e o disciplină care merită păstrată: așa nu sari nicio permutare și nu scrii una de două ori.

4. Compunerea: „întâi una, apoi cealaltă"

Două permutări de același grad se pot compune, pentru că sunt funcții de la $\{1,\dots ,n\}$ la $\{1,\dots ,n\}$: ieșirea uneia intră direct în cealaltă. Definiția e cea a compunerii funcțiilor, pe care o știi din Operații cu funcții. Compunerea:

$$(\sigma \circ \tau )(k)=\sigma (\tau (k)),k\in \{1,2,\dots ,n\}.$$

⚠️ Ordinea, o dată pentru totdeauna: în $\sigma \circ \tau$ se aplică întâi $\tau$, apoi $\sigma$. Se citește de la dreapta la stânga, exact ca la orice compunere de funcții. Este singura convenție folosită în această lecție, în toate lecțiile clasei a XI-a și în toate baremele; dacă o inversezi, jumătate dintre rezultate ies greșit.

Rezultatul compunerii a două permutări de grad $n$ este tot o permutare de grad $n$: compunerea a două funcții bijective este bijectivă, deci $\sigma \circ \tau \in S_n$.

Cum se calculează, practic. Iei pe rând $k=1,2,\dots ,n$ și faci două citiri: găsești $\tau (k)$ în tabloul din dreapta, apoi cauți acest număr pe linia de sus a tabloului din stânga și cobori. Scrii rezultatul sub $k$ în tabloul final. Trei citiri pentru $S_3$, patru pentru $S_4$ — mai puțin decât pare.

5. Exemplul-etalon: compunerea nu este comutativă

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).$$

Calculăm $\sigma \circ \tau$, adică „întâi $\tau$, apoi $\sigma$":

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

Deci

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

Acum schimbăm ordinea și calculăm $\tau \circ \sigma$, adică „întâi $\sigma$, apoi $\tau$":

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

adică

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

Cele două rezultate sunt diferite. Concluzia, de reținut ca atare: compunerea permutărilor nu este comutativă. Există perechi care comută (orice permutare comută cu ea însăși și cu permutarea identică), dar nu e regula. De aceea, într-un enunț, „calculați $\sigma \circ \tau$" și „calculați $\tau \circ \sigma$" sunt două cerințe distincte, iar la Bacalaureat M1 se punctează separat.

6. Permutarea identică

Printre cele $n!$ permutări există una care nu mișcă nimic: cea care duce fiecare element în el însuși. Se notează cu $e$ și se numește permutarea identică:

$$e=\left(\begin{array}{ccccc}1& 2& 3& \cdots & n\\ 1& 2& 3& \cdots & n\end{array}\right),e(k)=k\text{ pentru orice }k.$$

Ea joacă, la compunere, rolul pe care îl joacă $1$ la înmulțirea numerelor: pentru orice $\sigma \in S_n$,

$$\sigma \circ e=e\circ \sigma =\sigma .$$

Verificarea e imediată: $(\sigma \circ e)(k)=\sigma (e(k))=\sigma (k)$ și $(e\circ \sigma )(k)=e(\sigma (k))=\sigma (k)$.

7. Inversa unei permutări

O permutare este funcție bijectivă, deci are inversă, iar inversa ei este tot o funcție bijectivă de la $\{1,\dots ,n\}$ la $\{1,\dots ,n\}$ — adică tot o permutare de grad $n$. Se notează ${\sigma }^{-1}$ și este definită de condiția

$$\sigma \circ {\sigma }^{-1}={\sigma }^{-1}\circ \sigma =e.$$

Cum se află, în două mișcări. Schimbi între ele cele două linii ale tabloului (imaginile sus, argumentele jos), apoi reordonezi coloanele astfel încât linia de sus să devină $1,2,\dots ,n$. Pentru $\sigma$ de mai sus:

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

Control obligatoriu: $(\sigma \circ {\sigma }^{-1})(1)=\sigma (3)=1$, $(\sigma \circ {\sigma }^{-1})(2)=\sigma (1)=2$, $(\sigma \circ {\sigma }^{-1})(3)=\sigma (2)=3$, deci într-adevăr $\sigma \circ {\sigma }^{-1}=e$.

O permutare poate fi propria ei inversă: pentru $\tau$ din exemplul-etalon avem $\tau \circ \tau =e$, deci ${\tau }^{-1}=\tau$. Se întâmplă ori de câte ori permutarea doar schimbă între ele câteva perechi de valori și lasă restul pe loc.

Regula de inversare a unui produs. Ca la orice compunere de funcții bijective, $(\sigma \circ \tau {)}^{-1}={\tau }^{-1}\circ {\sigma }^{-1}$ — ordinea se răstoarnă. Intuiția: dacă îmbraci întâi cămașa și apoi haina, la dezbrăcat scoți întâi haina.

8. Proprietățile compunerii, strânse la un loc

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

• asociativitate: $(\sigma \circ \tau )\circ \rho =\sigma \circ (\tau \circ \rho )$ — moștenită de la compunerea funcțiilor, deci se poate scrie $\sigma \circ \tau \circ \rho$ fără paranteze;
• element neutru: $\sigma \circ e=e\circ \sigma =\sigma$;
• inversă: $\sigma \circ {\sigma }^{-1}={\sigma }^{-1}\circ \sigma =e$;
• necomutativitate: în general $\sigma \circ \tau \ne \tau \circ \sigma$ (vezi exemplul-etalon).

Un exemplu de asociativitate, cu $\rho =\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$ și $\sigma$, $\tau$ de mai sus: $(\sigma \circ \tau )\circ \rho$ duce $1\to \rho (1)=3\to (\sigma \circ \tau )(3)=1$, apoi $2\to 1\to 3$ și $3\to 2\to 2$; iar $\sigma \circ (\tau \circ \rho )$ dă aceleași imagini. Ambele au rezultatul $\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$.

Aici ne oprim: programa cere permutările doar ca instrument pentru definiția determinantului, „fără extinderi la alte proprietăți sau particularități". Ce urmează în lecția Inversiuni și semnul unei permutări este ultima piesă de care avem nevoie — un număr $\epsilon (\sigma )\in \{-1,+1\}$ atașat fiecărei permutări. Cu el, determinantul de ordin $n$ va putea fi scris într-un singur rând.

Exemple rezolvate

Exemplul 1 — Recunoașterea unei permutări

Care dintre tablourile următoare reprezintă permutări de grad $4$? $A=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$, $B=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 2& 3\end{array}\right)$, $C=\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 5& 3& 4\end{array}\right)$.

Rezolvare. Verificăm de fiecare dată linia de jos: trebuie să conțină exact numerele $1,2,3,4$, fiecare o dată.

$A$: linia de jos este $3,1,4,2$ — toate cele patru numere, fără repetiție. Deci $A\in S_4$.

$B$: valoarea $2$ apare de două ori (sub $1$ și sub $3$), iar $1$ nu apare deloc. Funcția nu e injectivă, deci $B\notin S_4$.

$C$: apare valoarea $5$, care nu este în mulțimea $\{1,2,3,4\}$; funcția nici măcar nu ia valori în mulțimea cerută. Deci $C\notin S_4$.

Exemplul 2 — Compunere în $S_3$, în ambele ordini

Fie $u=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$ și $v=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$. Calculați $u\circ v$ și $v\circ u$.

Rezolvare. Pentru $u\circ v$ aplicăm întâi $v$, apoi $u$:

$$(u\circ v)(1)=u(1)=3,(u\circ v)(2)=u(3)=2,(u\circ v)(3)=u(2)=1,$$

deci $u\circ v=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$.

Pentru $v\circ u$ aplicăm întâi $u$, apoi $v$:

$$(v\circ u)(1)=v(3)=2,(v\circ u)(2)=v(1)=1,(v\circ u)(3)=v(2)=3,$$

deci $v\circ u=\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$. Într-adevăr, $u\circ v\ne v\circ u$.

Exemplul 3 — Inversa unei permutări de grad $4$

Determinați inversa permutării $\alpha =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$ și verificați rezultatul.

Rezolvare. Schimbăm liniile și reordonăm coloanele după linia de sus:

$$\left(\begin{array}{cccc}3& 1& 4& 2\\ 1& 2& 3& 4\end{array}\right)⟶{\alpha }^{-1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right).$$

Citim direct: $\alpha (2)=1$, deci ${\alpha }^{-1}(1)=2$; $\alpha (4)=2$, deci ${\alpha }^{-1}(2)=4$; $\alpha (1)=3$, deci ${\alpha }^{-1}(3)=1$; $\alpha (3)=4$, deci ${\alpha }^{-1}(4)=3$.

Verificare: $(\alpha \circ {\alpha }^{-1})(1)=\alpha (2)=1$, $(\alpha \circ {\alpha }^{-1})(2)=\alpha (4)=2$, $(\alpha \circ {\alpha }^{-1})(3)=\alpha (1)=3$, $(\alpha \circ {\alpha }^{-1})(4)=\alpha (3)=4$. Deci $\alpha \circ {\alpha }^{-1}=e$.

Exemplul 4 — Puterile unei permutări

Fie $w=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$. Calculați $w\circ w$ și $w\circ w\circ w$.

Rezolvare. Permutarea $w$ „împinge cu un pas": $1\to 2\to 3\to 4\to 1$. Compunând-o cu ea însăși, împinge cu doi pași:

$$(w\circ w)(1)=w(2)=3,(w\circ w)(2)=w(3)=4,(w\circ w)(3)=w(4)=1,(w\circ w)(4)=w(1)=2,$$

deci $w\circ w=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$. Încă o compunere cu $w$ dă trei pași:

$$w\circ w\circ w=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 1& 2& 3\end{array}\right).$$

Observație utilă pentru control: mai compunând o dată cu $w$ am obține patru pași, adică revenirea la punctul de plecare — permutarea identică $e$.

Exemplul 5 — Ecuație în $S_3$

Rezolvați în $S_3$ ecuația $\sigma \circ x=\tau$, unde $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$.

Rezolvare. Compunem ambii membri la stânga cu ${\sigma }^{-1}$ — de care parte se înmulțește contează, pentru că operația nu e comutativă:

$${\sigma }^{-1}\circ (\sigma \circ x)={\sigma }^{-1}\circ \tau ⟹({\sigma }^{-1}\circ \sigma )\circ x={\sigma }^{-1}\circ \tau ⟹e\circ x={\sigma }^{-1}\circ \tau ⟹x={\sigma }^{-1}\circ \tau .$$

Am folosit asociativitatea și proprietatea elementului neutru. Cu ${\sigma }^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$ obținem

$$x(1)={\sigma }^{-1}(\tau (1))={\sigma }^{-1}(2)=1,x(2)={\sigma }^{-1}(1)=3,x(3)={\sigma }^{-1}(3)=2,$$

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

Verificare: $(\sigma \circ x)(1)=\sigma (1)=2$, $(\sigma \circ x)(2)=\sigma (3)=1$, $(\sigma \circ x)(3)=\sigma (2)=3$ — exact $\tau$.

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră permutările $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right)$ și $\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$ din $S_4$. a) Calculați $\sigma \circ \tau$. b) Determinați ${\sigma }^{-1}$. c) Rezolvați în $S_4$ ecuația $\sigma \circ x=\tau$.

Rezolvare. a) Aplicăm întâi $\tau$, apoi $\sigma$:

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

Deci $\sigma \circ \tau =e$ — cele două permutări sunt una inversa celeilalte.

b) Din punctul a) rezultă direct ${\sigma }^{-1}=\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$. Verificăm și prin schimbarea liniilor: din $\sigma (3)=1$ avem ${\sigma }^{-1}(1)=3$; din $\sigma (1)=2$, ${\sigma }^{-1}(2)=1$; din $\sigma (4)=3$, ${\sigma }^{-1}(3)=4$; din $\sigma (2)=4$, ${\sigma }^{-1}(4)=2$. ✓

c) Ca la exemplul 5, $x={\sigma }^{-1}\circ \tau =\tau \circ \tau$. Calculăm:

$$x(1)=\tau (\tau (1))=\tau (3)=4,x(2)=\tau (1)=3,x(3)=\tau (4)=2,x(4)=\tau (2)=1,$$

deci $x=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$.

Verificare: $(\sigma \circ x)(1)=\sigma (4)=3$, $(\sigma \circ x)(2)=\sigma (3)=1$, $(\sigma \circ x)(3)=\sigma (2)=4$, $(\sigma \circ x)(4)=\sigma (1)=2$ — adică exact $\tau$. ✓

Să exersăm

La fiecare compunere, scrie mai întâi ce înseamnă: „întâi cea din dreapta, apoi cea din stânga". La fiecare rezultat, verifică dacă linia de jos conține toate numerele de la $1$ la $n$, fiecare o dată — dacă nu, ai greșit undeva.

1. Câte elemente are $S_5$? Dar $S_6$? Dar $S_7$?

2. Fie $u=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$. Scrie $u(1)$, $u(2)$, $u(3)$ și verifică faptul că $u$ este o permutare.

3. Cu $u$ de mai sus și $v=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$, calculează $u\circ v$ și $v\circ u$.

4. Pentru aceleași $u$ și $v$, determină $u^{-1}$ și $v^{-1}$.

5. (Adevărat/Fals cu motivare.) „Pentru orice două permutări $\sigma ,\tau \in S_n$ avem $\sigma \circ \tau =\tau \circ \sigma$."

6. Fie $a=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right)$ și $b=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$. Calculează $a\circ b$ și $b\circ a$ și compară rezultatele.

7. Pentru $a$ și $b$ de la exercițiul precedent, determină $a^{-1}$ și $b^{-1}$.

8. Rezolvă în $S_3$ ecuația $\sigma \circ x=\tau$, unde $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$.

9. Rezolvă în $S_3$ ecuația $x\circ \sigma =\tau$, cu aceleași $\sigma$ și $\tau$. Compară cu răspunsul de la exercițiul $8$.

10. Fie $w=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$. Calculează $w\circ w$, $w\circ w\circ w$ și $w\circ w\circ w\circ w$.

11. (Adevărat/Fals cu motivare.) „Singura permutare din $S_n$ care este propria ei inversă este permutarea identică."

12. (Problemă aplicată.) Un utilaj mută patru piese de pe pozițiile $1,2,3,4$ după regula $\pi =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$ (piesa de pe poziția $k$ ajunge pe poziția $\pi (k)$). Ce se întâmplă dacă utilajul face ciclul de două ori la rând?

13. Determină toate permutările din $S_3$ care comută cu $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$, adică toate $x$ cu $\sigma \circ x=x\circ \sigma$.

14. Fie $p=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$ și $q=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 4& 3\end{array}\right)$. Calculează $p\circ q$ și $q\circ p$.

15. (Exercițiu tip Bacalaureat M1.) Se consideră $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right)$ și $\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$. a) Arată că $\sigma \circ \tau =e$. b) Deduce ${\sigma }^{-1}$. c) Rezolvă ecuația $x\circ \sigma =\tau$.

16. Verifică pe exemplul $\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)$ egalitatea $(\sigma \circ \tau {)}^{-1}={\tau }^{-1}\circ {\sigma }^{-1}$.

17. Câte permutări din $S_4$ au proprietatea $\sigma (1)=3$? Dar câte au $\sigma (1)=3$ și $\sigma (2)=1$?

18. (Provocare.) Pe o tablă $4\times 4$ se așază patru turnuri astfel încât să nu se atace două câte două. Câte așezări există? Explică de ce fiecare așezare corespunde exact unei permutări din $S_4$ și cum se citește permutarea din desen.

Răspunsuri și explicații

1. $\mathrm{card}{S}_5=5!=120$, $\mathrm{card}{S}_6=6!=720$, $\mathrm{card}{S}_7=7!=5040$. Fiecare grad adăugat înmulțește numărul cu $n$.

2. $u(1)=3$, $u(2)=1$, $u(3)=2$. Linia de jos, $3,1,2$, conține fiecare dintre numerele $1,2,3$ exact o dată, deci $u$ este bijectivă, adică o permutare de grad $3$.

3. $u\circ v$: $u(v(1))=u(1)=3$; $u(v(2))=u(3)=2$; $u(v(3))=u(2)=1$, deci $u\circ v=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$. $v\circ u$: $v(u(1))=v(3)=2$; $v(u(2))=v(1)=1$; $v(u(3))=v(2)=3$, deci $v\circ u=\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$. Rezultatele diferă.

4. $u^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ (din $u(2)=1$, $u(3)=2$, $u(1)=3$). Iar $v^{-1}=v=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$, pentru că $v$ doar schimbă între ele valorile $2$ și $3$, deci aplicată de două ori dă $e$.

5. Fals. Contraexemplul din lecție: pentru $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$ avem $\sigma \circ \tau =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$, iar $\tau \circ \sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$. Un singur contraexemplu răstoarnă afirmația.

6. $a\circ b$: $a(b(1))=a(4)=3$; $a(3)=1$; $a(2)=4$; $a(1)=2$, deci $a\circ b=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$. $b\circ a$: $b(a(1))=b(2)=3$; $b(4)=1$; $b(1)=4$; $b(3)=2$, deci $b\circ a=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$. Aici cele două rezultate coincid — o dovadă că necomutativitatea este regula generală, nu o lege fără excepții.

7. $a^{-1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$ (din $a(3)=1$, $a(1)=2$, $a(4)=3$, $a(2)=4$). Iar $b^{-1}=b$, pentru că $b$ schimbă între ele perechile $1\leftrightarrow 4$ și $2\leftrightarrow 3$, deci aplicată de două ori revine la $e$.

8. $x={\sigma }^{-1}\circ \tau$, cu ${\sigma }^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$: $x(1)={\sigma }^{-1}(2)=1$; $x(2)={\sigma }^{-1}(1)=3$; $x(3)={\sigma }^{-1}(3)=2$. Deci $x=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$.

9. Aici se compune la dreapta cu ${\sigma }^{-1}$: din $x\circ \sigma =\tau$ obținem $x=\tau \circ {\sigma }^{-1}$. Calculăm: $x(1)=\tau ({\sigma }^{-1}(1))=\tau (3)=3$; $x(2)=\tau (1)=2$; $x(3)=\tau (2)=1$, deci $x=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$ — alt rezultat decât la exercițiul $8$, exact pentru că operația nu e comutativă.

10. $w\circ w=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$; $w\circ w\circ w=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 1& 2& 3\end{array}\right)$; compunând a patra oară obținem $e$, pentru că fiecare element a făcut un tur complet.

11. Fals. De exemplu $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$ verifică $\tau \circ \tau =e$, deci ${\tau }^{-1}=\tau$, deși $\tau \ne e$. Orice permutare care doar schimbă între ele perechi de valori are aceeași proprietate.

12. Aplicarea de două ori înseamnă $\pi \circ \pi$: $\pi (\pi (1))=\pi (3)=1$; $\pi (\pi (2))=\pi (4)=2$; $\pi (\pi (3))=\pi (1)=3$; $\pi (\pi (4))=\pi (2)=4$. Deci $\pi \circ \pi =e$: după două cicluri, toate piesele sunt exact pe pozițiile de plecare. Utilajul „se anulează singur".

13. Sunt trei: $e=\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right)$, $\sigma$ însăși și $\sigma \circ \sigma =\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$. Se verifică prin calcul direct că celelalte trei permutări din $S_3$ nu comută cu $\sigma$; de exemplu, pentru $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$ am văzut deja că $\sigma \circ \tau \ne \tau \circ \sigma$.

14. $p\circ q$: $p(q(1))=p(2)=3$; $p(1)=2$; $p(4)=1$; $p(3)=4$, deci $p\circ q=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 2& 1& 4\end{array}\right)$. $q\circ p$: $q(p(1))=q(2)=1$; $q(3)=4$; $q(4)=3$; $q(1)=2$, deci $q\circ p=\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 4& 3& 2\end{array}\right)$. Diferite.

15. a) $(\sigma \circ \tau )(1)=\sigma (3)=1$, $(\sigma \circ \tau )(2)=\sigma (1)=2$, $(\sigma \circ \tau )(3)=\sigma (4)=3$, $(\sigma \circ \tau )(4)=\sigma (2)=4$, deci $\sigma \circ \tau =e$. b) Din a) rezultă ${\sigma }^{-1}=\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$. c) $x=\tau \circ {\sigma }^{-1}=\tau \circ \tau$: $x(1)=\tau (3)=4$; $x(2)=\tau (1)=3$; $x(3)=\tau (4)=2$; $x(4)=\tau (2)=1$, deci $x=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$. Verificare: $(x\circ \sigma )(1)=x(2)=3$, $(x\circ \sigma )(2)=x(4)=1$, $(x\circ \sigma )(3)=x(1)=4$, $(x\circ \sigma )(4)=x(3)=2$ — adică $\tau$. ✓

16. Avem $\sigma \circ \tau =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$, care este propria ei inversă, deci $(\sigma \circ \tau {)}^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$. Pe de altă parte ${\tau }^{-1}=\tau$ și ${\sigma }^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$, iar $({\tau }^{-1}\circ {\sigma }^{-1})(1)=\tau (3)=3$, $({\tau }^{-1}\circ {\sigma }^{-1})(2)=\tau (1)=2$, $({\tau }^{-1}\circ {\sigma }^{-1})(3)=\tau (2)=1$. Aceeași permutare. ✓

17. Dacă $\sigma (1)=3$ este fixat, rămân de repartizat valorile $1,2,4$ pe pozițiile $2,3,4$, în orice ordine: $3!=6$ permutări. Dacă se fixează și $\sigma (2)=1$, rămân valorile $2$ și $4$ pentru pozițiile $3$ și $4$: $2!=2$ permutări.

18. Sunt $4!=24$ de așezări. Fiecare așezare pune exact un turn pe fiecare linie, deci definește o funcție $\sigma$ de la mulțimea liniilor la mulțimea coloanelor ($\sigma (i)=$ coloana turnului de pe linia $i$); condiția „niciun turn nu se atacă" spune că nu există două turnuri pe aceeași coloană, adică $\sigma$ e injectivă, deci bijectivă. Reciproc, orice permutare din $S_4$ dă o așezare validă. Permutarea se citește din desen luând, linie cu linie de sus în jos, numărul coloanei în care stă turnul.

De reținut

• Definiția: o permutare de grad $n$ este o funcție bijectivă $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$; mulțimea lor se notează $S_n$ și are $\mathrm{card}{S}_n=n!$ elemente.
• Notația cu două linii: sus argumentele în ordine crescătoare, jos imaginile. Un tablou e permutare valabilă doar dacă linia de jos conține fiecare număr de la $1$ la $n$ exact o dată.
• Ordinea compunerii: $(\sigma \circ \tau )(k)=\sigma (\tau (k))$ — întâi cea din dreapta, apoi cea din stânga. Se citește de la dreapta la stânga.
• Compunerea nu este comutativă: în general $\sigma \circ \tau \ne \tau \circ \sigma$. De aceea, în ecuații, contează de care parte compui.
• Identitatea și inversa: $\sigma \circ e=e\circ \sigma =\sigma$ și $\sigma \circ {\sigma }^{-1}={\sigma }^{-1}\circ \sigma =e$; inversa se obține schimbând liniile și reordonând coloanele.

Greșeli frecvente

• Compunerea în ordine inversă. A calcula $\sigma (\tau (k))$ „aplicând întâi $\sigma$" este greșeala numărul unu. Scrie de fiecare dată, înainte de calcul, fraza „întâi $\tau$, apoi $\sigma$"; ea te costă trei secunde și îți salvează tot exercițiul.
• Uitarea liniei de sus. Scrisul lui $\sigma$ ca simplu șir $231$ merge cât timp lucrezi singur, dar într-o lucrare tabloul se cere complet: fără linia argumentelor, nu se vede sub ce număr stă fiecare imagine.
• Confuzia cu matricele. Tabloul cu două linii nu este o matrice: nu se adună cu altul, nu se înmulțește cu un scalar și nu are determinant. Coincidența de scriere e doar tipografică.
• Inversa obținută „schimbând liniile" și atât. După schimbarea liniilor trebuie reordonate coloanele, ca sus să apară $1,2,\dots ,n$. Cine sare pasul acesta obține un tablou corect ca informație, dar scris greșit — și nemarcat la corectare.
• Compunerea de partea greșită într-o ecuație. Din $\sigma \circ x=\tau$ rezultă $x={\sigma }^{-1}\circ \tau$, iar din $x\circ \sigma =\tau$ rezultă $x=\tau \circ {\sigma }^{-1}$. Cele două soluții sunt, în general, diferite.

Aplică acasă

1. Tabla de turnuri. Desenează o tablă $4\times 4$ și așază patru turnuri care nu se atacă. Scrie permutarea corespunzătoare, apoi mai desenează două așezări și scrie-le permutările. Verifică de fiecare dată că linia de jos conține exact numerele $1,2,3,4$.

2. Amestecul de cărți de joc. Ia patru cărți, numerotează pozițiile $1$–$4$ și inventează o regulă de amestecare (de exemplu: prima carte trece pe locul al treilea). Scrie permutarea, apoi aplic-o de două ori și verifică prin calcul dacă rezultatul coincide cu ce vezi pe masă.

3. Toate cele șase. Scrie pe o foaie toate permutările din $S_3$ și, pentru fiecare, inversa ei. Vei observa că trei dintre ele sunt propriile inverse, iar celelalte două nenule formează o pereche. Explică, în două fraze, de ce identitatea apare mereu ca inversă a ei însăși.

Pentru părinți și profesori

Lecția introduce prima noțiune nouă din unitatea de determinanți și e, prin natura ei, o lecție de notație și disciplină de calcul, nu de raționament greu. Programa cere explicit permutările „doar ca instrumente necesare introducerii definiției determinantului de ordin $n$, fără extinderi", deci nu se predau notația pe cicluri, ordinul unei permutări sau structura algebrică a lui $S_n$ — orice adaos în această direcție iese din programă și consumă timp din capitolul de determinanți.

De verificat în caiet: (1) linia de jos a fiecărui tablou conține toate numerele o dată; (2) la orice compunere e scris explicit „întâi cea din dreapta"; (3) inversa e obținută cu reordonarea coloanelor, nu doar cu schimbarea liniilor; (4) la ecuații, compunerea s-a făcut de partea corectă. Întrebări de control: „Ce înseamnă $\sigma \circ \tau$?"; „Câte elemente are $S_4$?"; „Cum verifici că un tablou e permutare?"; „De ce $\sigma \circ x=\tau$ și $x\circ \sigma =\tau$ au soluții diferite?".

La BAC M1 permutările apar aproape întotdeauna ca punct de plecare în subiectele de algebră: se cere o compunere, o inversă sau semnul (lecția următoare), iar apoi se trece la determinanți. Semn că elevul a înțeles: calculează o compunere de grad $4$ fără ezitare și își verifică singur rezultatul, aplicând inversa.

Întrebări frecvente

Ce este o permutare de grad n? Este o funcție bijectivă de la mulțimea $\{1,2,\dots ,n\}$ la ea însăși. Practic, o regulă care duce fiecare număr de la $1$ la $n$ într-un număr din aceeași mulțime, fără repetiții și fără să sară vreo valoare.

Cum se scrie o permutare cu două linii? Pe linia de sus se scriu argumentele $1,2,\dots ,n$ în ordine crescătoare, iar pe linia de jos, sub fiecare argument, imaginea lui. Tot tabloul se pune între paranteze rotunde.

Cum se compun două permutări? $(\sigma \circ \tau )(k)=\sigma (\tau (k))$: se aplică întâi permutarea din dreapta, apoi cea din stânga. Pentru fiecare $k$ cauți $\tau (k)$, apoi cauți acest număr pe linia de sus a lui $\sigma$ și cobori.

De ce compunerea permutărilor nu este comutativă? Pentru că ordinea în care aplici două transformări schimbă rezultatul. Exemplul clasic: pentru $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$ se obține $\sigma \circ \tau =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$, dar $\tau \circ \sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$.

Cum se află inversa unei permutări? Schimbi cele două linii între ele, apoi reordonezi coloanele astfel încât linia de sus să fie $1,2,\dots ,n$. Verificarea se face compunând: trebuie să obții permutarea identică.

Ce este permutarea identică? Este permutarea $e$ care duce fiecare element în el însuși; are pe ambele linii aceleași numere. La compunere se comportă ca numărul $1$ la înmulțire: $\sigma \circ e=e\circ \sigma =\sigma$.

Câte permutări de grad n există? Exact $n!$: la prima poziție ai $n$ alegeri, la a doua $n-1$, și tot așa. Pentru $n=3$ sunt $6$, pentru $n=4$ sunt $24$, pentru $n=5$ sunt $120$.

La ce folosesc permutările la clasa a XI-a? Exclusiv la construirea definiției determinantului de ordin $n$: fiecare termen al determinantului corespunde unei permutări, iar semnul lui e dat de signatura acesteia. De aceea capitolul le tratează pe scurt, ca instrument, și trece mai departe.