Fixed points and cycles of parking functions

Abstract

A parking function of length n is a sequence π=(π1,…,πn) of positive integers such that if λ1≤⋯≤λn is the increasing rearrangement of π1,…,πn, then λi≤i for 1≤i≤n. The index i is a fixed point of the parking function π if πi=i. More generally, for m≥1, the indices (i1,…,im) where the ij's are all distinct constitute an m-cycle of the parking function π if πi1=i2,πi2=i3,…,πim−1=im,πim=i1. In this paper we obtain some exact results on the number of fixed points and cycles of parking functions. Our derivations are based on generalizations of Pollak's argument and the symmetry of parking coordinates. Extensions of our techniques are discussed.