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

Répondre

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)?
quatre-vingt onze plus cinquante deux
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.

Retour

Résumé de la discussion (messages les plus récents en premier)

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

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 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 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$.

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.

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.

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

Pied de page des forums