Guy Louchard ; Helmut Prodinger - Probabilistic Analysis of Carlitz Compositions

dmtcs:302 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5 - https://doi.org/10.46298/dmtcs.302
Probabilistic Analysis of Carlitz CompositionsArticle

Authors: Guy Louchard 1; Helmut Prodinger 2

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.


Volume: Vol. 5
Published on: January 1, 2002
Imported on: March 26, 2015
Keywords: Carlitz compositions,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

4 Documents citing this article

Consultation statistics

This page has been seen 258 times.
This article's PDF has been downloaded 209 times.