Pullback parking functions
Jennifer Elder*, Pamela E. Harris, Lybitina Koene, Ilana Lavene · 2025
Read Pullback parking functions by Jennifer Elder*, Pamela E. Harris, Lybitina Koene, Ilana Lavene (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17256.txt.
Introduction
Elder and co-authors introduce in 2025 pullback parking functions, a generalization of classic parking functions. Cars face limits on moving backward and forward, set by two parameters. There are n spots on a one way street and m cars trying to park.
Each car drives to its preferred spot and parks if it is free. Else it checks up to k spots behind, then returns and checks up to l spots ahead. If it fails, parking stops. Counting these functions by final parking order gives one formula, and a recursive formula gives another. Special cases recover counts for Naples parking functions, old and new.
Catalog record
| CREATOR | Jennifer Elder*, Pamela E. Harris, Lybitina Koene, Ilana Lavene |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17256
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pullback parking functions Jennifer Elder*, Pamela E. Harris, Lybitina Koene, Ilana Lavene Abstract We introduce a generalization of parking functions in which cars are limited in their movement backwards and forwards by two nonnegative integer parameters k k and ℓ \ell , respectively. In this setting, there are n n spots on a one-way street and m m cars attempting to park in those spots, and 1 ≤ m ≤ n 1\leq m\leq n . We let α = ( a 1 , a 2 , … , a m ) ∈ [ n ] m \alpha=(a_{1},a_{2},\ldots,a_{m})\in[n]^{m} denote the parking preferences for the cars, which enter the street sequentially. Car i i drives to their preference a i a_{i} and parks there if the spot is available. Otherwise, car i i checks up to k k spots behind their preference, parking in the first available spot it encounters if any. If no spots are available, or the car reaches the start of the street, then the car returns to its preference and attempts to park in the first spot it encounters among spots a i + 1 , a i + 2 , … , a i + ℓ a_{i}+1,a_{i}+2,\ldots,a_{i}+\ell . If car i i fails to park, then parking ceases. If all cars are able to park given the preferences in α \alpha , then α \alpha is called a ( k , ℓ ) (k,\ell) -pullback ( m , n ) (m,n) -parking function. Our main result establishes counts for these parking functions in two ways: counting them based on their final parking outcome (the order in which the cars park on the street), and via a recursive formula. Specializing ℓ = n − 1 \ell=n-1 , our result gives a new formula for the number of k k -Naples ( m , n ) (m,n) -parking functions and further specializing m = n m=n recovers a formula for the number of k k -Naples parking functions given by Christensen et al. The specialization of k = ℓ = 1 k=\ell=1 , gives a formula for the number of vacillating ( m , n ) (m,n) -parking functions, a generalization of vacillating parking functions studied by Fang et al., and the m = n m=n result answers a problem posed by the authors. We conclude with a few directions for further study. American Journal of Combinatorics Research Article Volume 4 (2025), Pages 1–22 † † footnotetext: * Corresponding author MSC2020: 05A05, 05A10; Keywords: Parking function, Interval parking function, k -Naples parking function, (m,n) -parking function, Pullback parking function Received Oct 23, 2024; Revised Feb 19, 2025; Accepted Feb 21, 2025; Published Feb 24, 2025 © The author(s). Released under the CC BY 4.0 International License 1 Introduction Consider the following parking scenario. There are m cars attempting to park on a one-way street with n parking spots (with n\geq m ). The queue of cars has a list of parking spot preferences represented by a tuple, \alpha=(a_{1},a_{2},\ldots,a_{m}) , where each a_{i}\in[n]=\{1,2,\ldots,n\} . The cars enter the street in sequential order from car 1 to car m , and firstly will attempt to park in their preference. If that space is unoccupied, then the car parks there. Otherwise, the car proceeds forward and parks in the first available spot it encounters (if there is any). We refer to this parking process as the classical parking rule . If the list of parking preferences allows all cars to park among the n spots on the street, then we call the list of preferences an (m,n) -parking function . For example, when n=m=4 , the preference list (1,4,3,2) allows all of the cars to park as they each prefer a different parking spot. However, when m=3 and n=4 , the preference list (1,4,4) is not a parking function as the third car finds the fourth spot occupied by the second car, and drives forward to the end of the street, unable to park. Throughout, we let \mathrm{PF}_{m,n} denote the set of parking functions with m cars and n spots, and when the number of cars and spots is clear from context, we simply refer to this set as the set of parking functions. Of course, if m>n , then, no matter what the cars’ preferences are, there will always be a car that fails to park. Hence, whenever m>n , |\mathrm{PF}_{m,n}|=0 . In the case where m\leq n , Konheim and Weiss [ 11 ] established that |\mathrm{PF}_{m,n}|=(n+1-m)(n+1)^{m-1} . In particular, if n=m , we let \mathrm{PF}_{n}=\mathrm{PF}_{n,n} , and note that the cardinality of this set of parking functions simplifies nicely to |\mathrm{PF}_{n}|=(n+1)^{n-1} . There are many generalizations of parking functions and most important to our study are k -Naples parking functions and \ell -interval parking functions. Introduced by Baumgardner [ 3 ] , and generalized by Christensen, Harris, Jones, Loving, Ramos Rodríguez, Rennie, and Rojas Kirby [ 5 ] , the set of k -Naples parking functions sets m=n and extends the classical parking rule by allowing a car that finds its preferred parking spot occupied to first back up to k spaces, checking one spot at a time, for 0\leq k<n , in its attempt to park. If possible, the car parks in the first available spot among those k spots. If none of the k spaces before its preferred parking spot are available (or the car reaches the start of the street), then the car continues past its preferred spot and parks in the first available spot beyond it. We call this parking rule the k -Naples parking rule . If the parking preference \alpha allows all cars to park using the k -Naples parking rule, then we say that \alpha is a k -Naples parking function of length n . We let \mathrm{PF}_{n}(k) denote the set of k -Naples parking functions of length n . If k=0 , then \mathrm{PF}_{n}(0)=\mathrm{PF}_{n} . Also, when k=1 , the set \mathrm{PF}_{n}(1) is called the set of Naples parking functions of length n . Based on these definitions one can observe that \mathrm{PF}_{n}(k-1)\subseteq\mathrm{PF}_{n}(k) for all 0<k<n . The set inclusion occurs because every car that can park when allowed to back up k-1 spots can also park when allowed to back up k spots. Christensen et al. established a recursive formula for the number of k -Naples parking functions [ 5 , Theorem 1.1] . In our work, we extend the definition of k -Naples parking functions to the case where there are more parking spaces than cars, and we refer to this set as the set of k -Naples (m,n) -parking functions. We denote this set by \mathrm{PF}_{m,n}(k) . In Corollary 3.15 , we give a recursion for the number of k -Naples (m,n) -parking functions for all m\leq n and 0\leq k<n . Another generalization of classical parking functions called \ell -interval (m,n) -parking func-tions was introduced by Aguilar-Fraga, Elder, Garcia, Hadaway, Harris, Harry, Hogan, Johnson, Kretschmann, Lawson-Chavanu, Martínez Mori, Monroe, Quiñonez, Tolson III, and Williams II [ 2 ] . In this scenario, a car drives to its preference and parks there if the spot is available. Otherwise, if occupied, then the car drives forward, checks up to