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
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