### 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.