Algorithmic counting of nonequivalent compact Huffman codes

Christian Elsholtz, Clemens Heuberger, Daniel Krenn

It is known that the following five counting problems lead to the same integer sequence~$f_t(n)$: the number of nonequivalent compact Huffman codes of length~$n$ over an alphabet of $t$ letters, the number of nonequivalent' canonical rooted $t$-ary trees (level-greedy trees) with $n$~leaves, the number of proper' words, the number of bounded degree sequences, and the number of ways of writing $1= \frac{1}{t^{x_1}}+ \dots + \frac{1}{t^{x_n}}$ with integers $0 \leq x_1 \leq x_2 \leq \dots \leq x_n$. In this work, we show that one can compute this sequence for \textbf{all} \$n

arrow_drop_up