TOPICS
Search

Bilateral Parking Procedure


A bilateral parking procedure is a rule for parking cars at spaces indexed by all integers in which a car takes its preferred space if it is free and otherwise takes either the nearest free space to its left or the nearest free space to its right (Nadeau 2026, p. 6). A preference word of length r is successful when the resulting occupied spaces are exactly {1,...,r}.

The procedure is local when it is invariant under translating all preferences by the same integer, and the choice at an occupied preferred space depends only on the preference subword of the cars that parked in the contiguous occupied block containing that space. This subword retains the arrival order and the original preferences of those cars, so a local rule need not depend only on the current occupied set (Nadeau 2026, p. 7).

For every local bilateral parking procedure, the number of successful preference words of length r>=1 is

 (r+1)^(r-1).

Thus the classical parking function count holds throughout this class (Nadeau 2026, p. 2).

Examples include always parking to the right, choosing the closer of the two nearest free spaces with ties resolved to the right, and parking to the left precisely when the occupied block size is a prime number. For the closer-space rule, the preferences (2,2,2) occupy spaces 2, 3, and 1, respectively. The bounded backward-search rule for a Naples parking function is a different generalization and does not satisfy the translation-invariance condition (Nadeau 2026, pp. 6-7).


See also

Naples Parking Function, Parking Function

Explore with Wolfram|Alpha

References

Konheim, A. G. and Weiss, B. "An Occupancy Discipline and Applications." SIAM J. Appl. Math. 14, 1266-1274, 1966. https://doi.org/10.1137/0114101.Nadeau, P. "Bilateral Parking Procedures." Elec. J. Combin. 33, P4.15, 2026. https://doi.org/10.37236/15244.

Cite this as:

Weisstein, Eric W. "Bilateral Parking Procedure." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BilateralParkingProcedure.html

Subject classifications