Enumerating Parking Completions Using Join and Split
Issue Date
2020-06-12Author
Adeniran, Ayomikun
Butler, Steve
Dorpalen-Barry, Galen
Harris, Pamela E.
Hettle, Cyrus
Liang, Qingzhong
Martin, Jeremy L.
Nam, Hayan
Publisher
Electronic Journal of Combinatorics
Type
Article
Article Version
Scholarly/refereed, publisher version
Rights
Copyright The authors. This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
Metadata
Show full item recordAbstract
Given a strictly increasing sequence t with entries from [n] := {1, . . . , n}, a parking completion is a sequence c with |t| + |c| = n and |{t ∈ t | t 6 i}| + |{c ∈ c | c 6 i}| > i for all i in [n]. We can think of t as a list of spots already taken in a street with n parking spots and c as a list of parking preferences where the i-th car attempts to park in the ci-th spot and if not available then proceeds up the street to find the next available spot, if any. A parking completion corresponds to a set of
preferences c where all cars park.
We relate parking completions to enumerating restricted lattice paths and give formulas for both the ordered and unordered variations of the problem by use of a pair of operations termed Join and Split. Our results give a new volume formula for most Pitman-Stanley polytopes, and enumerate the signature parking functions of Ceballos and Gonz´alez D’Le´on.
Collections
Citation
Adeniran et al., "Enumerating Parking Completions Using Join and Split", The Electronic Journal of Combinatorics, vol. 27, no. 2 (2020), DOI: 10.37236/9194
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.