Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#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
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,
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
Pages : 1