Combinatorics of oriented trees and tree-like structures

Abstract

In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given indegree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of indegree 0) or sinks (vertices of outdegree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these famiii Stellenbosch University https://scholar.sun.ac.za iii Abstract lies and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts colou-red Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions.