Distinctness of compositions of an integer: A probabilistic analysis

DOI10.1002/RSA.10008zbMath1014.05008OpenAlexW1983026764MaRDI QIDQ2772926

Pawel Hitczenko, Guy Louchard

Publication date: 5 July 2003

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10008

zbMATH Keywords

asymptotic distributionsrandom integer composition

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Combinatorial probability (60C05)

Related Items (18)

Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform ⋮ Rounding of continuous random variables and oscillatory asymptotics ⋮ Record statistics in a random composition ⋮ Local limit theorems for finite and infinite urn models ⋮ Tight Markov chains and random compositions ⋮ Unnamed Item ⋮ Longest run of equal parts in a random integer composition ⋮ Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set ⋮ On gaps and unoccupied urns in sequences of geometrically distributed random variables ⋮ The largest missing value in a composition of an integer ⋮ Some large polyominoe's perimeter: a stochastic analysis ⋮ Gap-free compositions and gap-free samples of geometric random variables ⋮ The number of distinct adjacent pairs in geometrically distributed words: a probabilistic and combinatorial analysis ⋮ On random trees obtained from permutation graphs ⋮ On the variance of the number of occupied boxes ⋮ The asymmetric leader election algorithm: Number of survivors near the end of the game ⋮ Monotone runs of uniformly distributed integer random variables: A probabilistic analysis ⋮ Runs of geometrically distributed random variables: A probabilistic analysis

Cites Work

• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• General combinatorial schemas: Gaussian limit distributions and exponential tails
• Three problems in combinatorial asymptotics
• Approximate counting: a detailed analysis
• Probabilistic counting algorithms for data base applications
• Brownian motion and algorithm complexity
• Analytical depoissonization and its applications
• Probability approximations via the Poisson clumping heuristic
• Inequalities for rare events in time-reversible Markov chains. II
• Markov chain models - rarity and exponentiality
• On Carlitz compositions
• On convergence rates in the central limit theorems for combinatorial structures
• The number of distinct part sizes in a random integer partition
• Measures of distinctness for random partitions and compositions of an integer
• Recurrence times and capacities for finite ergodic chains
• Discrete limit distributions in the problem of balls falling in cells with arbitrary probabilities
• Central and local limit theorems applied to asymptotic enumeration
• The distribution of the number of summands in the partitions of a positive integer
• Expected Number of Distinct Part Sizes in a Random Integer Composition
• Singularity Analysis of Generating Functions
• Exact and asymptotic distributions in digital and binary search trees
• Data Structures' Maxima
• Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
• Asymptotic Normality in the Classical Ball Problem

This page was built for publication: Distinctness of compositions of an integer: A probabilistic analysis