Parking function

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

A parking function of length

positive integers, each in the range from 1 to

[1] For instance, there are 16 parking functions of length three: The name is explained by the following thought experiment.

drivers in cars travel down a one-way street having

Each driver travels until reaching their preferred space, and then parks in the first available spot.

[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 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

[2] John Riordan credits to Henry O. Pollak the following argument for this formula.

cars will always be able to park, no matter what preference each driver has for their starting space.

choices for the preferences, each of which leaves one vacant space.

choices for preferences that leave 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

This bijection, together with Cayley's formula for the number of spanning trees, again shows that there are

[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.