Geodesic
A generalization of parking functions allowing backward movement
The electronic journal of combinatorics, Tome 27 (2020) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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. A corrigendum was added to this paper on 2 April 2020. A corrigendum was added to this paper on 8 February 2021.
DOI : 10.37236/8948
Classification : 05A15, 05A19
Mots-clés : parking preferences, \(k\)-Naples parking function

Alex Christensen    ; Pamela E. Harris  1   ; Zakiya Jones    ; Marissa Loving    ; Andrés Ramos Rodríguez    ; Joseph Rennie    ; Gordon Rojas Kirby 

1 Williams College 
@article{10_37236_8948,
     author = {Alex Christensen and Pamela E. Harris and Zakiya Jones and Marissa Loving and Andr\'es Ramos Rodr{\'\i}guez and Joseph Rennie and Gordon Rojas Kirby},
     title = {A generalization of parking functions allowing backward movement},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8948},
     zbl = {1432.05010},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8948/}
}
TY  - JOUR
AU  - Alex Christensen
AU  - Pamela E. Harris
AU  - Zakiya Jones
AU  - Marissa Loving
AU  - Andrés Ramos Rodríguez
AU  - Joseph Rennie
AU  - Gordon Rojas Kirby
TI  - A generalization of parking functions allowing backward movement
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8948/
DO  - 10.37236/8948
ID  - 10_37236_8948
ER  - 
%0 Journal Article
%A Alex Christensen
%A Pamela E. Harris
%A Zakiya Jones
%A Marissa Loving
%A Andrés Ramos Rodríguez
%A Joseph Rennie
%A Gordon Rojas Kirby
%T A generalization of parking functions allowing backward movement
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8948/
%R 10.37236/8948
%F 10_37236_8948
Alex Christensen; Pamela E. Harris; Zakiya Jones; Marissa Loving; Andrés Ramos Rodríguez; Joseph Rennie; Gordon Rojas Kirby. A generalization of parking functions allowing backward movement. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8948

Cité par Sources :