Parking with Frustrated Drivers
Abstract
Imagine there are n cars lined up along a one-way street containing n spots. Each car contains a group of friends, including a reluctant driver. Each car has a preferred spot and cars enter one by one. The cars drive to their preferred spot and if it is empty park there. If it is not empty, a friend in the back yells out ``Hey! You should have driven faster!". Frustrated by this, the driver continues down the road until they find the last unoccupied spot (if one exists) and parks there. We say a sequence (a1,a2,…, an) of preferred spots is a frustrated parking function if all cars can park under this rule. In this paper, we study the enumerative properties of frustrated parking functions. In particular, we show that the number of frustrated parking functions of length n is (2n−1)!!. This is done by associating frustrated parking functions with height labeled Dyck paths. Using this association, we are then able to better understand the sets of lucky cars and lucky spots for frustrated parking functions. We show that the frustrated parking functions of length n where the first k cars (or first k spots) are lucky is given by k!S(n,k) where S(n,k) is the Stirling number of the second kind. This in turn implies that the number of frustrated parking functions where once a car (or spot) is unlucky, the remaining cars (or spots) are unlucky is counted by the nth Fubini number. We also show that the number of frustrated parking functions with k lucky cars (or spots) is given by the second order Eulerian number.
Related
BibTeX
@misc{hallam2026parking,
title = {{Parking with Frustrated Drivers}},
author = {Joshua Hallam and Jenson Molebash and Chris Porter},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35638},
eprint = {2609.35638},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35638},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Parking with Frustrated Drivers
AU - Joshua Hallam
AU - Jenson Molebash
AU - Chris Porter
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35638
UR - https://arxiv.org/abs/2609.35638
AB - Imagine there are n cars lined up along a one-way street containing n spots. Each car contains a group of friends, including a reluctant driver. Each car has a preferred spot and cars enter one by one. The cars drive to their preferred spot and if it is empty park there. If it is not empty, a friend in the back yells out ``Hey! You should have driven faster!". Frustrated by this, the driver continues down the road until they find the last unoccupied spot (if one exists) and parks there. We say a sequence (a_1,a_2,…, a_n) of preferred spots is a frustrated parking function if all cars can park under this rule. In this paper, we study the enumerative properties of frustrated parking functions. In particular, we show that the number of frustrated parking functions of length n is (2n−1)!!. This is done by associating frustrated parking functions with height labeled Dyck paths. Using this association, we are then able to better understand the sets of lucky cars and lucky spots for frustrated parking functions. We show that the frustrated parking functions of length n where the first k cars (or first k spots) are lucky is given by k!S(n,k) where S(n,k) is the Stirling number of the second kind. This in turn implies that the number of frustrated parking functions where once a car (or spot) is unlucky, the remaining cars (or spots) are unlucky is counted by the n^th Fubini number. We also show that the number of frustrated parking functions with k lucky cars (or spots) is given by the second order Eulerian number.
ER -