a Parking Function?

Consider a one-way street with $n \in \{1, 2, \ldots \}$ numbered parking spots, denoted $s_1, s_2, \ldots , s_n$. A sequence of $n$ cars enters the street one at a time, each with a preferred spot. Upon its arrival, car $1 \leq i \leq n$, denoted $c_i$, drives to its preferred spot $x_i \in [n] \coloneq \{1, 2, \ldots , n\}$. If spot $x_i$ is unoccupied, car $c_i$ is lucky and parks there. Otherwise, car $c_i$ displaces further down the street until it finds the first unoccupied spot in which to park, if such a spot exists. If no such spot exists, car $c_i$ reneges the search process unable to park. Let $\mathbf{x} = (x_1, x_2, \ldots , x_n) \in [n]^n$ be the $n$-tuple encoding the cars’ parking preferences. If all cars are able to park, then $\mathbf{x}$ is said to be a parking function of length $n$.

Parking functions were first implicitly studied by Pyke Pyk59 in his study of Poisson processes and later on by Konheim and Weiss KW66 in their study of hashing with linear probing. Parking functions can be seen as functions in the sense that the “parking experiment” narrated above assigns, to each $n$-tuple of parking preferences, a single $n$-tuple encoding its parking outcome. If the $n$-tuple of preferences is indeed a parking function, its outcome can be treated as a permutation of $[n]$ written in one-line notation. For example, as depicted in Figure 1, $(1,3,1,1)$ is a parking function of length $4$ with outcome $(1,3,2,4)$.

Figure 1.

The parking function $(1,3,1,1)$ has outcome $(1,3,2,4)$. Cars $c_1$ and $c_2$ are lucky and park in their preferred spots $s_1$ and $s_3$, whereas cars $c_3$ and $c_4$ displace further down the street before ultimately parking in spots $s_2$ and $s_4$, respectively.

Classical enumerative results about parking functions foreshadow their rich mathematical structure. There are

$$\begin{equation} (n+1)^{n-1} {\tag{1}} \end{equation}$$

parking functions of length $n \geq 1$ (OEIS A000272)—this is Cayley’s formula Cay89 for the number of labeled trees on $n + 1$ vertices. This count was established independently by Pyke Pyk59 and Konheim and Weiss KW66, and has been recovered bijectively by numerous authors; refer to Yan Yan15, Section 13.2 and the references therein.

An elegant proof of 1, due to Pollak as credited by Riordan Rio69, is as follows. Consider a circular one-way street with $n + 1$ numbered parking spots, denoted $s_1, s_2, \ldots , s_n, s_{n+1}$. Say, it is a roundabout with no exits and a single entry between spots $s_{n+1}$ and $s_1$. There are $n$ cars attempting to park, so that each $n$-tuple $\mathbf{x} = (x_1, x_2, \ldots , x_n) \in [n+1]^n$ encodes a possibility for the cars’ parking preferences. How many of these $n$-tuples are in fact parking functions of length $n$? Since there are $n+1$ spots but only $n$ cars, there will always be one spot left unoccupied; which exact spot this is depends on the preferences. Note that the preference tuples form a group $G$ under component-wise addition modulo $n + 1$, and consider the subgroup $H \leq G$ generated by the all-ones preference tuple $(1, 1, \ldots , 1)$. As depicted in Figure 2, the cosets $\mathbf{x}H = \{\mathbf{x} + h : h \in H\}$ for $\mathbf{x} \in G$ form equivalence classes of order $n + 1$, each of which contains exactly one parking function, namely whichever tuple leaves spot $n + 1$ unoccupied in its outcome. Therefore, there are $(n+1)^n / (n+1) = (n+1)^{n-1}$ parking functions of length $n$.

Figure 2.

Pollak’s argument for 1 using the example in Figure 1. The tuples $(1,3,1,1)$, $(5,2,5,5)$, $(4,1,4,4)$, $(3,5,3,3)$, and $(2,4,2,2)$ form an equivalence class of order $5$. Their outcomes are depicted as layers overlaying a circular one-way road with spots $s_1, s_2, \ldots , s_5$. The only parking function in this class is $(1,3,1,1)$ because it is the only tuple that leaves spot $s_5$ unoccupied in its outcome, as depicted in the outermost layer of the illustration.

Now, consider an arbitrary $n$-tuple $\mathbf{x} = (x_1, x_2, \ldots , x_n) \in [n]^n$. Can one tell whether it is a parking function of length $n$ without explicitly considering its parking outcome? A classical inequality-based characterization of parking functions allows precisely this. Let $\mathbf{x}' = (x_1', x_2', \ldots , x_n')$ be the weakly increasing rearrangement of $\mathbf{x}$. Then, the following holds:

$$\begin{equation} \text{$\mathbf{x}$ is a parking function of length $n$} \iff \text{$x_i' \leq i$ for all $1 \leq i \leq n$.} {\tag{2}} \end{equation}$$

This characterization can be verified as follows. If there exists some $i$ for which $x_i' > i$, then at least $n - i + 1$ cars attempt to park in the last $n - i$ spots $s_{i + 1}, s_{i + 2}, \ldots , s_n$. This is more cars than spots available, so at least one of these cars will be unable to park. Conversely, if some car is unable to park, then there exists an earliest spot $s_i$ left unoccupied, which can only be the case if $x_i' > i$.

Note that 2 has the following remarkable implication: parking functions are invariant under the action of the symmetric group $\mathfrak{S}_n$, which permutes their subscripts. In particular, the set of parking functions is obtained from the rearrangements of weakly increasing parking functions. For example, $(1,3,1,1)$, $(1,1,3,1)$, $(1,1,1,3)$, and $(3,1,1,1)$ are all parking functions of length $4$, each with a different parking outcome, whereas no rearrangement of $(1,3,3,4)$ can possibly be a parking function of length $4$.

Parking functions are also closely related to the Catalan numbers (OEIS A000108), which are given by the recurrence relation

$$\begin{equation} C_{n} = \sum _{i=1}^{n} C_{i-1} \cdot C_{n - i} {\tag{3}} \end{equation}$$

for $n \geq 1$ with $C_0 = 1$. In particular, the set of weakly increasing parking functions of length $n$ is enumerated by 3. To verify this, suppose you construct a weakly increasing parking function of length $n$, denoted $\mathbf{x}' = (x_1', x_2', \ldots , x_n') \in [n]^n$, with your choice of $1 \leq i \leq n$ for the greatest index satisfying $x_i' = i$. For any such choice of $i$, the $(i-1)$-tuple $(x_1', x_2', \ldots , x_{i-1}')$ must be a parking function of length $i-1$, the $(n-i)$-tuple $(x_{i+1}' - i + 1, x_{i+2}' - i + 1, \ldots , x_n' - i + 1)$ must be a parking function of length $n-i$, and by induction there are $C_{i-1} \cdot C_{n - i}$ possibilities.

As a consequence, weakly increasing parking functions are in bijection with the wide variety of Catalan objects; refer to Stanley Sta15 for a survey. For example, weakly increasing parking functions of length $n$ are in bijection with Dyck paths of length $2n$; these are lattice paths from $(0,0)$ to $(n,n)$ using only north steps $(1,0)$ and east steps $(0,1)$, denoted “N” and “E” respectively, and which do not cross below the main diagonal. Armstrong, Loehr, and Warrington ALW16, Section 2.2 describe the following bijection: given a Dyck path of length $2n$, obtain a weakly increasing parking function $\mathbf{x}' = (x_1', x_2', \ldots , x_n')$ of length $n$ by letting $x_i'$ be one plus the total number of E steps appearing before the $i$th N step for all $1 \leq i \leq n$. Figure 3 illustrates this construction using the weakly increasing parking function $(1,1,1,3)$; the weakly increasing rearrangement of the example in Figure 1.

Figure 3.

The Dyck path $NNNEENEE$ of length $8$, illustrated with bold dashed red lines, maps to the weakly increasing parking function $\mathbf{x}' = (x_1', x_2', x_3', x_4') = (1,1,1,3)$ of length $4$. For example, the fourth $N$ step in the path is the sixth step overall, as illustrated with a solid bold red line. There are a total of two $E$ steps before it, so $x_4' = 1 + 2 = 3$.

Note that if $\mathbf{x}' = (x_1', x_2', \ldots , x_n') \in [n]^n$ is a weakly increasing parking function, then the $i$th car $c_i$ (with preference $x_i'$) parks in the $i$th spot $s_i$. Therefore, the total displacement of a weakly increasing parking function $\mathbf{x}'$ is given by

$$\begin{equation} \sum _{i=1}^n i - x_i' = \frac{n(n+1)}{2} - \sum _{i=1}^n x_i'. {\tag{4}} \end{equation}$$

This statistic has further combinatorial interpretations. For example, the number of full squares between a Dyck path and the main diagonal, which in the case of Figure 3 is $4$, is the same as the total displacement of its corresponding weakly increasing parking function. Lastly, note that the dependency of 4 on $\mathbf{x}'$ reduces to the summation of its terms. This implies that the total displacement of a parking function is also preserved under rearrangements!

Despite first appearing in the literature more than six decades ago, the combinatorics of parking functions remains a vibrant area of research. Recent work ranges from the study of discrete statistics such as displacement KY23EHKMM23 or the number of lucky cars GS04SV24SY23, the introduction of new variants and/or generalizations on the classical “parking experiment” rule (refer to Carlson et al. CCH$^{+}$21 for an accessible tour of endless possibilities in the style of “choose your own adventure”), polyhedral aspects AW22HLVM24, and surprising connections to seemingly unrelated objects AAH$^{+}$23HKMM24, to mention just a few. In recent work, my collaborators and I use a subset of parking functions we call unit Fubini rankings, and in particular their outcome map, to characterize and enumerate the Boolean intervals of rank $k$ in the weak order poset of $\mathfrak{S}_n$ EHKMM24. Figure 4 illustrates our construction.

Figure 4.

Weak order poset of $\mathfrak{S}_6$ with a Boolean interval of rank $3$ highlighted, with minimal element $341625$ and maximal element $436152$ written in one-line notation. The outcome of $(3,5,1,2,6,4)$, a parking function of length $6$, is $(3, 4, 1, 6, 2, 5)$ and corresponds to the minimal element of the interval. The outcome of $(3,5,1,1,5,3)$, another parking function of length $6$, is again $(3, 4, 1, 6, 2, 5)$ and corresponds to the minimal element of the interval. In fact, $(3,5,1,1,5,3)$ is a “unit Fubini ranking with $3$ distinct ranks” and corresponds to a Boolean interval of rank $6-3 = 3$ (i.e., a cube), whereas $(3,5,1,2,6,4)$ is a “unit Fubini ranking with $6$ distinct ranks” and corresponds to a Boolean interval of rank $6 - 6=0$ (i.e., a node). Refer to Elder et al. EHKMM24 for details.