Lattice path enumeration on restricted domains

Abstract

This thesis concerns the enumeration and structural properties of lattice paths. The study of Dyck paths and their characteristics is a classical combinatorial subject. In particular, it is well-known that many of their characteristics are counted by the Narayana numbers. We begin by presenting an explicit bijection between Dyck paths with two such characteristics, peaks and up-steps at odd height, and extend this bijection to bilateral Dyck paths. We then move on to an enumeration problem in which we utilise the Kernel method, which is a cutting-edge tool in algebraic combinatorics. However, while it has proven extremely useful for nding generating functions when used with one or two catalytic variables, there have been few examples where a Kernel method has been successfully used in a general multivariate setting. Here we provide one such example. We consider walks on a triangular domain that is a subset of the triangular lattice. We then specialise this by dividing the lattice into two directed sublattices with di erent weights. Our central result on this model is an explicit formula for the generating function of walks starting at a xed point in this domain and 5 6 ending anywhere within the domain. We derive this via use of the algebraic Kernel method with three catalytic variables. Intriguingly, the specialisation of this formula to walks starting in a fixed corner of the triangle shows that these are equinumerous to bicoloured Motzkin paths, and bicoloured three-candidate Ballot paths, in a strip of unite height. We complete this thesis by providing bijective proofs for small cases of this result.