A Survey of Parking Functions
History Corner 200 205
Monday, January 27, 2020 2:00 PM
Professor Richard Stanley
A parking function of length n is a sequence a1,a2,. . . , anof positive integers whose increasing rearrangement b1 ≤ b2 ≤ · · · ≤ bnsatisfies bi≤ i. Parking functions go back to Pyke in 1959; the term “parking function” and the connection with the parking of cars is due to Konheim and Weiss (1966).Pollak gave an elegant proof that the number of parking functions of length n is (n + 1)n−1. There are close connections between parking functions and other combinatorial objects such as trees, non-crossing partitions, and the Shi hyperplane arrangement. Parking functions arise in several unexpected algebraic areas, such as representations of the symmetric group and Haiman’s theory of diagonal harmonics. Parking functions also have a number of natural generalizations which fit together in a nice way. We will survey these aspects of the theory of parking functions.