A New Approach to Naples Parking Functions Through Complete Parking Preferences, and its Enumerative Consequences

Abstract

Naples parking functions were introduced as a generalization of classical parking functions, in which cars are allowed to park backwards, by checking up to a fixed number of previous spots, before proceeding forward as usual.   In this work we introduce the notion of a complete parking preference, through which we are able to give some information on the combinatorics of Naples parking functions. Roughly speaking, a complete parking preference is a parking preference such that, for any index $j$, there are more cars with preference at least $j$ than spots available from $j$ onward. We provide a characterization of Naples parking functions in terms of certain complete subsequences of them. As a consequence of this result we derive a characterization of permutation-invariant Naples parking functions which turns out to be equivalent to the one given by (Carvalho et al., 2021), but using a totally different approach (and language).   Concerning enumeration, we propose an effective approach to enumerate permutation-invariant Naples parking functions and complete Naples parking functions which is based on some natural combinatorial decompositions. We thus obtain formulas depending on some (generally simpler) quantities, which are of interest in their own right, and that can be described in a recursive fashion.