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 134 statistics on Dyck paths 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 of the Dyck path, with the initial positi....
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 the Dyck path, except for the path....
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.
St000998 Dyck paths ⟶ ℤ
Number of indecomposable projective modules with injective dimension smaller than....
St000999 Dyck paths ⟶ ℤ
Number of indecomposable projective module with injective dimension equal to the ....
St001000 Dyck paths ⟶ ℤ
Number of indecomposable modules with projective dimension equal to the global di....
St001001 Dyck paths ⟶ ℤ
The number of indecomposable modules with projective and injective dimension equa....
St001002 Dyck paths ⟶ ℤ
Number of indecomposable modules with projective and injective dimension at most ....
St001003 Dyck paths ⟶ ℤ
The number of indecomposable modules with projective dimension at most 1 in the N....
St001006 Dyck paths ⟶ ℤ
Number of isimple modules with projective dimension equal to the global dimension....
St001007 Dyck paths ⟶ ℤ
Number of simple modules with projective dimension 1 in the Nakayama algebra corr....
St001008 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with projective dimension 1 in the Nak....
St001009 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with projective dimension g when g is ....
St001010 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with projective dimension g-1 when g i....
St001011 Dyck paths ⟶ ℤ
Number of simple modules of projective dimension 2 in the Nakayama algebra corres....
St001012 Dyck paths ⟶ ℤ
Number of simple modules with projective dimension at most 2 in the Nakayama alge....
St001013 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with codominant dimension equal to the....
St001014 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with codominant dimension equal to the....
St001015 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with codominant dimension equal to one....
St001016 Dyck paths ⟶ ℤ
Number of indecomosable injective modules with codominant dimension at most 1 in ....
St001017 Dyck paths ⟶ ℤ
Number of indecomposable injective modules with projective dimension equal to the....
St001018 Dyck paths ⟶ ℤ
Sum of projective dimension of the indecomposable injective modules of the Nakaya....
St001019 Dyck paths ⟶ ℤ
Sum of the projective dimensions of the simple modules in the Nakayama algebra co....
St001020 Dyck paths ⟶ ℤ
Sum of the codominant dimensions of the non-projective indecomposable injective m....
St001021 Dyck paths ⟶ ℤ
Sum of the differences between projective and codominant dimension of the non-pro....
St001022 Dyck paths ⟶ ℤ
Number of simple modules with projective dimension 3 in the Nakayama algebra corr....
St001023 Dyck paths ⟶ ℤ
Number of simple modules with projective dimension at most 3 in the Nakayama alge....
St001024 Dyck paths ⟶ ℤ
Maximum of dominant dimensions of the simple modules in the Nakayama algebra corr....
St001025 Dyck paths ⟶ ℤ
Number of simple modules with projective dimension 4 in the Nakayama algebra corr....
St001026 Dyck paths ⟶ ℤ
The maximum of the projective dimensions of the indecomposable non-projective inj....
St001027 Dyck paths ⟶ ℤ
Number of simple modules with projective dimension equal to injective dimension i....
St001028 Dyck paths ⟶ ℤ
Number of simple modules with injective dimension equal to the dominant dimension....
St001031 Dyck paths ⟶ ℤ
The height of the bicoloured Motzkin path associated with the Dyck path.
St001032 Dyck paths ⟶ ℤ
The number of horizontal steps in the bicoloured Motzkin path associated with the....
St001033 Dyck paths ⟶ ℤ
The normalized area of the parallelogram polyomino associated with the Dyck path.....
St001034 Dyck paths ⟶ ℤ
The area of the parallelogram polyomino associated with the Dyck path.
St001035 Dyck paths ⟶ ℤ
The convexity degree of the parallelogram polyomino associated with the Dyck path....
St001036 Dyck paths ⟶ ℤ
The number of inner corners of the parallelogram polyomino associated with the Dy....
St001037 Dyck paths ⟶ ℤ
The number of inner corners of the upper path of the parallelogram polyomino asso....
St001038 Dyck paths ⟶ ℤ
The minimal height of a column in the parallelogram polyomino associated with the....
St001039 Dyck paths ⟶ ℤ
The maximal height of a column in the parallelogram polyomino associated with a D....
St001063 Dyck paths ⟶ ℤ
Numbers of 3-torsionfree simple modules in the corresponding Nakayama algebra.
St001064 Dyck paths ⟶ ℤ
Number of simple modules in the corresponding Nakayama algebra that are 3-syzygy ....
St001065 Dyck paths ⟶ ℤ
Number of indecomposable reflexive modules in the corresponding Nakayama algebra.....
St001066 Dyck paths ⟶ ℤ
The number of simple reflexive modules in the corresponding Nakayama algebra.
St001067 Dyck paths ⟶ ℤ
The number of simple modules of dominant dimension at least two in the correspond....
St001068 Dyck paths ⟶ ℤ
Number of torsionless simple modules in the corresponding Nakayama algebra.
St001088 Dyck paths ⟶ ℤ
Number of indecomposable projective non-injective modules with dominant dimension....
St001089 Dyck paths ⟶ ℤ
Number of indecomposable projective non-injective modules minus the number of ind....

6. Maps

We have the following 42 maps from and to Dyck paths 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.