Go->sérendipité->permutations

Bruno Greco · April 2018

Bonjour,
donc par la coopération inopinée de l'appli de Go de mon smartphone, je tombe sur un résultat que je ne connaissais pas (je ne suis pas une référence...).

Il est bien connu que les cycles $b=(01),\ c=(012),\ d=(0123)$ etc. engendrent $\mathfrak S_n$=groupe des permutations de $\{0,1,\ldots,n-1\}$. Mais à ma grande surprise, j'ai constaté que toute permutation de $\mathfrak S_n$ peut s'écrire comme produit d'au plus $n-1$ cycles $b,c,d, \ldots$. Vous avez bien lu : cycles et non puissances de cycles !
Ainsi par exemple la permutation $01234\mapsto 04213$ peut s'écrire $d e d e$ et la permutation $01234\mapsto 20341$ s'écrit $c e$ ou $b e b$ ou $d e b c$.
1) Voyez-vous pourquoi ? (ce n'est pas sorcier, mais la marge est trop étroite).
2) Ce résultat (ou la méthode de tri correspondante) a-t-il un nom ?

Cordialement, Bruno Greco

Foys · April 2018

Tout élément de $\mathfrak S_n$ est produit de cycles à supports disjoints (si $s\in \mathfrak S_n$ et $x_1\in \{1,\ldots,n\}$, $s$ induit un cycle sur $\{s^k(x_1)\mid k \in \N\}=:U_1$. Si $\{1,\ldots,n\} \setminus U_1$ n'est pas vide, prendre $x_2$ dans cet ensemble et recommencer ; etc.).
Comme leurs supports sont disjoints, il ne peut pas y avoir plus de $n$ tels cycles.

Bruno Greco · April 2018

Pardon Foys, je ne crois pas que tu réponds à la question, je ne donne droit qu'aux cycles $(0 1 2..k)$, pas à n'importe quel cycle.

Go->sérendipité->permutations

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 10