# Parking Functions and Dyck Paths

Federico mentioned in lecture that the number of increasing parking functions of length n is equal to $C_n$, the nth Catalan number, which suggests that there is a bijection between increasing parking functions of length n and Dyck paths of length 2n. I think I have one: Let $P$ be a Dyck path of length 2n. For each $1 \le j \le n$, let $a_j$ be the number of down steps of $P$ prior to the $j$th up step, and let $\mathbf{p} = (a_1 + 1, \ldots, a_n + 1)$. (So, for example, if n = 4 and P = UDUUDUDD, then $\mathbf{p} = (1, 2, 2, 3)$.) Then $\mathbf{p}$ is an increasing parking function (why?), and, since this map is invertible (given $\mathbf{p}$, construct $P$ by starting with an up step, placing $a_j - a_{j - 1}$ down steps between the (j – 1)th and jth up steps, and place as many down steps at the end of the sequence as is necessary to get back down to the axis), it is a bijection.

Advertisements

### 2 comments

1. mattcadier

I had a similar thought, and I think that it is essentially the same:

To create a bijection between the set of sequences of length $n$ where $a_i\leq i$
and Dyck paths of length $2n$, we take the sequence $(a_1, a_2, \dots a_n)$, subtract 1 from each $a_i$, then draw the histogram (bar chart) of that sequence. Since each $a_i-1< i$, if we trace the upper boundary of the bars, we'll have a path from (0,0) to (n,n) that stays below diagonal.
Flipping this around, it is a Dyck path of length 2n. The inverse is obvious: add 1 to each
bar to get back the $a_i$'s.

But I think this is equivalent to your bijection. If we take the Dyck path given above (UDUUDUDD)
and draw it as a path from (0,0) to (n,n) that stays above the diagonal and interpreting the positive $y$
direction as "Up" we can view "the number of down steps of $P$ prior to the $j$th step up as the horizontal length of the bar drawn between $[j-1,j]$ on the $y$ axis and the path.
So adding 1 to these lengths would get you an increasing parking function.

2. mattcadier

Just realized I can’t edit comments so errata:
(in line 2) *a bijection between the set of increasing sequences…