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

In combinatorics, lattice paths are widely studied. They have many applications in various domains such as computer science, biology and physics [?], and they have very tight links with other combinatorial objects such as directed animals, pattern avoiding permutations, bargraphs, RNA structures and so on [?, ?, ?]. A classical problem in combinatorics is the enumeration of these paths with respect to their length and other statistics [?, ?, ?, ?, ?, ?, ?, ?, ?]. In the literature, Dyck and Motzkin paths are the most often considered. They are counted by the famous Catalan and Motzkin numbers (see \underline{A000108} and \underline{A001006} in Sloane’s On-line Encyclopedia of Integer Sequences [?]). In 2005, Krinik et al. [?] 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 ≥ 2. Banderier and Wallner [?] study these paths by providing enumerative results and limit laws.

In this paper, we introduce and study the 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 ℤ^{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 ≥ 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 A_{n} be the set of n-length Dyck paths with air pockets. By definition A_{0} = A_{1} = ∅ and we set A = ⋃_{n≥2} A_{n}.

Figure 1: The Dyck path with air pockets UUDUD_{2}UUUD_{2}UD_{2}UUD_{2}.

A Dyck path with air pockets is called prime whenever it ends with D_{k}, k ≥ 2, and returns to the x-axis only once. The set of all prime Dyck paths with air pockets of length n is denoted P_{n}. Notice that UD is not prime so we set P = ⋃_{n≥3} P_{n}. If α = UβUD_{k} ∈ P_{n}, then 2 ≤ k < n, β is a (possibly empty) prefix of a path in A, and we define the Dyck path with air pockets α^{♭} = βUD_{k−1}, called the ‘lowering’ of α. For example, the path α = UUDUUD_{3} is prime, and α^{♭} = UDUUD_{2}. The map α ↦ α^{♭} is clearly a bijection from P_{n} to A_{n−1} for all n ≥ 3, and we let γ^{♯} denote the inverse image of γ ∈ A_{n−1} (α^{♯} is a kind of ‘elevation’ of α, drawing inspiration for the term from Deutsch’s definition of elevated Dyck paths [?]). Any Dyck path with air pockets α ∈ A can be decomposed depending on its second-to-last return to the x-axis: either (i) α = UD, or (ii) α = βUD with β ∈ A, or (iii) α ∈ P, or (iv) α = βγ where β ∈ A and γ ∈ P. So, if A(x) = ∑_{n≥2} a_{n}x^{n} where a_{n} is the cardinality of A_{n}, and P (x) = ∑_{n≥3} p_{n}x^{n} where p_{n} is the cardinality of P_{n}, then we have P (x) = xA(x) and the previous decompositions imply the functional equation A(x) = x^{2} + x^{2}A(x) + xA(x) + xA(x)^{2}, and

A(x) = \frac{1 − x − x^{2} − \sqrt{x^{4} − 2x^{3} − x^{2} − 2x + 1}}{2x}  (1)

which generates the generalized Catalan numbers (see \underline{A004148} [?]), which among other things, counts the peakless Motzkin paths. The first values of a_{n} for 2 ≤ n ≤ 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{πn}(3 − \sqrt{5})} (\frac{\sqrt{5} + 3}{2})^{n} .

If a Dyck path with air pockets α ∈ A_{n} has k ≥ 1 peaks (a peak is an occurrence UD_{i} for some i ≥ 1), then it contains n − k up-steps. If we ‘unfurl’ all of its down-steps D_{i}, i ≥ 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} [?].

In the following, a pattern consists of consecutive steps in a path, and a statistic s is an integer-valued function from a set S of paths. Given a pattern p, we associate p with the pattern statistic p : S → ℕ where p(a) is the number of occurrences of the pattern p in a ∈ 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 ≥ 1, we let n̂ denote the constant statistic returning the value n. The popularity of a pattern p in S is the total number of occurrences of p over all objects of S, that is p(S) = ∑_{a∈S} p(a) [?, ?, ?]. Let S′ be another set of combinatorial objects, we say that two statistics, s on S and t on S′, have the same distribution if there exists a bijection f : S → S′ satisfying s(a) = t(f(a)) for any a ∈ S. In this case, with a slight abuse of the notation already used in the literature [?], we write f(s) = t or s = 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) = ∑_{n,k≥0} a_{n,k}x^{n}y^{k} for the distributions of some statistics s, i.e., the coefficient a_{n,k} of x^{n}y^{k} is the number of paths α ∈ A_{n} satisfying s(α) = k. Then, we deduce the popularities of some patterns (U, D, peak, return, catastrophe, pyramid, …) by calculating ∂_{y}(A(x, y))|_{y=1}, and we provide asymptotic approximations for them using classical methods [?, ?]. 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 [?, ?]). In Section 4, we make a similar study for non-decreasing Dyck paths with air pockets.

Pattern Pattern popularity in A_{n}  OEIS
U  1, 2, 5, 13, 32, 80, 201, 505, 1273, 3217  \underline{A110320}
D  1, 0, 2, 3, 7, 17, 40, 97, 238, 587  \underline{A051291}
Peak  1, 1, 3, 7, 16, 39, 95, 233, 577, 1436  \underline{A203611}
Ret  1, 1, 3, 6, 13, 29, 65, 148, 341, 793  \underline{A093128}
Cat  0, 1, 1, 4, 8, 19, 44, 102, 239, 563
Δ_{k}  \underbrace{0, …, 0}_{k−1 zeroes}, 1, 0, 2, 3, 7, 17, 40, 97, 238, 587  \underline{A051291}
Δ_{≥k}  \underbrace{0, …, 0}_{k−1 zeroes}, 1, 1, 3, 6, 13, 30, 70, 167, 405  \underline{A201631}(= u_{n})
Δ_{≤k}  Δ_{≤1} 1, 0, 2, 3, 7, 17, 40, 97, 238, 587  u_{n} − u_{n−k}

Δ_{≤2} 1, 1, 2, 5, 10, 24, 47, 137, 335, 825, … Δ_{≤3} 1, 1, 3, 5, 12, 27, 64, 154, 375, 922, …

⋮

Table 1: Pattern popularity in A_{n}, for 2 ≤ n ≤ 11.

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 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 = ⋃_{n≥1} M_{n}.

Definition 1. We recursively define the map ψ from A to M as follows. For α ∈ A, we set

ψ(α) = \begin{cases}F, & if α = UD;  (i) \\ Uψ(β)D, & if α = βUD, with β ∈ A;  (ii) \\ ψ(α^{♭})F, & if α ∈ P;  (iii) \\ ψ(γ^{♭})Uψ(β)D, & if α = βγ, with β ∈ A and γ ∈ P. (iv) \end{cases}

Notice that each factor in the above decomposition is nonempty, and that ψ maps nonempty objects to nonempty ones. Due to the recursive definition, the image by ψ 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_{2}UD_{2}UD are respectively F, F F, and UUF F DF D. We refer to Figure 2 for an illustration of this mapping.

β ψ(β) α ψ(α^{♭}) β γ ψ(γ^{♭}) ψ(β)

Figure 2: Illustration of the map ψ according to Definition 1.

Theorem 2. For all n ≥ 2, the map ψ induces a bijection between A_{n} and M_{n−1}.

Proof. It is well known that the cardinality of M_{n} is given by the n-th term of generalized Catalan number (see \underline{A004148} [?]). So it suffices (see observation after relation (1)) to prove the injectivity of ψ. We proceed by induction on n. The case n = 2 is obvious since A_{2} = {UD} and M_{1} = {F }. For all k ≤ n, we assume that ψ is an injection from A_{k} to M_{k−1}, and we prove the result for k = n + 1. According to Definition 1, if α and β in A_{n+1} satisfy ψ(α) = ψ(β), then α and β necessarily come from the same case among (i) – (iv). Using the induction hypothesis, we conclude directly that α = β, which completes the induction. Thus ψ is injective and so bijective.

Proposition 3. For all n ≥ 2 and k ≥ 1, and ψ : A_{n} → M_{n−1}, the following holds:

• ψ(U) = F + U = F + D

• ψ(D) = ψ(UD) = �_{F} + UFD + �_{UMD} + U^{2}MD^{2}

• ψ(DU) = UFD + U^{2}MD^{2}

• ψ(UU) = F − ˆ1

• ψ(Δ_{k}) = �_{F^{k}} + UF^{k}D + �_{F^{k−1}UMD} + UF^{k−1}UMD^{2}

• ψ(Peak) = U + ˆ1

• ψ(Ret) = n̂ − LastF

• ψ(SLast) = Ret,

where �_{β}(α) = 1 if α = β and 0 otherwise; �_{UMD}(α) is equal to 1 if there exists β ∈ M such that α = UβD and 0 otherwise; U^{2}MD^{2}(α) is the number of occurrences U^{2}βD^{2} in α for β ∈ M; Δ_{k}(α) is the number of occurrences U^{k}D_{k} in α; Peak(α) = ∑_{k≥1} UD_{k}(α); Ret(α) is the number of returns to the x-axis of α; LastF(α) is the position of the rightmost flat-step in α, and SLast(α) is the size of the the last step of α (i.e., k if the last step is D_{k}).

Proof. We provide the proof for ψ(U) and ψ(Δ_{k}) since those for the other relations can be obtained mutatis mutandis.

We proceed by induction on n. Since A_{2} = {UD} and M_{1} = {F } the statements trivially hold for n = 2. Now, assume the statements are true for all k ≤ n and let us prove them for n + 1.

If α ∈ A_{n+1} with n ≥ 2, then we have either (i) α = βUD, (ii) α = γ^{♯} or (iii) α = βγ^{♯} where β, γ ∈ A. In the case (i), U(βUD) = 1 + U(β) and with the induction hypothesis, U(βUD) = 1 + (U + F)(ψ(β)) = (U + F)(Uψ(β)D) = (U + F)(ψ(βUD)) as expected. In the case (ii), U(γ^{♯}) = 1 + U(γ) and with the induction hypothesis, U(γ^{♯}) = 1 + (U + F)(ψ(γ)) = (U + F)(ψ(γ)F) = (U + F)(ψ(γ^{♯})). Case (iii) is handled in the same way.

So, we have ψ(U) = U + F. Using a similar reasoning, we can easily prove ψ(D) = �_{F} + UFD + �_{UMD} + U^{2}MD^{2}.

Now, let us give details for the slightly less straightforward case of ψ(Δ_{k}) for k ≥ 1. The case k = 1 is already handled since we have ψ(UD) = ψ(D). So, we assume k ≥ 2. We consider the following case analysis: any given Dyck path with air pockets is either of the form (i) βUD, (ii) βΔ_{k−1}^{♯}, (iii) βΔ_{k}^{♯}, (iv) β(αΔ_{k})^{♯} with α ∈ A, or (v) βα^{♯} with α ∈ A being neither Δ_{k−1}, nor Δ_{k}, nor α′Δ_{k} (α′ ∈ A), and β ∈ A ∪ {ε}. Reasoning by induction, case (ii) unfolds as follows: if β = ε, then we get

(�_{F^{k}} + UF^{k}D + �_{F^{k−1}UMD} + UF^{k−1}UMD^{2})(F^{k}) = 1,

which is the same as Δ_{k}(Δ_{k−1}^{♯}). Otherwise, we have

(�_{F^{k}} + UF^{k}D + �_{F^{k−1}UMD} + UF^{k−1}UMD^{2})(ψ(βΔ_{k−1}^{♯}))
= (�_{F^{k}} + UF^{k}D + �_{F^{k−1}UMD} + UF^{k−1}UMD^{2})(F^{k−1}Uψ(β)D)
= �_{F^{k}}(ψ(β)) + UF^{k}D(ψ(β)) + 1 + �_{F^{k−1}UMD}(ψ(β))
+ UF^{k−1}UMD^{2}(ψ(β))
= 1 + Δ_{k}(β) = Δ_{k}(βΔ_{k−1}^{♯}).

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 [?], 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) = ∑_{n,k,ℓ≥0} a_{n,k,ℓ}x^{n}y^{k}z^{ℓ} be the generating function (g.f.) where a_{n,k,ℓ} is the number of paths in A_{n} having k up-steps U and ℓ down-steps D = D_{1}. Then the following holds:

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

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γ, (ii) U^{2}D_{2}γ, (iii) (αUD)^{♯}γ with α ∈ A, (iv) α^{♯}γ with α ∈ A not being UD nor βUD (β ∈ A), where γ ∈ A ∪ {ε}. These four cases are disjoint and cover 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^{2}yz}_{(i)} + \underbrace{x^{3}y^{2}}_{(ii)} + \underbrace{x^{3}y^{2}A}_{(iii)} + \underbrace{xy(A − x^{2}yz(1 + A))}_{(iv)})(1 + A),

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

Corollary 5. For all n ≥ 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 \underline{A000108} [?]).

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

Corollary 6. For all n ≥ 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 ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{k}c_{k}, where c_{k} = \frac{1}{k+1} \binom{2k}{k} (see \underline{A005043} [?]).

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

Corollary 7. The g.f. for the popularity of up-steps U in 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 \underline{A110320} [?]. An asymptotic approximation of the n-th term is

\frac{\sqrt{5} − 1}{2\sqrt{πn}\sqrt{14\sqrt{5} − 30}} (\frac{3 + \sqrt{5}}{2})^{n} ,

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

\frac{\sqrt{5} + 5}{10}n ∼ 0.723606799 · n.

Proof. The g.f. is given by ∂_{y}(A(x, y, 1))|_{y=1}. The asymptotic approximation is obtained using classical methods [?, ?].

Corollary 8. The g.f. for the popularity of down-steps D = D_{1} in 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 \underline{A051291} [?]. An asymptotic approximation of the n-th term is

\frac{5\sqrt{5} − 11}{2\sqrt{πn}\sqrt{14\sqrt{5} − 30}} (\frac{3 + \sqrt{5}}{2})^{n} ,

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

\frac{5 − 2\sqrt{5}}{5}n ∼ 0.105572797 · n.

Proof. The g.f. is given by ∂_{z}(A(x, 1, z))|_{z=1}.

3.2 The number of peaks

In this part, we study the distribution of peaks, i.e., patterns UD_{m} for m ≥ 1.

Theorem 9. Let P (x, y) = ∑_{n,k≥0} p_{n,k}x^{n}y^{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 \underline{A089732} [?].

Proof. If a Dyck path with air pockets equals αUD with α ∈ A ∪ {ε}, then its contribution to P (x, y) is (1 + P (x, y))x^{2}y; if it has the form αβ^{♯} with β ∈ 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^{2}y + xP (x, y)),

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

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 \underline{A203611} [?]. An asymptotic approximation of the n-th term is

\frac{\sqrt{5} − 2}{\sqrt{πn}\sqrt{14\sqrt{5} − 30}} (\frac{3 + \sqrt{5}}{2})^{n} ,

and an asymptotic for the expectation of the peak number is

\frac{5 − \sqrt{5}}{10}n ∼ 0.276393191 · 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

Peak(A_{n}) = ∑_{k=1}^{⌊ \frac{n}{2} ⌋} kN(n − k, k) = ∑_{k=1}^{⌊ \frac{n}{2} ⌋} \frac{k}{n − k} \binom{n − k}{k}\binom{n − k}{k − 1}.

Using the formula for the sequence \underline{A203611} [?], we get the following identity:

∑_{k=1}^{⌊ \frac{n}{2} ⌋} \binom{n − k − 1}{k − 1}\binom{n − k}{k − 1} = ∑_{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 ≥ 1, ending on the x-axis.

Theorem 12. Let R(x, y) = ∑_{n,k≥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 \underline{A098086} [?] 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 1).

Proof. If a Dyck path with air pockets equals αUD with α ∈ A ∪ {ε}, then its contribution to R(x, y) is (1 + R(x, y))x^{2}y; if it has the form αβ^{♯} with β ∈ A, then its contribution is (1 + R(x, y))xyA(x). So, we deduce

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

which gives the result using relation (1).

Corollary 13. The g.f. for the popularity of returns to the x-axis in 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 \underline{A093128} [?], 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{πn}} (\frac{3 + \sqrt{5}}{2})^{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 ≥ 2, ending on the x-axis.

Theorem 14. Let C(x, y) = ∑_{n,k≥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 αUD with α ∈ A ∪ {ε}, then its contribution to C(x, y) is (1 + C(x, y))x^{2}; if it has the form αβ^{♯} with β ∈ 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)).

Corollary 15. The g.f. for the popularity of catastrophes in 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{πn}} (\frac{3 + \sqrt{5}}{2})^{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 A_{n} to the popularity of returns in A_{n} tends to \frac{4−\sqrt{5}}{\sqrt{5}} = 0.788854 … when n tends toward ∞.

3.5 The number of pyramids U^{k}D_{k}

A k-pyramid Δ_{k} in a path is an occurrence of the pattern U^{k}D_{k}, k ≥ 1.

Theorem 17. For all k ≥ 1, the g.f. P_{k}(x, y) = ∑_{n,m≥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) Δ_{m}γ with 1 ≤ m ≤ k − 1, (ii) Δ_{k}γ, (iii) Δ_{k+1}γ, (iv) (αΔ_{k})^{♯}γ with α ∈ A, (v) β^{♯}γ with β ∈ A not being Δ_{m} with 1 ≤ m ≤ k, nor αΔ_{k} with α ∈ A, where γ ∈ A ∪ {ε}. These five cases are disjoint and cover all Dyck paths with air pockets. So, we deduce

P_{k} = (\underbrace{∑_{i=2}^{k} x^{i}}_{(i)} + \underbrace{x^{k+1}y}_{(ii)} + \underbrace{x^{k+2}}_{(iii)} + \underbrace{x^{k+2}P_{k}}_{(iv)} + \underbrace{x · (P_{k} − ∑_{i=2}^{k} x^{i} − x^{k+1}y(1 + P_{k}))}_{(v)})(1 + P_{k}),

where P_{k} stands for P_{k}(x, y). Solving for P_{k}, we get the result.

Corollary 18. For k ≥ 1, the g.f. for the popularity Δ_{k}(A_{n}) of k-pyramids in 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 \underline{A051291} [?]. In particular, we have Δ_{1}(A_{n}) = Δ_{k}(A_{n+k−1}) for all k ≥ 1 and n ≥ 2, which means that there are as many 1-pyramids in A_{n} as there are k-pyramids in A_{n+k−1}. An asymptotic approximation of the n-th term of this sequence is

\frac{\sqrt{5} − 1}{2\sqrt{πn}\sqrt{14\sqrt{5} − 30}} (\frac{3 + \sqrt{5}}{2})^{n−k−1} ,

and for the expected number of k-pyramids we have

\frac{5 − \sqrt{5}}{10} (\frac{3 − \sqrt{5}}{2})^{k} · n.