## Abstract

It is known that the following five counting problems lead to the same integer sequence f_{t}(n) : (1)the number of nonequivalent compact Huffman codes of length n over an alphabet of t letters,(2)the number of “nonequivalent” complete rooted t-ary trees (level-greedy trees) with n leaves,(3)the number of “proper” words (in the sense of Even and Lempel),(4)the number of bounded degree sequences (in the sense of Komlós, Moser, and Nemetz), and(5)the number of ways of writing (Formula presented.) with integers 0 ≤ x_{1}≤ x_{2}≤ ⋯ ≤ x_{n}.In this work, we show that one can compute this sequence for alln< N with essentially one power series division. In total we need at most N^{1}^{+}^{ε} additions and multiplications of integers of cN bits (for a positive constant c< 1 depending on t only) or N^{2}^{+}^{ε} bit operations, respectively, for any ε> 0. This improves an earlier bound by Even and Lempel who needed O(N^{3}) operations in the integer ring or O(N^{4}) bit operations, respectively.

Original language | English |
---|---|

Number of pages | 17 |

Journal | Applicable Algebra in Engineering, Communications and Computing |

Early online date | Jan 2023 |

DOIs | |

Publication status | E-pub ahead of print - Jan 2023 |

## Keywords

- Counting
- Generating function
- Huffman codes
- t-ary trees
- Unit fractions

## ASJC Scopus subject areas

- Algebra and Number Theory
- Applied Mathematics