Computing and estimating the number of \(n\)-ary Huffman sequences of a specified length. (English) Zbl 1209.94032
The paper deals with the number \(h(q,n)\) of different \(n\)-ary Huffman sequences of length \(q\). For \(n=2\) the number \(h(q,2)\) has been established in [E. Norwood, IEEE Trans. Inf. Theory 13, 613–616 (1967; Zbl 0183.22005)]. This paper presents the recursive formula for computation of \(h(n,q)\), for each \(n \geq 2\). Moreover, it permits an estimation of \(h(q,n)\) which, for \(n=2\), upscales the result of J. Burkert [Bull. Inst. Comb. Appl. 58, 79–82 (2010; Zbl 1222.11020)].
Reviewer: Jerzy Żurawiecki (Lublin)
MSC:
| 94A45 | Prefix, length-variable, comma-free codes |
| 05A15 | Exact enumeration problems, generating functions |
Online Encyclopedia of Integer Sequences:
Irregular triangle read by rows: T(n,k) = number of Huffman-equivalence classes of ternary trees with 3n+1 leaves and 4k leaves on the bottom level (n>=1, k>=1).References:
| [1] | Burkert, J., Simple bounds on the numbers of binary Huffman sequences, Bull. Inst. Combin. Appl., 58, 79-82 (2010) · Zbl 1222.11020 |
| [2] | Even, S.; Lempel, A., Generation and enumeration of all solutions on the characteristic sum condition, Inform. Control, 21, 476-482 (1972) · Zbl 0248.94020 |
| [3] | Hankerson, D.; Harris, G. A.; Johnson, P. D., Introduction to Information Theory and Data Compression (2003), CRC Press: CRC Press Boca Raton · Zbl 1030.94021 |
| [4] | Hoffman, D.; Johnson, P.; Wilson, N., Generating Huffman sequences, J. Algorithms, 54, 115-121 (2005) · Zbl 1090.68116 |
| [5] | Norwood, E., The number of different possible compact codes, IEEE Trans. Inform. Theory, October, 613-616 (1967) · Zbl 0183.22005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
