A thesis submitted to the Faculty of Science, University of the
Witwatersrand, Johannesburg, in ful lment of the requirements for
the degree of Master of Science.
Johannesburg, 2013. / Our main focus in this research is to compute formulae for the generating function
of lattice paths. We will only concentrate on two types of lattice paths, Dyck
paths and Motzkin paths. We investigate di erent ways to enumerate these paths
according to various parameters. We start o by studying the relationship between
the Catalan numbers Cn, Fine numbers Fn and the Narayana numbers vn;k together
with their corresponding generating functions. It is here where we see how the the
Lagrange Inversion Formula is applied to complex generating functions to simplify
computations. We then study the enumeration of Dyck paths according to the
semilength and parameters such as, number of peaks, height of rst peak, number
of return steps, e.t.c. We also show how some of these Dyck paths are related.
We then make use of Krattenhaler's bijection between 123-avoiding permutations of
length n, denoted by Sn(123), and Dyck paths of semilength n. Using this bijective
relationship over Sn(123) with k descents and Dyck paths of semilength n with
sum of valleys and triple falls equal to k, we get recurrence relationships between
ordinary Dyck paths of semilength n and primitive Dyck paths of the same length.
From these relationships, we get the generating function for Dyck paths according
to semilength, number of valleys and number of triple falls.
We nd di erent forms of the generating function for Motzkin paths according to length and number of plateaus with one horizontal
step, then extend the discussion to the case where we have more than one horizontal
step. We also study Motzkin paths where the horizontal steps have di erent colours,
called the k-coloured Motzkin paths and then the k-coloured Motzkin paths which
don't have any of their horizontal steps lying on the x-axis, called the k-coloured
c-Motzkin paths. We nd that these two types of paths have a special relationship
which can be seen from their generating functions. We use this relationship to
simplify our enumeration problems.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/13017 |
| Date | 07 August 2013 |
| Creators | Mutengwe, Phumudzo Hector |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0116 seconds