Unit-Interval Parking Functions and the Permutohedron

Abstract

Unit-interval parking functions are subset of parking functions in which cars park at most one spot away from their preferred parking spot. In this paper, we characterize unit-interval parking functions by understanding how they decompose into prime parking functions and count unit-interval parking functions when exactly $k<n$ cars do not park in their preference. This count yields an alternate proof of a result of Hadaway and Harris establishing that unit-interval parking functions are enumerated by the Fubini numbers. Then, our main result, establishes that for all integers $0\le k<n$, the unit-interval parking functions of length $n$ with displacement $k$ are in bijection with the $k$-dimensional faces of the permutohedron of order $n$. We conclude with some consequences of this result.

15 pages, 5 figures