Groupe symétrique

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$.