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 jth 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 jth 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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: