Enumeration of Trees With Local Orientation by Degree Sequences and Reachability of Vertices

Abstract

Trees in which edges are oriented from a vertex of lower label towards a vertex of higher label, commonly referred to as locally oriented trees, were introduced by Du and Yin in an attempt to solve a problem conjectured by Ethan Cotterill in his study of secant planes in Algebraic Geometry. Du and Yin, Shin and Zeng, and StephanWagner provided proofs for a formula which counts the number of locally oriented trees with a given indegree sequence. Recent studies have concentrated on finding the number of these trees in which both indegree and outdegree sequences are simultaneously given. In this thesis, formulas for the number of locally oriented trees with one source and given outdegree sequences are obtained. Moreover, reachability questions on vertices of locally oriented trees and locally oriented noncrossing trees (first studied by Okoth) have been extensively answered though equivalent results for locally oriented ordered trees had not been obtained. The purpose of this study was to enumerate trees with local orientation by indegree and outdegree sequences as well as reachability of vertices. The specific objectives were; to establish a closed formula for the number of locally oriented trees whose indegree and outdegree sequences are simultaneously given and, to determine formulas counting the number of reachable vertices in labelled ordered trees with local orientation according to path lengths, first children, non-first children, sinks, leaf sinks, non-leaf sinks and left most paths. To achieve the first objective, we used induction approach as well as construction approach to develop recurrence relations. We then used generating functions to find closed formulas. For the second objective, we used construction approach of Seo and Shin, recurrence relations, generating functions and direct proofs. We have obtained closed formulas for reachable vertices in labelled plane trees with respect to: path lengths, sinks, leaf sinks, left most path, first children, non first children and non leaf sinks. The results obtained in this work will add to the already existing literature in this area of research and will also be of importance to computer scientists as most data in computers are stored in form of plane trees.