Soit $n$ un entier naturel strictement positif.
Considérons l'ensemble $E_n=\{1,2,\ldots,n\}$
Permutations
On dit qu'une fonction $\sigma$ de $E_n$ dans $E_n$ est une permutation de $E_n$ si $\sigma$ est une bijection.
Autrement dit : $\sigma$ est telle que pour tout $y\in E$, il existe un unique $x\in E$ tel que $\sigma(x)=y $.
On note $\mathfrak S_n $ l'ensemble des permutations de $E$. On munit $\mathfrak S_n $ de la loi de composition notée ici $\cdot $.
Ainsi $\tau \cdot \sigma$ est définie pour tout $x\in E$ par $$\tau\cdot \sigma (x)=\tau(\sigma(x)) $$
Nous avons vu dans l'article Groupe des bijections que l'ensemble des permutations de $E_n $ forme un groupe pour l'opération $\cdot$. Le groupe $\mathfrak S_n $ est appelé le groupe symétrique.
Quelques notations
Permutations cycliques
Pour tout $n\in\mathbb N $, on note $\left(\begin{array}{cc} a & b \end{array}\right)$ la permutation de $E $ définie par :
- $\left(\begin{array}{cc} a & b \end{array}\right)(x)=x $ si $x\not \in\left\{a,b \right\} $
- $(\begin{array}{cc} a & b \end{array})(a)=b $
- $(\begin{array}{cc} a & b \end{array})(b)=a $
Une telle permutation est appelée une transposition.
Plus généralement, si $a_1,a_2,\ldots, a_{r-1},a_r $ sont $r$ éléments de $E_n$, on note
$$(\begin{array}{ccccc} a_1 & a_2 & \ldots & a_{r-1} & a_r \end{array}) $$
la permutation $\sigma $ de $E$ définie par :
- $\sigma (x)=x $ si $x\not \in\left\{a_1,a_2,\ldots, a_{r-1},a_r \right\} $
- $\sigma(a_i)=a_{i+1} $ si $i\in\left\{1,2,\ldots,r-1 \right\}$
- $\sigma(a_r)=a_{1} $
Notation matricielle d'une permutation
Si $\sigma$ est une permutation, on peut la noter sous forme matricielle :
$$\sigma=\left(\begin{array}{ccccc} 1 & 2 & \ldots & n-1 & n\\ \sigma(1) & \sigma(2) & \ldots & \sigma(n-1) & \sigma(n) \\ \end{array}\right)$$
Exemple.
Dans $\mathfrak S_2 $, on a $$\left(\begin{array}{cc} 1 &2 \end{array}\right)=\left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 1 & 3 \\ \end{array}\right)$$
Commutativité ?
En général les permutations $E_n $ ne commutent pas, $\mathfrak S_n $ n'est pas abélien.
Par exemple, pour $n\geq 3$, on a
$$ (\begin{array}{cc} 1 & 2 \end{array})\cdot(\begin{array}{cc} 1 & 3 \end{array})= (\begin{array}{ccc}1& 3 & 2 \end{array})$$
En effet, si on note $\sigma= (\begin{array}{cc} 1 & 2 \end{array})\cdot(\begin{array}{cc} 1 & 3 \end{array}) $, alors $\sigma $ effectue les transformations suivantes :
- $1\mapsto 3 \mapsto 3$
- $2\mapsto 2\mapsto 1$
- $3\mapsto 1 \mapsto 2$
Si on note $\tau= (\begin{array}{cc} 1 & 3 \end{array})\cdot(\begin{array}{cc} 1 & 2 \end{array}) $, alors $\tau $ effectue les transformations suivantes :
- $1\mapsto 2 \mapsto 2$
- $2\mapsto 1\mapsto 3$
- $3\mapsto 3 \mapsto 1$
On en déduit que $\tau= (\begin{array}{cc} 1 & 3 \end{array})\cdot(\begin{array}{cc} 1 & 2 \end{array})=(\begin{array}{ccc}1& 2 & 3 \end{array}) $
Donc $(\begin{array}{cc} 1 & 2 \end{array})\cdot(\begin{array}{cc} 1 & 3 \end{array})\neq (\begin{array}{cc} 1 & 3 \end{array})\cdot(\begin{array}{cc} 1 & 2 \end{array})$
Propriétés de décomposition des permutations
Décomposition en cycle
- (cas 1). Si $\sigma(n+1)=n+1 $, alors la restriction $\sigma' $ en tant que fonction de $\sigma $ aux $n$ premiers entiers naturel donne une permutation de $E_n$. En effet, l'injectivité de $\sigma' $ provient de cellle de $\sigma $.
Pour la surjectivité, soit un quelconque $y\in E_n $, montrons que $y$ possède un antécédent par $\sigma $. Comme $E_n\subset E_{n+1} $, il existe par surjectivité de $\sigma $, $x\in E_{n+1}$ tel que $\sigma(x)=y $. Mais $x\neq n+1 $ car l'image de $n+1$ par $\sigma $ est $n+1$. Par conséquent, $\sigma'(x)=y$, ce qui prouve que $y$ a un antécédent par $\sigma' $. $\sigma' $ est donc une permutation de $E_n $.
Dans ce cas, d'après notre hypothèse de récurrence, on peut écrire :
$$\sigma'=c_s\cdot c_{s-1}\cdot\ldots\cdot c_1 $$
où $c_1,\ldots,c_s $ sont de cycles appartenant à $\mathfrak S_n $.
On peut prologer les $c_i$ en tant que fonction sur $E_{n+1}$, on pose pour cela : $\gamma_i(x)=c_i(x) $ si $x\in E_n $
$\gamma_i(n+1)=\gamma(n+1) $
Les $c_i $ étant des cycles de $\mathfrak S_n $, les $\gamma_i $ sont des cycles de $\mathfrak S_{n+1} $.
De plus on a
$$\sigma=\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1 $$
En effet, on voit facilement, avec une récurrence sur $s$, que si $x\in E_n $,
$$\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1(x)=c_s\cdot c_{s-1}\cdot\ldots\cdot c_1(x)=\sigma'(x)=\sigma(x) $$ - (cas 2). Maintenant si $\sigma(n+1)\neq n+1 $. Notons $a=\sigma^{-1}(n+1) $ (autrement dit $\sigma(a)=n+1 $). On a nécessairement $1\leq a \leq n $.
On note $\tau=\left(\begin{array}{cc} n+1 & a\end{array}\right) $.
Notons $\widetilde{\sigma}= \sigma\cdot \tau $. On a $\widetilde{\sigma}(n+1)=\sigma\cdot \tau(n+1)= \sigma(a)=n+1 $.
Comme $\widetilde{\sigma} $ est une permutation, et que $\widetilde{\sigma}(n+1)=n+1 $, on est ramené au cas précédent. Donc il existe un entier naturel $s$ et $s$ cycles $\gamma_1,\ldots,\gamma_s $ éléments de $\mathfrak S_{n+1} $ tels que $$\widetilde{\sigma}=\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1 $$
Comme $\widetilde{\sigma}=\sigma\cdot \tau $, on a $\widetilde{\sigma}\cdot \tau^{-1}=\sigma$, d'où
$$\sigma=\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1\cdot \tau^{-1} $$
Mais $\tau^{-1}=\left(\begin{array}{cc} n+1 & a\end{array}\right) =\tau $ est aussi un cycle d'ordre 2, donc la propriété est démontrée.