Federico mentioned in lecture that the number of increasing parking functions of length n is equal to , 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 be a Dyck path of length 2n. For each , let be the number of down steps of prior to the th up step, and let . (So, for example, if n = 4 and P = UDUUDUDD, then .) Then is an increasing parking function (why?), and, since this map is invertible (given , construct by starting with an up step, placing 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.
Parking Functions and Dyck Paths