# Enumeration of Dyck paths with air pockets

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, Vincent Vajnovszki

► To cite this version:

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, Vincent Vajnovszki. Enumeration of Dyck paths with air pockets. Journal of Integer Sequences, 2023, 26. http://jис.ис.сciences.hal-03731272v2

HAL Id: hal-03731272

https://hal.science/hal-03731272v2

Submitted on 4 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

# Enumeration of Dyck Paths with Air Pockets

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki

LIB

Université de Bourgogne

B.P. 47 870

21078 Dijon-Cedex

France

barjl@u-bourgogne.fr

sergey.kirgizov@u-bourgogne.fr

remi_marechal01@etu.u-bourgogne.fr

vvajnov@u-bourgogne.fr

## Abstract

We introduce and study the new combinatorial class of Dyck paths with air pockets. We exhibit a bijection with the peakless Motzkin paths, which transports several pattern statistics, and give bivariate generating functions for the distribution of patterns as peaks, returns, and pyramids. Then we deduce the popularities and asymptotic expectations of these patterns, and point out a link between the popularity of pyramids and a special kind of closed smooth self-overlapping curves, a subset of Fibonacci meanders. Finally, we conduct a similar study for non-decreasing Dyck paths with air pockets.

# 1 Introduction and notation

Lattice paths are widely studied in combinatorics. They have many applications in various domains, such as computer science, biology, and physics [23], and they have very tight links with other combinatorial objects such as directed animals, pattern avoiding permutations, bargraphs, RNA structures, and so on [4, 11, 23]. A classical problem in combinatorics is the enumeration of these paths with respect to their length and other statistics [1, 2, 3, 7, 15, 16, 18, 20, 21]. In the literature, Dyck and Motzkin paths are the ones most often considered.
They are counted by the famous Catalan and Motzkin numbers (see A000108 and A001006 in Sloane's On-line Encyclopedia of Integer Sequences [22]). In 2005, Krinik et al. [13] introduced Dyck paths with catastrophes in the context of queuing theory. They correspond to the evolution of a queue by allowing some resets. The push (resp., pop) operation corresponds to a step $U = (1, 1)$ (resp., $D = (1, -1)$), and the reset operations are modeled by catastrophe steps $D_k = (1, -k)$ ending on x-axis, $k \ge 2$. Banderier and Wallner [1] studied these paths by providing enumerative results and limit laws.

In this paper, we introduce and study paths with air pockets corresponding to a queue evolution with partial reset operations that cannot be consecutive. These paths can also be viewed as airplane flights, sometimes showcasing turbulences that are known as *air pockets*, where consecutive turbulences are considered to be one. More formally, a *Dyck path with air pockets* is a nonempty lattice path in the first quadrant of $\mathbb{Z}^2$ starting at the origin, ending on the x-axis, and consisting of up-steps $U = (1, 1)$ and down-steps $D_k = (1, -k)$, $k \ge 1$, where two down steps cannot be consecutive. For short, we set $D = D_1$. The *length* of a Dyck path with air pockets is the number of its steps. Let $\mathcal{A}_n$ be the set of $n$-length Dyck paths with air pockets. By definition $\mathcal{A}_0 = \mathcal{A}_1 = \emptyset$ and we set $\mathcal{A} = \bigcup_{n \ge 2} \mathcal{A}_n$.

<figure><img src="image_3.png" /><figcaption>Figure 1: The Dyck path with air pockets $UUDUD_2UUUD_2UD_2UUD_2$.</figcaption></figure>

A Dyck path with air pockets is called *prime* whenever it ends with $D_k$, $k \ge 2$, and returns to the x-axis only once. The set of all prime Dyck paths with air pockets of length $n$ is denoted $\mathcal{P}_n$. Notice that $UD$ is not prime so we set $\mathcal{P} = \bigcup_{n \ge 3} \mathcal{P}_n$. If $\alpha = U\beta UD_k \in \mathcal{P}_n$, then $2 \le k < n$, $\beta$ is a (possibly empty) prefix of a path in $\mathcal{A}$, and we define the Dyck path with air pockets $\alpha^\flat = \beta UD_{k-1}$, called the 'lowering' of $\alpha$. For example, the path $\alpha = UUDUUD_3$ is prime, and $\alpha^\flat = UDUUD_2$. The map $\alpha \mapsto \alpha^\flat$ is clearly a bijection from $\mathcal{P}_n$ to $\mathcal{A}_{n-1}$ for all $n \ge 3$, and we let $\gamma^\sharp$ denote the inverse image of $\gamma \in \mathcal{A}_{n-1}$ ($\alpha^\sharp$ is a kind of 'elevation' of $\alpha$, drawing inspiration for the term from Deutsch's definition of elevated Dyck paths [7]). Any Dyck path with air pockets $\alpha \in \mathcal{A}$ can be decomposed depending on its *second-to-last return to the x-axis*: either

(i) $\alpha = UD$; or

(ii) $\alpha = \beta UD$ with $\beta \in \mathcal{A}$; or

(iii) $\alpha \in \mathcal{P}$; or

(iv) $\alpha = \beta\gamma$ where $\beta \in \mathcal{A}$ and $\gamma \in \mathcal{P}$.
So if $A(x) = \sum_{n \ge 2} a_n x^n$ where $a_n$ is the cardinality of $\mathcal{A}_n$, and $P(x) = \sum_{n \ge 3} p_n x^n$ where $p_n$ is the cardinality of $\mathcal{P}_n$, then we have $P(x) = xA(x)$ and the previous decompositions imply the functional equation $A(x) = x^2 + x^2A(x) + xA(x) + xA(x)^2$, and

$$A(x) = \frac{1 - x - x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1}}{2x}, \quad (1)$$

which generates the generalized Catalan numbers (see A004148 [22]), which among other things, counts the peakless Motzkin paths. The first values of $a_n$ for $2 \le n \le 10$ are 1, 1, 2, 4, 8, 17, 37, 82, 185. An asymptotic approximation for the coefficient of $x^n$ in the series expansion of $A(x)$ is

$$\frac{\sqrt{14\sqrt{5}-30}}{2n\sqrt{\pi n}(3-\sqrt{5})} \left(\frac{\sqrt{5}+3}{2}\right)^n.$$

If a Dyck path with air pockets $\alpha \in \mathcal{A}_n$ has $k \ge 1$ peaks (a peak is an occurrence $UD_i$ for some $i \ge 1$), then it contains $n-k$ up-steps. If we ‘unfurl’ all of its down-steps $D_i$, $i \ge 1$, into runs $D^i$ of $i$ consecutive $D$-steps, then we obtain a Dyck path of length $2(n-k)$ having $k$ peaks. This gives rise to a bijection between Dyck paths of semilength $n-k$ with $k$ peaks and $n$-length Dyck paths with air pockets with $k$ peaks. Hence, the number of $n$-length Dyck paths with air pockets with $k$ peaks is equal to the Narayana number $N(n-k, k) = \frac{1}{n-k} \binom{n-k}{k} \binom{n-k}{k-1}$ [7].

In the following, a *pattern* consists of consecutive steps in a path, and a *statistic* $\mathbf{s}$ is an integer-valued function from a set $\mathcal{S}$ of paths. Given a pattern $p$, we associate $p$ with the pattern statistic $\mathbf{p}: \mathcal{S} \to \mathbb{N}$ where $\mathbf{p}(a)$ is the number of occurrences of the pattern $p$ in $a \in \mathcal{S}$ (we use the boldface to denote statistics). For example, the statistic giving the number of occurrences of the consecutive pattern $UU$ in a path is denoted by $UU$. For $n \ge 1$, we let $\hat{\mathbf{n}}$ denote the constant statistic returning the value $n$. The *popularity* of a pattern $p$ in $\mathcal{S}$ is the total number of occurrences of $p$ over all objects of $\mathcal{S}$, that is $\mathbf{p}(\mathcal{S}) = \sum_{a \in \mathcal{S}} \mathbf{p}(a)$ [6, 9, 10]. Let $\mathcal{S}'$ be another set of combinatorial objects, we say that two statistics, $\mathbf{s}$ on $\mathcal{S}$ and $\mathbf{t}$ on $\mathcal{S}'$, have the *same distribution* if there exists a bijection $f: \mathcal{S} \to \mathcal{S}'$ satisfying $\mathbf{s}(a) = \mathbf{t}(f(a))$ for any $a \in \mathcal{S}$. In this case, with a slight abuse of the notation already used in the literature [5], we write $f(\mathbf{s}) = \mathbf{t}$ or $\mathbf{s} = \mathbf{t}$ whenever $f$ is the identity.

The remainder of this paper is organized as follows. In Section 2, we present a constructive bijection between $n$-length Dyck paths with air pockets and peakless Motzkin paths of length $n-1$, and we show how this bijection transports some statistics. In Section 3, we provide bivariate generating functions $A(x, y) = \sum_{n,k \ge 0} a_{n,k} x^n y^k$ for the distributions of some statistics $\mathbf{s}$, i.e., the coefficient $a_{n,k}$ of $x^n y^k$ is the number of paths $\alpha \in \mathcal{A}_n$ satisfying $\mathbf{s}(\alpha) = k$. Then we deduce the popularities of some patterns $(U, D, \text{peak}, \text{return}, \text{catastrophe}, \text{pyramid}, \dots)$ by calculating $\partial_y(A(x, y))|_{y=1}$, and we provide asymptotic approximations for them using classical methods [8, 17]. We refer to Table 1 for an overview of the results. As a byproduct, we point out a link between the popularity of pyramids and a special kind of closed smooth self overlapping curves in the plane (a subset of Fibonacci meanders defined
by Luschny and Wienand on their web pages [14, 24]). In Section 4, we make a similar study for non-decreasing Dyck paths with air pockets.

<table><caption>Table 1: Pattern popularity in $A_n$, for $2 \le n \le 11$.</caption><thead><tr><th>Pattern</th><th>Pattern popularity in A<sub>n</sub></th><th>OEIS</th></tr></thead><tbody><tr><td>U</td><td>1, 2, 5, 13, 32, 80, 201, 505, 1273, 3217</td><td>A110320</td></tr><tr><td>D</td><td>1, 0, 2, 3, 7, 17, 40, 97, 238, 587</td><td>A051291</td></tr><tr><td>Peak</td><td>1, 1, 3, 7, 16, 39, 95, 233, 577, 1436</td><td>A203611</td></tr><tr><td>Ret</td><td>1, 1, 3, 6, 13, 29, 65, 148, 341, 793</td><td>A093128</td></tr><tr><td>Cat</td><td>0, 1, 1, 4, 8, 19, 44, 102, 239, 563</td><td></td></tr><tr><td>Δ<sub>k</sub></td><td>0, ..., 0, 1, 0, 2, 3, 7, 17, 40, 97, 238, 587</td><td>A051291</td></tr><tr><td>Δ<sub>≥k</sub></td><td>0, ..., 0, 1, 1, 3, 6, 13, 30, 70, 167, 405</td><td>A201631(= u<sub>n</sub>)</td></tr><tr><td>Δ<sub>≤k</sub></td><td>Δ<sub>≤1</sub> 1, 0, 2, 3, 7, 17, 40, 97, 238, 587<br>Δ<sub>≤2</sub> 1, 1, 2, 5, 10, 24, 47, 137, 335, 825, ...<br>Δ<sub>≤3</sub> 1, 1, 3, 5, 12, 27, 64, 154, 375, 922, ...<br>⋮</td><td>u<sub>n</sub> - u<sub>n-k</sub></td></tr></tbody></table>

## 2 Bijection with peakless Motzkin paths

In this section we exhibit a constructive bijection between $n$-length Dyck paths with air pockets and $(n-1)$-length peakless Motzkin paths, i.e., lattice paths in the first quarter plane starting at the origin, ending at $(n-1, 0)$, made up of $U$, $D$ and $F = (1, 0)$ and having no occurrence of $UD$. Moreover, we show how our bijection transports some pattern based statistics. We let $M_n$ denote the set of peakless Motzkin paths of length $n$, and $M = \cup_{n \ge 1} M_n$.

**Definition 1.** We recursively define the map $\psi$ from $A$ to $M$ as follows. For $\alpha \in A$, we set

$$ \psi(\alpha) = \begin{cases} F, & \text{if } \alpha = UD; \tag{i} \\ U\psi(\beta)D, & \text{if } \alpha = \beta UD, \text{ with } \beta \in A; \tag{ii} \\ \psi(\alpha^\flat)F, & \text{if } \alpha \in \mathcal{P}; \tag{iii} \\ \psi(\gamma^\flat)U\psi(\beta)D, & \text{if } \alpha = \beta\gamma, \text{ with } \beta \in A \text{ and } \gamma \in \mathcal{P}. \tag{iv} \end{cases} $$

Notice that each factor in the above decomposition is nonempty, and that $\psi$ maps nonempty objects to nonempty ones. Due to the recursive definition, the image by $\psi$ of a $n$-length Dyck path with air pockets is a peakless Motzkin path of length $n-1$. For instance, the images of $UD$, $UUD_2$, $UUUD_2UD_2UD$ are respectively $F$, $FF$, and $UUFFDFFD$. We refer to Figure 2 for an illustration of this mapping.
<figure><img src="image_4.png" /><figcaption>Figure 2: Illustration of the map $\psi$ according to Definition 1.</figcaption></figure>

**Theorem 2.** For all $n \ge 2$, the map $\psi$ induces a bijection between $\mathcal{A}_n$ and $\mathcal{M}_{n-1}$.

*Proof.* It is well known that the cardinality of $\mathcal{M}_n$ is given by the $n$-th term of generalized Catalan number (see A004148 [22]). So it suffices (see observation after relation (1)) to prove the injectivity of $\psi$. We proceed by induction on $n$. The case $n = 2$ is obvious since $\mathcal{A}_2 = \{UD\}$ and $\mathcal{M}_1 = \{F\}$. For all $k \le n$, we assume that $\psi$ is an injection from $\mathcal{A}_k$ to $\mathcal{M}_{k-1}$, and we prove the result for $k = n + 1$. According to Definition 1, if $\alpha$ and $\beta$ in $\mathcal{A}_{n+1}$ satisfy $\psi(\alpha) = \psi(\beta)$, then $\alpha$ and $\beta$ necessarily come from the same case among (i)-(iv). Using the induction hypothesis, we conclude directly that $\alpha = \beta$, which completes the induction. Thus $\psi$ is injective and so bijective. $\square$

**Proposition 3.** For all $n \ge 2$ and $k \ge 1$, and $\psi : \mathcal{A}_n \to \mathcal{M}_{n-1}$, the following hold:

$$ \bullet \psi(U) = F + U = F + D $$

$$ \bullet \psi(D) = \psi(UD) = 1_F + UFD + 1_{UMD} + U^2MD^2 $$

$$ \bullet \psi(DU) = UFD + U^2MD^2 $$

$$ \bullet \psi(UU) = F - \hat{1} $$

$$ \bullet \psi(\Delta_k) = 1_{F^k} + UF^kD + 1_{F^{k-1}UMD} + UF^{k-1}UMD^2 $$

$$ \bullet \psi(\text{Peak}) = U + \hat{1} $$

$$ \bullet \psi(\text{Ret}) = \hat{n} - \text{LastF} $$

$$ \bullet \psi(\text{SLast}) = \text{Ret}, $$

where

$\bullet 1_\beta(\alpha) = 1$ if $\alpha = \beta$ and 0 otherwise;

$\bullet 1_{UMD}(\alpha)$ is equal to 1 if there exists $\beta \in \mathcal{M}$ such that $\alpha = U\beta D$ and 0 otherwise;

$\bullet U^2MD^2(\alpha)$ is the number of occurrences $U^2\beta D^2$ in $\alpha$ for $\beta \in \mathcal{M}$;
• $\mathbf{\Delta}_k(\alpha)$ is the number of occurrences $U^k D_k$ in $\alpha$;

• $\text{Peak}(\alpha) = \sum_{k \ge 1} \text{UD}_k(\alpha);$

• $\text{Ret}(\alpha)$ is the number of returns to the x-axis of $\alpha$;

• $\text{LastF}(\alpha)$ is the position of the rightmost flat-step in $\alpha$; and

• $\text{SLast}(\alpha)$ is the size of the last step of $\alpha$ (i.e., $k$ if the last step is $D_k$).

*Proof.* We provide the proof for $\psi(\mathbf{U})$ and $\psi(\mathbf{\Delta}_k)$ since those for the other relations can be obtained, mutatis mutandis.

We proceed by induction on $n$. Since $\mathcal{A}_2 = \{\text{UD}\}$ and $\mathcal{M}_1 = \{F\}$ the statements trivially hold for $n=2$. Now assume the statements are true for all $k \le n$ and let us prove them for $n+1$.

If $\alpha \in \mathcal{A}_{n+1}$ with $n \ge 2$, then we have either

(i) $\alpha = \beta \text{UD};$

(ii) $\alpha = \gamma^{\sharp}$; or

(iii) $\alpha = \beta\gamma^{\sharp}$ where $\beta, \gamma \in \mathcal{A}$.

In case (i), we have $\mathbf{U}(\beta \text{UD}) = 1 + \mathbf{U}(\beta)$ and with the induction hypothesis, $\mathbf{U}(\beta \text{UD}) = 1 + (\mathbf{U} + \mathbf{F})(\psi(\beta)) = (\mathbf{U} + \mathbf{F})(U\psi(\beta)D) = (\mathbf{U} + \mathbf{F})(\psi(\beta \text{UD}))$ as expected.

In case (ii), we have $\mathbf{U}(\gamma^{\sharp}) = 1 + \mathbf{U}(\gamma)$ and with the induction hypothesis, $\mathbf{U}(\gamma^{\sharp}) = 1 + (\mathbf{U} + \mathbf{F})(\psi(\gamma)) = (\mathbf{U} + \mathbf{F})(\psi(\gamma)F) = (\mathbf{U} + \mathbf{F})(\psi(\gamma^{\sharp}))$.

Case (iii) is handled in the same way.

So we have $\psi(\mathbf{U}) = \mathbf{U} + \mathbf{F}$. Using similar reasoning, we can easily prove $\psi(\mathbf{D}) = \mathbb{1}_{\mathbf{F}} + \mathbf{UFD} + \mathbb{1}_{\mathbf{UMD}} + \mathbf{U}^2\mathcal{M}\mathbf{D}^2$.

Now let us give details for the slightly less straightforward case of $\psi(\mathbf{\Delta}_k)$ for $k \ge 1$. The case $k=1$ is already handled since we have $\psi(\text{UD}) = \psi(\mathbf{D})$. So we assume $k \ge 2$. We consider the following case analysis: any given Dyck path with air pockets is either of the form

(i) $\beta \text{UD}$;

(ii) $\beta \Delta_{k-1}^{\sharp}$;

(iii) $\beta \Delta_k^{\sharp}$;

(iv) $\beta(\alpha \Delta_k)^{\sharp}$ with $\alpha \in \mathcal{A}$; or

(v) $\beta \alpha^{\sharp}$ with $\alpha \in \mathcal{A}$ being neither $\Delta_{k-1}$, nor $\Delta_k$, nor $\alpha' \Delta_k$ ($\alpha' \in \mathcal{A}$), and $\beta \in \mathcal{A} \cup \{\varepsilon\}$.
Reasoning by induction, case (ii) unfolds as follows: if $\beta = \varepsilon$, then we get

$$ (\mathbb{1}_{\mathbb{F}^k} + \mathbf{UF}^k\mathbf{D} + \mathbb{1}_{\mathbb{F}^{k-1}\mathcal{UMD}} + \mathbf{UF}^{k-1}\mathcal{UMD}^2)(F^k) = 1, $$

which is the same as $\Delta_k(\Delta_{k-1}^\sharp)$. Otherwise, we have

$$ \begin{aligned} & (\mathbb{1}_{\mathbb{F}^k} + \mathbf{UF}^k\mathbf{D} + \mathbb{1}_{\mathbb{F}^{k-1}\mathcal{UMD}} + \mathbf{UF}^{k-1}\mathcal{UMD}^2)(\psi(\beta\Delta_{k-1}^\sharp)) \\ &= (\mathbb{1}_{\mathbb{F}^k} + \mathbf{UF}^k\mathbf{D} + \mathbb{1}_{\mathbb{F}^{k-1}\mathcal{UMD}} + \mathbf{UF}^{k-1}\mathcal{UMD}^2)(F^{k-1}\mathcal{U}\psi(\beta)D) \\ &= \mathbb{1}_{\mathbb{F}^k}(\psi(\beta)) + \mathbf{UF}^k\mathbf{D}(\psi(\beta)) + 1 + \mathbb{1}_{\mathbb{F}^{k-1}\mathcal{UMD}}(\psi(\beta)) \\ &\quad + \mathbf{UF}^{k-1}\mathcal{UMD}^2(\psi(\beta)) \\ &= 1 + \Delta_k(\beta) = \Delta_k(\beta\Delta_{k-1}^\sharp). \end{aligned} $$

The four remaining cases are obtained in the same way. □

Notice that the mirror of a Dyck path with air pockets is a Łukasiewicz path avoiding flat steps and two consecutive up-steps. Since there is a bijection between Łukasiewicz paths and plane trees [12], we easily deduce that Dyck paths with air pockets are in one-to-one correspondence with plane trees without unary nodes, and such that the first child of any node is always a leaf. We leave open the question of knowing how this bijection transports some pattern-based statistics.

# 3 Distribution and popularity of patterns

## 3.1 The numbers of U and D

**Theorem 4.** Let $A(x, y, z) = \sum_{n,k,\ell \ge 0} a_{n,k,\ell} x^n y^k z^\ell$ be the generating function (g.f.) where $a_{n,k,\ell}$ is the number of paths in $\mathcal{A}_n$ having $k$ up-steps U and $\ell$ down-steps D = $D_1$. Then the following holds:

$$ A(x, y, z) = \frac{1 - xy - x^2yz - 2x^3y^2 + 2x^3y^2z - \sqrt{R}}{2xy(1 + x^2y - x^2yz)}, $$

with

$$ R = x^4 y^2 z^2 + 2x^3 y^2 z - 4x^3 y^2 + x^2 y^2 - 2x^2 yz - 2xy + 1. $$

*Proof.* Due to the first return decomposition, any Dyck path with air pockets has one of the following forms:

(i) $UD\gamma$;

(ii) $U^2D_2\gamma$;

(iii) $(\alpha UD)^\sharp\gamma$ with $\alpha \in \mathcal{A}$; or
(iv) $\alpha^{\#}\gamma$ with $\alpha \in \mathcal{A}$ not being UD nor $\beta UD$ ($\beta \in \mathcal{A}$), where $\gamma \in \mathcal{A} \cup \{\varepsilon\}$.

These four cases are disjoint and cover $\mathcal{A}$ entirely. Then we deduce the functional equation by taking into account the length, and the numbers of $U$ and $D$ with respect to $x$, $y$ and $z$:

$$A = \underbrace{(x^2yz + x^3y^2 + x^3y^2A + xy(A - x^2yz(1+A)))}_{(i)}(1+A), \quad (ii) \quad (iii) \quad (iv)$$

where $A$ stands for $A(x, y, z)$. Solving for $A$, we get the result. $\square$

**Corollary 5.** For all $n \ge 1$, the number of Dyck paths with air pockets (of any length) having $n$ up-steps $U$ is the $n$-th Catalan number $\frac{1}{n+1} \binom{2n}{n}$ (see A000108 [22]).

*Proof.* We check that $1 + A(1, y, 1)$ is the g.f. of the Catalan numbers. $\square$

**Corollary 6.** For all $n \ge 1$, the number of Dyck paths with air pockets having $n$ up-steps $U$ and no down-steps $D$ is the $n$-th Riordan number $\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} c_k$, where $c_k = \frac{1}{k+1} \binom{2k}{k}$ (see A005043 in [22]).

*Proof.* We check that $1 + A(1, y, 0)$ is the g.f. of the Riordan numbers. $\square$

**Corollary 7.** The g.f. for the popularity of up-steps $U$ in $\mathcal{A}_n$ is

$$\frac{1 - x - x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1}}{2x\sqrt{x^4 - 2x^3 - x^2 - 2x + 1}},$$

which generates a shift of the sequence A110320 [22]. An asymptotic approximation of the $n$-th term is

$$\frac{\sqrt{5} - 1}{2\sqrt{\pi n}\sqrt{14\sqrt{5} - 30}} \left( \frac{3 + \sqrt{5}}{2} \right)^n,$$

and an asymptotic for the expectation of the up-step number is

$$\frac{\sqrt{5} + 5}{10} n \sim 0.723606799 \cdot n.$$

*Proof.* The g.f. is given by $\partial_y(A(x, y, 1))|_{y=1}$. The asymptotic approximation is obtained using classical methods [8, 17]. $\square$

**Corollary 8.** The g.f. for the popularity of down-steps $D = D_1$ in $\mathcal{A}_n$ is

$$\frac{x^2(1 + 2x^2 - x^3 + (1-x)\sqrt{x^4 - 2x^3 - x^2 - 2x + 1})}{2\sqrt{x^4 - 2x^3 - x^2 - 2x + 1}},$$
which generates a shift of the sequence A051291 [22]. An asymptotic approximation of the n-th term is

$$ \frac{5\sqrt{5}-11}{2\sqrt{\pi n}\sqrt{14\sqrt{5}-30}} \left( \frac{3+\sqrt{5}}{2} \right)^n, $$

and an asymptotic for the expectation of the D-step number is

$$ \frac{5-2\sqrt{5}}{5}n \sim 0.105572797 \cdot n. $$

*Proof.* The g.f. is given by $\partial_z(A(x, 1, z))|_{z=1}$. $\square$

## 3.2 The number of peaks

In this part, we study the distribution of peaks, i.e., patterns $UD_m$ for $m \ge 1$.

**Theorem 9.** Let $P(x, y) = \sum_{n,k \ge 0} p_{n,k} x^ny^k$ be the g.f. where $p_{n,k}$ is the number of n-length Dyck paths with air pockets having $k$ peaks. Then we have

$$ P(x, y) = \frac{1 - x - x^2 y - \sqrt{(1 - x - x^2 y)^2 - 4x^3 y}}{2x}, $$

which generates a shift of the sequence A089732 [22].

*Proof.* If a Dyck path with air pockets equals $\alpha UD$ with $\alpha \in A \cup \{\varepsilon\}$, then its contribution to $P(x, y)$ is $(1 + P(x, y))x^2y$; if it has the form $\alpha \beta^\sharp$ with $\beta \in A$, then its contribution is $(1 + P(x, y))xP(x, y)$. Hence, the second-to-last return decomposition yields

$$ P(x, y) = (1 + P(x, y))(x^2y + xP(x, y)), $$

which gives the result after solving for $P(x, y)$. $\square$

**Corollary 10.** The g.f. for the popularity of peaks in $A_n$ is

$$ \frac{x(1 + x - x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1})}{2\sqrt{x^4 - 2x^3 - x^2 - 2x + 1}}, $$

which generates a shift of the sequence A203611 [22]. An asymptotic approximation of the n-th term is

$$ \frac{\sqrt{5}-2}{\sqrt{\pi n}\sqrt{14\sqrt{5}-30}} \left( \frac{3+\sqrt{5}}{2} \right)^n, $$

and an asymptotic for the expectation of the peak number is

$$ \frac{5-\sqrt{5}}{10}n \sim 0.276393191 \cdot n. $$
Remark 11. Another way of finding the total number of peaks in all Dyck paths with air pockets of length $n$ is the following: since the number of $n$-length Dyck paths with air pockets with $k$ peaks is $N(n-k,k)$, we have

$$ \text{Peak}(\mathcal{A}_n) = \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} kN(n-k,k) = \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} \frac{k}{n-k} \binom{n-k}{k} \binom{n-k}{k-1}. $$

Using the formula for the sequence A203611 [22], we get the following identity:

$$ \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} \binom{n-k-1}{k-1} \binom{n-k}{k-1} = \sum_{k=0}^{n-1} \binom{k-1}{2k-n} \binom{k}{2k-n+1}. $$

## 3.3 The number of returns to the x-axis

A return to the $x$-axis is a step $D_m$, $m \ge 1$, ending on the $x$-axis.

**Theorem 12.** Let $R(x, y) = \sum_{n,k \ge 0} r_{n,k} x^n y^k$ be the g.f. where $r_{n,k}$ is the number of $n$-length Dyck paths with air pockets with $k$ returns. Then:

$$ R(x, y) = \frac{2}{2 - y(1 - x + x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1})} - 1, $$

which generates the triangle A098086 [22] where the row $n$ and column $k$ gives the number of peakless Motzkin paths having its leftmost F-step on the $k$-th step (see also Proposition 3).

*Proof.* If a Dyck path with air pockets equals $\alpha U D$ with $\alpha \in \mathcal{A} \cup \{\varepsilon\}$, then its contribution to $R(x, y)$ is $(1 + R(x, y))x^2y$; if it has the form $\alpha\beta^k$ with $\beta \in \mathcal{A}$, then its contribution is $(1 + R(x, y))xyA(x)$. So we deduce that

$$ R(x, y) = (1 + R(x, y))(x^2y + xyA(x)), $$

which gives the result using relation (1).

<figure><img src="image_5.png" /></figure>

**Corollary 13.** The g.f. for the popularity of returns to the $x$-axis in $\mathcal{A}_n$ is

$$ 2 \frac{1 - x + x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1}}{(1 + x - x^2 + \sqrt{x^4 - 2x^3 - x^2 - 2x + 1})^2}, $$

which corresponds to the sequence A093128 [22], where the $n$-th term counts all possible dissections of a regular $(n+2)$-gon using zero or more strictly disjoint diagonals. An asymptotic approximation of the $n$-th term is

$$ \frac{\sqrt{14\sqrt{5} - 30\sqrt{5}}}{4n\sqrt{\pi n}} \left( \frac{3 + \sqrt{5}}{2} \right)^{n+1}, $$

and an asymptotic for the expectation of the return number is $\sqrt{5}$.
## 3.4 The number of catastrophes

A catastrophe is a step $D_m$, $m \ge 2$, ending on the x-axis.

**Theorem 14.** Let $C(x, y) = \sum_{n,k \ge 0} c_{n,k} x^n y^k$ be the g.f. where $c_{n,k}$ is the number of n-length Dyck paths with air pockets with k catastrophes. Then we have

$$C(x, y) = \frac{2}{2 - 2x^2 - y(1 - x - x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1})} - 1.$$

*Proof.* If a Dyck path with air pockets equals $\alpha UD$ with $\alpha \in \mathcal{A} \cup \{\varepsilon\}$, then its contribution to $C(x, y)$ is $(1 + C(x, y))x^2$; if it has the form $\alpha\beta^\#$ with $\beta \in \mathcal{A}$, then its contribution is $(1 + C(x, y))xyA(x)$. So we deduce $C(x, y) = (1 + C(x, y))(x^2 + xyA(x))$. $\square$

**Corollary 15.** The g.f. for the popularity of catastrophes in $\mathcal{A}_n$ equals

$$2 \frac{1 - x - x^2 - \sqrt{x^4 - 2x^3 - x^2 - 2x + 1}}{(1 + x - x^2 + \sqrt{x^4 - 2x^3 - x^2 - 2x + 1})^2}.$$

An asymptotic approximation of the n-th term is

$$\frac{\sqrt{14\sqrt{5} - 30}(4 - \sqrt{5})}{4n\sqrt{\pi n}} \left( \frac{3 + \sqrt{5}}{2} \right)^{n+1},$$

and an asymptotic for the expectation of the catastrophe number is $4 - \sqrt{5}$.

*Remark 16.* As a byproduct of Corollaries 13 and 15, the ratio of the popularity of catastrophes in $\mathcal{A}_n$ to the popularity of returns in $\mathcal{A}_n$ tends to $\frac{4-\sqrt{5}}{\sqrt{5}} = 0.788854...$ when $n$ tends toward $\infty$.

## 3.5 The number of pyramids $U^k D_k$

A k-pyramid $\Delta_k$ in a path is an occurrence of the pattern $U^k D_k$, $k \ge 1$.

**Theorem 17.** For all $k \ge 1$, the g.f. $P_k(x, y) = \sum_{n,m \ge 0} p_{n,m}^k x^n y^m$ where $p_{n,m}^k$ is the number of n-length Dyck paths with air pockets having m k-pyramids is given by

$$P_k(x, y) = \frac{x^{k+1}(y-1) - 2x^{k+2}(y-1) + x^2 + x - 1 + \sqrt{Q}}{2(x^{k+2}(y-1) - x)},$$

where

$$Q = x^{k+1}(y-1)(x^{k+1}(y-1) + 4x + 2(x^2 - x - 1)) + x^4 - 2x^3 - x^2 - 2x + 1.$$

*Proof.* We refine the first return decomposition so that any Dyck path with air pockets falls into one of the following cases:
(i) $\Delta_m\gamma$ with $1 \le m \le k-1$;

(ii) $\Delta_k\gamma$;

(iii) $\Delta_{k+1}\gamma$;

(iv) $(\alpha\Delta_k)^{\#}\gamma$ with $\alpha \in \mathcal{A}$;

(v) $\beta^{\#}\gamma$ with $\beta \in \mathcal{A}$ not being $\Delta_m$ with $1 \le m \le k$, nor $\alpha\Delta_k$ with $\alpha \in \mathcal{A}$, where $\gamma \in \mathcal{A} \cup \{\varepsilon\}$.

These five cases are disjoint and cover all Dyck paths with air pockets. So we deduce

$$P_k = \underbrace{(\sum_{i=2}^{k} x^i + x^{k+1}y + x^{k+2} + x^{k+2}P_k + x \cdot (P_k - \sum_{i=2}^{k} x^i - x^{k+1}y(1+P_k)))}_{(v)} (1+P_k), \underbrace{\underbrace{(\sum_{i=2}^{k} x^i + x^{k+1}y + x^{k+2} + x^{k+2}P_k + x \cdot (P_k - \sum_{i=2}^{k} x^i - x^{k+1}y(1+P_k)))}_{(v)} (1+P_k), \dots$$

where $P_k$ stands for $P_k(x, y)$. Solving for $P_k$, we get the result. $\square$

**Corollary 18.** For $k \ge 1$, the g.f. for the popularity $\Delta_k(\mathcal{A}_n)$ of k-pyramids in $\mathcal{A}_n$ equals

$$Y_k(x) = \frac{x^{k+1}(1 + 2x^2 - x^3 + (1-x)\sqrt{x^4 - 2x^3 - x^2 - 2x + 1})}{2\sqrt{x^4 - 2x^3 - x^2 - 2x + 1}},$$

which generates the $(n-k-2)$-th term of the sequence A051291 [22]. In particular, we have $\Delta_1(\mathcal{A}_n) = \Delta_k(\mathcal{A}_{n+k-1})$ for all $k \ge 1$ and $n \ge 2$, which means that there are as many 1-pyramids in $\mathcal{A}_n$ as there are k-pyramids in $\mathcal{A}_{n+k-1}$. An asymptotic approximation of the n-th term of this sequence is

$$\frac{\sqrt{5}-1}{2\sqrt{\pi n}\sqrt{14\sqrt{5}-30}} \left(\frac{3+\sqrt{5}}{2}\right)^{n-k-1},$$

and for the expected number of k-pyramids we have

$$\frac{5-\sqrt{5}}{10} \left( \frac{3-\sqrt{5}}{2} \right)^k \cdot n.$$

Notice that $Y_1(x)$ corresponds to the generating function for the popularity of down-steps $D$ (see Corollary 7), since each $D$ is necessarily preceded by an up-step. Moreover, we have $Y_k(x) = x^{k-1}Y_1(x)$ since each pyramid $\Delta_k$ in a path of length $n$ comes from a pyramid $\Delta_1$ in a path of length $n-k+1$ by adding $k-1$ up-steps and by increasing the length of the down-step. An immediate consequence of Corollary 18 is the following.
**Corollary 19.** For $k \ge 1$, the g.f. for the popularities $\Delta_{\ge k}(\mathcal{A}_n)$ and $\Delta_{\le k}(\mathcal{A}_n)$ are respectively given by

$$Y_{\ge k}(x) = \frac{x^{k-1}}{1-x} Y_1(x) \quad \text{and} \quad Y_{\le k}(x) = \frac{1-x^k}{1-x} Y_1(x),$$

which means that $\Delta_{\le k}(\mathcal{A}_{n-k+1}) = \Delta_{\ge k}(\mathcal{A}_n) - \Delta_{\ge k}(\mathcal{A}_{n-k})$.

For any $k \ge 1$, the popularity of pyramids of size at least $k$ in $\mathcal{A}_n$ (see Corollary 19) seems to correspond to a shift of the sequence A201631 [22], which enumerates Fibonacci meanders with central angle 180 degrees (see Luschny's [14] and Wienand's [24] posts in OEIS Wiki about meanders). In order to prove this fact, we give the formal definition of such meanders, and provide their g.f. that does not exist in the literature (to our knowledge).

A Fibonacci meander with central angle 180 degrees is a closed smooth self-overlapping curve in the plane, consisting of an even length sequence of two types of arcs of angle 180 degrees, namely $L = \Uparrow$ and $R = \Downarrow$, starting at the origin with an $L$-arc toward the north, having no consecutive $L$-arcs except at the beginning where a run (of any length) of consecutive $L$-arcs is authorized. Each arc starts at the end of the previous arc and it preserves the direction of its arrow, i.e., $LLR$ corresponds to $\Uparrow$. Let $\mathcal{F}_{2n}$ be the set of such meanders of length $2n$. For instance, the left part of Figure 3 illustrates a meander in $\mathcal{F}_{20}$.

<figure><img src="image_6.png" /><figcaption>Figure 3: A Fibonacci meander in $\mathcal{F}_{20}$ where the sequence of arcs is given by $LLLLRRLRRLRLRRRLRLR$, and its associated lattice path.</figcaption></figure>

Now we define a function $\tau$, mapping a two-letter word over the alphabet $\{L, R\}$ into the set $\{U, D, F, \tilde{F}\}$:

$$\tau(a) = \begin{cases} U, & \text{if } a = RL; \\ D, & \text{if } a = LR; \\ F, & \text{if } a = RR; \\ \tilde{F}, & \text{if } a = LL. \end{cases}$$

and a function $\mu$, mapping a meander $w = w_1w_2\cdots w_{2n} \in \mathcal{F}_{2n}$ into an $n$-length word over the alphabet $\{U, D, F, \tilde{F}\}$:

$$\mu(w) = \tau(w_1w_2)\tau(w_3w_4)\cdots\tau(w_{2n-1}w_{2n}).$$
Grand Motzkin paths are lattice paths of length $n$ in $\mathbb{N} \times \mathbb{Z}$, consisting of steps $U = (1, 1)$, $D = (1, -1)$, and $F = (1, 0)$, starting at $(0, 0)$, ending at $(n, 0)$ (contrarily to classical Motzkin paths, they can go below the $x$-axis). For instance $DUUDDFDUUUD$ is a grand Motzkin path of length 11. Let $G_n$ be the set of peakless (i.e., with no occurrence of $UD$) grand Motzkin paths of length $n$ and $N_n$ be the subset of paths starting with a $D$-step in $G_n$. Let $S_n$ denote the set of peakless grand Motzkin paths of length $n$ starting with a down step or prefixed by a nonempty sequence of special flats, called wavy flats, $\tilde{F} = (1, 0)$. For instance, $\tilde{F}\tilde{F}DUUDDFDUUUD \in S_{13}$.

**Proposition 20.** The function $\mu$ induces a bijection from $\mathcal{F}_{2n}$ to $S_n$.

*Proof.* Every meander $a \in \mathcal{F}_{2n}$ avoids the pattern $LL$ except if the occurrence of $LL$ is only preceded by letters $L$, which means that $\mu(a)$ avoids the pattern $UD$. If the meander $a$ starts with a maximal prefix of the form $(LL)^k$, $k \ge 1$, then $\mu(a)$ starts, with a maximal sequence of $k$ wavy flats, $\tilde{F}^k$. If the meander $a$ starts with $LR$, then $\mu(a)$ starts with $D$. Moreover, the image by $\mu$ of a factor $RR$ is $F = \tau(RR)$ in $\mu(a)$, the image of $LR$ is $D$ and the image of $RL$ is $U$. Thus, the fact that $a$ is a closed curve, implies that $\mu(a)$ starts and ends on $x$-axis. Due to all these observations, $\mu$ is necessarily a bijection from $\mathcal{F}_{2n}$ to $S_n$. $\square$

Notice that the bijection $\mu$ is very close to the bijection of Roitner [19] between 2-watermelons with arbitrary deviation and weighted Motzkin paths, which suggests that there are tight links between 2-watermelons and Wienand-Luschny meanders. It would be interesting to explore this correspondence in future work.

**Theorem 21.** The g.f. $S(x) = \sum_{n \ge 0} s_n x^n$, where the coefficient $s_n$ is the number of 2n-length Fibonacci meanders with a central angle 180 degrees, is

$$S(x) = \frac{x^2 - x + 1 - \sqrt{R}}{(x-1)(R + (x^2 - x - 1)\sqrt{R})},$$

with $R = x^4 - 2x^3 - x^2 - 2x + 1$. Using Corollary 19, we have

$$S(x) = \frac{Y_1(x)}{x^2(1-x)} - 1,$$

which establishes the expected link between Fibonacci meanders and the popularity $\Delta_{\ge k}(A_n)$.

*Proof.* Considering Proposition 20, it suffices to enumerate $S_n$. We set $G = \bigcup_{n \ge 0} G_n$, $N = \bigcup_{n \ge 0} N_n$, and $S = \bigcup_{n \ge 0} S_n$. Recall that $M$ is the set of nonempty peakless Motzkin paths. Let $V$ denote the set of Motzkin paths without valleys $DU$ and by $\bar{V}$ the set of paths obtained by symmetry about the $x$-axis ($U \leftrightarrow D$) of valleyless Motzkin paths, e.g., $DUF DU \in \bar{V}$ since it is symmetric to $UDFUD \in V$. Let $W$ be the set of nonempty sequences of wavy flat steps. We use $M(x), V(x) = \bar{V}(x), G(x), N(x), W(x)$ to denote the corresponding generating functions with respect to the length.
Obviously, we have $W(x) = \frac{x}{1-x}$. From Relation (1) and Theorem 2 we obtain $M(x) = A(x)/x$. Also, there is a one-to-one correspondence $\nu$ between $M_n$ and $V_{n-1}$ that can be defined recursively by $\nu(F) = \varepsilon$, $\nu(FQ) = F\nu(Q)$, $\nu(UQD) = U\nu(Q)D$, and $\nu(UQDR) = U\nu(Q)DF\nu(R)$ if $R$ is non-empty. So we have $V(x) = M(x)/x = A(x)/x^2$. Finally, we decompose $G$, $N$ and $S$ as illustrated below:

<figure><img src="image_7.png" /></figure>

which induces the following system of functional equations:

$$ egin{cases} G(x) = 1 + xG(x) + x^2M(x)G(x) + N(x); \\ N(x) = x^2V(x) + x^4V(x)M(x)G(x) + x^3V(x)G(x); \\ S(x) = W(x)G(x) + N(x). \end{cases} $$

Solving this system, we obtain $S(x)$. $\square$

# 4 Non-decreasing Dyck paths with air pockets

A Dyck path with air pockets is non-decreasing if the sequence of heights of its valleys is non-decreasing, i.e., the sequence of the minimal ordinates of the occurrences $D_kU$, $k \ge 1$, is non-decreasing from left to right [2]. For example, the Dyck path with air pockets $UUDUDUD_2$ is non-decreasing, since its two valleys both lie at height 1, while the path $UUDUD_2UD$ is not, since its two valleys lie at heights 1 and 0 from left to right. Let $A_n^\alpha$, $n \ge 2$, be the set of $n$-length non-decreasing Dyck paths with air pockets and $A^\alpha = \bigcup_{n \ge 2} A_n^\alpha$. The subset of $n$-length prime non-decreasing Dyck paths with air pockets is defined as the intersection $P_n^\alpha := A_n^\alpha \cap P$, and we set $P^\alpha := \bigcup_{n \ge 2} P_n^\alpha$. Analogous to generic Dyck paths with air pockets, the map $\alpha \mapsto \alpha^\flat$ induces a bijection between $P_n^\alpha$ and $A_{n-1}^\alpha$, whose inverse is the map $\alpha \mapsto \alpha^\flat$.

**Theorem 22.** For $n \ge 2$, if $a_n^\alpha$ is the number of $n$-length non-decreasing Dyck paths with air pockets, then $a_2^\alpha = 1$ and $a_n^\alpha = 2^{n-3}$ for $n \ge 3$.
*Proof.* Any non-decreasing Dyck path with air pockets $\alpha$ has one of the following two forms: (i) $\alpha \in \mathcal{P}^{\alpha} \cup \{UD\}$, or (ii) $\alpha = \Delta_k \beta$ where $k \ge 1$ and $\beta \in \mathcal{A}^{\alpha}$. So if $A^{\alpha}(x) = \sum_{n \ge 2} a_n^{\alpha} x^n$ where $a_n^{\alpha}$ is the cardinality of $\mathcal{A}_n^{\alpha}$, then the previous decomposition implies the functional equation

$$A^{\alpha}(x) = x(A^{\alpha}(x) + x) + \frac{x^2}{1-x}A^{\alpha}(x).$$

Thus we have $A^{\alpha}(x) = \frac{x^2(1-x)}{1-2x}$ which completes the proof. $\square$

## 4.1 The numbers of U and D

**Theorem 23.** Let $A^{\alpha}(x, y, z) = \sum_{n,k,\ell \ge 0} a_{n,k,\ell}^{\alpha} x^n y^k z^{\ell}$ be the trivariate g.f. where $a_{n,k,\ell}^{\alpha}$ is the number of n-length non-decreasing Dyck paths with air pockets having k up-steps U and $\ell$ down-steps D. Then $A^{\alpha}(x, y, z)$ equals

$$\frac{x^2y(1-xy)(xyz-xy-z)(x^2yz+xy-1)}{(x^3y^2(z-1)+x^2y(y-z)-2xy+1)(x^3y^2(z-1)-x^2yz-xy+1)}.$$

*Proof.* Let $Z(x, y, z) = \sum_{n,k,\ell \ge 0} z_{n,k,\ell} x^n y^k z^{\ell}$, where $z_{n,k,\ell}$ is the number of n-length non-decreasing Dyck paths with air pockets having only valleys at height 0, k up-steps U and $\ell$ down-steps D. Such a path has the form $UD\alpha$ or $\Delta_k\alpha$ with $k \ge 2$, where $\alpha$ has all its valleys at height 0. Then we have

$$Z(x, y, z) = (1 + Z(x, y, z)) \left( x^2 y z + \frac{x^3 y^2}{1 - x y} \right).$$

Solving for $Z(x, y, z)$, we get

$$Z(x, y, z) = \frac{x^2 y (xy(1-z) + z)}{x^3 y^2 (z-1) - x^2 y z - xy + 1}.$$

Now any non-decreasing Dyck path with air pockets belongs to one of the following cases:

(i) $\beta UD$;

(ii) $\beta (UD)^{\sharp}$;

(iii) $\beta (\alpha UD)^{\sharp}$ ($\alpha$ having all its valleys at height 0);

(iv) $\beta \alpha^{\sharp}$ ($\alpha$ having all its valleys at height 0, and not ending with $UD$), where $\beta$ is either empty or has all its valleys at height 0.

Thus, we have (for short, we use $A^{\alpha}$ and $Z$ instead of $A^{\alpha}(x, y, z)$ and $Z(x, y, z)$)

$$A^{\alpha} = (1 + Z)(x^2 y z + x^3 y^2 + x^3 y^2 Z + xy(A^{\alpha} - x^2 y z(1 + Z))).$$

Solving for $A^{\alpha}$, we get the result. $\square$
**Porism 24.** For all $n \ge 1$, the number of $n$-length non-decreasing Dyck paths with air pockets which have all valleys at height 0 is equal to $F_{n-1}$, where $F_k$ is the $k$-th Fibonacci number.

*Proof.* Plugging $y = z = 1$ into the trivariate g.f. $Z$ in the proof of the previous theorem we obtain $Z(x, 1, 1) = \frac{x^2}{1-x-x^2}$, which is the g.f. for the right shift of the sequence of Fibonacci numbers. $\square$

As we have done in Section 3.1, we deduce the following.

**Corollary 25.** For all $k \ge 1$, the number of non-decreasing Dyck paths with air pockets:

* having $n$ up-steps $U$ is the $k$-th term of the sequence A001519;

* having $k$ up-steps $U$ and no down-steps $D$ is the $(k-1)$-th term of the sequence A099036.

*Proof.* We calculate $Z(1, y, 1)$ and $Z(1, y, 0)$, respectively. $\square$

**Corollary 26.** The popularity of up-steps $U$ in $A_n^\lambda$ is equal to the $(n-2)$-th term of the sequence A098156 [22]. An asymptotic for the expectation of the up-step number is $(3n-2)/4$.

*Proof.* We calculate $\partial_y(Z(x, y, 1))|_{y=1}$. $\square$

**Corollary 27.** The g.f. for the popularity of down-steps $D$ in $A_n^\lambda$ equals

$$ \frac{x^2(1-x)(1-4x+5x^2-2x^3+x^5)}{(1-2x)^2(1-x-x^2)} $$

An asymptotic approximation of the $n$-th term is $n \cdot 2^{n-6}$. An asymptotic for the expectation of the down-step number is $n/8$.

*Proof.* We calculate $\partial_z(Z(x, 1, z))|_{z=1}$. $\square$

## 4.2 The number of peaks

**Theorem 28.** For all $n \ge 2$ and $k \ge 1$, the number of $n$-length non-decreasing Dyck paths with air pockets having $k$ peaks is equal to $\binom{n-2}{2(k-1)}$.

*Proof.* Let $B(x, y)$ be the g.f. where the coefficient of $x^ny^k$ is the number of $n$-length paths in $A^\lambda$ having $k$ peaks. Any non-decreasing Dyck path with air pockets is either of the form $\Delta_1 = UD$, or $\alpha^\sharp$, or $\Delta_k\beta$ with $k \ge 1$, with $\alpha, \beta \in A^\lambda$. This yields the following functional equation:

$$ B(x, y) = x^2y + xB(x, y) + \frac{x^2}{1-x}yB(x, y) $$

with the solution $B(x, y) = \frac{(1-x)x^2y}{(1-x)^2-x^2y}$, which generates the sequence A034839 [22]. $\square$

**Corollary 29.** The popularity of peaks in $A_n^\lambda$ is the $(n-2)$-th term of the sequence A045891 [22], which is equal to $(n+2) \cdot 2^{n-5}$ for $n \ge 4$. Then the expectation of the peak number is $(n+2)/4$.
## 4.3 The number of returns to the x-axis

**Theorem 30.** The bivariate g.f. where the coefficient of $x^n y^k$ is the number of n-length non-decreasing Dyck paths with air pockets having k returns is

$$R(x, y) = \frac{x^2 y(1-x)(1-x-x^2)}{(1-2x)(1-x-x^2y)}.$$

*Proof.* Using the second-to-last return decomposition of $A^k$, we easily get the following functional equation:

$$R(x, y) = x^2 y + x^2 y R(x, y) + xy A^k(x) + \frac{x^3}{1-x} y R(x, y),$$

which gives the result. □

**Corollary 31.** The g.f. for the popularity of returns in $A_n^k$ is

$$\frac{x^2(1-x)^2}{(1-2x)(1-x-x^2)},$$

and for $n \ge 2$ the coefficient of $x^n$ is $2^{n-2} - F_{n-2}$, where $F_n$ is the n-th Fibonacci number (see A099036 [22]). Then the expectation of the return number is $2 - F_{n-2}/2^{n-3}$ that tends to 2.

## 4.4 The number of catastrophes

**Theorem 32.** The bivariate g.f. where the coefficient of $x^n y^k$ is the number of n-length non-decreasing Dyck paths with air pockets having k catastrophes is

$$C(x, y) = \frac{x^2(1-x)(1+x(y-2)-x^2y)}{(1-2x)(1-x-x^2-x^3(y-1))}.$$

*Proof.* First, let us determine the bivariate g.f. $U(x, y)$ with respect to the length and number of catastrophes for non-decreasing Dyck paths with air pockets having all their valleys at height 0. It is easy to see that

$$U(x, y) = (1 + U(x, y)) \left( x^2 + \frac{x^3 y}{1-x} \right),$$

which yields

$$U(x, y) = \frac{x^2(1-x+xy)}{1-x-x^2-x^3(y-1)}.$$

Then any non-decreasing Dyck path with air pockets has one of the following forms:

(i) $\beta U D$; or
(ii) $\beta U^2 D_2$; or

(iii) $\beta\alpha^\sharp$ with $\alpha$ not belonging to forms (i) or (ii), and where $\beta$ is either empty or a non-decreasing Dyck path with air pockets which only has valleys that lie at height 0.

Hence, the bivariate generating function $C(x, y)$ satisfies the following equation:

$$C(x, y) = (1 + U(x, y))(x^2 + x^3y(1 + U(x, 1)) + xy(C(x, 1) - x^2(1 + U(x, 1)),$$

which gives the result.

<figure><img src="image_8.png" /></figure>

**Corollary 33.** The g.f. for the popularity of catastrophes in $\mathcal{A}_n^\gamma$ equals

$$\frac{x^3(1-x)(1-x+x^2)}{(1-2x)(1-x-x^2)},$$

and for $n \ge 4$ the coefficient of $x^n$ is $3 \cdot 2^{n-4} + 2F_{n-3}$, where $F_n$ is the n-th Fibonacci number (see the sequence A175657 [22]). Then the expectation of the catastrophe number is $3/2 - F_{n-3}/2^{n-4}$ that tends to $3/2$.

*Remark 34.* As a byproduct of Corollary 31 and Corollary 33, the ratio of the popularity of catastrophes in $\mathcal{A}_n^\gamma$ to the popularity of returns in $\mathcal{A}_n^\gamma$ tends to $3/4$ when $n$ tends toward $\infty$.

## 4.5 The number of pyramids

**Theorem 35.** For $k \ge 1$, let $P_k(x, y) = \sum_{n,m \ge 0} p_{n,m}^k x^ny^m$ be the g.f. where $p_{n,m}^k$ is the number of n-length non-decreasing Dyck paths with air pockets with m occurrences of the pattern $\Delta_k = U^k D_k$. Then the following holds:

$$P_k(x, y) = \frac{x^2\left(1 - \frac{x^2}{1-x} + x^{k-1}\left(1 - x - \frac{x^2(2-x)}{1-x}\right)(y-1) - x^{2k}(y-1)^2\right)}{\left(1 - x - \frac{x^2}{1-x} - x^{k+1}(y-1)\right)\left(1 - \frac{x^2}{1-x} - x^{k+1}(y-1)\right)}.$$

*Proof.* First, let us determine the expression of the bivariate g.f. $Z_k(x, y)$ with respect to the length and the number of patterns $\Delta_k$ for non-decreasing Dyck paths with air pockets having all their valleys at height 0. The second-to-last return decomposition of $\mathcal{A}^\gamma$ yields

$$Z_k(x, y) = (1 + Z_k(x, y))(x^{k+1}y + \left(\frac{x^2}{1-x} - x^{k+1}\right)).$$

Hence, we get $Z_k(x, y) = \frac{1}{1 - \frac{x^2}{1-x} - x^{k+1}(y-1)} - 1$.

Now, assuming that $k \ne 1$, any Dyck path has one of the following forms:

(i) $\beta U D$;

(ii) $\beta \Delta_{k-1}^\sharp$;
(iii) $\beta\Delta_k^{\sharp}$;

(iv) $\beta(\alpha\Delta_k)^{\sharp}$ with $\alpha$ having all of its valleys at height 0;

(v) $\beta\alpha^{\sharp}$ with $\alpha \in \mathcal{A}^{\flat}$, $\alpha \neq \Delta_{k-1}, \Delta_k, \gamma\Delta_k$ ($\gamma$ having all of its valleys at height 0), and where $\beta$ is either empty or has all its valleys at height 0.

This yields (for short we use $P_k$ and $Z_k$ instead of $P_k(x, y)$ and $Z_k(x, y)$)

$$P_k = (1 + Z_k)(x^2 + x^{k+1}y + x^{k+2}(1 + Z_k) + x(P_k - x^k - x^{k+1}y(1 + Z_k))).$$

Solving for $P_k$, we get the result for $k \ge 2$.

If $k = 1$, the expression of $P_1(x, y)$ is the same as that of the bivariate g.f. associated with the pattern $D$ in $\mathcal{A}^{\flat}$ (given in Theorem 30), because $D$ occurs exactly as often as $UD = \Delta_1$. $\square$

**Corollary 36.** For $k \ge 1$, the g.f. for the popularity $\Delta_k(\mathcal{A}_n^{\flat})$ of k-pyramids in $\mathcal{A}_n^{\flat}$ is

$$W_k(x) = \frac{x^{k+1}(1-x)(1-4x+5x^2-2x^3+x^5)}{(1-2x)^2(1-x-x^2)}.$$

In particular, we can see that $\Delta_1(\mathcal{A}_n^{\flat}) = \Delta_k(\mathcal{A}_{n+k-1}^{\flat})$, which means that there are as many 1-pyramids in $\mathcal{A}_n^{\flat}$ as there are k-pyramids in $\mathcal{A}_{n+k-1}^{\flat}$. An asymptotic approximation of the n-th term is $n \cdot 2^{n-5-k}$, and an asymptotic approximation for the expectation of the k-pyramid number is $n/2^{k+2}$.

An immediate consequence of the previous corollary is the following one, which is the $\mathcal{A}_n^{\flat}$-counterpart of Corollary 19.

**Corollary 37.** For $k \ge 1$, the g.f. for the popularities $\Delta_{\ge k}(\mathcal{A}_n^{\flat})$ and $\Delta_{\le k}(\mathcal{A}_n^{\flat})$ are respectively given by

$$W_{\ge k}(x) = \frac{x^{k-1}}{1-x}W_1(x) \text{ and } W_{\le k}(x) = \frac{1-x^k}{1-x}W_1(x),$$

which means that $\Delta_{\le k}(\mathcal{A}_{n-k+1}^{\flat}) = \Delta_{\ge k}(\mathcal{A}_n^{\flat}) - \Delta_{\ge k}(\mathcal{A}_{n-k}^{\flat})$.

**Going further.** It should be interesting to give natural bijections whenever our enumerative results suggest such bijections. Also, asymptotic investigations of expectations could be extended to a study of the limit distributions. It will also be of interest to investigate the ‘Grand’ counterpart of Dyck paths with air pockets, that are paths where negative ordinates are allowed, or ‘Motzkin’ counterpart where flat steps (1, 0) are allowed.

# 5 Acknowledgments

The authors would like to thank the anonymous referees for useful remarks and comments. This work was supported in part by the project ANER ARTICO funded by Bourgogne-Franche-Comté region of France and ANR-22-CE48-0002.
<table><caption>Table 2: Pattern popularity in $A_n^?$ for $2 \le n \le 11$.</caption><thead><tr><th>Pattern</th><th>Pattern popularity in A<sub>n</sub><sup>?</sup></th><th>OEIS</th></tr></thead><tbody><tr><td>U</td><td>1, 2, 5, 13, 32, 76, 176, 400, 896, 1984</td><td>A098156</td></tr><tr><td>D</td><td>1, 0, 2, 3, 7, 15, 33, 72, 157, 341</td><td></td></tr><tr><td>Peak</td><td>1, 1, 3, 7, 16, 36, 80, 176, 384, 832</td><td>A045891</td></tr><tr><td>Ret</td><td>1, 1, 3, 6, 13, 27, 56, 115, 235, 478</td><td>A099036</td></tr><tr><td>Cat</td><td>0, 1, 1, 4, 8, 18, 38, 80, 166, 342</td><td>A175657</td></tr><tr><td>Δ<sub>k</sub></td><td>0, ..., 0, 1, 0, 2, 3, 7, 15, 33, 72, 157, 341</td><td></td></tr><tr><td>Δ<sub>≥k</sub></td><td>0, ..., 0, 1, 1, 3, 6, 13, 28, 61, 133, 290, 631</td><td>New (= v<sub>n</sub>)</td></tr><tr><td>Δ<sub>≤k</sub></td><td>Δ<sub>≤1</sub> 1, 0, 2, 3, 7, 15, 33, 72, 157, 341<br>Δ<sub>≤2</sub> 1, 1, 2, 5, 10, 22, 48, 105, 229, 498<br>Δ<sub>≤3</sub> 1, 1, 3, 5, 12, 25, 55, 120, 262, 570<br>⋮</td><td>v<sub>n</sub> - v<sub>n-k</sub></td></tr></tbody></table>

## References

[1] C. Banderier and M. Wallner, Lattice paths with catastrophes, *Discrete Math. Theor. Comput. Sci.* **19** (2017), #23.

[2] E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck paths and *q*-Fibonacci numbers, *Discrete Math.* **170** (1997), 211–217.

[3] J.-L. Baril and A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, *Discrete Math.* **338** (2015), 655–660.

[4] J.-L. Baril, D. Bevan, and S. Kirgizov, *Bijections between directed animals, multisets and Grand-Dyck paths*, *Electron. J. Combin.* **27** (2020), #P2.10.

[5] J.-L. Baril, R. Genestier, and S. Kirgizov, *Pattern distributions in Dyck paths with a first return decomposition constrained by height*, *Discrete Math.* **342** (2020), 111–195.

[6] M. Bóna, Surprising symmetries in objects counted by Catalan numbers, *Electron. J. Combin.* **19** (2012), #P62.

[7] E. Deutsch, Dyck path enumeration, *Discrete Math.* **204** (1999), 167–202.

[8] P. Flajolet and R. Sedgewick, *Analytic Combinatorics*, Cambridge University Press, 2009.

[9] C. Homberger, Expected patterns in permutation classes, *Electron. J. Combin.* **19** (2012), #P43.
[10] S. Kitaev, *Patterns in Permutations and Words*, Springer Science & Business Media, 2011.

[11] D. E. Knuth, *The Art of Computer Programming*, Volume 1, Fundamental Algorithms, Addison-Wesley, 1973.

[12] I. Kortchemski and C. Marzouk, Simply generated non-crossing partitions, *Combin. Probab. Comput.* **26** (2017), 560–592.

[13] A. Krinik, G. Rubino, D. Marcus, R. J. Swift, H. Kasfy, and H. Lam, Dual processes to solve single server systems, *J. Statist. Plann. Inference* **135** (2005), 121–147.

[14] P. Luschny, Fibonacci meanders, http://oeis.org/wiki/User:Peter_Luschny/FibonacciMeanders, 2011.

[15] T. Mansour, Statistics on Dyck paths, *J. Integer Sequences* **9** (2006), Article 06.1.5.

[16] D. Merlini, R. Sprugnoli, and M. C. Verri, Some statistics on Dyck paths, *J. Statist. Plann. Inference* **101** (2002), 211–227.

[17] A. G. Orlov, On asymptotic behavior of the Taylor coefficients of algebraic functions, *Sibirsk. Mat. Zh.* **35** (1994), 1125–1137. Translation in *Siberian Math. J.* **35** (1994), 1002–1013.

[18] A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck paths, *J. Combin. Math. Combin. Comput.* **40** (2002), 33–39.

[19] V. Roitner, Contacts and returns in 2-watermelons without wall, *Bull. Inst. Combin. Appl.* **89** (2020), 75–92.

[20] A. Sapounakis, I. Tasoulas, and P. Tsikouras, Counting strings in Dyck paths, *Discrete Math.* **307** (2007), 2909–2924.

[21] Y. Sun, The statistic “number of udu’s” in Dyck paths, *Discrete Math.* **287** (2004), 177–186.

[22] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org, 2023.

[23] R. P. Stanley. *Enumerative Combinatorics*, Vol. 2, Cambridge University Press, 1999.

[24] S. Wienand, Personal page on the OEIS Wiki, http://oeis.org/wiki/User:Susanne_Wienand#Definition_of_meanders_concerned_by_these_sequences, 2011.
2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A16, 05A19, 68R05.
Keywords: Dyck path, pattern distribution, popularity, Fibonacci meander.

(Concerned with sequences A000108, A001006, A001519, A004148, A005043, A034839, A045891, A051291, A089732, A093128, A098086, A098156, A099036, A110320, A175657, A201631, and A203611.)

Received September 6 2022; revised versions received March 3 2023, March 6 2023, March 8 2023, March 9 2023. Published in *Journal of Integer Sequences*, March 9 2023.

Return to *Journal of Integer Sequences* home page.