L'image de fond est un animal dirigé aléatoire.
CS est un nouveau programme, écrit en MuPAD, dédié à l'étude des structures combinatoires. Comme la bibliothèque Combstruct le fait en Maple, CS permet de construire automatiquement les procédures MuPAD pour l'énumération et la génération aléatoire uniforme de structures combinatoires décomposables. Mais CS offre d'autres fonctionnalités importantes :
La correspondance de Robinson-Schensted (Schensted 61) est un cas particulier, dans le cas des tableaux standard, d'algorithmes similaires pour les tableaux oscillants (Delest-Dulucq-Favreau 88, Sundaram 92) et les tableaux oscillants gauches (Dulucq-Sagan 95). Dans un premier temps, nous proposons l'extension, dans le cas des tableaux oscillants, d'algorithmes et de propriétés classiques pour les tableaux standard dus à Viennot (77), Schutzenberger (63, 77) et Knuth (70). Dans un deuxième temps, reprenant une idée de Sagan et Stanley (90), nous étendons ces résultats aux tableaux oscillants gauches. Enfin, nous proposons une extension, dans le cas des tableaux oscillants gauches, d'un algorithme dû à Beissinger (87) .
Investigation of the dynamics of majority nets (graphs of finite degrees with vertices loaded by a + or - unit charge, that undergo simultaneous recharging by local majority rule) reveal some surprising properties. These properties could be metaphors for some mysterious physical phenomena, as a transition from classical to quantum condition, and of phase transition.
Les permutations à motifs exclus sont à la mode ces temps-ci. Celles qui évitent un motif croissant sont particulièrement agréables parce qu'il y a des choses à en dire. Le centre de l'exposé sera une formule déterminantale (Gessel 90) qui donne la série génératrice (de Bessel) des permutations évitant le motif 123...n. On en donnera une preuve bijective (Gessel 97), et on commentera l'utilité de cette formule peut-être méconnue.
Dans un article paru dans JCT-A et intitulé "Multivariable Lagrange Inversion, Gessel-Viennot Cancellation, and the Matrix Tree Theorem", I.P. Goulden et D.M. Kulkarni donnent une preuve combinatoire d'une forme étendue du théorème d'inversion de Lagrange-Good pour les séries génératrices exponentielles multivariées.
La preuve est basée sur une interprétation en termes, d'une part, d'arbres étiquetés et, d'autre part, d'endofonctions. Elle généralise la preuve de G. Labelle du cas unidimensionnel. Comme corollaire apparaît une curieuse formule d'inversion de Lagrange arborescente, à ma connaissance inconnue jusqu'ici.
Afin de mettre encore un peu de couleur locale à cet exposé, je montrerai comment déduire de ce résultat un algorithme de génération aléatoire d'une famille de cactacées fort en vogue sous nos latitudes.
Jean Berstel m'a fait observer que les facteurs de Lyndon qui apparaissent dans la factorisation du mot de Fibonacci sont égaux au produit de deux facteurs singuliers consécutifs du mot susdit, que définissent les frères Wen et Wen.
Je développerai ce thème, avec une généralisation aux mots sturmiens ; mais je crois bien que je vous épargnerai les détails dont il faut s'empêtrer pour jouir de la généralité de la chose ...
Dans le modèle des tas de sable de Dhar sur une grille rectangulaire, l'étude dynamique de la superposition des tas révèle un attracteur fini R qu'il s'agit de dénombrer. Pour cela, on propose deux méthodes : une à caractère géométrique consistant à compter des points à coordonnées entières contenus dans un hyper-parallélépipède, l'autre de nature combinatoire consistant à mettre en bijection les éléments de R avec les arbres couvrants d'un graphe contenant la grille.
Miklos Bona a donné une formule exacte pour dénombrer les permutations excluant le motif 1342 (permutations dont aucune sous-suite abcd n'est telle que a<d<b<c). Il s'agit du premier cas d'énumération de permutations excluant un motif de longueur supérieure à trois et différent du motif identite 12...k.
La preuve fait intervenir une bijection avec des arbres planaires étiquetés introduits par Robert Cori, Benjamin Jacquard et Gilles Schaeffer, arbres eux-mêmes en correspondance avec des cartes pointées bi-cubiques. Les résultats d'énumération se déduisent de cette bijection.
Un grand nombre de suites, séries génératrices et fonctions issues de la combinatoire et de la théorie des fonctions spéciales sont manipulables par le calcul formel dans le cadre de la théorie de l'holonomie. L'apport de cette théorie est de fournir plusieurs propriétés de clôture pour une vaste classe de suites et fonctions, et de rendre ces propriétés algorithmiques.
En particulier, les travaux de D.Zeilberger dans le début des années 1990 ont permis le développement de nouveaux algorithmes pour la sommation et l'intégration définie. Fondé sur un algorithme développé en 1978 par W.Gosper pour le calcul de sommes indéfinies de suites hypergéométriques, l'algorithme de Zeilberger est une extension astucieuse pour la sommation définie de suites hypergéométriques. Un autre algorithme de Zeilberger, plus général mais aussi plus lent, traite le cas plus large des fonctions holonomes. Bien que le cas général holonome n'ait plus reçu beaucoup d'attention depuis les premiers travaux de Zeilberger, il est fréquent en combinatoire et dans la théorie des fonctions spéciales.
Dans cet exposé, nous récapitulons les agréables propriétés de clôture des fonctions holonomes et rappelons brièvement les algorithmes de Gosper et de Zeilberger. Nous montrons ensuite leur généralisation pour obtenir des algorithmes rapides dans un contexte holonome.
Il y aura 9 chapitres:
Durant cet exposé, on présentera des travaux récents de A. Postnikov portant sur l'énumération de deux familles d'arbres, les arbres alternants et les arbres binaires de recherche "locaux". On donnera une preuve combinatoire de ces résultats d'énumération, résolvant ainsi un problème posé par A. Postnikov dans son article intitulé "Intransitive Trees" paru dans J. Combin. Theory Ser. A, vol. 79, n°2, p. 360-366 (1997).
Jusqu'à présent, l'étude des cartes a porté essentiellement sur les cartes pointées, c'est-à-dire ayant une arête distinguée et orientée. Nous levons cette restriction dans le cas des cartes à deux faces. On dénombre ces cartes selon la distribution des degrés des sommets et des faces. Les classes suivantes de cartes à deux faces non pointées sont considérées : étiquetées (aux sommets) ou non, plongées dans le plan ou sur la sphère. La motivation de cette recherche vient de la classification des fonctions de Belyi.
Voir l'article de Michel Bousquet, Gilbert Labelle et Pierre Leroux : Enumeration of planar 2-face maps (48 pages, PostScript comprimé, 114K).
Mireille Bousquet-Mélou, bousquet@labri.u-bordeaux.fr, gère le séminaire d'informatique fondamentale, le vendredi à 15h15.
Akka Zemmari gère le groupe de travail GASCom (Génération Aléatoire de Structures Combinatoires), le mercredi à 11h.