Résumé

I. Dutour.
Grammaires d'objets : énumération, bijections et génération aléatoire.
PhD thesis, Université Bordeaux 1, January 1996.

Cette thèse aborde divers problèmes du domaine de la combinatoire énumérative et bijective. Elle concerne la formalisation de la notion de grammaires d'objets - descriptions récursives d'objets combinatoires exprimées sous forme de dessins - ainsi que l'étude de différents domaines d'application : énumération, constructions de bijections, et génération aléatoire uniforme.

En appliquant des valuations d'objets linéaires (ou q-linéaires) aux grammaires d'objets, nous pouvons déduire directement le système d'équations algébriques (ou de q-équations) vérifié par la série génératrice des objets engendrés.

Dans le cadre des bijections, notre théorème central propose un élément de réponse à une constatation bien connue : ``Pourquoi les mots de Dyck jouent-ils un rôle si important dans le codage des objets combinatoires ?''. En effet, il exhibe la construction de bijections entre les mots de Dyck et tout ensemble d'objets engendré par une grammaire d'objets de dimension 1 et de degré supérieur ou égal à 2.

Notre contribution dans le domaine de la génération aléatoire d'objets combinatoires est une approche systématique de la méthode récursive pour des objets engendrés par des grammaires d'objets auxquelles sont appliquées des valuations linéaires ou q-linéaires. La génération selon des paramètres non algébriques est ainsi rendue accessible. Ce travail est implémenté en Maple.

Mots-clés :

grammaires d'objets, valuations d'objets, énumération, bijections, mots de Dyck, génération aléatoire uniforme.