Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2013-10-18  10:45-11:45
TitrePermutations triables par deux piles en parallèle 
RésuméOn sait depuis certains travaux de Knuth que si on dispose d'une pile, on peut trier Cn permutations de longueur n, où Cn est le énième nombre de Catalan. C'est facile à voir, car chaque permutation triable ne peut être triée que d'une façon possible, et les « mots de tri » sont les mots de Dyck. Et si on a deux piles, placées en parallèle ? Combien de permutations de longueur n peut-on trier ? Les choses se compliquent, car il y a en général plusieurs façons de trier une permutation (triable). Toutefois, on peut décrire un ensemble de mots de tri canoniques, en bijection avec les permutations triables, et on réussit à les dénombrer — du moins à caractériser leur série génératrice par un système d'équations —. Les mots de tri sont maintenant des chemins de Dyck en dimension 2, c'est-à-dire des chemins dans le quart de plan. L'étude du comportement asymptotique du nombre de permutations triables repose sur des conjectures, qui résistent, portant sur le dénombrement de ces chemins pondérés par le nombre de virages NW et ES. Travail est en commun (et en cours, et depuis 2008) avec Michael Albert, de Dunedin, Nouvelle-Zélande. Pour les « anciens » du groupe, il n'y a pas grand lien avec les permutations triables par deux piles à la West-Zeilberger.  
Lieu076 
OrateurMireille Bousquet-Mélou 



Aucun document lié à cet événement.

Retour
Retour à l'index