Parking Functions And Generalized Catalan Numbers

Abstract

Since their introduction by Konheim and Weiss, parking functions have evolved into objects of surprising combinatorial complexity for their simple definitions. First, we introduce these structures, give a brief history of their development and give a few basic theorems about their structure. Then we examine the internal structures of parking functions, focusing on the distribution of descents and inversions in parking functions. We develop a generalization to the Catalan numbers in order to count subsets of the parking functions. Later, we introduce a generalization to parking functions in the form of k-blocked parking functions, and examine their internal structure. Finally, we expand on the extension to the Catalan numbers, exhibiting examples to explore its internal structure. These results continue the exploration of the deep structures of parking functions and their relationship to other combinatorial objects.