Cycles de permutations

[inviteba9bce0d]

Bonjour,
je ne sais pas si je suis dans le bon forum mais c'est celui qui m'a semblé le plus approprié pour poser mon problème (absence de section "Algorithmique"). Cà fait environ 2 mois en cours d'algorithmique que mon prof m'a demandé de l'aider pour la démonstration d'une propriété (surement en désespoirs de causes ). Le problème est le suivant : "Prouver mathématiquement que tous les chiffres d'une permutation se retrouvent dans leurs cycles". Je m'explique :

Une permutation d'ordre n possède tous les chiffres entre 1 et n. Par exemple, la permutation 4132 est d'ordre 4, 51423 d'ordre 5, en revanche 5234 n'est pas une permutation, tout comme 412 et 64125. Les cycles d'une permutation sont des ensembles de chiffres appartenant à celle-ci. Il peut y avoir entre 1 et n cycles pour une permutation. Je ne sais pas vraiment comment le définir correctement, mais un cycle d'une permutation signifie qu'il existe tel que :

et

Exemples, les cycles de permutations de 461352 sont (4,3,1), (6,2) et (5). Ceux de 53421 sont (5,1) et (3,4,2), et ceux de 7432156 sont (7,6,5,1), (4,2) et (3).

Le problème est maintenant de prouver que (chaque est unique).

Voilà, si vous avez des idées je suis preneur .
-----

[invite4ef352d8]

Salut !

ce qu'il faut montrer, c'est qu'une permutation est égal au produit de ces cycles (dans le sens composition, les cycles etant de support disjoint ils comutent)... du coup connaissant les cycles tu retrouve la permutation.

[inviteba9bce0d]

une permutation est égal au produit de ces cycles

Oui, c'est justement çà qu'on veut montrer.

[invite4ef352d8]

oui, mais ca c'est clair :

on fixe une permutation s.

chaque element de i [|1,n|] est contenu dans un et un seul cycle de s (en comptant les point fixe de s comme des cycle d'un element) : c'est le cycle (i,s(i),s²(i)...s^v(i)) ou v est le plus petit entier telle que s^(v+1)(i)=i

si on prend un autre element j dans le cycle, alors le cycle obtenu est (j,s(j),...s^v(j) ) = (s^m(i),...s^(v+m)(i) ) = (i,...s^v(i) ) est exactement le meme.

finalement, si on forme p=p1...pk le produit des cycles qui compose s alors p(i)=s(i) car pk(i) = i et pk(s(i))=s(i) pour tous les cycle sauf celui qui contiens i et pk(i)=s(i) pour le cyle qui contiens i...

qu'elle point te pose te problème ? ( c'est essentiellement evident, le tous est de s'en convaincre ^^)

[A voir en vidéo sur Futura]

[inviteba9bce0d]

En fait j'ai du mal comprendre le sens de "produit des cycles".
Je n'ai pas vraiment suivi ton raisonnement car la notation me gène, i est l'ensemble des chiffres de 1 à n ? Si oui, pourquoi i est dans un cycle, sachant qu'un cycle n'a pour élément que des chiffres. Je ne vois pas non plus à quoi correspond s(i), et je suppose que v+1=k dans mon exmple mais j'en suis pas sur.

Voilà, désolé pour l'incompréhension mais là :X

[invite4ef352d8]

Ok.

ce que j'appelle cycle d'ordre p est une permutation s dont le support (l'ensemble des point tel que s(i) est différent de i) est de cardinal p et tel que pour tous element du support s^k(i)<>i pour tous k<p et s^p(i)=i.

un cycle d'une permutation est un cycle qui coincide avec la permutation sur le support du cycle.

quand je dis qu'un entier i appartiens au cycle, c'est un abus de language pour dire que l'entier est dans le support du cycle...