A parking function of length 
is a sequence 
of integers between
1 and 
whose nondecreasing rearrangement 
satisfies
 |
It describes preferences for 
cars arriving in order at 
numbered parking spaces. Each car takes its preferred space
if free, or the next free space with a larger number. The sequence
is a parking function iff every car parks (Konheim and Weiss
1966).
For example, 
is a parking function, with cars occupying spaces 2, 1, and 3. The sequence 
is not. The rearrangement criterion
shows that permuting the cars' preferences preserves the parking-function property.
There are 
parking functions of length 
. One proof uses 
spaces arranged in a circle.
Every preference sequence then leaves one space empty,
and rotational symmetry makes each space equally likely to be empty. Cutting the
circle at the empty space gives the linear parking rule.
The number of nondecreasing parking functions is the Catalan
number 
.
The Naples parking function generalizes the rule by allowing a bounded backward search.
