Enumerating Parking Completions Using Join and Split

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.