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.


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 ith 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]


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:


  • [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.