Premium
Distinctness of compositions of an integer: A probabilistic analysis
Author(s) -
Hitczenko Paweł,
Louchard Guy
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10008
Subject(s) - probabilistic logic , mathematics , markov chain , composition (language) , integer (computer science) , limiting , distribution (mathematics) , singularity , random variable , discrete mathematics , combinatorics , computer science , statistics , mathematical analysis , mechanical engineering , philosophy , linguistics , engineering , programming language
Abstract Compositions of integers are used as theoretical models for many applications. The degree of distinctness of a composition is a natural and important parameter. In this article, we use as measure of distinctness the number of distinct parts (or components). We investigate, from a probabilistic point of view, the first empty part, the maximum part size and the distribution of the number of distinct part sizes. We obtain asymptotically, for the classical composition of an integer, the moments and an expression for a continuous distribution F , the (discrete) distribution of the number of distinct part sizes being computable from F . We next analyze another composition: the Carlitz one, where two successive parts are different. We use tools such as analytical depoissonization, Mellin transforms, Markov chain potential theory, limiting hitting times, singularity analysis and perturbation analysis. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 407–437, 2001