Vacillating Parking Functions and the Fibonacci Numbers

Abstract

Vacillating parking functions are parking functions in which a car only tolerates parking in its preferred spot, in the spot behind its preferred spot, or in the spot ahead of its preferred spot, which they check precisely in that order. Our main result characterizes the possible permutations that arise as parking outcomes from the parking process of nondecreasing vacillating parking functions, which are vacillating parking functions in which every car prefers a spot at least the preference of the previous car. We show that a permutation is the outcome of a nondecreasing vacillating parking function if and only if the permutation is a product of commuting adjacent transpositions. This readily implies that the number of distinct permutations arising as outcomes of nondecreasing vacillating parking functions is a Fibonacci number. We also show that the number of nondecreasing vacillating parking functions that have a fixed outcome consisting of \(k\) commuting adjacent transpositions is always a power of two. We conclude by using these results to give a new formula for the number of nondecreasing vacillating parking functions.