Enumerating Parking Completions Using Join and Split
Preprint
Abstract
Given a strictly increasing sequence $\mathbf{t}$ with entries from $[n]:=\{1,\ldots,n\}$, a parking completion is a sequence $\mathbf{c}$ with $|\mathbf{t}|+|\mathbf{c}|=n$ and $|\{t\in \mathbf{t}\mid t\le i\}|+|\{c\in \mathbf{c}\mid c\le i\}|\ge i$ for all $i$ in $[n]$. We can think of $\mathbf{t}$ as a list of spots already taken in a street with $n$ parking spots and $\mathbf{c}$ as a list of parking preferences where the $i$-th car attempts to park in the $c_i$-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 $\mathbf{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 \textbf{Join} and \textbf{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.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Probabilizing parking functionsAdvances in Applied Mathematics, 2017
- Rational Dyck Paths in the Non Relatively Prime CaseThe Electronic Journal of Combinatorics, 2017
- Affine permutations and rational slope parking functionsTransactions of the American Mathematical Society, 2016
- Parking Cars of Different SizesThe American Mathematical Monthly, 2016
- Rational Parking Functions and Catalan NumbersAnnals of Combinatorics, 2015
- Rational Associahedra and Noncrossing PartitionsThe Electronic Journal of Combinatorics, 2013
- A Refinement of Cayley's Formula for TreesThe Electronic Journal of Combinatorics, 2004