Enumerative Sequences of Leaves in Rational Trees

. We prove that any IN-rational sequence s = (sn)n1 of nonnegative integers satisfying the Kraft strict inequality P n1 snk \Gamman ! 1 is the enumerative sequence of leaves by height of a rational k-ary tree. Particular cases of this result had been previously proven. We give some partial results in the equality case. 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 enumerative sequence of leaves in a rational tree. Let s be an IN-rational sequence of nonnegative numbers, that is a sequence s = (s n ) n1 such that s n is the number of paths of length n going from an initial state to a final state in a finite multigraph or a finite automaton. We say that s satisfies the Kraft inequality for a positive integer k if P n1 s n k ..