Discrete Mathematics & Theoretical Computer Science, Vol 5 (2002)

Font Size:  Small  Medium  Large

Probabilistic Analysis of Carlitz Compositions

Guy Louchard, Helmut Prodinger


Using generating functions and limit theorems, we obtain a stochastic description of Carlitz compositions of large integer n (i.e. compositions two successive parts of which are different). We analyze: the number M of parts, the number of compositions T(m,n) with m parts, the distribution of the last part size, the correlation between two successive parts, leading to a Markov chain. We describe also the associated processes and the limiting trajectories, the width and thickness of a composition. We finally present a typical simulation. The limiting processes are characterized by Brownian Motion and some discrete distributions.

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