The Cali Garmo

does Math

Dyck Paths

By Cali G, Published on Fri 18 October 2019
Category: Symmetric functions

A Dyck path has two equivalent definitions. For both of them, we start by looking at and constructing a path which starts at .

Two Definitions

Definition 1: A Dyck path in is a path from to which takes only north and east steps and that never crosses the diagonal. The best way to see this is through an example.

Definition 2: A Dyck path in is a path from to which takes only north-east steps and south-east steps which never cross the 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 be a Dyck path and draw the Dyck path as we did in our first definition. For each row in (bottom row is row ) we can count the number of full boxes between the diagonal and the Dyck path. This gives us a number which we denote by .

In our example above we have To see this more closely, notice that 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 :

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 . First let's calculate the distribution using area. There are possible Dyck paths where 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 , , and . We can calculate these using either method, but since there are only a few of these (only Dyck path in and and only in ) it's easier to just look at the areas.

There is only one Dyck path from to and it has area. Therefore Similarly, there is only one Dyck path from to and it has area. Therefore Finally, there are only two Dyck paths from to : Since one has area and one has area 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 , then the major index is given by:

As an example, if then , , , etc. and since and , then .

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 . For each th step, if we go north then we let else we let . We let denote this number sequence of a Dyck path .

As an example, suppose we have the Dyck path from before: Now notice that, starting from 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 . We have 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. https://doi.org/10.1215/S0012-7094-64-03136-9
  • [Mac60] P.A MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York., 1960.