Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

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

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 458

inversions et permutations

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


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

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

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 458

Re : inversions et permutations

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.


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

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

Michel Coste
Membre
Inscription : 05-10-2018
Messages : 1 170

Re : inversions et permutations

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.

Hors ligne

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

Michel Coste
Membre
Inscription : 05-10-2018
Messages : 1 170

Re : inversions et permutations

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)

Hors ligne

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

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 458

Re : inversions et permutations

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


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

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

Michel Coste
Membre
Inscription : 05-10-2018
Messages : 1 170

Re : inversions et permutations

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 ;)

Hors ligne

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

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 458

Re : inversions et permutations

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


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
cinquante neuf moins quaranteet un
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums