Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis

Heuberger, Clemens ; Krenn, Daniel ; Wagner, Stephan (2015)

CITATION: Heuberger, C., Krenn, D. & Wagner, S. 2015. Canonical trees, compact prefix-free codes, and sums of unit fractions: a probabilistic analysis. SIAM Journal on Discrete Mathematics, 29(3):1600–1653, doi:10.1137/15M1017107.

The original publication is available at http://epubs.siam.org/journal/sjdmec

Article

For fixed t ≥ 2, we consider the class of representations of 1 as a sum of unit fractions whose denominators are powers of t, or equivalently the class of canonical compact t-ary Huffman codes, or equivalently rooted t-ary plane “canonical” trees. We study the probabilistic behavior of the height (limit distribution is shown to be normal), the number of distinct summands (normal distribution), the path length (normal distribution), the width (main term of the expectation and concentration property), and the number of leaves at maximum distance from the root (discrete distribution).

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/99918
This item appears in the following collections: