Une méthode algorithmique pour le calcul des séries génératrices des classes de permutations, et pour la génération aléatoire dans ces classes

L’objectif de l’exposé est de présenter un cheminement algorithmique qui, partant d’une classe de permutations C donnée par sa base (supposée finie), permet d’obtenir automatiquement des résultats énumératifs sur la classe C , et un générateur aléatoire de permutations de C.

Je commencerai par définir les classes de permutations, et expliquerai comment le point de vue de la décomposition par substitution peut être efficacement utilisé pour décrire les permutations de toute classe donnée dans le formalisme des structures combinatoires. Une fois dans ce cadre classique, il devient aisé d’obtenir des résultats d’énumération et des générateurs aléatoires. La difficulté principale est de passer algorithmiquement de la description d’une classe par sa base à un système d’équations la décrivant comme une structure combinatoire. Je montrerai les principales étapes de ce cheminement, et esquisserai une explication plus détaillée de certaines d’entre elles.

Il s’agit d’un travail en commun avec Frédérique Bassino, Adeline Pierrot, Carine Pivoteau et Dominique Rossin.