Compositions into powers of b: asymptotic enumeration and parameters

DOI10.1007/S00453-015-0061-3zbMATH Open1344.05016OpenAlexW2125515704WikidataQ59461597 ScholiaQ59461597MaRDI QIDQ308944FDOQ308944

Authors Daniel Krenn, Stephan Wagner

Publication date 6 September 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4331

zbMATH Keywords

compositionsasymptotic enumerationinfinite transfer matricespowers of 2

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatorial aspects of partitions of integers (05A17) Other combinatorial number theory (11B75) Other number representations (11A67)

Abstract: For a fixed integer base $bgeq2$, we consider the number of compositions of $1$ into a given number of powers of $b$ and, related, the maximum number of representations a positive integer can have as an ordered sum of powers of $b$. We study the asymptotic growth of those numbers and give precise asymptotic formulae for them, thereby improving on earlier results of Molteni. Our approach uses generating functions, which we obtain from infinite transfer matrices. With the same techniques the distribution of the largest denominator and the number of distinct parts are investigated.

Recommendations

• The number of compositions into powers of \(b\)
• REPRESENTATION OF A 2-POWER AS SUM OF k 2-POWERS: THE ASYMPTOTIC BEHAVIOR
• Compositions with parts constrained by the leading summand.
• The distribution of ascents of size \(d\) or more in compositions
• Locally restricted compositions. I. Restricted adjacent differences

Cites work

• scientific article; zbMATH DE number 5281503 (Why is no real title available?)
• scientific article; zbMATH DE number 3910298 (Why is no real title available?)
• scientific article; zbMATH DE number 3232846 (Why is no real title available?)
• scientific article; zbMATH DE number 3047573 (Why is no real title available?)
• A Sufficient Condition for the Convergence of an Infinite Determinant
• Analytic combinatorics
• Cancellation in a short exponential sum
• Infinite systems of functional equations and Gaussian limiting distributions
• Large deviations of combinatorial distributions. II: Local limit theorems
• Level number sequences for trees
• On Mahler's partition problem
• On a Special Functional Equation
• On convergence rates in the central limit theorems for combinatorial structures
• On the vector space of the automatic reals
• REPRESENTATION OF A 2-POWER AS SUM OF k 2-POWERS: THE ASYMPTOTIC BEHAVIOR
• Representation of a 2-power as sum of \(k\) 2-powers: a recursive formula
• Singularity Analysis of Generating Functions
• The Number of Huffman Codes, Compact Trees, and Sums of Unit Fractions
• The asymptotic number of solutions of a diophantine equation from coding theory
• The number of compositions into powers of \(b\)

Cited in

(2)

• The number of compositions into powers of \(b\)
• The associative-commutative spectrum of a binary operation

Describes a project that uses

Uses Software

• SageMath
• OEIS

This page was built for publication: Compositions into powers of \(b\): asymptotic enumeration and parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q308944)