Enumerations and bijections of Dyck paths
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A Dyck path is a non-negative lattice path with the steps u = (1, 1) and d = (1, −1) such that the path starts at the origin and ends on the x-axis. In this research we consider some bijections that Dyck paths have with certain Catalan objects: bargraphs, d-ary trees, Motzkin paths and other Dyck paths. We apply the bijections to derive relationships that arise between the statistics of the Dyck paths and the Catalan objects, and subsequently show the enumerations of Dyck paths with regard to these statistics. The statistics that we consider include: the semiperimeter minus the number of peaks of the corresponding bargraph, the semilength and size k of the downward step d = (1, −k) of the k-Dyck path, the semilength, the size k of the downward step d = (1, −k) and the lower bound y = −t of the kt-Dyck path, the number of hills, odd rises, even rises, returns and semilength of the Dyck path, and lastly the number of centred, left and right tunnels, centred multitunnels and semilength of the Dyck path. Finally, we apply several techniques of the symbolic method to derive the enumeration of cornerless Motzkin paths, bargraphs and kt-Dyck paths.
Description
A research report submitted in fulfilment of the requirements for the degree of Master of Science to the Faculty of Science, School of Mathematics, University of the Witwatersrand, Johannesburg, 2023
Keywords
Dyck path, Catalan