Marking in Combinatorial Constructions : Images and Preimages in Ramdom Mappings

M. Drmota, M. Soria

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

PostScript : Ko /Kb

Titre / Title: Marking in Combinatorial Constructions : Images and Preimages in Ramdom Mappings

Résumé : Cet article présente un théorème général permettant de caractériser les distributions limites d'une large classe de schémas combinatoires. Par exemple, de nombreux paramètres liés aux points images et préimages dans les graphes fonctionnels, sont traités par ce théorème et présentent trois types de lois limites : gaussienne, de type rayleigh, ou convolution des deux. En particulier, on montre que la distribution limite du nombre de points ayant un nombre total de prédécesseurs fixé est gaussienne.

Abstract : This paper presents a general theorem which can be used to identify the limiting distributions for a class of combinatorial schemata. For example, many parameters related to image and preimage points in random mappings, can be covered in this way, and present three types of limit laws : Gaussian, Rayleigh or a convolution of both. Especially we show that the limiting distribution of the number of points having a fixed number of total predecessors is Gaussian.

Publications internes Litp 1995 / Litp research reports 1995