Profesor de Matematică - Elena Micu
Fie $A = \{a_1, a_2, \dots, a_n\}$ o mulțime finită cu $n$ elemente distincte, unde $n \in \mathbb{N}^*$.
Se numește permutare a mulțimii $A$ orice mulțime ordonată formată cu toate elementele acesteia.
O permutare a mulțimii $A$ se poate scrie sub forma $\left(a_{i_1}, a_{i_2}, \dots, a_{i_n}\right)$, unde indicii $(i_1, i_2, \dots, i_n)$ formează o reordonare (rearanjare) a mulțimii $\{1, 2, \dots, n\}$.
Se observă că această permutare este descrisă în mod unic de o funcție bijectivă $f\colon A \to A$, definită prin legea: $f(a_k) = a_{i_k},\ (\forall)\, k \in \{1, 2, \dots, n\}$.
Această descriere funcțională poate fi reprezentată în mod sugestiv sub forma unui tablou biliniar (numit și tabloul Cauchy al permutării):
$$f = \begin{pmatrix} a_1 & a_2 & \dots & a_k & \dots & a_n \\ a_{i_1} & a_{i_2} & \dots & a_{i_k} & \dots & a_{i_n} \end{pmatrix}$$Informația din acest tablou este structurată astfel:
Deoarece natura specifică a elementelor mulțimii $A = \{a_1, a_2, \dots, a_n\}$ nu influențează proprietățile algebrice ale permutărilor, funcției $f\colon A \to A$ i se asociază în mod natural funcția bijectivă pe mulțimea indicilor:
$$\sigma\colon \{1, 2, \dots, n\} \to \{1, 2, \dots, n\},\quad \sigma(k) = i_k,\ (\forall)\, k \in \{1, 2, \dots, n\}.$$Această funcție se reprezintă sub tabloul simplificat:
$$\sigma = \begin{pmatrix} 1 & 2 & \dots & k & \dots & n \\ i_1 & i_2 & \dots & i_k & \dots & i_n \end{pmatrix} = \begin{pmatrix} 1 & 2 & \dots & k & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(k) & \dots & \sigma(n) \end{pmatrix}.$$Dat fiind că funcția $\sigma$ este bijectivă, valorile $\sigma(1), \sigma(2), \dots, \sigma(k), \dots, \sigma(n)$ sunt toate elementele mulțimii $\{1, 2, \dots, n\}$ distincte două câte două.
Studiul permutărilor oricărei mulțimi finite $A$ de cardinal $n$ este echivalent cu studiul permutărilor mulțimii numerelor naturale $M_n = \{1, 2, \dots, n\}$, adică a funcțiilor bijective $\sigma\colon \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$.
Mulțimea tuturor permutărilor de grad $n$ (adică a permutărilor mulțimii $\{1, 2, \dots, n\}$) se notează cu $S_n$.
Numărul total de permutări de grad $n$ este dat de produsul primelor $n$ numere naturale nenule:
$$|S_n| = n! = 1 \cdot 2 \cdot 3 \cdots n.$$O permutare $\sigma \in S_n$ este determinată unic de valorile din imaginea sa, $(\sigma(1), \sigma(2), \dots, \sigma(n))$.
Conform regulii produsului, numărul total de funcții bijective este:
$$|S_n| = n \cdot (n - 1) \cdot (n - 2) \cdots 1 = n!.$$Să analizăm structura mulțimii $S_n$ pentru primele valori ale lui $n$:
a) Pentru $n = 1$, $A = \{1\}$ și $|S_1| = 1!$, iar $S_1 = \left\{ \begin{pmatrix} 1 \\ 1 \end{pmatrix} \right\}$.
b) Pentru $n = 2$, $A = \{1, 2\}$ și $|S_2| = 2!$, iar $S_2 = \left\{ \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \right\}$.
c) Pentru $n = 3$, mulțimea $A = \{1, 2, 3\}$ și $|S_3| = 3! = 6$. Cele 6 elemente distincte ale lui $S_3$ sunt:
$$\begin{aligned} S_3 = \Big\{ & \sigma_1 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix},\ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix},\ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \\ & \sigma_4 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix},\ \sigma_5 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix},\ \sigma_6 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \Big\}. \end{aligned}$$În studiul algebric al permutărilor, două tipuri de permutări joacă un rol fundamental:
Permutarea $e \in S_n$ definită prin: $e = \begin{pmatrix} 1 & 2 & 3 & \dots & k & \dots & n \\ 1 & 2 & 3 & \dots & k & \dots & n \end{pmatrix}$ se numește permutarea identică de gradul $\boldsymbol{n}$. Aceasta lasă toate elementele neschimbate: $e(k) = k$, pentru orice $k \in \{1, 2, \dots, n\}$.
Fie $i, j \in \{1, 2, \dots, n\}$ cu $i \neq j$. Permutarea $\delta_{ij} \in S_n$ (notată uneori și $(i, j)$) de forma:
$$\delta_{ij} = \begin{pmatrix} 1 & 2 & \dots & i-1 & \boldsymbol{i} & i+1 & \dots & j-1 & \boldsymbol{j} & j+1 & \dots & n \\ 1 & 2 & \dots & i-1 & \boldsymbol{j} & i+1 & \dots & j-1 & \boldsymbol{i} & j+1 & \dots & n \end{pmatrix}$$care schimbă între ele doar elementele $i$ și $j$, lăsând toate celelalte elemente neschimbate, se numește transpoziție.
Formulată explicit prin lege de corespondență, transpoziția $\tau_{ij}$ acționează astfel:
$$\delta_{ij}(k) = \begin{cases} j, & \text{dacă } k = i, \\ i, & \text{dacă } k = j, \\ k, & \text{dacă } k \in \{1, 2, \dots, n\} \setminus \{i, j\}. \end{cases}$$1) Simetria: $\delta_{ij} = \delta_{ji}$, pentru orice $i \neq j$.
2) Involuția (Proprietatea de auto inversabilitate): Aplicată de două ori succesiv, o transpoziție revine la starea inițială: $\delta_{ij}^2 = \delta_{ij} \circ \delta_{ij} = e \Longrightarrow \delta_{ij}^{-1} = \delta_{ij}$.
3) Numărul de transpoziții distincte: În mulțimea $S_n$ există exact $C_n^2 = \frac{n(n-1)}{2}$ transpoziții distincte.
| Noțiune | Notație | Descriere / Proprietate Cheie |
|---|---|---|
| Permutare a mulțimii $A$ | $f\colon A \to A$ | Funcție bijectivă definită pe o mulțime finită de cardinal $n$. |
| Mulțimea permutărilor | $S_n$ | Mulțimea tuturor permutărilor de grad $n$. Număr elemente: $|S_n| = n!$. |
| Permutarea identică | $e \in S_n$ | $e(k) = k,\ (\forall)\, k \in \{1, \dots, n\}$. |
| Transpoziție | $\delta_{ij} \in S_n$ | Schimbă $i \leftrightarrow j$ și lasă fixe celelalte elemente. $\delta_{ij}^2 = e$. |
Burtea, M., & Burtea, G. (2006). Matematică: Manual pentru clasa a XI-a: Trunchi comun + curriculum diferențiat: M1. Editura Carminis.