Helmut Prodinger

The protection number of a plane tree is the minimal distance of the root to a leaf; this definition carries over to an arbitrary node in a plane tree by considering the maximal subtree having this node as a root. We study the the protection number of a uniformly chosen random tree of size n and also the protection number of a uniformly chosen node in a uniformly chosen random tree of size n. The method is to apply singularity analysis to appropriate generating functions. Additional results are provided as well.

The number of “nonequivalent” compact Huffman codes of length r over an alphabet of size t has been studied frequently. Equivalently, the number of “nonequivalent” complete t-ary trees has been examined. We first survey the literature, unifying several independent approaches to the problem. Then, improving on earlier work, we prove a very precise asymptotic result on the counting function, consisting of two main terms and an error term.

We give another short and simple proof of

We present enumeration results for d-ary trees whose vertices are coloured by k colours in a specific way. Besides generating functions proofs of these results we also give direct bijections between these coloured trees and uncoloured d-ary trees.