A generalization of parking functions allowing backward movement

DOI10.37236/8948MaRDI QIDQ2294100zbMATH OpenOpenAlexFDO

Authors Alex Julia Hinojosa Christensen, Pamela E. Harris, Zakiya Jones, Marissa Loving, Andrés Ramos Rodríguez, Joseph Rennie, Gordon Rojas Kirby

Publication date 10 February 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1908.07658, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p33

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-Naples parking functionparking preferences

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: Classical parking functions are defined as the parking preferences for $n$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $1$ to $n$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $n$-tuple containing the cars' parking preferences a parking function. In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $k$ spaces west of their preferred spot to park before proceeding east if all of those $k$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $k$-Naples parking functions of length $n$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $n$-tuples of positive integers $1$ to $n$, the case when $kgeqn-1$. Our main result provides a recursive formula for counting $k$-Naples parking functions of length $n$. We also give a characterization for the $k=1$ case by introducing a new function that maps $1$-Naples parking functions to classical parking functions, i.e. $0$-Naples parking functions. Lastly, we present a bijection between $k$-Naples parking functions of length $n$ whose entries are in weakly decreasing order and a family of signature Dyck paths.

Review text

Summary: Classical parking functions are defined as the parking preferences for \(n\) cars driving (from west to east) down a one-way street containing parking spaces labeled from \(1\) to \(n\) (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the \(n\)-tuple containing the cars' parking preferences a parking function. In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to \(k\) spaces west of their preferred spot to park before proceeding east if all of those \(k\) spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule \(k\)-Naples parking functions of length \(n\). This generalization gives a natural interpolation between classical parking functions, the case when \(k=0\), and all \(n\)-tuples of positive integers \(1\) to \(n\), the case when \(k\geq n-1\). Our main result provides a recursive formula for counting \(k\)-Naples parking functions of length \(n\). We also give a characterization for the \(k=1\) case by introducing a new function that maps \(1\)-Naples parking functions to classical parking functions, i.e. \(0\)-Naples parking functions. Lastly, we present a bijection between \(k\)-Naples parking functions of length \(n\) whose entries are in weakly decreasing order and a family of signature Dyck paths.

Recommendations

• Counting k-Naples parking functions through permutations and the k-Naples area statistic
• Connecting k-Naples parking functions and obstructed parking functions via involutions
• Generalizing parking functions with randomness
• Subset parking functions
• On increasing and invariant parking sequences

Cites work

• An Occupancy Discipline and Applications
• Descents in parking functions
• Generalized parking functions, tree inversions, and multicolored graphs
• Mappings of acyclic and parking functions
• Parking Functions: Choose Your Own Adventure
• Signature Catalan combinatorics
• The Supremum and Infimum of the Poisson Process

Cited in

(16)

• Connecting k-Naples parking functions and obstructed parking functions via involutions
• Generalizing parking functions with randomness
• Counting k-Naples parking functions through permutations and the k-Naples area statistic
• Parking Functions: Choose Your Own Adventure
• Subset parking functions
• scientific article; zbMATH DE number 7058727 (Why is no real title available?)
• Probabilistic parking functions
• On the outcome map of MVP parking functions: permutations avoiding 321 and 3412, and Motzkin paths
• On friendship and cyclic parking functions
• Primeness of generalized parking functions
• Interval and -interval rational parking functions
• Probabilistic (m, n)-parking functions
• Metered parking functions
• Enumerating k-Naples parking functions through Catalan objects
• The defective parking space and defective Kreweras numbers
• A new approach to Naples parking functions through complete parking preferences, and its enumerative consequences

This page was built for publication: A generalization of parking functions allowing backward movement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294100)