inversions et permutations

bridgslam · 10-10-2023 18:20:53

Bonjour,

Allez un petit exercice de réflexion sur les permutations de {1,...,n} pour finir la soirée mathématique (dans mon cas en tout cas :-) )

Montrer que deux permutations ont les mêmes paires d'inversions si et seulement si elles sont égales.
( rappel: $i \ne j \;forment \;une \;paire \; d'inversion \; de \; \sigma \in \mathfrak{S}_n \iff i \lt j \Rightarrow \sigma(i) \gt \sigma(j)$ )

Autrement dit l'application $\sigma \rightarrow Inv( \sigma)\; où \; Inv(\sigma) \; représente \;l'ensemble \;des\; inversions \;de \;\sigma \; est \; injective $
J'ai trouvé cela dans un exercice "à explorer" d'un recueil sur les groupes (origine québecoise, multi auteurs), sous-chapitre permutations.
Je le recommande d'ailleurs, de jolies diagrammes en couleur à foison, et très soigné.
Apparemment la version 2021 a rajouté la rubrique sur les groupes résolubles.

Je ne mets pas d'indice, c'est très faisable, sans être un expert du tout.
Alain

bridgslam · 11-10-2023 10:04:14

Bonjour,

Je tape une réponse possible, au cas où la question vous aurait intéressé ( moi c'est surtout Latex qui est -un peu - galère).
On pressent ce résultat quand on pense aux transpositions ( avec quelques connaissances sur $\mathfrak{S}_n$ ), encore faut-il trouver une preuve complète.

Le sens $\sigma = \gamma \Rightarrow Inv(\sigma) = Inv(\gamma)$ est clair.
Montrons le sens contraire.

Supposons donc maintenant que $Inv(\sigma) = Inv(\gamma)$.
Notons $\mathcal{I}(\sigma) = Card( Inv(\sigma))$ pour une permutation $\sigma$ quelconque.

L'idée est d'abaisser conjointement $\mathcal{I}$ pour $\sigma $ et $\gamma$ afin d'arriver à 0, tout en préservant l'égalité de leurs ensembles d'inversions.
En effet $\mathcal{I}(\sigma) = 0 \Rightarrow \sigma= Id$ ( résultat facile car Id est la seule $\sigma$ à vérifier $\sigma(1) < \sigma(2) < ... < \sigma(n)$.

- si $\mathcal{I}(\sigma) = 0 = \mathcal{I}(\gamma)$ , il n'y a rien à faire vu qu'elles sont égales à l'identité.
- sinon il existe un couple $ ( i, i+1) \in Inv(\sigma) = Inv(\gamma)$.

Alors on remarque, d'une part, que pour $\sigma o (i,i+1) $ et $\gamma o (i,i+1) $ , $\mathcal{I}$ diminue d'une unité.
D'autre part un calcul facile montre que $Inv(\sigma o (i,i+1)) = Inv(\gamma o (i,i+1))$.

On peut donc itérer le procédé tant que l'on n'atteint pas 0.
Quand on obtient 0 après quelques étapes, on a donc $\sigma o (i,i+1)o (u,u+1) o ...o(z,z+1) = \gamma o (i,i+1)o (u,u+1) o ...o(z,z+1) = id$.

Il suffit de composer à droite Id par $(z,z+1) o ....o(u,u+1)o(i,i+1)$ pour voir l'égalité de $\sigma$ et $\gamma$
Voilà, en fait plus lourd à rédiger qu'autre chose (en espérant ne pas avoir fait d'erreurs).

Il n'est pas impossible qu'on puisse affaiblir l'hypothèse, par exemple avec $Card ( Inv(\sigma) \Delta Inv(\gamma) ) $ suffisamment petit, donc les deux ensembles d'inversion presque égaux, notamment pour des grandes valeurs de n.

A.

Michel Coste · 11-10-2023 10:33:07

Bonjour,
On peut raisonner facilement par récurrence sur $n$.
Quand on ajoute $n+1$, on le place juste avant les entiers avec lesquels il présente une inversion.

Michel Coste · 11-10-2023 11:57:51

bridgslam a écrit :

Il n'est pas impossible qu'on puisse affaiblir l'hypothèse, par exemple avec $Card ( Inv(\sigma) \Delta Inv(\gamma) ) $ suffisamment petit

Si, c'est impossible : pour toute permutation $\sigma$, il est très facile de donner un exemple de permutation $\gamma$ telle que $\text{Card}(\text{Inv}(\sigma) \bigtriangleup \text{Inv}(\gamma) ) =1$.

Dernière modification par Michel Coste (11-10-2023 11:58:13)

bridgslam · 11-10-2023 12:03:35

Bonjour,

Bien vu - c'est bien joli, merci.
Apparemment, comme dans la vie, il vaut mieux tenter de monter que de descendre visiblement :-).

Bonne journée
Alain

Michel Coste · 11-10-2023 12:19:16

Le raisonnement par récurrence est complètement lié au procédé de comptage des inversions suivant pour une permutation de {1,...,n} :
compter les entiers écrits après n, effacer n ;
compter les entiers écrits après n-1 et ajouter au total précédent, effacer n-1 ;
etc.
Là, on descend ;)

bridgslam · 11-10-2023 17:32:42

Bonjour,

Michel Coste a écrit :

bridgslam a écrit :
Il n'est pas impossible qu'on puisse affaiblir l'hypothèse, par exemple avec $Card ( Inv(\sigma) \Delta Inv(\gamma) ) $ suffisamment petit
Si, c'est impossible : pour toute permutation $\sigma$, il est très facile de donner un exemple de permutation $\gamma$ telle que $\text{Card}(\text{Inv}(\sigma) \bigtriangleup \text{Inv}(\gamma) ) =1$.

Avec $\sigma(i) = 1, \sigma(j)=2 \;\; on \;a \; Inv( (1,2) o \sigma ) = Inv( \sigma) \cup \{(i,j) \} \;ou \; Inv( (1,2) o \sigma ) = Inv( \sigma) \setminus \{(i,j)\}$ selon que $i<j \;ou\; i>j $ sauf erreur.

On ne peut donc pas affaiblir la condition. J' avais eu tort de lancer cette affirmation (un peu "au pif" à vrai dire, ce qui ne porte pas chance en général).
Merci pour la rectification.

Cordialement
Alain

Forum de mathématiques - Bibm@th.net

#1 10-10-2023 18:20:53

inversions et permutations

#2 11-10-2023 10:04:14

Re : inversions et permutations

#3 11-10-2023 10:33:07

Re : inversions et permutations

#4 11-10-2023 11:57:51

Re : inversions et permutations

#5 11-10-2023 12:03:35

Re : inversions et permutations

#6 11-10-2023 12:19:16

Re : inversions et permutations

#7 11-10-2023 17:32:42

Re : inversions et permutations

Réponse rapide

Pied de page des forums