Dyck paths

# 1. Definition

A Dyck path of size $n$ is

• a lattice path from $(0,0)$ to $(2n,0)$ consisting of $n$ up steps of the form $(1,1)$ and $n$ down steps of the form $(-1,1)$ which never goes below the x-axis $y=0$.

Clearly equivalently, one can see a Dyck path as

• a lattice path from $(0,0)$ to $(n,n)$ consisting of $n$ up steps of the form $(1,0)$ and $n$ down steps of the form $(0,1)$ which never goes below the diagonal $y=x$.

A Dyck path can also be identified with its Dyck word being $(0,1)$-sequence with $1$'s representing up steps and $0$'s representing down steps. Denote all Dyck paths of size $n$ by $\mathfrak{D}_n$.

# 2. Examples

• $\mathfrak{D}_1 = \{ [1,0] \}$

• $\mathfrak{D}_2 = \{ [1,0,1,0],[1,1,0,0] \}$

• $\mathfrak{D}_3 = \{[1,0,1,0,1,0], [1,1,0,0,1,0], [1,1,1,0,0,0], [1,0,1,1,0,0], [1,1,0,1,0,0] \}$

• $\mathfrak{D}_4 =$

# 3. Properties

• The cardinality of $\mathfrak{D}_n$ is the $n^{th}$ Catalan number $\operatorname{Cat}_n = \frac{1}{n+1} \binom{2n}{n}$. This can for example be seen using the reflection principle.

• A Dyck path $D$ of size $n+1$ can be decomposed into a Dyck path $D_1$ of size $k$ and a Dyck path $D_2$ of size $n-k$, where

• $(2k+2,0)$ is the first touch point of $D$ at the x-axis,

• $D_1$ is the prefix of $D$ from $(1,1)$ to $(2k-1,1)$ never going below the line $y=1$, and where

• $D_2$ is the suffix of $D$ from $(2k,0)$ to $(2n,0)$.

This yields the recurrence $\operatorname{Cat}_{n+1} = \sum_{k=1}^n \operatorname{Cat}_k \operatorname{Cat}_{n-k}$.

# 4. Remarks

• There is a natural extension of Dyck paths to $m$-Dyck paths which can be seen as lattice paths from $(0,0)$ to $(mn,n)$ that never go below the diagonal $y = \frac{1}{m} x$. The number of $m$-Dyck paths is given by the Fuss-Catalan number $C_n^{(m)} = \frac{1}{mn+1} \binom{(m+1)n}{n}$ [Kra89].

• Dyck paths and $m$-Dyck paths can be seen as type A instances of a more general combinatorial object for root systems, namely positive chambers in the (generalized) Shi arrangement [Ath04].

# 5. Statistics

We have the following 41 statistics in the database:

The bounce statistic of a Dyck path.
The dinv statistic of a Dyck path.
The number of touch points of a Dyck path.
The area of a Dyck path.
The height of a Dyck path.
The number of parking functions supported by a Dyck path.
The number of peaks of a Dyck path.
The number of double rises of a Dyck path.
The number of initial rises of a Dyck paths.
The position of the first return of a Dyck path.
The major index of a Dyck path.
The number of elements smaller than the given Dyck path in the Tamari Order.
The product of the heights of the descending steps of a Dyck path.
The number of valleys of a Dyck path not on the x-axis.
The number of valleys of the Dyck path.
The number of alternating sign matrices for a given Dyck path.
The number of centered tunnels of a Dyck path.
The number of left tunnels of a Dyck path.
The pyramid weight of the Dyck path.
The bounce count of a Dyck path.
The number of evenly positioned ascents, with the initial position equal to 1.
The number of upper interactions of a Dyck path.
The difference of lower and upper interactions.
The number of non-final maximal sub-paths of length greater than one.
The dinv deficit of a Dyck path.
The bounce deficit of a Dyck path.
The number of factors DDU in a Dyck path.
The sum of the heights of the peaks of a Dyck path minus the number of peaks.
The sum of the heights of the peaks of a Dyck path.
The number of Dyck paths that are weakly below a Dyck path.
The number of Dyck paths that are weakly above a Dyck path, except for the path i....
The number of Dyck paths that are weakly above a Dyck path.
The number of Dyck paths that are weakly below a Dyck path, except for the path i....
The position of the last up step in a Dyck path.
The position of the first down step of a Dyck path.
The maximal area to the right of an up step of a Dyck path.
The number of long tunnels of a Dyck path.
The length of the maximal rise of a Dyck path.
The number of rises of length 1 of a Dyck path.
The sum of the semi-lengths of tunnels before a valley of a Dyck path.
The number of global maxima of a Dyck path.

# 6. Maps

We have the following 19 maps in the database:

to non-crossing permutation
to 321-avoiding permutation
to 132-avoiding permutation
to ordered tree
to partition
reverse
to Tamari-corresponding binary tree
zeta map
to 312-avoiding permutation
inverse zeta map
to two-row standard tableau
to binary tree: up step, left tree, down step, right tree
to alternating sign matrix
to binary word
bounce path
touch composition
decomposition reverse
rise composition
peeling map

# 7. References

[Ath04]   C.A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc., 36 (2004), pp. 294-392.

[Kra89]   C. Krattenthaler, Counting lattice paths with a linear boundary II, Sitz.ber. d. ÖAW Math.-naturwiss. Klasse 198 (1989), 171-199.

# 8. Sage examples

DyckPaths (last edited 2015-12-02 16:32:57 by ChristianStump)