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 :