Ji Li and Ginny Bohme presented Preferred Parking Perplexity
for MEAD, January 30, 2010
The problem of counting parking functions is a traditional one in combinatorics. It was first studied by Konheim and Weiss in their 1966 paper.
Imagine n parking spaces {1, ..., n} in a one-way street. The cars arrive in order, with the i-th arrival being assigned position Ai. If an earlier car already took that spot then car i will try the next place along until it parks or fails at the last parking space and gives up. If no car is forced to give up, then the sequence {A1, ... An} is called a parking function.
As it turns out, the number of parking functions for n cars is the same as the number of labeled trees on n+1 vertices as in Cayley's formula in 1899, which is n+1 to the (n-1)-th power. Before talking about this formula, participants want to go through listing all parking functions up to the order 3, in order to find some basic patterns of what a parking function looks like.
During the discussion, the topic of permutations of a multi-set is brought up. A multi-set is such that each member has a multiplicity indicating how many times it is a member. For example, in the multi-set {a, a, b, c}, the multiplicities of a, b, and c are 2, 1, and 1. The number of permutations of multi-sets are multinomial coefficients.
To prove the formula for the number of parking functions on on, we need to introduce the circular parking function. Here there are n+1 parking spaces for n cars, and each car is assigned a position Ai that ranges from 1 through n+1. Quickly we observe that no matter what the sequence {A1, ... An} is, all cars can always park, and there is always one parking spot left empty in the end. Moreover, each parking spot has equal chance of being left empty, and if the spot n+1 is empty, then we just have a parking function. This leads to writing down the desired formula for the number of parking functions on n.
|
|
Ji Li observes the high school groups working. | Ginny Bohme makes a point as Ron Hopley listens. |
