Combinatorial Theory

A parking function is a sequence \((\pi_1,\dots, \pi_n)\) of positive integers such that if \(\lambda_1\leq\cdots\leq \lambda_n\) is the increasing rearrangement of \(\pi_1,\dots,\pi_n\), then \(\lambda_i\leq i\) for \(1\leq i\leq n\). In this paper we obtain some new results on the enumeration of parking functions. We will consider the joint distribution of several sets of statistics on parking functions. The distribution of most of these individual statistics is known, but the joint distributions are new. Parking functions of length \(n\) are in bijection with labelled forests on the vertex set \([n]=\{1,2,\dots,n\}\) (or rooted trees on \([n]_0=\{0,1,\dots,n\}\) with root \(0\)), so our results can also be applied to labelled forests. Extensions of our techniques are discussed, including an extension to a probabilistic scenario.

Mathematics Subject Classifications: 05A15, 60C05, 05A19

Keywords: Parking function, labelled forest, generating function, recurrence, Pollak's circle argument