The Cali Garmo

does Math

Dyck Paths

By Cali G , Published on Fri 18 October 2019
Category: math / symmetric functions

A Dyck path has two equivalent definitions. For both of them, we start by looking at $\mathbb{Z}^2$ and constructing a path which starts at $(0,0)$.

Two Definitions

Definition 1: A Dyck path in $\mathcal{D}_n$ is a path from $(0,0)$ to $(n,n)$ which takes only north and east steps and that never crosses the $x = y$ diagonal. The best way to see this is through an example.

Definition 2: A Dyck path in $\mathcal{D}_n$ is a path from $(0,0)$ to $(2n,0)$ which takes only north-east steps and south-east steps which never cross the $x = 0$ line. Taking the same example as before, we have.

Area

One of the most common statistics that we place on Dyck paths is area. Let $\pi \in \mathcal{D}_n$ be a Dyck path and draw the Dyck path as we did in our first definition. For each row $i$ in $\pi$ (bottom row is row $1$) we can count the number of full boxes between the diagonal and the Dyck path. This gives us a number which we denote by $a_i$.

In our example above we have To see this more closely, notice that $a_4 = 2$ since there are two full boxes to the right of the path and to the left of the diagonal:

To get the area of the Dyck path, it suffices to sum up all the $a_i$:

In our example,

Distribution using area

We can look at the distribution of Dyck paths using previous Dyck paths thanks to Carlitz and Riordan. They showed the following theorem.

Theorem [CR64]

Let's look at an example of this. We'll try and find $C_3(q)$. First let's calculate the distribution using area. There are $5$ possible Dyck paths where $n = 3$ and these are given by: So we should find:

Let's now try and use the second summation. We have: In essence, we need to calculate $C_0(q)$, $C_1(q)$, and $C_2(q)$. We can calculate these using either method, but since there are only a few of these (only $1$ Dyck path in $\mcD_0$ and $\mcD_1$ and only $2$ in $\mcD_2$) it's easier to just look at the areas.

There is only one Dyck path from $(0,0)$ to $(0,0)$ and it has $0$ area. Therefore Similarly, there is only one Dyck path from $(0,0)$ to $(1,1)$ and it has $0$ area. Therefore Finally, there are only two Dyck paths from $(0,0)$ to $(2,2)$: Since one has area $0$ and one has area $1$ therefore:

Finally: Which is the same as earlier.

Distribution using major index

We next look at how to assign to each Dyck path a major index and count the number of Dyck paths with a certain major index.

Recall that given a sequence of number $\sigma = \sigma_1 \sigma_2 \ldots \sigma_n$, then the major index is given by:

As an example, if $\sigma = 010101$ then $\sigma_1 = 0$, $\sigma_2 = 1$, $\sigma_3 = 0$, etc. and since $\sigma_2 > \sigma_3$ and $\sigma_4 > \sigma_5$, then $maj(\sigma) = 2 + 4 = 6$.

Thanks to MacMahon, we know the distribution of the Dyck paths relative to their major indices. To view this, we must first show how to go from a Dyck path to a sequence of numbers. For this, we look at the first definition of a Dyck path and start from $(0,0)$. For each $i$th step, if we go north then we let $\sigma_i = 0$ else we let $\sigma_i = 1$. We let $\sigma(\pi)$ denote this number sequence of a Dyck path $\pi$.

As an example, suppose we have the Dyck path from before: Now notice that, starting from $(0,0)$ we first go north 3 times, then east, then north, etc. This means that we have the following number sequence:

Theorem [Mac60]

where

Let's look at a full distribution when $n = 3$. We have $5$ different Dyck paths that are possible for which I've placed the word associated to it on the right

This gives us the following major indices: In other words:

On the other hand:

References

• [CR64] L. Carlitz, J. Riordan, Two element lattice permutation numbers and their $q$-generalization, Duke Math J. [31]-3 (1964), 371-388. DOI
• [Mac60] P.A MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York., 1960.