Definition & Example

A Parking Function of size $n$ is a sequence $(a_1,\dots,a_n)$ of positive integers such that its weakly increasing rearrangement $a'_1 \leq a'_2 \leq \dots \leq a'_n$ satisfies $a'_i \leq i$. In particular, any permutation of a parking function is a again parking function.

the 16 Parking functions of size 3

[1,1,1] [1,1,2] [1,2,1] [2,1,1] [1,1,3] [1,3,1] [3,1,1] [1,2,2]

[2,1,2] [2,2,1] [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

Additional information

Imagine there is a parking lot with $n$ consecutive spots labelled from $1$ to $n$. There are also $n$ cars and car $i$ would prefer to park in spot $a_i$. Then the sequence $(a_1,\ldots,a_n)$ is a parking function if and only if every car can park as follows: aach car first drives up to its preferred parking spot to park. If that spot is taken, the car continues on to the next available spot; the cars are not allowed to reverse back to an open spot. If there are not any open parking spots after their preferred spot, they cannot park.

Parking functions are in bijection with labelled Dyck paths as follows. A labelled Dyck path of semi-length $n$ is a Dyck path of semi-length $n$ with up-steps being labelled by the numbers $1,\ldots,n$ such that the labels of consecutive up-steps are increasing. Let $(a_1,\ldots,a_n)$ be a parking function and let $u_i$ count the number of occurrences of $i$. First, let $D$ be the Dyck path with $u_i$ up-steps after the $(i-1)$-st down-step (the parking property ensures that this indeed encodes a Dyck path). Second, label the $u_i$ up-steps after the $(i-1)$-st down-step by the positions of the letter $i$ inside $(a_1,\ldots,a_n)$.
This shows in particular that non-decreasing parking functions of length $n$ are in bijection with Dyck paths of semilength $n$.

There is a bijection between maximal chains of non-crossing set partitions of $\{1,2,\ldots,n+1\}$ and parking functions of length $n$ [Sta].
Parking functions play an important role in the theory of symmetric functions, see [Hag2008], [Hic2010], [CM2015].

[CM2015] E. Carlsson and A. Mellit, A Proof of the Shuffle Conjecture, http://arxiv.org/pdf/1508.06239v1.pdf
[Hag2008] J. Haglund, The q,t-Catalan numbers and the space of diagonal harmonics, University Lecture Series, American Mathematical Society, Providence, RI
[Hic2010] A. Hicks, A Parking Function Bijection Suggested by the Haglund-Morse-Zabrocki Conjecture, University of California- San Diego
[Sta] R. Stanley, Parking Functions, http://math.mit.edu/~rstan/transparencies/parking.pdf

If you want to edit this wiki page, you can download the raw markdown and send your new version to info@findstat.org