Compositions into powers of b: asymptotic enumeration and parameters

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

Authors: Daniel Krenn, Stephan Wagner 

Publication date: 6 September 2016

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (1)

• The associative-commutative spectrum of a binary operation

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)