Counting Parking functions: A New Bijection

Start: 04/09/2014 - 4:15pm
End  : 04/09/2014 - 5:15pm


Amanda Ruiz (HMC)


Imagine a one--way cul--de--sac with four parking spots. Initially they are all free, but there are four cars approaching the street, and they would all like to park. To make life interesting, every car has a parking preference, and we record the preferences in a sequence of four numbers; e.g., the sequence $ (2, 1, 1, 3) $ means that the first car would like to park at spot number $ 2 $, the second and third drivers prefer parking spot number $ 1 $, and the last car would like to part at slot number $ 3 $. The street is very narrow, so there is no way to back up. Now each car enters the street and approaches its preferred parking spot; if it is free, it parks there, and if not, it moves down the street to the first available spot. We call a sequence a parking function if all cars end up finding a parking spot. For example, our sequence $ (2, 1, 1, 3) $ is a parking function, whereas $ (1, 3, 3, 4) $ is not.

Naturally, we could ask about parking functions for any number of parking spots; we call this number the length of the parking function. A moment's thought reveals that there is one parking function of length $ 1 $, three parking functions of length $ 2 $, and sixteen parking functions of length $ 3 $. A beautiful theorem due to Konheim and Weiss says that there is a pattern to be found here: there are precisely $ (n+1)^{n-1} $ parking functions of length $ n $. We will hint at a proof of this theorem and illustrate a connections between parking functions to seemingly unrelated objects, which happen to exhibit the same counting pattern: a certain set of hyperplanes in $ n $--dimensional space first studied by Shi, and a certain family of mixed graphs, which we introduced in recent joint work with Matthias Beck, Ana Berrizbeitia, Michael Dairyko, Claudia Rodriguez, and Schuyler Veeneman.

This talk will be accessible undergraduates at all levels and will require audience participation.

Shanahan Center for Teaching and Learning, Shanahan B460 (basement level), Harvey Mudd College, 320 E. Foothill Blvd.

Ruiz.pdf137.95 KB