Queries for Parking functions: search statistic / browse statistics / browse maps from / browse maps to

# 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 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]
• There are $(n+1)^{n-1}$ parking functions of size $n$, see OEIS:A000272.

## 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

[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, (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.

# 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.