L'image de fond est un animal dirigé aléatoire.
For more than 40 years an important method in the study of problems in Statistical Mechanics has been based on a combinatorial formulation of the problem, followed by enumeration of the first 5-500 coefficients of the generating function. These coefficients are then used to estimate the asymptotic behaviour, or in some cases to conjecture the exact solution.
I will describe the various methods used, with particular application to problems in combinatorics.
fn+1 = 6 fn - fn-1.
J.Bonin, L.Shapiro et R. Simion ont posé le problème de donner une interprétation combinatoire de la relation liant les nombres NSW :
fn+1 = 6 fn - fn-1, avec f1 = 1 et f2 = 7 .
Dans ce travail je définis un language rationnel L dont le nombre de mots de longueur n est fn+1 . Puis j'en déduis une preuve combinatoire de la formule précédente .
Il s'agit d'un travail commun avec Alain Goupil (LaCIM). Le but de l'exposé est de répondre à la question suivante : étant donnée la permutation cyclique pi=(1...n) et deux partitions de n, notées a et b, combien existe-t-il de factorisations de pi sous la forme : sigma.tau=pi où sigma est de type cyclique a, tau est de type cyclique b.
En combinant un peu de théorie des caractères du groupe symétrique avec beaucoup de bijections sur des partitions coloriées, on montrera une formule explicite pour ce coefficient. Cette formule généralise des cas particuliers donnés par Stanley, Goupil et Goulden et Jackson.
Par ailleurs ce coefficient s'interprète comme le nombre de cartes biparties à une face, dont la bi-distribution des degrés des sommets est donnée. En particulier lorsque les distributions sont planaires, les cartes ont une seule face et sont des arbres bicoloriés.
The tree graph T(G) of a connected graph G has as vertices the spanning trees of G, and two trees are adjacent if one is obtained from the other by interchanging one edge. We introduce the restricted tree graph of G, denoted T*(G), where adjacencies are defined by disconnecting one leaf and reconnecting it to a different vertex. If n = |V(G)|, we show that the diameter of T*(G) is O(n2), and that this bound cannot be improved in general. On other hand, we obtain upper and lower bounds for the chromatic number both of T(G) and T*(G). In particular, for even n, we obtain the exact value of the chromatic number of T*(Kn).
Le théorème de Cayley affirme que le nombre des arbres avec (n+1) sommets étiquetés est (n+1)n-1. Il est facile d'en conclure que le nombre des arbres avec n arêtes étiquetées est (n+1)n-2. Parmi les preuves diverses du théorème de Cayley il y a une preuve de E. Looijenga (1974). Cette preuve montre que le nombre des arbres avec les arêtes étiquetées est égal à la multiplicité de l'"application de Lyashko-Looijenga", qui associe à chaque polynôme complexe un autre polynôme, dont les racines sont les valeurs critiques du polynôme d'origine.
L'application de la même technique à d'autres classes de fonctions permet d'énumérer d'autres classes de graphes. Les résultats établissent une correspondance entre la multiplicité de l'application de Lyashko-Looijenga d'une part, et des formules de Goulden et Jackson d'énumération des cactus et de représentations d'une permutation comme produit de transpositions.
Je donnerai des grammaires pour la génération des mots de Dyck "étendus" à une "pente" rationnelle p/q (au lieu de 1), dont Hélène Jacquet nous a déjà parlé. Ces grammaires conduisent à des résultats (encore partiels) d'énumération suivant des chemins quelque peu détournés.
Nous présenterons d'abord le paquetage Maple combstruct développé en commun avec le projet Algorithmes de l'Inria, et nous indiquerons comment s'en servir pour spécifier, dénombrer et générer aléatoirement des structures combinatoires. Les applications de combstruct vont des "mathématiques expérimentales" à la génération de jeux de tests de programmes. Puis nous montrerons comment générer aléatoirement des arbres non enracinés, qu'ils soient planaires (1, 1, 1, 2, 3, 6, 14, 34, 95, 280, etc.) ou non (1, 1, 1, 2, 3, 6, 11, 23, 47, 106, etc.). Puis nous présenterons quelques problèmes ouverts en génération aléatoire uniforme.
La théorie des structures décomposables permet de définir de façon générique, à partir d'un faible nombre de constructeurs, de larges classes de structures de données utilisées fréquemment en mathématiques ou en informatique. On pourra par exemple décrire les permutations, les arbres généraux ou encore les graphes fonctionnels. Le nombre de classes que l'on peut représenter est illimité. Il est en effet possible de substituer les éléments de base d'une structure par n'importe quelle autre structure. La bibliothèque combstruct de génération aléatoire, écrite en Maple par Paul Zimmermann et Eithne Murray, permet d'engendrer de façon uniforme des structures combinatoires décomposables. Mais il est souvent difficile d'interpréter les résultats obtenus.
Je présenterai le programme CGraph, un outil permettant de créer de façon interactive et de tracer de façon automatique des graphes possédant des relations d'adjacence et d'inclusion entre les noeuds. CGraph peut être utilisé conjointement avec combstruct pour former un outil intégré de génération aléatoire et de tracé de structures décomposables.
HISTORIQUE. Les partitions "Lecture Hall" (ou amphi) de longueur n sont les n-uplets (L1, ... , Ln) tels que
Voir le mémoire The major counting of nonintersecting lattice paths and generating functions for tableaux (109 pages, PostScript comprimé, 298K), et les articles Counting nonintersecting lattice paths with turns (17 pages, PostScript comprimé, 64K), A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, with M. Prohaska (29 pages, PostScript comprimé, 103K),
A bijective proof for Stanley's hook-content formula for the generating function for tableaux of a given shape is given that does not involve the involution principle of Garsia and Milne. It is based on the Hillman-Grassl algorithm and Schützenberger's jeu de taquin.
Voir l'article An involution principle-free bijective proof of Stanley's hook-content formula (23 pages, PostScript comprimé, 86K).
It is well known that the number of ways of triangulating a convex polygon is a Catalan. In this talk we discuss the enumeration of triangulations of non convex polygons, as well as the enumeration of triangulations of convex polygons with respect to several parameters.
Les fonctions de Belyi relient la combinatoire des cartes avec la théorie de Galois, la théorie des nombres algébriques et la théorie des surfaces de Riemann. Cet exposé présente le calcul des fonctions de Belyi pour une classe de cartes semi-régulières, correspondant à ce qu'on appelle les solides d'Archimède.
Voir l'article Belyi Functions for Archimedean Solids (16 pages, PostScript comprimé, 454K), par Nicolas Magot et Alexander Zvonkin.
We consider two combinatorial statistics on permutations. One is the genus. The other, $dd$, is defined for alternating permutations, as the sum of the number of descents in the subwords formed by the peaks and by the valleys. We investigate the distribution of $dd$ on genus zero permutations and Baxter permutations. Our enumerative results relate the $dd$ statistic to lattice path enumeration, the rank generating function and characteristic polynomial of non-crossing partition lattices.
Voir aussi l'environnement de cet article, en particulier l'article de R.Stanley Hipparchus, Plutarch, Schröder and Hough (12 pages, 62K, PostScript comprimé).
L'auteur introduit une famille d'opérations sur les arbres. Ces opérations sont obtenues a l'aide d'une définition récursive a partir d'une opération initiale. Elles apparaissent comme une généralisation des opérations addition, multiplication et exponentiation des nombres entiers. Elles transportent, dans un sens à préciser, des paramètres connus sur les arbres binaires comme par exemple les nombres de Strahler.
I will show how the problem of enumerating lattice paths by length and number of wall contacts can be expressed as a constant term formula. The combinatorial interpretation of the constant term formula includes several classical bijections and involutions: theses include the reflection principle, the determinant method and a bijection to terraced paths. I will also show how the problem of enumerating osculating lattice paths (ie. non-crossing paths that can have common vertices) can also be written as a constant term formula. A special case gives rise to a constant term formula for the number of alternating sign matrices.
Some of the most famous results in mathematics involve a proof of the intrinsic unsolvability of certain problems - such as the roots of a general quintic. In mathematical physics such results are largely unknown. I will describe a powerful numerical technique that provides compelling evidence for (but is not a proof of) the unsolvability of a wide variety of classical, unsolved problems in Statistical Mechanics and Combinatorics, in terms of the "standard" functions of mathematical physics (including D-finite functions).
Usando una particolare classe di alberi ternari (alberi sinistri), illustriamo una dimostrazione combinatoria della formula che enumera le carte planari puntate non separabili secondo il numero di archi . Il primo passo della dimostrazione consiste nello stabilire una biezione tra alberi sinistri aventi n nodi e le carte planari puntate non separabili aventi n+1 archi . Il secondo passo consiste nella deteminazione di una biezione tra alberi ternari non sinistri aventi n nodi interni e le coppie di alberi ternari aventi complessivamente n nodi. Da cio segue la determinazione della formula enumerativa degli alberi sinistri e quindi la dimostrazione biettiva della formula che enumera le carte planari puntate non separabili .
Mireille Bousquet-Mélou, bousquet@labri.u-bordeaux.fr, gère le séminaire d'informatique fondamentale, le vendredi à 15h15.