Distinctness of compositions of an integer: A probabilistic analysis
Paweł Hitczenko, Guy Louchard · Random Structures and Algorithms · 2001
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 distributionF, the (discrete) distribution of the number of distinct part sizes being computable fromF. 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