A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Master of Science. Johannesburg, 2014. / This dissertation consists of ve chapters which deal with lattice paths such as
Dyck paths, skew Dyck paths and generalized Motzkin paths. They never go below the horizontal axis. We derive the
generating functions to enumerate lattice paths according to di erent parameters.
These parameters include strings of length 2, 3, 4 and r for all r 2 f2; 3; 4; g,
area and semi-base, area and semi-length, and semi-base and semi-perimeter. The
coe cients in the series expansion of these generating functions give us the number
of combinatorial objects we are interested to count. In particular
1. Chapter 1 is an introduction, here we derive some tools that we are going to
use in the subsequent Chapters. We rst state the Lagrange inversion formula which
is a remarkable tool widely use to extract coe cients in generating functions, then
we derive some generating functions for Dyck paths, skew Dyck paths and Motzkin
paths.
2. In Chapter 2 we use generating functions to count the number of occurrences
of strings in a Dyck path. We rst derive generating functions for strings of length 2,
3, 4 and r for all r 2 f2; 3; 4; g, we then extract the coe cients in the generating
functions to get the number of occurrences of strings in the Dyck paths of semi-length
n.
3. In Chapter 3, Sections 3.1 and 3.2 we derive generating functions for the
relationship between strings of lengths 2 and 3 and the relationship between strings
of lengths 3 and 4 respectively. In Section 3.3 we derive generating functions for the
low occurrences of the strings of lengths 2, 3 and 4 and lastly Section 3.4 deals with
derivations of generating functions for the high occurrences of some strings .
4. Chapter 4, Subsection 4.1.1 deals with the derivation of the generating functions
for skew paths according to semi-base and area, we then derive the generating
functions according to area. In Subsection 4.1.2, we consider the same as in Section
4.1.1, but here instead of semi-base we use semi-length. The last section 4.2, we
use skew paths to enumerate the number of super-diagonal bar graphs according to
perimeter.
5. Chapter 5 deals with the derivation of recurrences for the moments of generalized
Motzkin paths, in particular we consider those Motzkin paths that never
touch the x-axis except at (0,0) and at the end of the path.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/15328 |
| Date | 01 September 2014 |
| Creators | Ncambalala, Thokozani Paxwell |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0024 seconds