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

Let $D$ be a Dyck path of size $n$.

St000013: The

**height**of $D$ is the largest $i$ for which $D$ touches the line $y=i$.St000025: The

**number of initial rises**of $D$ the number of consecutive up steps of $D$ starting from $(0,0)$.St000024: The

**number of double rises**of $D$ is the number of consecutive up steps. Note that the subsequence $1111$ contains $3$ double rises.St000015: The

**number of peaks**(**number of valleys**) of $D$ is the number of up steps (down steps) that are followed by a down step (an up step). The number of peaks of a Dyck path is always one larger than the number of valleys.The number of Dyck paths with exactly $k$ peaks is given by the $(n,k)$-th

**Narayana number**$\operatorname{Nar}_{n,k} = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}$ [Sul99].The number of Dyck paths with exactly $k$ valleys equals the number of Dyck paths with exactly $k$ double rises, see the involution decomposition reverse or the zeta map.

St000011: The

**number of touch points**of $D$ is the number of points where $D$ touches the diagonal x-axis $y=0$.The number of Dyck paths with exactly $k$ touch points is given by $\frac{k}{2n-k}\binom{2n-k}{n}$ [Deu99a].

The number of Dyck paths with exactly $k$ touch points equals the number of Dyck paths with exactly $k$ initial rises, see the involution decomposition reverse.

A

**tunnel**of $D$ is a horizontal segment between two lattice points of $D$ that intersects $D$ only in these two points, and stays always below $D$. A tunnel is**centered**if the $x$-coordinate of its midpoint is $n$. A left/right tunnel is defined similarly. The**number of left/centered/right tunnels**is defined accordingly [EP04].A

**pyramid**of the Dyck path is a part of the path consisting of $h$ $(1,1)$ steps followed by $h$ $(-1,1)$ steps. A pyramid is maximal if it is not immediately preceded by a $(1,1)$ step and followed by a $(-1,1)$ step. The**pyramid weight**is the sums of the heights of the maximal pyramids and the**number of exterior pairs**(the number of steps that are not part of a maximal pyramid) is the size of the Dyck path minus the pyramid weight. [DS92]

The following statistics have individual pages with further explanations:

St000005 and St000006: bounce and dinv [Hag08]

St000014: The number of parking functions

# 6. Maps

The

**reverse**of a Dyck path is the Dyck path obtained by horizontally flipping to (i.e., such that the points $(i,j)$ and $(2n-i,j)$ are interchanged).Obviously, this operation of Dyck paths of size $n$ is an involution.

In terms of Dyck words, this corresponds to sending a $(0,1)$-sequence $[d_1,d_2,\ldots,d_{2n}]$ to the sequence $[1-d_{2n},1-d_{2n-1},\ldots,1-d_1]$.

The

**partition**$\lambda(D) = (\lambda_1,\ldots,\lambda_{n-1})$ associated to a Dyck path $D$ is defined to be the complementary partition inside the staircase partition $(n-1,\ldots,2,1)$ when cutting out $D$ considered as a path from $(0,0)$ to $(n,n)$.In terms of Dyck words, $\lambda_{i}$ is the number of $0$'s before the $(n+1-i)$-th $1$.

This map describes a bijection between Dyck paths of size $n$ and partitions inside the staircase partition $(n-1,\ldots,2,1)$.

We have $\operatorname{area}(D) + |\lambda(D)| = \binom{n}{2}$.

The

**touch composition**is the composition corresponding to the set $\{ i-1 : a_i=0\hbox{ for }2 \leq i \leq n\}$, the**bounce composition**would be the composition corresponding to the touch points of the bounce path.

The following maps have individual pages with further explanations:

(area,dinv) to (bounce,area) map [LW02, Theorem 1]

# 7. References

*Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes*, Bull. London Math. Soc.,

**36**(2004), pp. 294-392.

[Deu99a] E. Deutsch, *Dyck path enumeration*, Discrete Math. **204** (1999).

[Deu99b] E. Deutsch, *An involution on Dyck paths and its consequences*, Discrete Math. **204** (1999), pp. 163-166.

[DS92] A. Denise, R. Simion, *Two combinatorial statistics on Dyck paths*, Discrete Math **137** (1992), 155-176.

[FH85] J. Fürlinger, J. Hofbauer, *q-Catalan numbers*, J. Combin. Theory Ser. A **40** (1985), no. 2, 248-264.

[Hag08] J. Haglund, *The q,t-Catalan Numbers and the Space of Diagonal Harmonics*, University Lecture Series, Amer. Math. Soc. **41** (2008) [ pdf ].

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

[LW02] N. Loehr, G. Warrington, *Square q, t-lattice paths and $\nabla(p_n)$*, Transactions of the AMS **359**(2) (2007).

[Mah15] P.A. MacMahon, *Combinatory analysis vol. 1*, Cambridge University Press (1915).

[Sul99] R.A. Sulanke, *Constraint-sensitive Catalan path statistics having the Narayana distribution*, Discrete Math. **204** (1999).

# 8. Sage examples