Skip to Main content Skip to Navigation
Journal articles

Probabilistic Analysis of Carlitz Compositions

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958973
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:55:10 PM
Last modification on : Thursday, June 4, 2020 - 10:24:03 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:06:52 PM

File

dm050105.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958973, version 1

Collections

Citation

Guy Louchard, Helmut Prodinger. Probabilistic Analysis of Carlitz Compositions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.71-96. ⟨hal-00958973⟩

Share

Metrics

Record views

129

Files downloads

752