Utilité des permutations

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
masiuxus

Utilité des permutations

Message non lu par masiuxus »

Bonjour.
En regardant un autre sujet, je suis tombé sur un document où l'on parle de permutations et de décompositions en produits de cycles.
Je me souviens avoir adoré ça (c'était très simple, c'est pour ça), mais sans réellement savoir à quoi cela pouvait bien servir.
Est-ce qu'il y a des exemples qui me montreraient que les permutations servent à quelques chose ?

PS : le seul exemple que j'ai est l'histoire du créateur du taquin ... ce qui n'est déjà pas mal ... mais j'en voudrais plus :D
oleanet
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 257
Inscription : dimanche 24 décembre 2006, 15:17

Re: Utilité des permutations

Message non lu par oleanet »

masiuxus a écrit : Est-ce qu'il y a des exemples qui me montreraient que les permutations servent à quelques chose ?
Bonjour,

Les déterminants par exemple.
masiuxus

Re: Utilité des permutations

Message non lu par masiuxus »

Oui, effectivement ... Autant pour moi : je formule ma question différemment : y a-t-il des exemples qui n'apparaissent pas dans le programme du premier cycle universitaire ?
Tryphon
Modérateur honoraire
Modérateur honoraire
Messages : 1839
Inscription : mercredi 01 juin 2005, 18:39
Localisation : Un peu plus à l'Ouest

Re: Utilité des permutations

Message non lu par Tryphon »

A peu près toute la théorie des groupes finis, et par la même tout ce qui est basé dessus, comme la théorie de Galois, par exemple (mais ça n'est vraiment qu'un exemple, les groupes de permutation c'est quand même un très très gros morceau).
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Re: Utilité des permutations

Message non lu par jobherzt »

A vue de nez je dirais dans à peu pres toute les situation ou tu etudies ou simplifie un "systeme fini ou discret" à travers ses symétries. La théorie de Galois est effectivement une application majeure, mais aussi la theorie des invariants, des représentations, des fonctions symétriques, des groupes finis en général. Je pense qu'il y aussi des applications en physique, meme si dans la vraie vie c'est plutot des groupes de Lie qu'on voit apparaitre (qu encodent aussi une notion de symétrie). Il y a aussi la combinatoire algébrique, et les généralisations des groupes symétriques, comme les groupes de Coxeter par exemple. Un autre truc qui généralise plus ou moins la notion de permutation est la théorie des tresses (on peut voir une tresse comme une permutation qui "enregistre" les transpositions effectuées) qui jouent un role fondamental dans de nombreux domaines physiques, dans l'etude de certaines equa diff, en topologie de basse dimension, en logique fondamentale, avec des liens etroits avec la theorie des categories, ...

et j'en oublie surement beaucoup :)
Tryphon
Modérateur honoraire
Modérateur honoraire
Messages : 1839
Inscription : mercredi 01 juin 2005, 18:39
Localisation : Un peu plus à l'Ouest

Re: Utilité des permutations

Message non lu par Tryphon »

jobherzt a écrit :Je pense qu'il y aussi des applications en physique, meme si dans la vraie vie c'est plutot des groupes de Lie qu'on voit apparaitre (qu encodent aussi une notion de symétrie).
Tu peux préciser ton idée ? (je ne connais rien aux groupes de Lie)
Un autre truc qui généralise plus ou moins la notion de permutation est la théorie des tresses (on peut voir une tresse comme une permutation qui "enregistre" les transpositions effectuées) qui jouent un role fondamental dans de nombreux domaines physiques, dans l'etude de certaines equa diff, en topologie de basse dimension, en logique fondamentale, avec des liens etroits avec la theorie des categories, ...
Idem, ça a l'air âchement intéressant :)
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Re: Utilité des permutations

Message non lu par jobherzt »

Alors : pour ce qui est des groupes de Lie et de la physique, j'avoue que c'est un truc "qui se sait" qu'ils en rencontrent à tous les coins de rue, mais j'avoue que je ne suis pas hyper calé sur le sujet. Pour faire simple, les groupes de Lie qu'ils rencontrent sont surtout des sous groupes de $GL_n$.. Si je ne dis pas de betises, lidée est la suivante : On considere un certain systeme physique a etudier, ce qui revient a resoudre certaines equation (differentielles, a priori). Le systeme physique est inscrit dans notre espace a 3 dimension, peut donc avoir certaine symetrie, ce qui revient a dire qu'il existe un sous groupe $G$ de $GL_3$ qui le laisse stable. Par ailleurs, les solutions de l'equation associé forment un espace vectoriel disons de dimension $k$. L'action (naturelle, geometrique) de G sur le systeme va induire une action (a priori beaucoup moins evidente) de G sur cet espace de dimension $k$. Autrement dit, cet espace est une representation de G. Donc, connaitre toutes les representations de G (ce qu'on sait assez bien faire, de facon abstraite) permet de recuperer enormement d'nformation sur la structure de l'espace des solutions de notre equation, disons qu'au lieu d'un espace arbitraire, on a une certaine representation d'un groupe ce qui restreint pas mal les possibilités...

Tout ceci a prendre avec des pincettes, evidemment....

Pour les tresses, la il y a un paquet de choses à raconter, c'est vaste. Une bonne reference, plutot axé sur l'aspect combinatoire : http://www.math.unicaen.fr/~dehornoy/Surveys/Dgz.pdf

En gros, une tresse est a peu pres ce qu'on imagine, a savoir des bouts de fils qui se balladent et se croisent. On autorise les brins a bouger tant qu'ils ne se passent pas au travers. Comme souvent en maths, ca revient a dire qu'il existe plusieurs maniere de "dessiner" la meme tresse abstraite. Les tresses forment un groupe, ou la loi consiste simplement a empiler les tresses..

D'un point de vue combinatoire, les tresses ont été pas mal etudié. On sait reconnaitre efficacement que 2 dessins representent la meme tresse. On sait definir un ordre total sur les tresses. C'est la dessus que Dehornoy (document plus haut) a travaillé. C'est par ce biais qu'il y a des liens avec la logique fondamentale (decidabilité, theorie des grands cardinaux, etc..)

D'un point de vue topologique, les groupes de tresses sont les groupes fondamentaux de certains "espaces de configurations". En gros, tu imagines $n$ particules qui bougent dans un plan. L'espace de configuration associé est l'ensemble des configurations ou elles peuvent se trouver, sachant que 2 particules ne peuvent evidemment pas avoir les memes coordonnées. Une tresse represente donc un "chemin continu" d'une configuration vers une autre (imagine que les particules bougent en devidant chacune une pelote de ficelle derriere elle et que le plan monte au fur et a mesure, tu obtiendras une tresse).

De ce point de vue elles sont reliés a l'etude des equation KZ relié a l'etude du mouvement de particules. La c'est aussi relié avec les groupes quantiques.

Enfin, du point de vue categorique, les tresses sont reliés a ce qu'on appelle les "categories monoidales tressées" qui sont l'analogue categorique des monoides commutatifs (en gros le role de la multiplication est joué par un genre de produit tensoriel). Comme on travaille dans des categories, cad que les elements sont eux meme ddes structures, on ne demande pas que $A \otimes B=B \otimes A$ mais que $A \otimes B$ soit isomorphe à $B \otimes A$. Donc il y a une notion de permutation (tu peux changer l'ordre des termes) sauf qu'en fait les transpositions satisfont une relation ($\tau^2=Id$) que ces isomorphismes ne satisfont pas en general. C'est pour ca qu'en fait on ne permute pas les termes, on les tresse :) (c'est dit un peu rapidement, j'ai conscience que ca doit pas etre tres clair).

Typiquement, il existe des algebres de Hopf (dite quasi tiriangulaire) dont la categorie des modules est tressée. Ce tressage est induit par un element (la R-matrice) qui au passage a des applications en mecanique statistique (equation de Yang Baxter)....

C'est assez vaste, donc c'est dur de resumer, desolé !!! si tu as des questions, n'hesite pas.
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Re: Utilité des permutations

Message non lu par jobherzt »

Ah, et j'oubliais : si tu "refermes" une tresse, cad que tu attache les bouts du haut et les bouts du bas 2 a 2, tu obtiens un noeud (plus exactment un entrelac, cad une reunion disjointe de noeuds). Donc les tresses permettent de construire des invariants de noeuds, qui ont eux meme plein d'application en topologie et en physique.
Tryphon
Modérateur honoraire
Modérateur honoraire
Messages : 1839
Inscription : mercredi 01 juin 2005, 18:39
Localisation : Un peu plus à l'Ouest

Re: Utilité des permutations

Message non lu par Tryphon »

Merci pour ces réponses. J'ai imprimé le texte sur les tresses :D

Si t'avais un papier qui décrit un peu plus on histoire de sous-groupe de $GL_n$ qui agit sur l'espace des solutions d'une ED, je suis aussi preneur, ça a l'air très joli !
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Re: Utilité des permutations

Message non lu par jobherzt »

Je t'avoue que mes connaissances en physique sont limitées. Mais si tu n'as j'amais rencontré de groupes de Lie, je me rends compte que mon message peut donner l'impression de parler seulement d'une connexion un peu inattendue entre 2 domaines bien distincts. Ca n'est pas du tout ca, en réalité, les groupes et algèbres de Lie sont presque par définition des objets qui viennent de la géométrie différentielle. Or, la majeure partie de la physique "theorique" utilise a très haute dose de la géo diff. Il me semble meme qu'a chaque force fondamentale est associée un certain groupe de Lie, a tel point que par abus de langage on confond les 2....

Du coup je ne suis pas sur que ca aie un sens d'avoir "une" reference sur le sujet, physique et groupes sont vraiment imbriqués à tous les niveaux... Meme si ca m'interresserait toujours d'avoir des textes un peu facile à lire pour un matheux sur le sujet :)

Une piste quand meme : http://fr.wikipedia.org/wiki/Sym%C3%A9trie_de_jauge pour illustrer ce que je disais juste avant. SInon faut lire des cours de physique, ou chercher des trucs sur les origines des groupes de Lie, il me semble qu'ils ont vraiment été introduit comme des groupes de symétrie d'equation différentielles.
Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1172
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Re: Utilité des permutations

Message non lu par Framboise »

On retrouve quantité de transformations en chimie organique, dont des symétries, permutations.

Un casse tête avec les permutations : les lacets de chaussures. Comment les placer judicieusement, notamment en les faisant garder la symétrie pour la partie émergeante lacée et qu'ils n'aient pas tendance à favoriser un côté en se décalant d'un laçage à l'autre.
J'ai le virus des sciences, ça se soigne ?
masiuxus

Re: Utilité des permutations

Message non lu par masiuxus »

Bon, me voilà satisfait. Je vois que ça sert oui, mais dans des problèmes qui ne s'intéressent pas trop :D
Tryphon
Modérateur honoraire
Modérateur honoraire
Messages : 1839
Inscription : mercredi 01 juin 2005, 18:39
Localisation : Un peu plus à l'Ouest

Re: Utilité des permutations

Message non lu par Tryphon »

Ca ça m'étonnerait. Qu'est ce qui t'intéresses ?
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
masiuxus

Re: Utilité des permutations

Message non lu par masiuxus »

En fait, parmi les quelques exemples qui ont été mentionnés ici (tresses, ...), je n'en trouve pas un qui m'intéresse. Je pensais que l'on pouvais trouver des exemples plus ... concret (je ne vois pas l'intérêt de la théorie des tresses par exemple). Je parlais dans mon message premier du taquin ... ça, c'est intéressant. Y a-t-il d'autres "jeux" qui font intervenir des permutations ?
Arnaud
Modérateur honoraire
Modérateur honoraire
Messages : 7097
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne
Contact :

Re: Utilité des permutations

Message non lu par Arnaud »

masiuxus a écrit :Y a-t-il d'autres "jeux" qui font intervenir des permutations ?
Les chaises musicales :D, enfin si on ne change pas le nombre de chaises.
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)
Tryphon
Modérateur honoraire
Modérateur honoraire
Messages : 1839
Inscription : mercredi 01 juin 2005, 18:39
Localisation : Un peu plus à l'Ouest

Re: Utilité des permutations

Message non lu par Tryphon »

Pourtant, si tu réfléchis deux minutes, tu dois trouver une foule de jeu dans lesquels on permute des choses. Un jeu de carte par exemple. Pour être plus précis, les permutations sont un objet de base de la combinatoire, elle-même omniprésente dans l'étude de jeux.

Mais bon, il va de soi que si tout ce qui t'intéresses et de résoudre un taquin ou un Rubik's Cube, même si tu peux faire plein de choses intéressantes dessus avec les permutations, ça n'est nullement obligatoire.

Dans le cas contraire, les permutations devraient avoir été au moins survolées par toute personne disposant d'un niveau Bac+2 en maths.

A propos du taquin, quelqu'un (Jobhertz ? Dark ? Valvino ?) y'a un an avait posté un TER qui parlait du taquin, de partitions d'un entier, et de diverses choses de combinatoire assez compliquées...
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
Valvino
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 921
Inscription : mercredi 21 mars 2007, 10:59

Re: Utilité des permutations

Message non lu par Valvino »

C'est pas moi :lol:
Tryphon
Modérateur honoraire
Modérateur honoraire
Messages : 1839
Inscription : mercredi 01 juin 2005, 18:39
Localisation : Un peu plus à l'Ouest

Re: Utilité des permutations

Message non lu par Tryphon »

Je me rappelle sue je l'avais parcouru, puis j'avais lâché prise parce que ça n'avait rien d'évident...
Pas de questions en MP
La calculatrice, c'est comme Linux, c'est de la merde !
masiuxus

Re: Utilité des permutations

Message non lu par masiuxus »

Tryphon a écrit :Dans le cas contraire, les permutations devraient avoir été au moins survolées par toute personne disposant d'un niveau Bac+2 en maths.
Je n'ai pas dit le contraire vu que j'ai parlé du taquin dans ma question initiale :D Mais comme les calculs sur les permutations sont simples, nous sommes passés très vite dessus (sans doute pour passer directement aux déterminants), sans nécessairement voir des choses plus élaborées.

Manquant sérieusement d'imagination, je ne vois pas réellement d'exemples concrets utiles de calculs sur les jeux de cartes faisant intervenir les permutations et leur signature. Enfin bon, à travers les quelques exemples que vous avez inscrit dans ce topic, je vois un peu. Merci.
Framboise
Utilisateur chevronné
Utilisateur chevronné
Messages : 1172
Inscription : lundi 21 mai 2007, 13:57
Statut actuel : Autre
Localisation : Dordogne

Re: Utilité des permutations

Message non lu par Framboise »

Un outil utile pour les groups:
http://www.gap-system.org/~gap/
qui peut être appliqué aux permutations.

J'ai une idée d'application : les tris qui utilisent beaucoup les permutations. tris par bulle, etc.

Voir:
http://www.nrbook.com/a/bookcpdf.php
chapitre 8 Sorting.
avec les pdf à télécharger freeware.

Un livre:
http://www.amazon.com/exec/obidos/ASIN/ ... ksclub-20/
C'est très ardu, y compris pour moi.
J'ai le virus des sciences, ça se soigne ?
Répondre