Marking in Combinatorial Constructions : Generating Functions and Limiting Distributions

M. Drmota, M. soria

IBP-Litp 1995/02: Rapport de Recherche Litp / Litp research reports
34 pages - Janvier/January 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Marking in Combinatorial Constructions : Generating Functions and Limiting Distributions

Résumé : Pour un grand nombre de constructions combinatoires, intervenant en particulier en analyse d'algorithmes, il existe une série génératrice explicite y(x) =S ynxn pour le nombre d'objets de taillen , et une série bivariéey(x,u) =S ynkxnuk pour le nombre d'objets de taillen ayant valeurk pour un autre paramètre. Ce paramètre supplémentaire peut être marqué de façon formelle dans la construction combinatoire considérée. Le but de cet article est de fournir des méthodes générales permettant d'obtenir la distribution limite de ce paramètre supplémentaire dans les objets de taillen .
Nous nous intéressons en particulier à l'obtention de théorèmes limites locaux, qui nécessitent l'estimation des coefficients de puissances de fonctions génératrices. Dans le cas de fonctions à singularité logarithmique, nous dérivons des approximations uniformes pour [xn ]y(x)k, pour k¾en ; nous obtenons en application la distribution limite conditionnelle du nombre d'arbres dans les graphes fonctionnels ayant un nombre de cycles donné.
Nous considérons aussi des schémas produits y(x,u) =g(x)F(uw(x)) : nous montrons comment, dans un tel schéma, la distribution limite peut être dictéé par by g(x) ou par F(uw(x)) , ou encore peut dépendre à la fois de g et F ; de nombreuses applications combinatoires sont présentées.

Abstract : There is a wide field of combinatorial constructions, especially in combinatorial analysis of algorithms, where it is possible to find an explicit generating function y(x) =S ynxn for the number yn of objects of sizen and a bivariate functiony(x,u) =S ynkxnuk for the number yn k of objects of sizen where another parameter has valuek . Formally this additional parameter is marked in the above combinatorial construction. The aim of this paper is to provide general methods to obtain the limiting distribution of this additional parameter in objects of sizen .
We are especially interested in local limit theorems, which involve estimating the coefficients of powers of generating functions. When is a function with a logarithmic singularity, we derive uniform approximations for [xn ]y(x)k, for k¾en ; as a byproduct, we obtain conditional limiting distributions for the number of trees in random mappings where the number of cycles is given.
Product schemas y(x,u) =g(x)F(uw(x)) are also considered: we show how the limiting distribution may be dictated either by g(x) or by F(uw(x)) , or should involve both g and F ; and we give many combinatorial applications.

Publications internes Litp 1995 / Litp research reports 1995