The number of Huffman codes, compact trees, and sums of unit fractions

Abstract

The number of "nonequivalent" Huffman codes of length r over an alphabet of size t has been studied frequently. Equivalently, the number of "nonequivalent" complete t-ary trees has been examined. We first survey the literature, unifying several independent approaches to the problem. Then, improving on earlier work we prove a very precise asymptotic result on the counting function, consisting of two main terms and an error term.

References in corpus (1)

• Egyptian Fractions with Restrictions

Cited by in corpus (6)

• Compositions into Powers of $b$: Asymptotic Enumeration and Parameters
• Canonical Trees, Compact Prefix-free Codes and Sums of Unit Fractions: A Probabilistic Analysis
• Divided power algebras over an operad
• Bounds on the Number of Huffman and Binary-Ternary Trees
• On solutions of ${\sum }_{i=1}^{n}1/x_i=1$ in integers of the form $2^a{k}^b$
• Algorithmic counting of nonequivalent compact Huffman codes