Parking with Frustrated Drivers

Source 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 $(a_1,a_2,\dots, 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.