parkingfunction

Parking functions are combinatorial objects that arise in the study of hashing, tree enumeration, and the theory of non‑crossing partitions. A parking function of length n is a sequence (a₁, a₂, …, aₙ) of non‑negative integers whose non‑decreasing rearrangement b₁ ≤ b₂ ≤ … ≤ bₙ satisfies b_i < i for each i = 1,…,n. Equivalently, one may view the sequence as preferences of n cars arriving sequentially at a one‑way street with n parking spots; each car attempts to park in its preferred spot and, if that spot is occupied, proceeds forward to the next vacant spot. The sequence is a parking function precisely when every car succeeds in finding a spot.

The number of parking functions of length n is (n + 1)^{\,n‑1}, a formula first proved by Konheim and Weiss (1966) in the context of hash‑table analysis. This enumeration links parking functions to labelled trees via the Prüfer code, since both sets have the same cardinality. Various bijections connect parking functions to rooted forests, non‑crossing partitions, and the regions of the Shi hyperplane arrangement.

Generalizations include parking functions with a given “capacity” vector, rational parking functions associated with coprime integers (a,b), and higher‑dimensional parking functions. In algebraic combinatorics, parking functions index bases of the space of diagonal harmonics and appear in the representation theory of the symmetric group. Recent work extends the concept to parking functions on graphs, where vertices represent parking spots and edges determine admissible moves.

Parking functions thus serve as a unifying theme linking discrete algorithms, combinatorial enumeration, and algebraic structures. Their simple definition belies a rich combinatorial landscape that continues to inspire research across mathematics and theoretical computer science.