Parking function

Parking functions are a generalization of permutations studied in combinatorics, a branch of mathematics.

Definition and applications

A parking function of length

n

{\displaystyle n}

is a sequence of

n

{\displaystyle n}

positive integers, each in the range from 1 to

n

{\displaystyle n}

, with the property that, for every

i

{\displaystyle i}

up to the sequence length, the sequence contains at least

i

{\displaystyle i}

values that are at most

i

{\displaystyle i}

. That is, it must contain at least one 1, at least two values that are 1 or 2, at least three values that are 1, 2, or 3, etc. Equivalently, if the sequence is sorted, then for each

i

{\displaystyle i}

in the same range, the

i

{\displaystyle i}

th value of the sorted sequence is at most

i

{\displaystyle i}

.

For instance, there are 16 parking functions of length three:

(1,2,3), (2,3,1), (3,1,2),

(3,2,1), (2,1,3), (1,3,2),

(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,1,1).

The name is explained by the following thought experiment. A sequence of

n

{\displaystyle n}

drivers in cars travel down a one-way street having

n

{\displaystyle n}

parking spaces, with each driver having a preferred parking space. Each driver travels until reaching their preferred space, and then parks in the first available spot. A parking function describes preferences for which all cars can park. For instance, the parking function (2,1,2,1) describes preferences for which the first and third drivers both prefer the second space, while the other two drivers both prefer the first space.