Loading...
Enumerating Parking Completions Using Join and Split
Adeniran, Ayomikun Butler, Steve Dorpalen-Barry, Galen Harris, Pamela E. Hettle, Cyrus Liang, Qingzhong Martin, Jeremy L. Nam, Hayan
Adeniran, Ayomikun
Butler, Steve
Dorpalen-Barry, Galen
Harris, Pamela E.
Hettle, Cyrus
Liang, Qingzhong
Martin, Jeremy L.
Nam, Hayan
Citations
Altmetric:
Abstract
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.
Description
Date
2020-06-12
Journal Title
Journal ISSN
Volume Title
Publisher
Electronic Journal of Combinatorics
Collections
Research Projects
Organizational Units
Journal Issue
Keywords
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