<>
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.
<>
- There are $(n+1)^{n-1}$ parking functions of size $n$, see [OEIS:A000272](http://oeis.org/A000272).
Additional information
======================
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.
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](/DyckPaths) 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$.
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$ [](http://math.mit.edu/~rstan/transparencies/parking.pdf)<>.
- Parking functions play an important role in the theory of symmetric functions, see <>, <>, [](http://arxiv.org/pdf/1508.06239v1.pdf)<>.
References
==========
<>
Sage examples
=============
{{{#!sagecell
for n in [2,3,4]:
PFs = ParkingFunctions(n)
print n, PFs.cardinality()
for PF in ParkingFunctions(3):
print PF
}}}
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.