Distinctness of compositions of an integer: A probabilistic analysis

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 & Suns, Inc.SCOPUS: ar.jFLWINinfo:eu-repo/semantics/publishedSpecial Issue: Analysis of Algorithms Dedicated to Don Knu