INFORMATION TO USERS This manuscript has been reproduced from the microfilm master. UMI films the text directly from the original or copy submitted. Thus, some thesis and dissertation copies are in typewriter face, while others may be from any type of computer printer. The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleedthrough, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send UMI a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. Oversize materials (e.g., maps, drawings, charts) are reproduced by sectioning the original, beginning at the upper left-hand corner and continuing from left to right in equal sections with small overlaps. ProQuest Information and Learning 300 North Zeeb Road, Ann Arbor, Ml 48106-1346 USA 800-521-0600 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. HOW ARD UN IVER SITY Random Walks, Trees and Extensions of Riordan Group Techniques A Dissertation Submitted to the Faculty of the Graduate School of HOW ARD U N IVER SITY in partial fulfillment of the requirements for the degree DOCTOR OF PHILOSOPHY Department of Mathematics by Naiom i Tuere Cameron Washington, D.C. May 2002 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. UMI Number: 3066485 UMI UMI Microform 3066485 Copyright 2003 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.O. Box 1346 Ann Arbor, Ml 48106-1346 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. HOW ARD UN IVER SITY GRADUATE SCHOOL DEPARTM ENT OF M ATHEM ATICS DISSERTATION COMMITTEE Neil Hindman, Ph.D. Chairperson Paul Peart, Ph.D. Tjmoi %{ j^xLpiy-u^ Louis W. Shapiro, Ph.D. Wen-Jin Woan, Ph.D. ^ohWoodson, Ph.D Associate Professor of Mathematics Morgan State University Louis W. Shapiro, Ph.D. Dissertation Advisor Candidate: Naiomi Tuere Cameron Date of Defense: January 17, 2002 ii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Dedication Dedicated to my beloved brother, Jarrell Ali Cameron (December 5, 1977 - September 14, 2001) You will live forever in my heart. iii Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Acknowledgments While it is not possible to name every person who supported me during my graduate studies, I would like to expressly thank those individuals whose support proved critical to the achievement of my goals. First and foremost, I thank my Lord and Saviour, Jesus Christ, through whom all things are possible. I would like to express my most sincerest appreciation to my beloved family, Jason, Kariyma and Omar, for their unconditional love and support throughout this chapter of our life. I could not have done this without their support. I also want to thank my Mom, my Dad, my sister Njeri and my brother Jawanza for their consistent love and understanding. I must also thank my mother-in-law Patricia Murphy for her constant encouragement. My advisor, Louis Shapiro, deserves the credit for raising many of the questions addressed in this research, and I would like to thank him for his care and guidance throughout this project. I must also thank the members of my committee and the Combinatorics Seminar, Paul Peart, Wen-Jin Woan, Seyoum Getu, Leon Woodson, Neil Hindman and Emeric Deutsch, for their invaluable input. In addition, the members of the Mathematics Department at Howard University have provided im­ mense support and encouragement. In particular, I would like to mention Adeniran Adeboye, Richard Bourgin, Francois Ramaroson, the graduate student body and the administrative support staff. I must extend a special thanks to Cora Sadosky for her support and mentorship to me as a mathematician and as a woman. iv Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. There are many extended family members and friends whose support of me and my family have been crucial to the completion of my dissertation. They include Lisa and Rick Square, Karen McFadden, Carla Jones-Chew, Sherry Scott, Latifa Barnett, Deangela Hill, Rena Stevens, Tiandra Speaks, Kim Cameron-Dominguez and all of my other family members, both big and small. I am especially grateful to two young women mathematicians whose friendship I treasure: Jillian McLeod and Lynnell Matthews. Jillian, your friendship has made my life better. Thank you for your consistent care and attention to me. Lynnell, this dissertation is not complete without yours. Thank you for the many days when you provided an ear for mathematics and the countless times when you provided an ear for a friend. v Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. Abstract The Catalan number sequence 1,1,2,5,14,42,. n + l \ nJ is one of the most important sequences in all of enumerative combinatorics. Richard Stanley cites at least 66 combinatorial settings where the sequence appears [7]. Among the numerous interpretations of the Catalan numbers, we have the number of paths restricted to the first quadrant of the x1 y-plane starting a.t (0, 0) and ending at (2n,0) using “up” steps (1,1) or “down” steps (1,-1) (known as Dyck paths). This research will focus on a generalization of the Catalan numbers which can be interpreted as taking Dyck paths and perturbing the length of the down step. One particular example of this generalization is given by the sequence of numbers known as the ternary numbers, 1,1,3,12,55,273,1428,7752,43263,..., — ( in) ,.... 2n + 1 \ n J This sequence arises in many natural contexts and extensions of known results re­ lated to combinatorial objects such as paths, trees, permutations, partitions, Young tableaux and dissections of convex polygons. Hence, we use this sequence as an important example of something which lies on the boundary of what is known and what is new. Much of this research is an attempt to extend many of the known results for the Catalan numbers to ternary and m-ary numbers. vi Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. In this dissertation, we establish, in the setting of the ternary numbers, several analogues to the better known Catalan numbers setting. We present an analogue to the Chung-Feller Theorem which says that for paths from (0,0) to (3n, 0) with step set {(1,1), (1, —2)}, the number of up (1,1) steps above the rr-axis is uniformly distributed. We also present analogues to the Binomial, Motzkin and Fine gener­ ating functions and discuss combinatorial interpretations of each. In addition, we establish some computational results regarding the area bounded by ternary paths and the number of returns to the ar-axis. We also present generating function proofs for the area under Dyck and ternary paths, an interesting connection to weighted trees, and a conjecture for a closed form generating function for the area under ternary paths. vn Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.