Journée en l'honneur de Dominique Gouyou-Beauchamps


Le 7 Mai 2010 en salle 79 du LRI Bâtiment 490, Université Paris-Sud


9h30 Laurence Puel (LRI)


9h45 Xavier Viennot (CNRS, Bordeaux)
Q-tableaux et automates planaires

Dominique aime bien les "tableaux". Nous introduisons une nouvelle notion, celle de Q-tableau, associée à une algèbre quadratique Q. Un exemple est formée par les permutations, associesée à l'algèbre de Weyl-Heisenberg avec géenéerateurs U, D et la relation UD = DU + Id. Un autre exemple provenant de la physique statistique des systèmes dynamiques hors de l'équilibre, sont les "tableaux alternatifs" et les "tableaux de permutations" associées à l'algèbre du PASEP dfiniecute;e par la relation DE = ED + E + D. Une algèbre plus géenérale à 4 générateurs permet de retrouver comme Q-tableaux beaucoup d'autres objets combinatoires liés à la physique statistique: matrices à signes alternants, FPL ("fully packed loops"), configurations de chemins ne se coupant pas, pavages (Aztec, calissons), configurations du modèle à "8-vertex". Nous introduisons une deuxième notion (que nous pensons nouvelle), celle d'automate planaire (à ne pas confondre avec les automates cellulaires). Ceci permet de définir des "figures" ou "configurations" planaires reconnues par un automate planaire. Ces objets sont exactement les Q-tableaux.

11h Cyril Nicaud (Marne la Vallée)
Distributions, Génération, Binomiales

Alonzo a proposé une méthode astucieuse pour tirer uniformément au hasard des mots de Motzkin de longueur n. Je présenterai comment Dominique et moi avons réutilisé cette idée, basée sur des rejets et des distributions binomiales, pour générer aléatoirement d'autres structures combinatoires, comme notamment les injections partielles et les arbres unaires-binaires colorés.

11h30 Julian West (Bristol)
Equivalence Relations of Permutations Generated by Constrained Transpositions

Nous considérons une famille de relations d'equivalence sur l'ensemble $S_{n}$ des permutations, qui généralisent les relations découvertes par Knuth dans ses recherches sur la correspondance de Robinson et Schensted. Dans notre contexte général, deux permutations sont considérées comme équivalentes si l'une peut être obtenue de l'autre auprès d'une séquence de remplacements d'un motif par un autre selon des règles précisées. Désormais, nous ne considérons dans l'oeuvre actuelle que les motifs qui correspondent à la transposition de deux éléments, avec l'intervention d'un troisième. Pour plusieurs exemples de ce problème, nous énumérons les classes d'équivalence, nous déterminons combien de permutations sur $n$ éléments sont équivalentes à l'identité, ou nous précisons la forme des éléments dans cette dernière classe. Bien que nos résultats retrouvent des séquences des entiers très bien connues (nombres de Catalan, de Fibonacci, de Tribonacci ...), ainsi que des classes de permutations déjà étudiées (en couches, connexes, sans motif $123$), nous trouvons également des séquences qui paraissent être nouvelles.


12h Srecko Brlek (UQAM, Canada)

Aspects combinatoires des pavages d'Escher
When Maurits Cornelis Escher started to produce astonishing tesselations of the plane in the late 30's, very few properties were known about theses. The ``simplest" tesselations make use of just one polygon or tile for tiling the entire plane, and the polygons that tile the plane by translation are characterized by a simple property due to Beauquier and Nivat (1991) stating that the border $b(P)$ of such a polygon may be factorized as $b(P) = ABC\hat(A) \hat(B)\hat(C)$. This equation maybe naturally translated in an equation on words, that led to the discovery of new classes of polyominoes, connected to the Fibonacci sequence and the Pell sequence.

12h30 Déjeuner (LRI et Nicole Polian)


14h Robert Cori (Bordeaux)
ABCD: Algorithmes, Bijections, dans le Chemin de Dominique.

Une visite commentée des sujets de prédilection de Dominique Gouyou-Beauchamps.

14h45 Jean-Paul Allouche (CNRS, LRI)
Séries formelles de Lucas et algébricité

Nous nous intéressons aux séries formelles d'une ou plusieurs variables qui ont la propriété p-Lucas pour de grandes familles de nombres premiers p. Nous caractérisons celles qui sont algébriques sur le corps des fractions rationnelles sur Q, et indiquons quelques conséquences de cette étude. (Il s'agit d'un travail commun avec DGB qui date d'une douzaine d'années et de conséquences récentes.)


15h15 Philippe Nadeau (Wien)
Combinatoire des configurations de Fully Packed Loops

Les configurations de Fully Packed Loops (FPLs) sont des structures issues de la physique statistique, en bijection avec les célèbres matrices à signe alternant. Nous nous intéresserons ici a leur énumération a couplage fixé, qui intervient en particulier dans la conjecture de Razumov-Stroganov, démontrée récemment par Cantini et Sportiello. Nous évoquerons en particulier certains polynômes énumérant ces FPLs, et leurs liens avec des questions de combinatoire algébrique.

15h45 Philippe Flajolet (INRIA)
Sur la somme d'une progression géométrique