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. DOI
- [Mac60] P.A MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York., 1960.