Louchard, Guy and Prodinger, Helmut - Probabilistic Analysis of Carlitz Compositions

dmtcs:302 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5
Probabilistic Analysis of Carlitz Compositions

Authors: Louchard, Guy and Prodinger, Helmut

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.


Source : oai:HAL:hal-00958973v1
Volume: Vol. 5
Published on: January 1, 2002
Submitted 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 62 times.
This article's PDF has been downloaded 45 times.