D Un peu d’histoire. . .
489
séries. En outre, les dites séries sont vues comme fonctions de la variable complexe :
à travers l’analyse des singularités, la richesse de l’analyse complexe est revisitée
(par exemple avec les lemmes de transfert et la méthode du col) afin d’extraire
la substantifique moelle de ces séries, à savoir le comportement asymptotique des
coefficients, et afin d’établir les propriétés des « grandes » structures combinatoires.
Cet ouvrage monumental sert de référence à la fois par l’exposition et aussi par le
très grand nombre d’exemples traités.
Parmi eux, et constituant l’un des sujets les plus exemplaires en termes d’emploi
complémentaire des méthodes combinatoires et probabilistes se trouvent les urnes
de Pólya. Modèle naturel, dès qu’il s’agit de dénombrer des objets de différents
types (couleurs) tirés aléatoirement uniformément, il a été introduit par Pólya [210]
dans les années 30 et étudié concurremment par méthodes probabilistes et analytiques. Les urnes de Pólya apparaissent dans le dénombrement des feuilles de
plusieurs arbres liés à l’algorithmique (arbres récursifs, bucket trees,. . . ) et le livre
de Mahmoud [173], Pólya urn models, présente de façon élémentaire ces modèles.
Deux avancées importantes dans l’étude de l’asymptotique de la composition d’une
telle urne se produisent à peu près au même moment : l’article Analytic urns de
Flajolet et al. [102] en 2005, article séminal sur l’utilisation dans ce domaine
de la combinatoire analytique ; et l’article de synthèse de Janson [147] en 2004,
Functional limit theorem for multitype branching processes and generalized Pólya
urns, dans lequel la méthode de plongement en temps continu d’une urne de Pólya
discrète est largement exploitée. L’utilisation de martingale, déjà présente dans les
travaux de Gouet [120, 121] et ceux de Smythe [236] et Mahmoud, est chez Janson
tout à fait fondamentale.
Enfin, le livre le plus proche du nôtre est sans doute celui de Drmota, Random
Trees. An Interplay between Combinatorics and Probabilities, [68], paru en 2008 :
les sujets traités, très similaires, le sont avec le même souci de présenter les deux
approches (combinatoire analytique et probabilités). Il est par certains côtés plus
complet que le présent ouvrage ; pour donner deux exemples, il étudie la forme et
le profil de plusieurs sortes d’arbres alors que nous ne faisons guère cette étude que
pour les arbres binaires de recherche, et il traite des arbres de Galton-Watson ou
des arbres récursifs à un niveau de détail supérieur au nôtre. Par contre, le point
de vue algorithmique est moins développé. Une autre différence réside dans la
présentation des résultats, qui sont souvent structurés par paramètre pour différents
types d’arbres, alors que nous étudions plutôt chaque type d’arbre sous différents
angles. Mais la différence essentielle est sans doute que ce livre ne s’adresse pas
exactement au même public que le nôtre : il est destiné davantage à des chercheurs
qu’à des étudiants, davantage à des spécialistes en combinatoire analytique ou
probabilités qu’à des chercheurs dans des domaines connexes. Prenons l’exemple
des arbres binaires de recherche : dans les deux livres sont étudiés la profondeur
d’insertion et le profil, à la fois par fonctions génératrices et par martingales et
méthode de contraction. Le livre de Drmota ajoute l’étude détaillée de la hauteur par
des équations différentielles retardées ; notre livre ajoute, outre les arbres binaires
de recherche biaisés, une coloration algorithmique (conséquences des résultats sur
489
séries. En outre, les dites séries sont vues comme fonctions de la variable complexe :
à travers l’analyse des singularités, la richesse de l’analyse complexe est revisitée
(par exemple avec les lemmes de transfert et la méthode du col) afin d’extraire
la substantifique moelle de ces séries, à savoir le comportement asymptotique des
coefficients, et afin d’établir les propriétés des « grandes » structures combinatoires.
Cet ouvrage monumental sert de référence à la fois par l’exposition et aussi par le
très grand nombre d’exemples traités.
Parmi eux, et constituant l’un des sujets les plus exemplaires en termes d’emploi
complémentaire des méthodes combinatoires et probabilistes se trouvent les urnes
de Pólya. Modèle naturel, dès qu’il s’agit de dénombrer des objets de différents
types (couleurs) tirés aléatoirement uniformément, il a été introduit par Pólya [210]
dans les années 30 et étudié concurremment par méthodes probabilistes et analytiques. Les urnes de Pólya apparaissent dans le dénombrement des feuilles de
plusieurs arbres liés à l’algorithmique (arbres récursifs, bucket trees,. . . ) et le livre
de Mahmoud [173], Pólya urn models, présente de façon élémentaire ces modèles.
Deux avancées importantes dans l’étude de l’asymptotique de la composition d’une
telle urne se produisent à peu près au même moment : l’article Analytic urns de
Flajolet et al. [102] en 2005, article séminal sur l’utilisation dans ce domaine
de la combinatoire analytique ; et l’article de synthèse de Janson [147] en 2004,
Functional limit theorem for multitype branching processes and generalized Pólya
urns, dans lequel la méthode de plongement en temps continu d’une urne de Pólya
discrète est largement exploitée. L’utilisation de martingale, déjà présente dans les
travaux de Gouet [120, 121] et ceux de Smythe [236] et Mahmoud, est chez Janson
tout à fait fondamentale.
Enfin, le livre le plus proche du nôtre est sans doute celui de Drmota, Random
Trees. An Interplay between Combinatorics and Probabilities, [68], paru en 2008 :
les sujets traités, très similaires, le sont avec le même souci de présenter les deux
approches (combinatoire analytique et probabilités). Il est par certains côtés plus
complet que le présent ouvrage ; pour donner deux exemples, il étudie la forme et
le profil de plusieurs sortes d’arbres alors que nous ne faisons guère cette étude que
pour les arbres binaires de recherche, et il traite des arbres de Galton-Watson ou
des arbres récursifs à un niveau de détail supérieur au nôtre. Par contre, le point
de vue algorithmique est moins développé. Une autre différence réside dans la
présentation des résultats, qui sont souvent structurés par paramètre pour différents
types d’arbres, alors que nous étudions plutôt chaque type d’arbre sous différents
angles. Mais la différence essentielle est sans doute que ce livre ne s’adresse pas
exactement au même public que le nôtre : il est destiné davantage à des chercheurs
qu’à des étudiants, davantage à des spécialistes en combinatoire analytique ou
probabilités qu’à des chercheurs dans des domaines connexes. Prenons l’exemple
des arbres binaires de recherche : dans les deux livres sont étudiés la profondeur
d’insertion et le profil, à la fois par fonctions génératrices et par martingales et
méthode de contraction. Le livre de Drmota ajoute l’étude détaillée de la hauteur par
des équations différentielles retardées ; notre livre ajoute, outre les arbres binaires
de recherche biaisés, une coloration algorithmique (conséquences des résultats sur