DMTCS Proceedings, Discrete Random Walks, DRW'03

Font Size:  Small  Medium  Large

The number of distinct part sizes of some multiplicity in compositions of an Integer. A probabilistic Analysis

Guy Louchard


Random compositions of integers are used as theoretical models for many applications. The degree of distinctness of a composition is a natural and important parameter. A possible measure of distinctness is the number X of distinct parts (or components). This parameter has been analyzed in several papers. In this article we consider a variant of the distinctness: the number X(m) of distinct parts of multiplicity m that we call the m-distinctness. A first motivation is a question asked by Wilf for random compositions: what is the asymptotic value of the probability that a randomly chosen part size in a random composition of an integer ν has multiplicity m. This is related to E(X(m)), which has been analyzed by Hitczenko, Rousseau and Savage. Here, we investigate, from a probabilistic point of view, the first full part, the maximum part size and the distribution of X(m). We obtain asymptotically, as ν→ ∞, the moments and an expression for a continuous distribution φ, the (discrete) distribution of X(m,ν) being computable from φ.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional