Prépa, 1re année › Groupe symétrique › Inversions, signature
Inversions, signature : définition (MPSI)
Définition
Inversions, signature
Soit $\sigma \in \mathfrak{S}_n$. Une inversion de $\sigma$ est un couple $(i,j)$ avec $1\leqslant i<j\leqslant n$ et $\sigma(i)>\sigma(j)$. On note $I(\sigma)$ le nombre d'inversions.
La signature de $\sigma$ est $$\varepsilon(\sigma)=(-1)^{I(\sigma)} \in \{-1,1\}.$$ On dit que $\sigma$ est paire si $\varepsilon(\sigma)=1$, impaire si $\varepsilon(\sigma)=-1$.
Exemple
Compter les inversions
Pour $\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\\ 3&5&7&8&2&6&1&4\end{pmatrix}$, on lit la deuxième ligne $3,5,7,8,2,6,1,4$ et on compte, pour chaque terme, les termes plus petits situés à sa droite :
| terme | 3 | 5 | 7 | 8 | 2 | 6 | 1 | 4 |
|---|---|---|---|---|---|---|---|---|
| plus petits à droite | 2 | 3 | 4 | 4 | 1 | 2 | 0 | 0 |
$I(\sigma)=16$, donc $\varepsilon(\sigma)=1$.
S’entraîner
- Décomposition, ordre et puissance d'une permutation de $\mathfrak{S}_9$
- Produits de cycles non disjoints
- Signature par les inversions
- Ordre maximal d'un élément de $\mathfrak{S}_7$
- Signature du battage parfait