Parking function

A parking function of length ${\displaystyle n}$ is a sequence of ${\displaystyle n}$ positive integers, each in the range from 1 to ${\displaystyle n}$, with the property that, for every ${\displaystyle i}$ up to the sequence length, the sequence contains at least ${\displaystyle i}$ values that are at most ${\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 ${\displaystyle i}$ in the same range, the ${\displaystyle i}$th value of the sorted sequence is at most ${\displaystyle i}$.^[1]

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 ${\displaystyle n}$ drivers in cars travel down a one-way street having ${\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.^[1] 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. The first driver parks in space 2, the second in space 1, and the third in space 3 (because space 2 is taken). The fourth driver starts looking for a free space at space 1, but doesn't find it until space 4; all previous spaces were taken. The sequence (3,3,1,3) is not a parking function: too many drivers prefer space 3, so the last driver starts looking for a space after already passing the only free space, and will be unable to park.^[2]

Parking functions also have a more serious application in the study of hash tables based on linear probing, a strategy for placing keys into a hash table that closely resembles the one-way parking strategy for cars.^[3]

The number of parking functions of length ${\displaystyle n}$ is exactly $${\displaystyle (n+1)^{n-1}.}$$ For instance for ${\displaystyle n=3}$ this number is ${\displaystyle 4^{2}=16}$.^[2]

John Riordan credits to Henry O. Pollak the following argument for this formula. On a circular one-way road with ${\displaystyle n+1}$ spaces, each of ${\displaystyle n}$ cars will always be able to park, no matter what preference each driver has for their starting space. There are ${\displaystyle (n+1)^{n}}$ choices for the preferences, each of which leaves one vacant space. All spaces are symmetric to each other, so by symmetry, there are ${\displaystyle (n+1)^{n-1}}$ choices for preferences that leave space ${\displaystyle n+1}$ as the vacant space. These choices are exactly the parking functions. The parking functions can also be placed in bijection with the spanning trees on a complete graph with ${\displaystyle n+1}$ vertices, one of which is designated as the root. This bijection, together with Cayley's formula for the number of spanning trees, again shows that there are ${\displaystyle (n+1)^{n-1}}$ parking functions.^[2]

Much research has studied the number of parking functions of a special form. As a very simple special case, the parking functions that allow each car to park in its own preferred spot are exactly the permutations, counted by the factorials. The parking functions that allow each car to park either in its preferred spot or in the next spot are counted by the ordered Bell numbers.^[4]