Soit $\rm E=\{1, \ldots,n\}$.
Définition :
Une permutation de $\rm E$ est une bijection de $\rm E$ dans $\rm E$.
L’ensemble des permutations de $\rm E$ est noté $\rm S_n$. Cet ensemble, muni de la loi de composition des applications est un groupe d’élément neutre l’identité $\rm Id$, appelé groupe symétrique d’ordre $\rm n$ sur l’ensemble $\rm E$.
Propriété : Si $\rm \sigma \in S_n$, on note : $\sigma=\Big(\begin{matrix} 1 & \dots & \rm n \\\sigma(1) & \dots & \sigma(\rm n) \end{matrix}\Big)$.
Propriété : $\rm |S_n|=n !$
Définition : Soit $\rm \sigma \in S_n$. L’ensemble $\rm supp(\sigma)=\{i/\sigma(i)\neq i\}$ est le support de $\sigma$.
Définition : Soit $\rm \sigma \in S_n$. $\sigma$ est un cycle de longueur $l\geq 2$ s’il existe $l$ éléments distincts $\rm a_1,\dots,a_l$ de $\rm E$ tels que $\rm \sigma(a_1)=a_2,\ldots,\sigma(a_{l-1})=a_l$, $\rm \sigma(a_l)=a_1$ et $\sigma(x)=x$ pour tout $x\in \rm E-\{a_1,\ldots,a_l\}$. On peut alors utiliser la notation cyclique $\rm \sigma=(a_1 a_2\dots a_l)$.
Remarque : un cycle de longueur $2$ est appelé une transposition.
Théorème : Soit $\rm \sigma \in S_n$ tel que $\rm \sigma\neq Id$.
Il existe $\rm k\geq 1$ et $\rm c_1,\dots,c_k$ des cycles à supports deux à deux disjoints tels que $\rm \sigma=c_1\dots c_k$.
Cette décomposition est unique à l’ordre près des facteurs et est appelée décomposition canonique de $\sigma$.
Remarque : en général, on n’indique pas les cycles de longueur $1$ dans l’écriture de $\sigma$ en produit de cycles.
Théorème : Soit $\rm \sigma \in S_n-\{id\}$ de décomposition canonique $\rm c_1\dots c_k$.
L’ordre de $\sigma$ est le PPCM des longueurs des cycles $\rm c_i$.
Définition : Soit $\sigma$ permutation de $\rm S_n$ et $\rm a\in [|1~ ;n|]$.
L’orbite de l’élément $\rm a$ selon la permutation $\sigma$ est l’ensemble $\rm O_{\sigma}(a)=\{\sigma^k(a)~ ;k\in\mathbb Z\}$.
Définition : Soit $\sigma$ permutation de $\rm S_n$.
$\sigma$ est une permutation circulaire si $\sigma$ n’admet qu’une seule orbite.
Définition : Soit $\sigma$ et $\sigma’$ deux permutations de $\rm S_n$.
$\sigma$ est conjuguée à $\sigma’$ s’il existe une permutation $\tau$ de $\rm S_n$ tel que $\sigma=\tau\circ\sigma’\circ \tau^{-1}$.
Propriété : Tous les cycles sont conjugués dans $\rm S_n$.
