Random Walks, Trees and Extensions of Riordan Group Techniques

D issertation A pproval S h e e t ............................................................................
D e d ic a tio n .................................................................................................................
A c k n o w le d g m e n ts ................................................................................................
A b s tr a c t ....................................................................................................................
L ist o f F ig u r e s .......................................................................................................
C hapter 1. In tro d u c tio n ...................................................................................
1.1 Basic Definitions and O ve rvie w ..................................................................
1.1.1 Definitions .............................................................................................
1.1.2 Overview .............................................................................................
1.2 The Catalan Numbers: Some Interpretations and Related Results . .
1.2.1 Combinatorial Interpretations of the Catalan Numbers . . . .
1.2.2 Statistics Related to the Catalan N um bers..................................
1.2.3 Functions Related to C { z ) ...............................................................
1.3 The Ternary numbers and Generalized Dyck P a th s ..............................
1.3.1 Combinatorial Interpretations of the Ternary Numbers . . . .
1.3.2 Generalized i-Dyck paths ...................................................................
viii
ii
iii
iv
vi
x
1
1
1
6
8
8
10
10
12
12
17
1.4 The Riordan G roup ............................................................................................. 17
C hapter 2. Analogues o f Catalan P ro p e rtie s ............................................ 24
2.1 T(z) is to N(z) as C(z) is to B (z ) ................................................................... 24
2.2 The Chung-Feller Theorem for f-Dyck p a th s .............................................. 26
2.3 The Motzkin Analogue ...................................................................................... 29
2.3.1 The Balls on the Lawn P roblem .......................................................... 30
2.3.2 The Euler Transform .............................................................................. 33
2.4 The Fine A nalogue ............................................................................................. 35
C hapter 3. R eturns and A re a .............................. 38
3.1 Expected Number of R e tu rn s ......................................................................... 38
3.1.1 Dyck P a th s ............................................................................................... 39
3.1.2 Ternary P aths ........................................................................................... 39
3.2 Techniques for Finding Area Under Paths ................................................... 43
3.2.1 Dyck P a th s ............................................................................................... 44
3.2.2 Ternary P aths ........................................................................................... 48
C hapter 4. Conclusions and Open Q u e s tio n s ............................................ 53
4.1 Summary and Work to be D o n e ...................................................................... 53
4.2 More Open Questions .......................................................................................... 54
4.2.1 Elements of Pseudo Order 2 ................................................................. 54
4.2.2 Determinant Sequences ........................................................................... 57
4.2.3 Narayana Analogue .................................................................................. 62