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 88 statistics in the database:

St000005
Dyck paths ⟶ ℤ
The bounce statistic of a Dyck path.
St000006
Dyck paths ⟶ ℤ
The dinv statistic of a Dyck path.
St000011
Dyck paths ⟶ ℤ
The number of touch points of a Dyck path.
St000012
Dyck paths ⟶ ℤ
The area of a Dyck path.
St000013
Dyck paths ⟶ ℤ
The height of a Dyck path.
St000014
Dyck paths ⟶ ℤ
The number of parking functions supported by a Dyck path.
St000015
Dyck paths ⟶ ℤ
The number of peaks of a Dyck path.
St000024
Dyck paths ⟶ ℤ
The number of double up and double down steps of a Dyck path.
St000025
Dyck paths ⟶ ℤ
The number of initial rises of a Dyck path.
St000026
Dyck paths ⟶ ℤ
The position of the first return of a Dyck path.
St000027
Dyck paths ⟶ ℤ
The major index of a Dyck path.
St000032
Dyck paths ⟶ ℤ
The number of elements smaller than the given Dyck path in the Tamari Order.
St000038
Dyck paths ⟶ ℤ
The product of the heights of the descending steps of a Dyck path.
St000052
Dyck paths ⟶ ℤ
The number of valleys of a Dyck path not on the x-axis.
St000053
Dyck paths ⟶ ℤ
The number of valleys of the Dyck path.
St000079
Dyck paths ⟶ ℤ
The number of alternating sign matrices for a given Dyck path.
St000117
Dyck paths ⟶ ℤ
The number of centered tunnels of a Dyck path.
St000120
Dyck paths ⟶ ℤ
The number of left tunnels of a Dyck path.
St000144
Dyck paths ⟶ ℤ
The pyramid weight of the Dyck path.
St000306
Dyck paths ⟶ ℤ
The bounce count of a Dyck path.
St000329
Dyck paths ⟶ ℤ
The number of evenly positioned ascents, with the initial position equal to 1.
St000331
Dyck paths ⟶ ℤ
The number of upper interactions of a Dyck path.
St000335
Dyck paths ⟶ ℤ
The difference of lower and upper interactions.
St000340
Dyck paths ⟶ ℤ
The number of non-final maximal sub-paths of length greater than one.
St000369
Dyck paths ⟶ ℤ
The dinv deficit of a Dyck path.
St000376
Dyck paths ⟶ ℤ
The bounce deficit of a Dyck path.
St000386
Dyck paths ⟶ ℤ
The number of factors DDU in a Dyck path.
St000394
Dyck paths ⟶ ℤ
The sum of the heights of the peaks of a Dyck path minus the number of peaks.
St000395
Dyck paths ⟶ ℤ
The sum of the heights of the peaks of a Dyck path.
St000418
Dyck paths ⟶ ℤ
The number of Dyck paths that are weakly below a Dyck path.
St000419
Dyck paths ⟶ ℤ
The number of Dyck paths that are weakly above a Dyck path, except for the path i....
St000420
Dyck paths ⟶ ℤ
The number of Dyck paths that are weakly above a Dyck path.
St000421
Dyck paths ⟶ ℤ
The number of Dyck paths that are weakly below a Dyck path, except for the path i....
St000438
Dyck paths ⟶ ℤ
The position of the last up step in a Dyck path.
St000439
Dyck paths ⟶ ℤ
The position of the first down step of a Dyck path.
St000442
Dyck paths ⟶ ℤ
The maximal area to the right of an up step of a Dyck path.
St000443
Dyck paths ⟶ ℤ
The number of long tunnels of a Dyck path.
St000444
Dyck paths ⟶ ℤ
The length of the maximal rise of a Dyck path.
St000445
Dyck paths ⟶ ℤ
The number of rises of length 1 of a Dyck path.
St000476
Dyck paths ⟶ ℤ
The sum of the semi-lengths of tunnels before a valley of a Dyck path.
St000617
Dyck paths ⟶ ℤ
The number of global maxima of a Dyck path.
St000645
Dyck paths ⟶ ℤ
The sum of the areas of the rectangles formed by two consecutive peaks and the va....
St000655
Dyck paths ⟶ ℤ
The length of the minimal rise of a Dyck path.
St000658
Dyck paths ⟶ ℤ
The number of rises of length 2 of a Dyck path.
St000659
Dyck paths ⟶ ℤ
The number of rises of length at least 2 of a Dyck path.
St000660
Dyck paths ⟶ ℤ
The number of rises of length at least 3 of a Dyck path.
St000661
Dyck paths ⟶ ℤ
The number of rises of length 3 of a Dyck path.
St000674
Dyck paths ⟶ ℤ
The number of hills of a Dyck path.
St000675
Dyck paths ⟶ ℤ
The number of centered multitunnels of a Dyck path.
St000676
Dyck paths ⟶ ℤ
The number of odd rises of a Dyck path.
St000678
Dyck paths ⟶ ℤ
The number of up steps after the last double rise of a Dyck path.
St000683
Dyck paths ⟶ ℤ
The number of points below the Dyck path such that the diagonal to the north-east....
St000684
Dyck paths ⟶ ℤ
The global dimension of the LNakayama algebra associated to a Dyck path.
St000685
Dyck paths ⟶ ℤ
The dominant dimension of the LNakayama algebra associated to a Dyck path.
St000686
Dyck paths ⟶ ℤ
The finitistic dominant dimension of a Dyck path.
St000687
Dyck paths ⟶ ℤ
The dimension of $Hom(I,P)$ for the LNakayama algebra of a Dyck path.
St000688
Dyck paths ⟶ ℤ
The global dimension minus the dominant dimension of the LNakayama algebra associ....
St000689
Dyck paths ⟶ ℤ
The maximal n such that the minimal generator-cogenerator module in the LNakayama....
St000790
Dyck paths ⟶ ℤ
The number of pairs of centered tunnels, one strictly containing the other, of a ....
St000791
Dyck paths ⟶ ℤ
The number of pairs of left tunnels, one strictly containing the other, of a Dyck....
St000874
Dyck paths ⟶ ℤ
The position of the last double rise in a Dyck path.
St000920
Dyck paths ⟶ ℤ
The logarithmic height of a Dyck path.
St000930
Dyck paths ⟶ ℤ
The k-Gorenstein degree of the corresponding Nakayama algebra with linear quiver.....
St000931
Dyck paths ⟶ ℤ
The number of occurrences of the pattern UUU in a Dyck path.
St000932
Dyck paths ⟶ ℤ
The number of occurrences of the pattern UDU in a Dyck path.
St000946
Dyck paths ⟶ ℤ
The sum of the skew hook positions in a Dyck path.
St000947
Dyck paths ⟶ ℤ
The major index of a Dyck path according to Zhao and Zhong.
St000949
Dyck paths ⟶ ℤ
Gives the number of generalised tilting modules of the corresponding LNakayama al....
St000950
Dyck paths ⟶ ℤ
Number of tilting modules of the corresponding LNakayama algebra, where a tilting....
St000951
Dyck paths ⟶ ℤ
The dimension of $Ext^{1}(D(A),A)$ of the corresponding LNakayama algebra.
St000952
Dyck paths ⟶ ℤ
Gives the number of irreducible factors of the Coxeter polynomial of the Dyck pat....
St000953
Dyck paths ⟶ ℤ
The largest degree of an irreducible factor of the Coxeter polynomial of the Dyck....
St000954
Dyck paths ⟶ ℤ
Number of times the corresponding LNakayama algebra has $Ext^i(D(A),A)=0$ for $i>0$.
St000955
Dyck paths ⟶ ℤ
Number of times one has $Ext^i(D(A),A)>0$ for $i>0$ for the corresponding LNakayama a....
St000964
Dyck paths ⟶ ℤ
Gives the dimension of Ext^g(D(A),A) of the corresponding LNakayama algebra, when....
St000965
Dyck paths ⟶ ℤ
The sum of the dimension of Ext^i(D(A),A) for i=1,.
St000966
Dyck paths ⟶ ℤ
Number of peaks minus the global dimension of the corresponding LNakayama algebra....
St000967
Dyck paths ⟶ ℤ
The value p(1) for the Coxeterpolynomial p of the corresponding LNakayama algebra....
St000968
Dyck paths ⟶ ℤ
We make a CNakayama algebra out of the LNakayama algebra (corresponding to the Dy....
St000969
Dyck paths ⟶ ℤ
We make a CNakayama algebra out of the LNakayama algebra (corresponding to the Dy....
St000970
Dyck paths ⟶ ℤ
Number of peaks minus the dominant dimension of the corresponding LNakayama algeb....
St000976
Dyck paths ⟶ ℤ
The sum of the positions of double up-steps of a Dyck path.
St000977
Dyck paths ⟶ ℤ
MacMahon's equal index of a Dyck path.
St000978
Dyck paths ⟶ ℤ
The sum of the positions of double down-steps of a Dyck path.
St000979
Dyck paths ⟶ ℤ
Half of MacMahon's equal index of a Dyck path.
St000980
Dyck paths ⟶ ℤ
The number of boxes weakly below the path and above the diagonal that lie below a....
St000981
Dyck paths ⟶ ℤ
The length of the longest zigzag subpath.
St000984
Dyck paths ⟶ ℤ
The number of boxes below precisely one peak.

6. Maps

We have the following 42 maps in the database:

Mp00007
Alternating sign matrices ⟶ Dyck paths
to Dyck path
Mp00012
Binary trees ⟶ Dyck paths
to Dyck path: up step, left tree, down step, right tree
Mp00020
Binary trees ⟶ Dyck paths
to Tamari-corresponding Dyck path
Mp00023
Dyck paths ⟶ Permutations
to non-crossing permutation
Mp00024
Dyck paths ⟶ Permutations
to 321-avoiding permutation
Mp00025
Dyck paths ⟶ Permutations
to 132-avoiding permutation
Mp00026
Dyck paths ⟶ Ordered trees
to ordered tree
Mp00027
Dyck paths ⟶ Integer partitions
to partition
Mp00028
Dyck paths ⟶ Dyck paths
reverse
Mp00029
Dyck paths ⟶ Binary trees
to Tamari-corresponding binary tree
Mp00030
Dyck paths ⟶ Dyck paths
zeta map
Mp00031
Dyck paths ⟶ Permutations
to 312-avoiding permutation
Mp00032
Dyck paths ⟶ Dyck paths
inverse zeta map
Mp00033
Dyck paths ⟶ Standard tableaux
to two-row standard tableau
Mp00034
Dyck paths ⟶ Binary trees
to binary tree: up step, left tree, down step, right tree
Mp00035
Dyck paths ⟶ Alternating sign matrices
to alternating sign matrix
Mp00043
Integer partitions ⟶ Dyck paths
to Dyck path
Mp00051
Ordered trees ⟶ Dyck paths
to Dyck path
Mp00056
Parking functions ⟶ Dyck paths
to Dyck path
Mp00093
Dyck paths ⟶ Binary words
to binary word
Mp00099
Dyck paths ⟶ Dyck paths
bounce path
Mp00100
Dyck paths ⟶ Integer compositions
touch composition
Mp00101
Dyck paths ⟶ Dyck paths
decomposition reverse
Mp00102
Dyck paths ⟶ Integer compositions
rise composition
Mp00103
Dyck paths ⟶ Dyck paths
peeling map
Mp00118
Dyck paths ⟶ Dyck paths
swap returns and last-descent
Mp00119
Dyck paths ⟶ Permutations
to 321-avoiding permutation (Krattenthaler)
Mp00120
Dyck paths ⟶ Dyck paths
Lalanne-Kreweras involution
Mp00121
Dyck paths ⟶ Dyck paths
Cori-Le Borgne involution
Mp00122
Dyck paths ⟶ Dyck paths
Elizalde-Deutsch bijection
Mp00123
Dyck paths ⟶ Dyck paths
Barnabei-Castronuovo involution
Mp00124
Dyck paths ⟶ Dyck paths
Mp00127
Permutations ⟶ Dyck paths
left-to-right-maxima to Dyck path
Mp00129
Dyck paths ⟶ Permutations
to 321-avoiding permutation (Billey-Jockusch-Stanley)
Mp00132
Dyck paths ⟶ Dyck paths
switch returns and last double rise
Mp00137
Dyck paths ⟶ Alternating sign matrices
to symmetric ASM
Mp00138
Dyck paths ⟶ Set partitions
to noncrossing partition
Mp00140
Dyck paths ⟶ Binary trees
logarithmic height to pruning number
Mp00141
Binary trees ⟶ Dyck paths
pruning number to logarithmic height
Mp00142
Dyck paths ⟶ Dyck paths
promotion
Mp00143
Dyck paths ⟶ Dyck paths
inverse promotion
Mp00146
Dyck paths ⟶ Perfect matchings
to noncrossing matching

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.