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

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

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