Noțiunea de permutare

Definiție. Fie o mulțime finită cu n elemente, n număr natural nenul,

$A = \{a_{1}, a_{2}, . . ., a_{n}\}$ .

Se numește permutare a mulțimii A, oricare mulțime ordonată formată cu elementele acesteia.

Definiție. Se numește permutare de grad n a mulțimii A={1,2,..., n}, orice funcție bijectivă

$σ : A \to A$

Mulțimea permutărilor de grad n se notează cu Sn, iar numărul de elemente al acesteia este |Sn|=n!.

Permutările de grad n se notează de obicei cu litere grecești și se reprezintă sub forma

$σ = (\begin{matrix} 1 & 2 & . . . & k & . . . & n \\ σ (1) & σ (2) & . . . & σ (k) & . . . & σ (n) \end{matrix})$

Exemple:

Dacă n=1, A={1}, |S1|=1!=1, iar

$S_{1} = \{(\begin{matrix} 1 \\ 1 \end{matrix})\}$

Dacă n=2, A={1,2}, |S2|=2!=2, iar

$S_{2} = \{(\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix}), (\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix})\}$

Dacă n=3, A= {1,2,3}, |S3|= 3!=6, iar

$S_{3} = \{(\begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix}), (\begin{matrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix})\}$

Definiție.Se numește permutare identică de grad n, permutarea

$e = (\begin{matrix} 1 & 2 & . . . & k & . . . & n \\ 1 & 2 & . . . & k & . . . & n \end{matrix})$

Definiție. Se numește transpoziție permutarea care lasă neschimbate toate elementele cu excepția elementelor i, j pe care le schimbă între ele, notată cu

$δ_{i j} = (\begin{matrix} 1 & 2 & . . . & i - 1 & i & i + 1 & . . . & k & . . . & j - 1 & j & j + 1 & . . . & n \\ 1 & 2 & . . . & i - 1 & j & i + 1 & . . . & k & . . . & j - 1 & i & j + 1 & . . . & n \end{matrix})$

Exemple. Dacă n=4,

$δ_{23} = (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{matrix}) = (23)$ $δ_{12} = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{matrix})$