An Addendum to Trees

This short Addendum uses trees to calculate a sum that arrises in the analysis of algorithms in exact (i.e., not in O-notation) closed form. The difficulty with this sum is that its terms involve the ceiling function —in something forbidding like \(\lambda x.\lceil \log _{2}x\rceil \) . In the area of discrete mathematics known as graph theory, trees —in particular binary trees— play a central role as special cases of the so-called directed graphs. While trees are studied for their own merit in modelling important data structures in computing practise, they have also unexpected applications to discrete mathematics such as the one we will demonstrate in this chapter. The chapter concludes with an application of generating functions used to compute a simple expression that computes the number of all extended trees that have n internal nodes.