parking function

Tags: #definition

parking function

Suppose you have

$n$ cars with $n$ parking spots on a one-way road.
Each driver's favorite spot is encoded by $f : [n] \to [n]$ , mapping the $i$ th driver to their favorite spot.
Drivers will arrive one by one by their index (so driver 1 arrives first) and drives straight to their favorite spot.
- If that spot is taken, they drive forwards until they see an empty spot and park there. If they do not find one, they drive away.

We say that $f$ is a parking function if under this arrangement, all drivers end up parked in a spot.

Properties

The following are equivalent:
- $f$ is a parking function
- $# {i ∣ f_{i} \geq n - k + 1} \leq k$ for all $k$
- there exists a permutation $w \in S_{n}$ such that $f_{i} \leq w_{i}$ for all $i$
The number of parking functions for $n$ is $(n + 1)^{n - 1}$ (proof)