Possible database queries for parking functions: search your data / browse all statistics / browse all maps
1. 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 sixteen parking functions size 3 in their orbits under entry permutations |
[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] |
There are $(n+1)^{n-1}$ parking functions of size $n$, see OEIS:A000272.
2. Additional information
2.1. Parking functions and parking cars
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.
2.2. Parking Functions as labelled Dyck Paths
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$.
3. Properties
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].
4. References
[Hag2008] J. Haglund, The q,t-Catalan numbers and the space of diagonal harmonics, University Lecture Series, American Mathematical Society, Providence, RI, (2008).
[Hic2010] A. Hicks, A Parking Function Bijection Suggested by the Haglund-Morse-Zabrocki Conjecture, University of California- San Diego, (2010).
[Sta] R. Stanley, Parking Functions, http://math.mit.edu/~rstan/transparencies/parking.pdf.
5. Sage examples
6. Technical information for database usage
- A parking function is uniquely represented as a list.
- Parking functions are graded by size.
- The database contains all parking functions of size at most 6.