## DMTCS Proceedings, Discrete Random Walks, DRW'03

DMTCS Conference vol AC (2003), pp. 155-170 ## Discrete Random Walks, DRW'03

### DMTCS Conference Volume AC (2003), pp. 155-170

author: Guy Louchard The number of distinct part sizes of some multiplicity in compositions of an Integer. A probabilistic Analysis Mellin transforms, urns models, Poissonization, saddle point method, generating functions 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 φ . If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. Guy Louchard (2003), The number of distinct part sizes of some multiplicity in compositions of an Integer. A probabilistic Analysis, in Discrete Random Walks, DRW'03, Cyril Banderier and Christian Krattenthaler (eds.), Discrete Mathematics and Theoretical Computer Science Proceedings AC, pp. 155-170 For a corresponding BibTeX entry, please consider our BibTeX-file. dmAC0115.ps.gz (60 K) dmAC0115.ps (204 K) dmAC0115.pdf (164 K)