Enumerative Sequences of Leaves and Nodes in Rational Trees

We prove that any N-rational sequence s = (s n ) n1 of nonnegative integers satisfying the Kraft strict inequality P n1 s n k \Gamman ! 1 is the enumerative sequence of leaves by height of a rational k-ary tree. We give an efficient algorithm to get a k-ary rational tree. Particular cases of this result had been previously proven. We give some partial results in the case of equality. Especially we study the similar problem of characterizing the enumerative sequences of nodes of k-ary rational trees and solve this question when the sequence has a primitive linear representation. Key words: Information theory, Kraft-McMillan theorem, Rational series, Source coding, State-splitting. 1 Introduction This paper is a study of problems linked with coding and symbolic dynamics. The results can be considered as an extension of the old results of Huffman, Kraft, McMillan and Shannon on source coding. We actually prove results on rational sequences of integers that can be realized as the enu..