## View/hide extracted text (may have errors)

Analysis of Parameters of Trees Corresponding to Huffman Codes and Sums of Unit Fractions* Clemens Heuberger† Daniel Krenn‡ Stephan Wagner§ Abstract • {1,...,t}* denotes the set of finite words over For fixed t ≥ 2, we consider the class of representations of 1 the alphabet {1,...,t}, as sum of unit fractions whose denominators are powers of t or equivalently the class of canonical compact t-ary Huffman • a code C is said to be prefix-free if no word in codes or equivalently rooted t-ary plane “canonical” trees. C is a proper prefix of any other word in C, We study the probabilistic behaviour of the height (limit distribution is shown to be normal), the number of distinct • a code C is said to be compact if the following summands (normal distribution), the path length (normal property holds: if w is a proper prefix of a distribution), the width (main term of the expectation word in C, then for every letter a ∈ {1,...,t}, and concentration property) and the number of leaves at maximum distance from the root (discrete distribution). wa is a prefix of a word in C, • a code C is said to be canonical if the lexico- 1 Introduction graphic ordering of its words corresponds to a Let t ≥ 2 be an integer. We consider the following non-decreasing ordering of the word lengths. combinatorial classes which turn out to be equivalent. This condition corresponds to taking equiva- See Figure 1 for examples. lence classes with respect to permutations of the alphabet (at each position in the words). 1. Partitions of 1 into powers of t (representation of 1 as sum of unit fractions whose denominators are The external size |C| of a code C is defined to be powers of t): the cardinality of C. n If C ∈ CCode with C = {w1,...,wr} and the CPartition = (x1,...,xr) ∈ Zr r ≥ 0, property that length(wi) ≤ length(wi+1) for all 0 ≤ x1 ≤ x2 ≤ ··· ≤ xr, xi = 1 . preserving the external size. CCode and CPartitionThis is a bijection between1Partitionr1o.∈ C))w(length,...,)w(length, then (itr=1iX The external size |(x1,...,xr)| of such a represen- 3. Canonical rooted t-ary trees: tation (x1,...,xr) is defined to be the number r of summands. CTree = {T rooted t-ary plane tree | T is canonical}. 2. Canonical compact t-ary Huffman codes: Here, CCode = {C ⊆ {1,...,t}* | C is prefix-free, compact and canonical}. • t-ary means that each vertex has no or t children, Here, • plane tree means that an ordering “from left to right” of the children of each vertex is *Supported by the Austrian Science Fund (FWF): S9606, that specified, is part of the Austrian National Research Network “Analytic Combinatorics and Probabilistic Number Theory”, by the Aus- • canonical means that the following holds for trian Science Fund (FWF): W1230, Doctoral Program “Discrete all k: if the vertices of depth (i.e., distance to Mathematics” and by the National Research Foundation of South the root) k are denoted by v1, ..., vK from Africa, grant number 70560. †Institut f¨ur Mathematik, Alpen-Adria-Universit¨at Klagen- i) ≤ deg(vi+1) holdsvleft to right, then deg( for all i. furt, Austria, E-mail address: clemens.heuberger@aau.at. ‡Institut f¨ur Optimierung und Diskrete Mathematik (Math B), The external size |T| of a tree is given by the TU Graz, Austria, E-mail address: krenn@math.tugraz.at. §Department of Mathematical Sciences, Stellenbosch Univer- number of its leaves, i.e., the number of vertices sity, South Africa, E-mail address: swagner@sun.ac.za. of degree 1. 33 Copyright © SIAM. Unauthorized reproduction of this article is prohibited.