Parking Functions

# 1. Definitions

• Parking Function: A parking function of size $n$ is a sequence $(a_1,…,a_n)$ of positive integers such that if $b_1 \leq b_2 \leq ... \leq b_n$ is the increasing rearrangement of $a_1,…,a_n$, then $b_i \leq i$.

• Preferred Parking Spot: The $ith$ element (car) in the sequence $(a_1,…,a_n)$ prefers the $a_ith$ parking spot. When it comes to the $ith$ turn, the $ith$ car will first go to the $a_ith$ spot. If the $a_ith$ spot is open, the car will park there. If the $a_ith$ spot is not open, the car will continue to the next spots until it finds an open one to park in.

• Lucky Car: A car that gets to park in its preferred parking spot.

• Jump List: The jump list is the list of car displacements. Rather, it is the subtraction of the preferred position from the actual position for each car. So for the Parking Function $(6, 1, 5, 2, 2, 1, 5)$, we have the jump list $(0, 0, 0, 0, 1, 3, 2)$. It is easy to count the number of lucky cars for a Parking Function by counting the number of 0's in the jump list - so for the previously mentioned Parking Function, the lucky cars are $(1, 2, 3, 4)$.

• Jump Number: The sum of the jump list. The jump number is always greater than or equal to 0.

# 2. Parking Functions and Dyck Paths

• Parking Function => Dyck Path: Start with an empty Dyck Path. Now, take the parking function and sort it into an increasing parking function, $(a_1,…,a_n)$. For each $a_j$ in $(a_1,…,a_{n-1})$, concatenate an up step (denoted by a 1) followed by $a_{j+1} - a_j$ down steps (denoted by a 0) to the Dyck Path. Then, after the $a_{n-1}th$ iteration, concatenate an upstep followed by as many downsteps as needed to get back to $x = 0$ for the Dyck Path.

• Formatting Parking Functions: A different way to format the parking function as a Dyck path is to use an $n$ x $n$ grid with a diagonal line running from the bottom left corner to the top right (illustration a). The length, $n$, is the length of the Parking Function. The Dyck path of the Parking Function is graphed on the line $y = x$. The parking function shown is $(1, 3, 5, 3, 1)$. To label the $n$ x $n$ grid, start in the 1’s column, and label the box(s) according to what position the 1’s is(are) in the parking function. If there is more than one of a number, they are ordered in ascending order with the smaller position closer to the bottom. Continue, labeling until the top row of the $n$ x $n$ grid has been reached. The labels should never go below the diagonal line, but they can go through it. This is shown in illustration c.

• The Area of a parking function is the number of lattice squares between its Dyck path and the main diagonal. We don’t count the half squares.

• Ex. The area of illustration c is 2.
• In a parking function two cars are primary attacking if they are on the same diagonal. These two cars form a primary dinv (diagonal inversion) when the car on the left is smaller. Two cars are secondary attacking if car $a$ is to the left of car $b$, and $b$ is on the diagonal just below $a$. These two cars form a secondary dinv when the car on the left is larger. The dinv of a parking function is total pairs forming a primary or secondary dinv.

• Ex. (illustration c): Primary attacking: {1,2},{1,3},{2,3},{4,5}, Primary dinv: {1,2},{1,3},{2,3}, Secondary attacking: {5,2},{5,3},{4,3}, Secondary dinv: {5,2},{5,3},{4,3}, Dinv = 6
• The word of a parking function is formed by reading cars by diagonals. Start with the diagonal farthest from the main diagonal, and read the cars from top-right to bottom-left.

• Ex. (illustration c): [3,4,5,2,1]
• The diagonal word of a parking function is found by reading the diagonals, again starting with the diagonal farthest from the main diagonal. Only this time the cars are recorded within a diagonal in increasing order.

• Ex. (illustration c): [3,4,5,1,2]

# 3. Examples

• Parking Function: Imagine there is a road that $n$ cars would like to park on. The parking spots are labeled from $1$ to $n$, and each car has a preferred parking spot. For example, the parking function $\{1,3,1\}$ means that car $1$ prefers spot $1$, car $2$ prefers spot $3$, and car $3$ prefers spot $1$. Each car first drives up to its preferred parking spot to park. If that spot is taken, the car continues on to the next available parking spot. To make things interesting, the cars are not allowed to reverse back to an open spot; If there are not any open parking spots after their preferred spot, they cannot park. We call a sequence of length n a parking function if each car is able to find a parking spot. For example, $\{4,1,2,1,3\}$ is a parking function, whereas $\{3,1,5,5,3\}$ is not.

• Lucky Cars: In the parking function $\{3,1,1,4\}$, cars number 1, 2, and 4 are lucky cars because they are able to park in their preferred parking spot.

• Parking Function => Dyck Path: Take the Parking Function [3, 2, 2, 1]. The first step is to convert the Parking Function into an increasing Parking Function. Thus, our Parking Function is now [1, 2, 2, 3].

• For the 1st iteration, we first place an upstep, then we take $a_2−a_1$, which is $2−1=1$. Thus, we place one downstep, and our Dyck Path becomes [1, 0].

• For the 2nd iteration, we first place an upstep, then we take $a_3−a_2$, which is $2−2=0$. Thus, we place zero downsteps, and our Dyck Path becomes [1, 0, 1]

• For the 3rd iteration, we first place an upstep, then we take $a_4−a_3$, which is $3−2=1$. Thus, we place one downstep, and our Dyck Path becomes [1, 0, 1, 1, 0].

• Finally, for the last step, we place an upstep, followed by as many downsteps as is needed to balance out the Dyck Path. Thus, we have [1, 0, 1, 1, 0, 1, 0, 0].

# 4. Properties

• Any permutation of a parking function is a parking function.
• The number of parking functions of length $n$ is $(n+1)^{n−1}$.

• Proof: We will start by changing the game a little. We will allow each car to go down the street to find a parking spot a second time (if necessary) and add an additional parking spot which we will label $n+1$. The number of parking preferences is: $(n+1)^n$. Note that:$(a_1,a_2,\ldots,a_n)$ would leave spot $i$ open, $(a_1+1,a_2+1,\ldots,a_n+1)$ would leave spot $i+1$ open, $(a_1+2,a_2+2,…,a_n+2)$ would leave spot $i+2$ open, . . . , $(a_1+n,a_2+n,\ldots,a_n+n)$ would leave spot $i+n$ open.

• This is allowed because if a car is set to park in a spot that is greater than $n+1$, since the cars are allowed to go down the street a second time, the car will park in a spot mod($n+1$).

Thus we have a group of $n+1$ parking functions, and exactly one will leave the spot $n+1$ open. We now consider this parking function that leaves $n+1$ open. It is open because no one preferred $n+$1, and no one had to drive down the street a second time (otherwise $n+1$ would have been filled). Therefore, it is a parking function.

• The number of non-decreasing parking functions of length $n$ is the $n$th Catalan Number.

• There is a bijection between maximal chains of non-crossing partitions of $\{1,2,\ldots,n+1\}$ and parking functions of length $n$ [STAN].

# 5. Conjectures

• Shuffle Conjecture: $$\nabla e_n = \sum_{PF\in PF_n}t^{area(PF)}q^{dinv(PF)}Q_{ides(PF)}$$

• For a interesting paper on this: [HICKS].

For a recently-proposed proof of the shuffle conjecture (August 2015): [CARLSSON].

# 6. Statistics

We have the following 7 statistics in the database:

The number of lucky cars of the parking function.
The dinv of a parking function.
Sum of the entries.
The cosum of a parking function.
The number of primary dinversion pairs of a labelled dyck path corresponding to a....
The number of secondary dinversion pairs of the dyck path corresponding to a park....
The sum of the entries of a parking function minus its length.

# 7. Maps

We have the following 6 maps in the database:

to non-decreasing parking function
to car permutation
to inverse des composition
to labelling permutation
to Dyck path
to touch composition

# 8. References

[CARLSSON]   E. Carlsson and A. Mellit, A Proof of the Shuffle Conjecture, http://arxiv.org/pdf/1508.06239v1.pdf.

[HICKS]   A. Hicks, A Parking Function Bijection Suggested by the Haglund-Morse-Zabrocki Conjecture, University of California- San Diego, (2010).

[STAN]   R. Stanley, Parking Functions, http://math.mit.edu/~rstan/transparencies/parking.pdf.

ParkingFunctions (last edited 2015-12-21 22:31:11 by JessicaStriker)