Connecting k-Naples parking functions and obstructed parking functions via involutions

DOI10.37236/10630MaRDI QIDQ2153403zbMATH OpenOpenAlexFDO

Authors Roger Tian

Publication date 4 July 2022

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/2012.02623

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

contained \(k\)-Naples parking functions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19) Traffic problems in operations research (90B20) Combinatorial inequalities (05A20)

Abstract: Parking functions were classically defined for $n$ cars attempting to park on a one-way street with $n$ parking spots, where cars only drive forward. Subsequently, parking functions have been generalized in various ways, including allowing cars the option of driving backward. The set $P{F}_{n,k}$ of $k$-Naples parking functions have cars who can drive backward a maximum of $k$ steps before driving forward. A recursive formula for $|P{F}_{n,k}|$ has been obtained, though deriving a closed formula for $|P{F}_{n,k}|$ appears difficult. In addition, an important subset $B_{n,k}$ of $P{F}_{n,k}$, called the contained $k$-Naples parking functions, has been shown, with a non-bijective proof, to have the same cardinality as that of the set $P{F}_n$ of classical parking functions, independent of $k$. In this paper, we study $k$-Naples parking functions in the more general context of $m$ cars and $n$ parking spots, for any $mleqn$. We use various parking function involutions to establish a bijection between the contained $k$-Naples parking functions and the classical parking functions, from which it can be deduced that the two sets have the same number of ties. Then we extend this bijection to inject the set of $k$-Naples parking functions into a certain set of obstructed parking functions, providing an upper bound for the cardinality of the former set.

Recommendations

• A generalization of parking functions allowing backward movement
• Counting k-Naples parking functions through permutations and the k-Naples area statistic
• Subset parking functions
• Generalizing parking functions with randomness
• Parking functions, valet functions and priority queues

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• A generalization of parking functions allowing backward movement
• A refinement of Cayley's formula for trees
• An Occupancy Discipline and Applications
• Counting defective parking functions
• Counting k-Naples parking functions through permutations and the k-Naples area statistic
• Mappings of acyclic and parking functions
• Parking cars after a trailer
• Parking functions on directed graphs and some directed trees

Cited in

(3)

• Counting k-Naples parking functions through permutations and the k-Naples area statistic
• A generalization of parking functions allowing backward movement
• On friendship and cyclic parking functions

This page was built for publication: Connecting \(k\)-Naples parking functions and obstructed parking functions via involutions

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