Computing and estimating the number of nn-ary Huffman sequences of a specified length

An nn-ary Huffman sequence of length qq is the list, in non-decreasing order, of the lengths of the code words in a prefix-free replacement code for a qq-letter source alphabet over an nn-letter code alphabet, optimal with respect to some probability (relative frequency) distribution over the source alphabet, meaning that the code minimizes the average number of code letters per source letter. Here we extend a theorem in [E. Norwood, The number of different possible compact codes, IEEE Trans. Inform. Theory (October) (1967) 613–616] about the case n=2n=2 to arbitrary n≥2n≥2. The theorem permits the recursive computation of the number, h(q,n)h(q,n), of different nn-ary Huffman sequences of length qq, and the estimation of h(q,n)h(q,n), which turns out to grow geometrically with qq, for each n≥2n≥2. Upper and lower estimates of h(q,n)h(q,n) are given for 2≤n≤62≤n≤6. For instance, c1(1.75488)q≤h(q,2)≤c2(1.83929)qc1(1.75488)q≤h(q,2)≤c2(1.83929)q for some constants c1,c2c1,c2; this result significantly tightens the estimates of h(q,2)h(q,2) in [J. Burkert, Simple bounds on the numbers of binary Huffman sequences, Bull. Inst. Combin. Appl. 58 (2010) 79–82].