Integer compositions with part sizes not exceeding k

2011/08/01 by Martin E. Malandro, Malandro, Martin E. · 2 citations
Mathematics · #05A15 #05A16 #11B37 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1108.0337

openalex publication_date 2011/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the compositions of an integer n whose part sizes do not exceed a fixed integer k. We use the methods of analytic combinatorics to obtain precise asymptotic formulas for the number of such compositions, the total number of parts among all such compositions, the expected number of parts in such a composition, the total number of times a particular part size appears among all such compositions, and the expected multiplicity of a given part size in such a composition. Along the way we also obtain recurrences and generating functions for calculating several of these quantities. Our results also apply to questions about certain kinds of tilings and rhythm patterns.

Cited by

• Asymptotic normality of integer compositions inside a rectangle
• On compositions of natural numbers

Related

• Expected number of distinct part sizes in a random integer composition
• Enumerating Segmented Patterns in Compositions and Encoding by Restricted Permutations
• Enumeration of 3-letter patterns in compositions
• Compositions with restricted parts
• Counting rises, levels and drops in compositions