TOPICS
Search

Naples Parking Function


A Naples parking function with backward allowance k, or k-Naples parking function, is a sequence (a_1,...,a_n) of preferences in {1,...,n} for which all cars park under the following modification of the parking function rule. If space a_i is occupied, car i checks spaces a_i-1, a_i-2, ..., down to max(1,a_i-k) in that order. It takes the first free space, or, if these spaces are occupied, searches forward from a_i (Christensen et al. 2020).

The case k=0 gives ordinary parking functions. For k>=n-1, all n^n preference sequences succeed. Unlike ordinary parking functions, success can depend on the order of the preferences. For k=1, (3,3,2) succeeds, while (2,3,3) fails.

Ferrari and Verciani (2026, Corollary 15) give a criterion for every rearrangement to succeed. Define

 U={j:2<=j<=n, |{i:a_i>=j}|>n-j+1}.

For k>=1, every rearrangement is a k-Naples parking function iff each maximal interval of consecutive integers in U contains at most k integers. For example, the preferences (3,3,2) give U={2,3}, so they are not invariant under rearrangement for k=1, but are for k=2.

For n>=2, Ferrari and Verciani (2026) call preferences complete when U={2,...,n}. Thus every threshold from 2 through n has more preferences at or above it than spaces at or above it.


See also

Parking Function, Permutation

Explore with Wolfram|Alpha

References

Christensen, A.; Harris, P. E.; Jones, Z.; Loving, M.; Ramos Rodríguez, A.; Rennie, J.; and Rojas Kirby, G. "A Generalization of Parking Functions Allowing Backward Movement." Electron. J. Combin. 27, P1.33, 2020. https://doi.org/10.37236/8948.Ferrari, L. and Verciani, F. "A New Approach to Naples Parking Functions Through Complete Parking Preferences, and Its Enumerative Consequences." Electron. J. Combin. 33, P3.54, 2026. https://doi.org/10.37236/14080.

Cite this as:

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

Subject classifications