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 Compositions

Authors: 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.


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]


Share

Consultation statistics

This page has been seen 121 times.
This article's PDF has been downloaded 113 times.