Ecole Jeunes Chercheurs en Algorithmique et Calcul Formel

(LaBRI, Université Bordeaux 1)

"Combinatoire analytique : application aux marches aléatoires"

Cyril Banderier, Projet Algorithmes, INRIA.

Résumé : Nombreux sont les domaines qui regorgent de structures combinatoires. On peut citer l'exemple historique des grammaires en théorie des langages, le cas des molécules d'alcools ou diverses structures cristallines en chimie, les partitions, les facteurs des polynômes en théorie des nombres, l'ADN en biologie, le modèle d'Ising, les tas de sable en physique statistique, les arbres, les permutations en algorithmique.

Or il se trouve que les égalités qui définissent une structure combinatoire peuvent être traduites en des équations fonctionnelles. Nous sommes alors ramenés à faire de l'analyse sur des séries génératrices. Les singularités des fonctions obtenues dictent la croissance des coefficients. Cela permet d'obtenir des résultats asymptotiques quant au dénombrement, de capter la moyenne, la variance et même les moments d'ordre supérieur d'un paramètre (et donc d'en trouver la loi limite).

La combinatoire analytique a été popularisée à la fin des années 60 par D.E. Knuth (confer TAOCP) qui fut le premier à l'appliquer à l'analyse d'algorithmes (une première étape étant de cerner la structure combinatoire dissimulée dans l'algorithme). En France, l'application de la combinatoire analytique à l'analyse d'algorithmes et à l'étude de nombreuses autres structures combinatoires peut être imputée à P. Flajolet.

Je vais ci-après illustrer un peu la philosophie et les méthodes de la combinatoire analytique sur un exemple concret, que j'ai etudié dans mon mémoire de DEA : celui de marches aléatoires dont les sauts obéissent à des règles précises.

***

Les mots engendrés par une grammaire avec un alphabet infini et un ensemble infini de productions peuvent être vus comme les traces d'une marche dans un automate infini.

C'est un problème qui équivaut à regarder les puissances itérées d'une matrice (infinie); c'est aussi, et c'est ce point de vue que nous retiendrons, équivalent à l'étude de marches (aléatoires) sur un réseau discret.

Nous nous intéresserons plus particulièrement aux séries génératrices de ces "marches aléatoires sur les entiers" qui décomptent les chemins de longueur n (les mots de longueur n) ou les excursions (les mots qui commencent et finissent en 0).

À titre d'illustration, un cas bien connu est le langage de Dyck qui peut être vu comme une marche pour laquelle on part de (0) et on finit en (0) en ne faisant que des pas +1 ou -1, tout en restant positif (la série génératrice donne les nombres de Catalan).

On donnera toute une classe de grammaires infinies donnant des séries rationnelles, algébriques ou transcendantes. Nous montrerons comment expliciter ces séries génératrices.

Nous illustrerons nos propos par quelques exemples ludiques :

  • les Motzkin, les Dyck, une marche rationnelle sur les nombres premiers,
  • la résolution de la conjecture de Pinzani sur les "arbres de génération",
  • le problème du cavalier d'échecs, déjà étudié via d'autres méthodes par Labelle et Yeh,
  • le lien avec les fractions continuées, développé dans un autre contexte par un article de Flajolet en 1980,
  • un problème ouvert de Petkovsek, sur un triangle "à la Pascal".

    Finalement, nous nous attaquerons également à des propriétés en moyenne (nombre moyen de facteurs d'un mot de Dyck) et surtout à l'asymptotique du nombre de mots de longueur n. L'inversion de Lagrange marche pour des équations u=z phi(u), nous devrons étudier l'équation plus générale u^c=z phi(u), ce qui se fait via la méthode du point col.

    La résolution de la conjecture de Pinzani a fait l'objet d'un article commun (C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy et D. Gouyou-Beauchamps), accepté à FPSAC'99.


    Cyril Banderier
    Projet Algorithmes
    INRIA Rocquencourt
    78153 Le Chesnay

    http://algo.inria.fr/banderier/
    Cyril.Banderier at inria.fr