Profesor de Matematică - Elena Micu
Fie $S_n$ mulțimea tuturor permutărilor de gradul $n$. Deoarece orice permutare $\sigma \in S_n$ este o funcție bijectivă $\sigma\colon \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$, putem defini operația de compunere (numită și produsul permutărilor) ca fiind compunerea funcțiilor.
Pentru orice $\sigma, \tau \in S_n$, compunerea lor este permutarea $\sigma \circ \tau \in S_n$ definită prin:
$$(\sigma \circ \tau)(k) = \sigma\big(\tau(k)\big),\ (\forall)\, k \in \{1, 2, \dots, n\}.$$Când permutările sunt reprezentate prin tabele cu două linii:
$$\sigma = \begin{pmatrix} 1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \end{pmatrix},\qquad \tau = \begin{pmatrix} 1 & 2 & \dots & n \\ \tau(1) & \tau(2) & \dots & \tau(n) \end{pmatrix}$$produsul $\sigma \circ \tau$ se evaluează de la dreapta la stânga:
Fie permutările de gradul 4, $\sigma, \tau \in S_4$:
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix},\qquad \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}.$$Să calculăm produsul $\sigma \circ \tau$:
Așadar, obținem permutarea identică:
$$\sigma \circ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix} = e.$$Compunerea permutărilor de gradul $n$ este o operație asociativă:
$$(\sigma \circ \alpha) \circ \beta = \sigma \circ (\alpha \circ \beta),\ (\forall)\, \sigma, \alpha, \beta \in S_n.$$Această proprietate rezultă direct din faptul că operația de compunere a funcțiilor este asociativă.
Permutarea identică de gradul $n$, notată cu $e \in S_n$:
$$e = \begin{pmatrix} 1 & 2 & \dots & n \\ 1 & 2 & \dots & n \end{pmatrix}$$este element neutru pentru operația de compunere a permutărilor de gradul $n$:
$$\sigma \circ e = e \circ \sigma = \sigma,\ (\forall)\, \sigma \in S_n.$$Pentru orice permutare $\sigma \in S_n$, există o unică permutare notată $\sigma^{-1} \in S_n$, numită inversa permutării $\sigma$, astfel încât:
$$\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = e.$$Dacă permutarea $\sigma$ este definită prin corespondențele $k \mapsto \sigma(k)$, inversa sa $\sigma^{-1}$ inversează corespondențele, adică $\sigma(k) \mapsto k$. Forma inițială a inversei este:
$$\sigma^{-1} = \begin{pmatrix} \sigma(1) & \sigma(2) & \dots & \sigma(n) \\ 1 & 2 & \dots & n \end{pmatrix},$$după care se reordonează coloanele astfel încât prima linie să fie $(1, 2, \dots, n)$.
Fie permutarea de gradul 5, $\sigma \in S_5$:
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 1 & 3 & 2 \end{pmatrix}.$$Avem inversarea liniilor:
$$\sigma^{-1} = \begin{pmatrix} 4 & 5 & 1 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}.$$Reordonând prima linie în ordine crescătoare, obținem:
$$\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}.$$Se verifică direct că $\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = e$.
Compunerea permutărilor de gradul $n \geq 3$ nu este o operație comutativă. Există $\sigma, \delta \in S_n$ astfel încât:
$$\sigma \circ \delta \neq \delta \circ \sigma.$$În $S_3$, considerăm permutările:
$$\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix},\qquad \delta = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}.$$Calculăm cele două produse:
$$\sigma \circ \delta = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix},$$ $$\delta \circ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}.$$Deoarece $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \neq \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$, deducem că $\sigma \circ \delta \neq \delta \circ \sigma$.
Pentru orice permutare $\sigma \in S_n$ și $k \in \mathbb{N}^*$, puterea a $k$-a se definește prin:
$$\sigma^0 = e,\quad \sigma^1 = \sigma,\quad \sigma^2 = \sigma \circ \sigma,\quad \dots,\quad \sigma^k = \underbrace{\sigma \circ \cdots \circ \sigma}_{k \text{ ori}}.$$Fie $\sigma \in S_n$. Au loc următoarele relații privind operațiile cu puteri:
a) $\sigma^m \circ \sigma^n = \sigma^{m+n}$, $(\forall)\, m, n \in \mathbb{N}$;
b) $\left(\sigma^m\right)^n = \sigma^{m \cdot n}$, $(\forall)\, m, n \in \mathbb{N}$.
Demonstrația acestor proprietăți se face folosind asociativitatea operației de compunere (temă).
Pentru exponenți negativi, avem $\sigma^{-k} = \left(\sigma^{-1}\right)^k$.
Regulile obișnuite de calcul cu exponenți au loc:
$$\sigma^a \circ \sigma^b = \sigma^{a+b},\qquad \left(\sigma^a\right)^b = \sigma^{ab},\ (\forall)\, a, b \in \mathbb{Z}.$$Fie $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix} \in S_4$. Să se calculeze $\sigma^{25103}$.
Soluție
Calculăm succesiv puterile mici ale lui $\sigma$:
$$\sigma^2 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix} = e.$$Așadar, $\sigma^2 = e$, deci pentru orice $m \in \mathbb{N}$ avem $\sigma^{2m} = e$ și $\sigma^{2m+1} = \sigma$.
Împărțim exponentul $25103$ la $2$:
$$25103 = 2 \cdot 12551 + 1.$$Așadar:
$$\sigma^{25103} = \sigma^{2 \cdot 12551 + 1} = \left(\sigma^2\right)^{12551} \circ \sigma^1 = e^{12551} \circ \sigma = e \circ \sigma = \sigma.$$Fie permutarea $\sigma \in S_4$:
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}.$$Să se calculeze $\sigma^2$, $\sigma^3$, $\sigma^4$ și $\sigma^{25103}$.
Soluție
Calculăm succesiv puterile mici ale permutării $\sigma$:
$$\sigma^2 = \sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}.$$ $$\sigma^3 = \sigma^2 \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}.$$ $$\sigma^4 = \sigma^3 \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix} = e.$$Deoarece $\sigma^4 = e$, spunem că ordinul permutării $\sigma$ este $4$.
Pentru a calcula $\sigma^{25103}$, împărțim exponentul $25103$ la $4$:
$$25103 = 4 \cdot 6275 + 3.$$Folosind proprietățile operațiilor cu puteri, avem:
$$\sigma^{25103} = \sigma^{4 \cdot 6275 + 3} = \sigma^{4 \cdot 6275} \circ \sigma^3 = \left(\sigma^4\right)^{6275} \circ \sigma^3 = e^{6275} \circ \sigma^3 = e \circ \sigma^3 = \sigma^3.$$Așadar,
$$\sigma^{25103} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}.$$O permutare $\tau \in S_n$ care schimbă între ele doar două elemente distincte $i, j \in \{1, 2, \dots, n\}$, cu $i \neq j$, și lasă toate celelalte elemente neschimbate se numește transpoziție și se notează $\tau = (i, j)$.
$$(i, j)(k) = \begin{cases} j, & \text{dacă } k = i, \\ i, & \text{dacă } k = j, \\ k, & \text{dacă } k \notin \{i, j\}. \end{cases}$$Fie $(i, j) \in S_n$ o transpoziție. Au loc următoarele relații:
a) Simetria: $(i, j) = (j, i)$;
b) Involuția (pătratul este identitatea): $(i, j)^2 = e$;
c) Inversa unei transpoziții: $(i, j)^{-1} = (i, j)$.
Numărul tuturor transpozițiilor distincte de gradul $n$ este dat de formula:
$$N_{\text{transpoziții}} = C_n^2 = \frac{n(n-1)}{2}.$$Demonstrație
Din proprietatea a) rezultă că o transpoziție este unic determinată de alegerea neordonată a unei perechi de două elemente distincte $\{i, j\} \subset \{1, 2, \dots, n\}$. Numărul tuturor acestor submulțimi cu 2 elemente este $C_n^2$.
Burtea, M., & Burtea, G. (2006). Matematică: Manual pentru clasa a XI-a: Trunchi comun + curriculum diferențiat: M1. Editura Carminis.