Permutări: compunere, inversă — lecție clasa a 11-a: teorie, exemple, exerciții

În această lecție afli ce este o permutare de gradul $n$ (o funcție bijectivă a mulțimii $\{1,2,\dots ,n\}$ pe ea însăși), cum se compun două permutări, cum se află inversa și cum se calculează puterile unei permutări. Permutările sunt primul capitol de algebră din clasa a XI-a: stau la baza definiției determinantului și reapar în clasa a XII-a la grupuri.

Teorie

Definiție și notație

Fie $n\in {\mathbb{N}}^{\ast }$ și $A=\{1,2,\dots ,n\}$. O funcție bijectivă $\sigma :A\to A$ se numește permutare de gradul $n$. Se scrie sub forma unui tabel cu două linii: pe prima linie elementele lui $A$, pe a doua imaginile lor:

$$\sigma =\left(\begin{array}{cccc}1& 2& \dots & n\\ \sigma (1)& \sigma (2)& \dots & \sigma (n)\end{array}\right).$$

Pentru că $\sigma$ este bijectivă, linia a doua conține fiecare număr de la 1 la $n$ exact o dată. Mulțimea permutărilor de gradul $n$ se notează $S_n$ și are $n!$ elemente (în clasa a X-a ai numărat funcțiile bijective $A\to A$). Exemplu: $S_3$ are $3!=6$ elemente.

Două permutări $\sigma ,\tau \in S_n$ sunt egale dacă $\sigma (k)=\tau (k)$ pentru orice $k\in A$. Permutarea identică este $e=\left(\begin{array}{cccc}1& 2& \dots & n\\ 1& 2& \dots & n\end{array}\right)$, adică $e(k)=k$.

Compunerea permutărilor

Produsul (compusul) permutărilor $\sigma ,\tau \in S_n$ este $\sigma \tau =\sigma \circ \tau$, definit prin

$$(\sigma \tau )(k)=\sigma (\tau (k)),k=1,2,\dots ,n.$$

Se aplică întâi $\tau$ (cea din dreapta), apoi $\sigma$. Compunerea a două bijecții este o bijecție, deci $\sigma \tau \in S_n$.

Proprietăți (pentru orice $\sigma ,\tau ,\pi \in S_n$):

• asociativitate: $(\sigma \tau )\pi =\sigma (\tau \pi )$ (compunerea funcțiilor este asociativă);
• element neutru: $\sigma e=e\sigma =\sigma$;
• în general nu este comutativă: pentru $n\ge 3$ există $\sigma ,\tau$ cu $\sigma \tau \ne \tau \sigma$ (exemplul 1). În $S_1$ și $S_2$ compunerea este comutativă.

Inversa unei permutări

Orice permutare $\sigma$ este bijectivă, deci are o funcție inversă ${\sigma }^{-1}\in S_n$, cu $\sigma {\sigma }^{-1}={\sigma }^{-1}\sigma =e$. Dacă $\sigma (i)=j$, atunci ${\sigma }^{-1}(j)=i$. Practic: schimbi între ele cele două linii și apoi reordonezi coloanele astfel încât prima linie să fie $1,2,\dots ,n$.

Proprietăți: $({\sigma }^{-1}{)}^{-1}=\sigma$ și $(\sigma \tau {)}^{-1}={\tau }^{-1}{\sigma }^{-1}$ (ordinea se inversează), pentru că $(\sigma \tau )({\tau }^{-1}{\sigma }^{-1})=\sigma (\tau {\tau }^{-1}){\sigma }^{-1}=\sigma {\sigma }^{-1}=e$.

Ecuații cu permutări

Pentru $\sigma ,\tau \in S_n$ date, fiecare ecuație are soluție unică:

$$\sigma x=\tau ⟺x={\sigma }^{-1}\tau ,x\sigma =\tau ⟺x=\tau {\sigma }^{-1}.$$

Se înmulțește cu ${\sigma }^{-1}$ de aceeași parte pe care se află $\sigma$; cele două soluții sunt în general diferite (exemplul 3).

Puterile unei permutări

Se definesc ${\sigma }^0=e$, ${\sigma }^1=\sigma$, ${\sigma }^{k+1}={\sigma }^k\sigma$; au loc ${\sigma }^m{\sigma }^p={\sigma }^{m+p}$ și $({\sigma }^m{)}^p={\sigma }^{mp}$. Cum $S_n$ are un număr finit de elemente, printre $\sigma ,{\sigma }^2,{\sigma }^3,\dots$ se repetă ceva, deci există un cel mai mic $k\ge 1$ cu ${\sigma }^k=e$, numit ordinul permutării. Atunci

$${\sigma }^N={\sigma }^r,\text{unde }r\text{ este restul împărțirii lui }N\text{ la }k.$$

O transpoziție $(ij)$ schimbă între ele doar $i$ și $j$ și lasă celelalte numere pe loc; pentru ea $(ij{)}^2=e$, deci $(ij{)}^{-1}=(ij)$.

De reținut

• $|S_n|=n!$; în linia a doua a unei permutări fiecare număr apare o singură dată.
• $(\sigma \tau )(k)=\sigma (\tau (k))$: calculezi de la dreapta la stânga.
• Compunerea este asociativă, are elementul neutru $e$, dar nu este comutativă pentru $n\ge 3$.
• Inversa: schimbi liniile și reordonezi; $(\sigma \tau {)}^{-1}={\tau }^{-1}{\sigma }^{-1}$.
• Puteri mari: afli ordinul $k$ și reduci exponentul modulo $k$.

Exemple rezolvate

Exemplul 1. Fie $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$. Calculează $\sigma \tau$ și $\tau \sigma$.

Vezi rezolvarea

1. $(\sigma \tau )(1)=\sigma (\tau (1))=\sigma (1)=2$; $(\sigma \tau )(2)=\sigma (3)=1$; $(\sigma \tau )(3)=\sigma (2)=3$.
2. $(\tau \sigma )(1)=\tau (\sigma (1))=\tau (2)=3$; $(\tau \sigma )(2)=\tau (3)=2$; $(\tau \sigma )(3)=\tau (1)=1$.
3. $\sigma \tau \ne \tau \sigma$: compunerea permutărilor nu este comutativă.

Răspuns: $\sigma \tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$, $\tau \sigma =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$

Exemplul 2. Află inversa permutării $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$.

Vezi rezolvarea

1. Schimbi liniile: $\left(\begin{array}{cccc}3& 1& 4& 2\\ 1& 2& 3& 4\end{array}\right)$, adică ${\sigma }^{-1}(3)=1$, ${\sigma }^{-1}(1)=2$, ${\sigma }^{-1}(4)=3$, ${\sigma }^{-1}(2)=4$.
2. Reordonezi coloanele după prima linie: ${\sigma }^{-1}(1)=2$, ${\sigma }^{-1}(2)=4$, ${\sigma }^{-1}(3)=1$, ${\sigma }^{-1}(4)=3$.
3. Verificare: $(\sigma {\sigma }^{-1})(1)=\sigma (2)=1$, $(\sigma {\sigma }^{-1})(2)=\sigma (4)=2$, $(\sigma {\sigma }^{-1})(3)=\sigma (1)=3$, $(\sigma {\sigma }^{-1})(4)=\sigma (3)=4$.

Răspuns: ${\sigma }^{-1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right)$

Exemplul 3. Cu $\sigma$ și $\tau$ din exemplul 1, rezolvă în $S_3$ ecuațiile a) $\sigma x=\tau$; b) $x\sigma =\tau$.

Vezi rezolvarea

1. Inversa lui $\sigma$: din $\sigma (1)=2$, $\sigma (2)=3$, $\sigma (3)=1$ rezultă ${\sigma }^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$.
2. a) $x={\sigma }^{-1}\tau$: $x(1)={\sigma }^{-1}(1)=3$, $x(2)={\sigma }^{-1}(3)=2$, $x(3)={\sigma }^{-1}(2)=1$.
3. b) $x=\tau {\sigma }^{-1}$: $x(1)=\tau (3)=2$, $x(2)=\tau (1)=1$, $x(3)=\tau (2)=3$.
4. Verificare a): $\sigma x$ duce $1\to 3\to 1$, $2\to 2\to 3$, $3\to 1\to 2$, adică $\tau$.

Răspuns: a) $x=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$; b) $x=\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$

Exemplul 4. Fie $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 3& 4& 1\end{array}\right)$. Calculează ${\sigma }^2$, ${\sigma }^3$, ${\sigma }^4$ și ${\sigma }^{2026}$.

Vezi rezolvarea

1. ${\sigma }^2(k)=\sigma (\sigma (k))$: $1\to 3$, $2\to 4$, $3\to 1$, $4\to 2$, deci ${\sigma }^2=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$.
2. ${\sigma }^3={\sigma }^2\sigma$: $1\to 4$, $2\to 1$, $3\to 2$, $4\to 3$, deci ${\sigma }^3=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 1& 2& 3\end{array}\right)$.
3. ${\sigma }^4={\sigma }^3\sigma =e$ (fiecare număr „înaintează” de 4 ori cu câte un pas și revine pe loc), deci ordinul lui $\sigma$ este 4.
4. $2026=4\cdot 506+2$, deci ${\sigma }^{2026}=({\sigma }^4{)}^{506}{\sigma }^2={\sigma }^2$.

Răspuns: ${\sigma }^4=e$, ${\sigma }^{2026}={\sigma }^2=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$

Exemplul 5. Determină toate permutările $\sigma \in S_3$ pentru care ${\sigma }^2=e$.

Vezi rezolvarea

1. ${\sigma }^2=e$ înseamnă $\sigma ={\sigma }^{-1}$: dacă $\sigma (i)=j$, atunci și $\sigma (j)=i$. Numerele sunt fie fixe, fie schimbate în perechi.
2. Toate fixe: $e$. O pereche schimbată (o transpoziție): $(12)$, $(13)$, $(23)$. Două perechi disjuncte nu încap în $\{1,2,3\}$.
3. Celelalte două permutări din $S_3$, $\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și inversa ei, au ordinul 3, deci nu verifică.

Răspuns: 4 permutări: $e$, $\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$, $\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$

Exemplul 6 (nivel Bacalaureat). Se consideră $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 4& 3\end{array}\right)$ și $\tau =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 1& 2\end{array}\right)$. a) Arată că $\sigma \tau =\tau \sigma$. b) Calculează $(\sigma \tau {)}^{2027}$. c) Rezolvă ecuația $\sigma x=\tau$.

Vezi rezolvarea

1. a) $(\sigma \tau )(1)=\sigma (3)=4$, $(\sigma \tau )(2)=\sigma (4)=3$, $(\sigma \tau )(3)=\sigma (1)=2$, $(\sigma \tau )(4)=\sigma (2)=1$; $(\tau \sigma )(1)=\tau (2)=4$, $(\tau \sigma )(2)=\tau (1)=3$, $(\tau \sigma )(3)=\tau (4)=2$, $(\tau \sigma )(4)=\tau (3)=1$. Deci $\sigma \tau =\tau \sigma =\pi$, cu $\pi =\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$.
2. b) $\pi$ schimbă 1 cu 4 și 2 cu 3, deci ${\pi }^2=e$. Cum $2027=2\cdot 1013+1$, ${\pi }^{2027}=({\pi }^2{)}^{1013}\pi =\pi$.
3. c) ${\sigma }^2=e$, deci ${\sigma }^{-1}=\sigma$ și $x={\sigma }^{-1}\tau =\sigma \tau =\pi$.

Răspuns: b) $(\sigma \tau {)}^{2027}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$; c) $x=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$

Greșeli frecvente

• Compui în ordinea greșită: în $\sigma \tau$ se aplică întâi $\tau$. Dacă aplici întâi $\sigma$, obții $\tau \sigma$, care în general este altă permutare.
• Inversa „citită de la coadă”: pentru $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$, linia a doua citită invers dă 1, 3, 2, dar ${\sigma }^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$. Regula corectă: $\sigma (i)=j\Rightarrow {\sigma }^{-1}(j)=i$.
• Simplifici ca la numere în ecuații: din $\sigma x=\tau$ rezultă $x={\sigma }^{-1}\tau$, nu $x=\tau {\sigma }^{-1}$. Înmulțești cu inversa de aceeași parte.
• Reduci exponentul modulo $n$ în loc de ordin: pentru $\sigma \in S_4$ cu ${\sigma }^2=e$, ${\sigma }^{2027}=\sigma$, deși $2027$ dă restul 3 la împărțirea cu 4. Exponentul se reduce modulo ordinul permutării.

Verifică-te

Exersează

• Lecția următoare: inversiuni și semnul unei permutări.
• Numărarea permutărilor ($n!$), din clasa a X-a: combinatorică: permutări, aranjamente, combinări și calculatorul de permutări.
• Unde le folosești mai departe: determinanți (clasa a XI-a) și fișa de lucru despre grupuri, clasa a 12-a (grupul permutărilor $(S_n,\circ )$).

Permutările sunt în programa de Bacalaureat M1 (clasa a XI-a: „noțiunea de permutare, operații, proprietăți”), dar în subiectele de Bac M1 din 2020–2026 nu a apărut niciun item despre permutările din $S_n$. Lecția este doar pentru profilul mate-info (M1); în programa M2 permutările apar numai ca număr $n!$, în combinatorica de clasa a X-a.

Întrebări frecvente

Ce este o permutare de gradul n? Este o funcție bijectivă $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$. Se scrie ca un tabel cu două linii: numerele de la 1 la $n$ și imaginile lor. Există $n!$ astfel de permutări, iar mulțimea lor se notează $S_n$.

Cum se calculează inversa unei permutări? Dacă $\sigma (i)=j$, atunci ${\sigma }^{-1}(j)=i$. Practic schimbi cele două linii ale tabelului între ele și reordonezi coloanele astfel încât prima linie să fie 1, 2, …, n. Verifici calculând $\sigma {\sigma }^{-1}=e$.

De ce compunerea permutărilor nu este comutativă? Pentru că în $\sigma \tau$ aplici întâi $\tau$, iar în $\tau \sigma$ întâi $\sigma$, iar rezultatul depinde de ordine. De exemplu, în $S_3$, pentru $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$, $(\sigma \tau )(1)=2$, dar $(\tau \sigma )(1)=3$.