TOPICS
Search

Frustrated Parking Function


A frustrated parking function of length n is a sequence (a_1,...,a_n) of preferred spots for n cars arriving in order at n numbered parking spaces. A car takes its preferred space when it is free. Otherwise, it continues down the one-way street to the last, or largest-numbered, unoccupied space, and the sequence is a frustrated parking function if every car can park (Hallam et al. 2026).

Every frustrated parking function is a parking function, but the converse does not hold. Hallam et al. (2026) used height-labeled Dyck paths to prove that the number F_n of frustrated parking functions of length n is

 F_n=(2n-1)!!.

Here !! denotes the double factorial. For n=0, 1, ..., the values are 1, 1, 3, 15, 105, 945, 10395, ... (OEIS A001147). A car is called lucky if it parks in its preferred space, and a space is lucky if it is occupied by a lucky car (Hallam et al. 2026). They also proved that the number of frustrated parking functions whose set of lucky cars equals {1,...,k} is k!S(n,k), and the same count holds for those whose set of lucky spaces equals {1,...,k}, where S(n,k) is a Stirling number of the second kind. The number with exactly k lucky cars or lucky spaces is the corresponding entry of the second-order Eulerian triangle, whose rows begin (1), (1,2), (1,8,6), (1,22,58,24), ... (OEIS A008517). The subclasses in which every car after the first unlucky car is unlucky, or every space after the first unlucky space is unlucky, are each counted by the nth ordered Bell number (also called a Fubini number). For n=0, 1, ..., these numbers are 1, 1, 3, 13, 75, 541, 4683, ... (OEIS A000670).


See also

Dyck Path, Ordered Bell Number, Parking Function

Explore with Wolfram|Alpha

References

Hallam, J.; Molebash, J.; and Porter, C. "Parking with Frustrated Drivers." 28 Sep 2026. https://arxiv.org/abs/2609.35638.Sloane, N. J. A. Sequences A000670, A001147, and A008517 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Frustrated Parking Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FrustratedParkingFunction.html

Subject classifications