Dyck Paths and Random Trees

honors thesisCollege of ScienceMathematicsTom AlbertsWe give an expository survey of random trees, focusing on the interplay between plane trees and Dyck paths. The material explained here summarizes what can be found in Aldous [1], Le Gall [10], and Drmota [6]. The bijection between plane trees and Dyck paths serves as motivation for the connection between limits of plane trees and Dyck paths. Using the bijection, we explore some combinatorial aspects of Dyck paths and plane trees. We then explore limits of Dyck paths. By placing uniform probability measure on the Dyck paths and scaling appropriately, we see that Dyck paths, in a sense, weakly converge to Brownian excursion. Spurred on by the bijection between plane trees and Dyck paths, we attempt to conceptualize the limit of plane trees. After developing some necessary definitions to make sense of plane tree convergence, this leads us to the weak limit of appropriately scaled plane trees, the continuum random tree