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.

### Like this:

Like Loading...

*Related*

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 where

and Dyck paths of length , we take the sequence , subtract 1 from each , then draw the histogram (bar chart) of that sequence. Since each , 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 '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

direction as "Up" we can view "the number of down steps of prior to the th step up as the horizontal length of the bar drawn between on the axis and the path.

So adding 1 to these lengths would get you an increasing parking function.

Just realized I can’t edit comments so errata:

(in line 2) *a bijection between the set of increasing sequences…