Journal of Integer Sequences, Vol. 22 (2019), Article 19.7.3

Subset Parking Functions

Sam Spiro
Department of Mathematics
University of California, San Diego
9500 Gilman Dr.
La Jolla, CA 92093


A parking function (c1, ... , cn) can be viewed as having n cars trying to park on a one-way street with n parking spots from left to right, where car i tries to park in spot ci, and otherwise it parks in the leftmost available spot after ci. Another way to view this is that each car has a set Ci of "acceptable" parking spots, namely Ci = [ci, n], and that each car tries to park in the leftmost available spot that it finds acceptable.

Motivated by this, we define a subset parking function (C1, ... , Cn), with each Ci a subset of {1, ... , n}, by having the ith car try to park in the leftmost available element of Ci. We further generalize this idea by restricting our sets to be of size k, intervals, and intervals of length k. In each of these cases we provide formulas for the number of such parking functions.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A053525 A327761 A327794.)

Received September 26 2019; revised versions received October 12 2019; October 15 2019. Published in Journal of Integer Sequences, October 15 2019.

Return to Journal of Integer Sequences home page