Définition :
Pour tout ensemble \(E\), on note \(S_E\) l'ensemble des bijections de \(E\) dans \(E\)
Un élément de \(S_E\) est appelé permutation de \(E\)
Notation
On peut noter une permutation \(f\) de la façon suivante : $$\begin{pmatrix}1&2&3&\ldots&n\\ f(1)&f(2)&f(3)&\ldots&f(n)\end{pmatrix}\begin{align}&\longleftarrow\text{la source}\\ &\longleftarrow\text{l'image}\end{align}$$
Proposition :
Toute permutation peut s'écrire comme un produit de transpositions et un produit de cycles à supports disjoints
(Transposition, Composition, Cycle - Permutation cyclique, Support d'un cycle, Ensembles disjoints)
Si \(\tilde\sigma\) est la permutation inverse de \(\sigma\), alors on a pour tout \(1\leqslant i\leqslant n\) : $$\tilde\sigma(i)={{n+1-\sigma(i)}}$$
Permutation aléatoire
Principe de conjugaison
Principe de conjugaison :
Soit \((a_1,\dots,a_n)\) un \(n\)-cycle et \(\sigma\) une permutation
Alors \(\sigma\circ(a_1,\dots,a_n)\circ\sigma^{-1}\) est un \(n\)-cycle et $${{\sigma\circ(a_1,\dots,a_n)\circ\sigma^{-1}}}={{(\sigma(a_1),\dots,\sigma(a_n))}}$$
Orbite d'un élément
Définition :
L'orbite d'un élément selon une permutation \(\sigma\) est l'ensemble des images successives de cet élément obtenues par applications répétées de \(\sigma\)
Sous-suite d'une permutation
Définition :
Si \(\sigma\in\mathfrak S_n\), une sous-suite de \(\sigma\) est une séquence \((\sigma(i_1),\dots,\sigma(i_k))\) tels que \(1\leqslant i_1\leqslant\dots\leqslant i_k\leqslant n\)
On dit que cette sous-suite est croissante si \(\sigma(i_1)\lt \dots\lt \sigma(i_k)\) et décroissante si \(\sigma(i_1)\gt \dots\gt \sigma(i_k)\)
Une sous-suite monotone est une sous-suite croissante ou décroissante