Trouver le nombre de permutations de \(\mathfrak{S}\left(n\right)\) qui ont exactement une inversion.


Barre utilisateur

[ID: 2099] [Date de publication: 17 mai 2021 11:26] [Catégorie(s): Groupe symétrique ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]




Solution(s)

Solution(s)

Exercice 336
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 17 mai 2021 11:26

Soit \(\sigma\) une telle permutation. Une inversion c’est une paire de flèches (rouges) qui se coupent. Pour n’avoir qu’une seule inversion, seules ces deux flèches doivent se couper.

Pour l’image de \(1\) par \(\sigma\), on doit avoir \(1\) sinon on aurait \(1\) qui serait l’image d’un \(k>1\) et la flèche \(1 \to \sigma(1)\) couperait la flèche \(k\to1\).

De même \(\forall p\in\llbracket 1,i-1\rrbracket\), on a \(\sigma(p) = p\).

Maintenant, on a \(\sigma(i) > i\). Donc nécessairement \(i\) est l’image d’un \(k>i\), dont la flèche \(k\to i\) va couper la flèche \(i \to \sigma(i)\). Comme il n’y en a qu’une seule qui coupe cette flèche \(i \to \sigma(i)\), à savoir la flèche \(j \to \sigma(j)\), on en déduit que \(k=j\) et \(\sigma(j) = i\). De même \(\sigma(i+1)\), l’image de \(i+1\) est plus grande que \(i+1\) (toutes les places \(1,2,\ldots,i\) sont déjà prises pour les images). Donc supposons l’espace d’un instant que \(i+1\neq j\), on aurait une flèche \(i+1 \to \sigma(i+1)\) différente de \(i \to \sigma(i)\) qui couperait \(j\to i\), ce qui n’est pas possible par hypothèse. Donc \(i+1 = j\).

Par la suite, toujours pour éviter que d’autres flèches se coupent, pour \(p>i+1\) (s’il en existe) on a \(\sigma(p) = p\). Réciproquement, une permutation de cette forme ne possède qu’une inversion.

On a donc \(n-1\) possibilités pour \(i\) et donc \(n-1\) permutations de \(\mathfrak{S}\left(n\right)\) qui ont exactement une inversion.


Documents à télécharger