Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper introduces and analyzes "frustrated parking functions," an alternative collision-resolution variant of classical parking functions where blocked agents skip ahead to the last available spot on a one-way street rather than taking the first open one. By establishing a bijection between these sequences and height-labeled Dyck paths, the authors resolve the enumerative structure of this non-local allocation process. They prove that exactly $(2n-1)!!$ frustrated parking configurations exist for length $n$, while showing that distributions of "lucky" agents and spots are governed by Stirling numbers of the second kind, Fubini numbers, and second-order Eulerian numbers.
Flipping the standard parking collision rule from greedy local insertion to terminal-spot allocation collapses the sequence space to exactly $(2n-1)!!$ configurations governed cleanly by second-order Eulerian and Stirling statistics.
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.