on appelle la permutation qui à [t(1),t(2),...,t(n)] on peut associer la permutation [t(n),t(n-1),...,t(1)] la permutation "miroir"

personne pour m'aider SVP ?

Salut,

il y a un point que je comprend pas, peux-tu m'éclairer?

Si je prend par exemple la transposition (1 3) donc d'après tes notations (3 2 1 4).

Alors le couple (1,3) est une inversion.

Je considère sa permutation miroir (4 1 2 3), le couple (1 3) en est toujours une inversion.

Ou ai-je mal compris la signification "permutation miroir".

je ne comprend pas pourquoi dans permutation miroir tu dis que le couple (1 3) est une inversion !
on a toujours i < j et t(i)<t(j) donc ce n'est pas une inversion !

Bien t(1)=4>t(3)=2.

je ne sais quoi répondre alors!

Comment as-tu compris la permutation miroir?

J'ai surement mal compris comment ca marchait c'est pour cela que je te demande.

voilà le texte : à une liste l composée des entiers de 1 à n on peut associer bijectivement une permutation sigma de Gn par sigma (i) = j si l'entier j se trouve en ième position dans l.
Cela permet-il d'apporter quelque chose de plus ?

Bien non c'est cela que j'ai considéré pourtant, ou alors je vois pas un truc possible....

je vais dire qu'il s'agit d'une erreur et puis c'est tout

Non c'est bizarre, il doit y avoir un truc qu'on a pas compris.

A mon avis, il faut comprendre autrement une inversion c'est un couple (i,j) tel que i<j et s(i)>s(j) ca c'est ma définition.

Donc la ça colle pas...

Maintenant si t'as trouvé cela dans un autre cadre genre informatique ca veut peut être dire un couple tel que i<j et si s(k)=i,s(l)=j alors k>l.

En gros ca veut dire que dans la liste i et j sont dans le bon ordre.

La je suis effectivement d'accord dans ce cas, avec le fait que la permutation miroir échange les inversions.

oui d'accord je pense que ça doit être cela.
Mais comment répondre à la question ? le nombre moyen d'inversions

Bien dans ce cas, tu ranges les permutations deux à deux avec leurs permutations miroirs, par exemple la permutation (1 2 .... n) avec (n n-1 .... 1) et bien dans la seconde tu as n(n-1)/2 inversions c'est le max et dans la première tu en as 0.

Le nombre moyen c'est donc n(n-1)/4 vu qu'en rangeant deux à deux tu as toutes les inversions par couple vu que être une inversion dans l'un est équivalent à ne pas en être une dans l'autre.


Sur google, je crois avoir trouvé ton énoncé mais c'est bizarre ils donnent bien la définition d'inversion que j'ai il y a un truc qui me gêne ca m'énerve

Bonjour
Pardon d'intervenir mais est ce que le résultat annoncé "n(n-1)/4" est vraiment sûr car je ne trouve pas çà.

Non pas du tout expose ton raisonnement

Pour l'instant je trouve tout simplement n et cela semble marcher avec n=2 ou 3 mais je vais revérifier mes calculs.

  Tu peux expliquer comment tu vois ca et ta démarche?

Etant donné qu'une permutation est composée de transpositions, je considère les différents types de transpositions, en particulier les « symétriques »
J'ai remarqué que le nombre d'inversions est égal au nombre de couples de couples
symétriques qui sont rangés dans un ordre différent dans une permutation car un couple a la même image que le transposé de son symétrique dans la permutation miroir. Comme il y a n2 - n couples tels que i différent de j et que deux couples sont symétriques l'un de l'autre il suffit de considérer (n2 - n)/2 cas pour une permutation .
Par exemple pour n=4 on aura au maximum 6 inversions  par permutation.
Ensuite toutes les symétries donnent pour chaque couple une inversion et même les n-cycles composés de transpositions symétriques aussi c'est à dire le maximum.
Mais avant de continuer il faudrait vérifier çà, je voudrais savoir si je ne fais pas fausse route.

C'est une transposition qui avec son miroir échange le même couple si on peut dire. Par exemple pour n=4 (4231) ou (1324)mais pas (2134).J'ai appelé çà comme par commodité pour ma recherche.

Ca échange le même couple, pour la première c'est la transposition (1 4) et la deuxième c'est (2 3) non?

Oui

Bien c'est pas le même couple ?

(4231) miroir (1324) il y a bien (41) et (14) d'une part et (23) et (32) d'autre part.Les images de 1 et 4 sont bien 1 ou 4 soit dans la permutation soit dans son miroir.Pour
(2134) miroir (4312)çà ne marche pas car l'image de 1 c'est d'abord 2 puis 4 dans le miroir non? ou alors je me trompe?

Ah d'accord j'avais pas compris ce que tu voulais dire.

Oui c'est exact, mon raisonnement n'est pas bon, je me suis aperçu que j'avais fais une erreur.

Ok, je pense que mon résultat est cohérent

Dernière remarque , juste pour éclaircir et répondre à la question demandée et le débat sera clos.
Par exemple dans la permutation (4213)  notée s, et dans son miroir (3124) noté s' et bien
_ s(12) = (42)
_ le symétrique de (12) est (34) (que j'avais pris au départ)
_ le transposé de (34) est (43)
_ s'(43) = (42)
donc la même image.
En fait le vrai symétrique de (12) est (43) et non pas (34) car dans (1234) et son miroir (4321) , 1 s'échange avec 4, l'image de(12) par le miroir est bien (43) et non (34).Donc inutile de passer par le transposé.
Mais tout ceci est un peu confus et sans intérêt  puisque ne faisant que compliquer avec en plus un résultat faux à la clé.
Désolé pour cette intervention très peu pertinente, avec toutes mes excuses.

Tu vas pas t'excuser non plus de nous donner tes idées quand même

Merci d'avoir éclairci, cependant j'ai toujours un peu de mal à te suivre totalement, tu as défini une transposition symétrique ok, mais ensuite tu parles de symétrique pour (12) comment tu le définis ceci?

Le transposé tu définis ca comment exactement?

Désolé d'être lourd, mais j'aime bien que cela soit totalement clair, bien sur ca serait plus simple si t'étais à côté de moi pour expliquer

Mon raisonnment n'est pas bon.Je n'arrive pas à démontrer plusieurs propriétés dont l'affirmation ci après:
Je n'avais pas trop envie d'exposer mais comme on me le demande et en plus j'aimerais bien savoir où sont les erreurs , dis moi ce qui ne va pas .(avec des notations en plus pas très rigoureuses)

Soit s : (s(1) , s(2) , ... , s(n)) une permutation
Soit s' : (s(n) , s(n-1) , ... , s(1) la permutation miroir
Soit (i ; j) un couple tel que i<j.
Il y a n(n-1)/2 couples.
Il y a donc au maximum n(n-1)/2 inversions et au minimum zéro par permutation
Affirmation : s'il y a p inversions pour s, il y aura n(n-1)/2-p inversions pour s' Tentative de démonstration :
s = (s(1) , s(2) ,..., s(i) ,..., s(j) ..., s(n))
s' = (s(n) , s(n-1) , ...s(j) ,...,s(i) ,... , s(1)
Faisons correspondre s(1) avec s(n) , s(2) avec s(n-1) etc
Le symétrique d'un couple de s dans s' est celui qui lui correspond par cette bijection.
Exemple
s =(12345) on a : (12) et (54) etc...
Dans le miroir les symétriques sont égaux puisqu'ils sont définis comme tels.
s = (31254)  s' = (45213)
Le symétrique de (35) est (35) celui de (31) est (31)
s' possède la propriété que si un couple est rangé dans un certain ordre dans s ,
le transposé de son symétrique est rangé dans un ordre différent dans s'.
Forcément car le transposé (b ; a) d'un couple (a ; b) n'est pas rangé dans le même ordre.
Comme de plus il y a bijection de l'ensemble sur lui même, tous les éléments de s sont dans s'.A chaque couple correspond un unique symétrique et un transposé unique.
On peut donc associer les permutations 2 par 2, s avec avec un permutation unique
qui inverse un couple dans s sans l'inverser dans cette permutation.
A elles deux elles inverseront n(n-1)/2 couples
Donc en moyenne n(n-1)/4
Exemple(précédent)
Vérifions toutes les inversions dans s et dans s' simultanément(O= oui et N = non)
(31)   et (13)  O et N
(32)   et (23)  O et N
(35)   et (53)   N et O
(34)   et (43)   N et O
(12)   et (21)   N et O
(15)   et (51)   N et O
(14)   et (41)   N et O
(25)   et (52)   N et O
(24)   et (42)   N et N
(54)   et (45)   O et N
Au total 3 inversions dans s et 10 - 3 = 7 dans l'autre
Vérification de l'affirmation (non démontrée)sur un autre exemple
s = (3214)
s' = (4123)
Inversions de s : 32  31  21    = trois
Inversions de s' : 41  42  43  = trois
Total 6 pour deux donc moyenne 3
Un autre
s = (1243)
s' = (3421)
Inversions de s : 43 = une
Inversions de s' : 34  32  31  42  41 = cinq
Total 6 et moyenne 3
Merci pour l'aide.

Voilà un raisonnement qui me semble meilleur.
Soit s une permutation de n éléments et r son miroir
r possède (par définition ou pas ?) la propriété suivante
Pour tout i , on a
s^-1(i) + r^-1(i) = n+1
Exemple
s=(312)  r =(213)  s^-1(3)=1 et r^-1(3) =3  et donc 3+1=4=n+1
Affirmation
Soit i et j tels que i<j , si s^-1(i)<s^-1(j) alors r^-1(i)>r^-1(j)
Démonstration
En effet, sinon on aurait s^-1(i)<s^-1(j) et r^-1(i) ≤r^-1(j)
donc s^-1(i)+r^-1(i)<s^-1(j)+r^-1(j)
et par suite d'après la propriété n+1<n+1, impossible
s^-1 et r^-1 sont deux permutation telles que si l'une inverse un couple ,l'autre non.
Etant donné qu'il y a n(n-1)/2 couples ordonnés pour deux permutations
il y aura en moyenne n(n-1)/4 inversions pour 2 permutations et en général
car on les regroupe toutes par deux.
Exemple au hasard
(432516)=s
(532146)=s^-1
(615234)=r
(245631)=r^-1
Vérifions tous les couples
i j  s^-1 r^-1

12 53 24    
13 52 25
14 51 26
15 54 23
16 56 21
23 32 45
24 31 46
25 34 43
26 36 41
34 21 56
35 34 43
36 26 51
45 14 63
46 16 61
56 46 31
7 inversions pour s^-1 et 8 pour r^-1 donc 15 au total ,moyenne15/2 = 6x5/4
Tous les couples qui sont inversés par s^-1 ne le sont pas par r^-1 (et inversement)
ce qui confirme le résultat
Mon raisonnement présente t il une faille quelque part ?
Merci

J'ai pas le courage la je te répond demain soir

Sur ton premier message j'ai du mal à te suivre, par contre sur le deuxième je suis d'accord et c'est plus rapide, d'ailleurs comme je l'avais signalé on travaille avec s^-1 et r^-1 plutot qu'avec s et r quand j'avais dit qu'il fallait plutot dire que s(i)=j si l'entier i se trouve en j-ième position.

Visuellement une inversion de s^-1  c'est un couple i<j tel que (i,j) n'est pas rangé dans l'ordre.