ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.08
https://doi.org/10.26493/1855-3974.3035.6ac
(Also available at http://amc-journal.eu)
Two kinds of partial Motzkin paths
with air pockets*
Jean-Luc Baril †
LIB, Université de Bourgogne, B.P. 47 870, 21078 Dijon Cedex, France
Paul Barry
School of Science, South East Technological University (SETU), Ireland
Received 23 December 2022, accepted 23 October 2023, published online 16 August 2024
Abstract
Motzkin paths with air pockets (MAP) are defined as a generalization of Dyck paths
with air pockets by allowing some horizontal steps with certain conditions. In this paper,
we introduce two generalizations. The first one consists of lattice paths in N2 starting at
the origin, made of steps U = (1, 1), Dk = (1,−k), k ⩾ 1 and H = (1, 0), where two
down steps cannot be consecutive, while the second one are lattice paths in N2 starting at
the origin, made of steps U , Dk and H , where each step Dk and H is necessarily followed
by an up step, except for the last step of the path. We provide enumerative results for these
paths according to the length, the type of the last step, and the height of its end-point. A
similar study is made for these paths read from right to left. As a byproduct, we obtain new
classes of paths counted by the Motzkin numbers. Finally, we express our results using
Riordan arrays.
Keywords: Enumeration, Motzkin paths, kernel method, Riordan array.
Math. Subj. Class. (2020): 05A05, 05A15, 05A15
1 Introduction
In a recent paper [2], the authors introduce, study and enumerate special classes of lattice
paths, called Dyck paths with air pockets (DAP for short). Such paths are non empty lattice
paths in the first quadrant of Z2 starting at the origin, and consisting of up-steps U = (1, 1)
and down-steps Dk = (1,−k), k ⩾ 1, where two down steps cannot be consecutive.
*The authors would like to thank the anonymous referees for useful remarks and comments.
†Corresponding author.
E-mail addresses: barjl@u-bourgogne.fr (Jean-Luc Baril), pbarry@wit.ie (Paul Barry)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.08
The length of a path is the number of its steps. These paths can be viewed as ordinary
Dyck paths where each maximal run of down-steps is condensed into one large down step.
As mentioned in [2], they also correspond to a stack evolution with (partial) reset opera-
tions that cannot be consecutive (see for instance [7]). Whenever the last point is on the
x-axis, they prove that DAP of length n are in one-to-one correspondence with the peakless
Motzkin paths of length n − 1. They also investigate the popularity of many patterns in
these paths and they give asymptotic approximations. We also refer to [10] for the enu-
meration of DAP with respect to the length, the type (up or down) of the last step and the
height of the end-point (i.e., the ordinate of the end-point). In a second work [3], the au-
thors make a study for a generalization of these paths by allowing them to go below the
x-axis. They call these paths Grand Dyck paths with air pockets (GDAP), and they also
yield enumerative results for these paths according to the length and several restrictions on
the height.
In this paper, we introduce two generalizations of partial Dyck paths of air pockets by
allowing some possible horizontal steps H = (1, 0) with some conditions. These two kinds
of paths can be viewed as special partial Motzkin paths (lattice paths in N2 starting at the
origin and made of U = (1, 1), D = (1,−1), and H = (1, 0)), where each maximal run of
down-steps is condensed into one large down step.
Definition 1.1. A partial Motzkin path with air pocket of the first kind is a lattice path in
N2 starting at the origin, consisting of steps U , Dk and H , where two down steps cannot
be consecutive. Let M1 be the set of these paths.
Definition 1.2. A partial Motzkin path with air pocket of second kind is a lattice path in N2
starting at the origin, consisting of steps U , Dk and H , where any step H and Dk (except
the last step of the path) is immediately followed by an up step U . Let M2 be the set of
these paths.
Whenever these paths end on the x-axis, we call them Motzkin paths with air pockets
of the first and second kinds, respectively. For short, we denote by PMAP all paths in Mi,
i ∈ {1, 2}, and we denote by MAP all paths ending on the x-axis.
For instance, UUUDHUD2 ∈ M1 and UUUDUHUD2 ∈ M2 are two PMAP of the
first and second kinds, respectively. The paths UUUDHUD3UD and UUUDUHUD4
UD are MAP of the first and second kinds, respectively. See also Figure 1 and Figure 5 for
other examples of PMAP and MAP.
We also consider lattice paths obtained from MAP in M1 and M2 by reading them
from right to left and by replacing down-steps with up-steps and vice versa. More precisely,
we define the two sets M′1 and M′2 as follows.
Definition 1.3. Let M′1 be the set of paths in N2 starting at the origin, consisting of up
steps Uk = (1, k), k ⩾ 1, horizontal step H and down step D, where two up steps cannot
be consecutive.
Definition 1.4. Let M′2 be the set of paths in N2 starting at the origin, consisting of up
steps Uk = (1, k), k ⩾ 1, horizontal step H and down step D, where any H and Uk,
k ⩾ 1, (except the first step of the path) is preceded by a down step D.
All paths in M′1 and M′2 will be be called PMAP from right to left, and in the case
where they end on the x-axis, we call them MAP from right to left. For instance, we
have UDU3DHUD ∈ M′1, UDU4DHDU ∈ M′2, and the path UDU3DHUDDD
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 3
(resp. UDU4DHDUDDD) is a MAP of the first (resp. second) kind from right to left.
See also Figure 3 and Figure 7 for other examples of PMAP and MAP from right to left.
Notice that D1 = D and U1 = U , and we will use both notations.
Throughout the paper, and for each class of paths Mi and M′i, i ∈ {1, 2}, described
above, we will use the following notations. For k ⩾ 0, we consider the generating function
fk = fk(z) (resp. gk = gk(z), resp. hk = hk(z)), where the coefficient of zn in the series
expansion is the number of partial Motzkin paths with air pockets of length n ending at
height k with an up-step, (resp. with a down-step, resp. with a horizontal step H).
We introduce the bivariate generating functions
F (z, u) =
∑
k⩾0
ukfk(z), G(z, u) =
∑
k⩾0
ukgk(z), and H(z, u) =
∑
k⩾0
ukhk(z).
For short, we also use the notation F (u), G(u) and H(u) for these functions, and we
introduce the generating function
Total(z, u) = F (u) +G(u) +H(u).
Finally, for any bivariate generating function H(z, u) = H(u), we will use the notation
[uk]H(u) for the coefficient of uk in H(u).
The outline of this paper is the following. In Section 2, we present enumerative results
for partial Motzkin paths with air pockets of the first kind, and for these paths when we read
them from right to left. We provide bivariate generating functions that count these paths
with respect to the length, the type of the last step (up, down or horizontal step) and the
height of the end-point. In Section 3, we make a similar study for PMAP of second kind,
and we present new classes of lattice paths counted by the well known Motzkin numbers.
All these results are obtained algebraically by using the famous kernel method for solving
several systems of functional equations. More precisely, Sections 2.1, 2.2, 3.1 and 3.2 have
the same structure: we show how to obtain a system of equations involving fk, gk and hk,
and we apply the kernel method in order to provide some expressions of F (u), G(u) and
H(u). Finally, in Section 4 we express our results using Riordan arrays and we deduce
closed forms for PMAP of length n ending at height k.
2 PMAP of the first kind
In this section, we focus on PMAP of the first kind, i.e. lattices paths in N2 starting at the
origin, made of steps U , Dk and H , such that two down steps cannot be consecutive. The
first subsection considers the paths in M1, while the second subsection handles the paths in
M′1 (see Introduction for the definition of these two sets). We yield enumerative results for
these paths according to the length, the type of the last step, and the height of its end-point.
2.1 PMAP in M1 - From left to right
In this part, we consider PMAP in M1. Figure 1 shows two examples of such paths.
Let P be a length n PMAP in M1 ending at height k ⩾ 0. If the last step of P is U ,
then k ⩾ 1 and P can be written P = QU where Q is a length (n − 1) PMAP ending at
height k − 1. So, we obtain the first relation fk = zfk−1 + zgk−1 + zhk−1 for k ⩾ 1,
anchored with f0 = 1 by considering the empty path. If the last step of P is a down step
Da, a ⩾ 1, then we have P = QDa where Q is a length (n − 1) PMAP ending at height
4 Ars Math. Contemp. 24 (2024) #P3.08
Figure 1: The left drawing shows a Motzkin path with air pockets of length 18 in M1. The
right drawing shows a partial Motzkin path with air pockets of length 18 ending at height
3 in M1.
ℓ = a + k ⩾ k + 1 with no down step at its end. So, we obtain the second relation
gk = z
∑
ℓ⩾k+1 fℓ + z
∑
ℓ⩾k+1 hℓ. If the last step of P is a horizontal step H , then we
have P = QH where Q is a length (n − 1) PMAP ending at height k, which implies
hk = zfk + zgk + zhk.
Therefore, we have to solve the following system of equations.
f0 = 1, and fk = zfk−1 + zgk−1 + zhk−1, k ⩾ 1,
gk = z
∑
ℓ⩾k+1
fℓ + z
∑
ℓ⩾k+1
hℓ, k ⩾ 0,
hk = zfk + zgk + zhk, k ⩾ 0.
(2.1)
Summing the recursions in (2.1), we have:
F (u) = 1 + z
∑
k⩾1
ukfk−1 + z
∑
k⩾1
ukgk−1 + z
∑
k⩾1
ukhk−1
= 1 + zuF (u) + zuG(u) + zuH(u),
G(u) = z
∑
k⩾0
uk
( ∑
ℓ⩾k+1
fℓ
)
+ z
∑
k⩾0
uk
( ∑
ℓ⩾k+1
hℓ
)
= z
∑
k⩾1
fk(1 + u+ . . .+ u
k−1) + z
∑
k⩾1
hk(1 + u+ . . .+ u
k−1)
= z
∑
k⩾1
uk − 1
u− 1
fk + z
∑
k⩾1
uk − 1
u− 1
hk
=
z
u− 1
(F (u)− F (1) +H(u)−H(1)),
H(u) = zF (u) + zG(u) + zH(u).
Notice that we have F (1) − H(1) = 1 by considering the difference of the first and
third equations. Now, setting a := F (1) and solving these functional equations, we obtain
F (u) =
2au z2 − u z2 + uz + z2 − u− z + 1
u2z + u z2 + z2 − u− z + 1
,
G(u) = −z (2auz + 2az − uz − 2a− z + 2)
u2z + u z2 + z2 − u− z + 1
,
H(u) =
z (2az − u− 2z + 1)
u2z + u z2 + z2 − u− z + 1
.
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 5
In order to compute a = F (1), we use the kernel method (see [1, 9]) on F (u). This
method consists in cancelling the denominator by finding u as an algebraic function of z,
s(z). So, if we substitute u with s(z) in the numerator, then it necessarily equals zero (in
order to counterbalance the cancellation of the denominator), which allows to find a =
F (1). Finally, we can deduce the generating function F (u).
We can write the denominator (which is a polynomial in u of degree 2), as z(u − r)
(u− s) with
r =
1− z2 +
√
z4 − 4z3 + 2z2 − 4z + 1
2z
,
s =
1− z2 −
√
z4 − 4z3 + 2z2 − 4z + 1
2z
.
Replacing u with s (which have a Taylor expansion at z = 0) in order to cancel the numer-
ator of F (u), we obtain the equation
2as z2 − s z2 + sz + z2 − s− z + 1 = 0.
Using zrs = z2 − z + 1, a straightforward calculation provides
a = F (1) = H(1) + 1 =
r(s− 1)
2z
.
Finally, after simplifying by the factor (u − s) in the numerators and denominators, we
obtain
F (u) =
r
r − u
, G(u) =
r(s− 1)− z
r − u
, and H(u) =
1
r − u
.
Extracting the coefficient of uk in the series expansion of each generating function, we
obtain
[uk]F (u) := fk =
1
rk
,
[uk]G(u) := gk =
s− 1
rk
− z
rk+1
,
[uk]H(u) := hk =
1
rk+1
.
Theorem 2.1. The bivariate generating function for the total number of PMAP in M1 with
respect to the length and the height of the end-point is given by
Total(z, u) =
1
z(r − u)
,
and we have
[uk]Total(z, u) =
1
zrk+1
.
Finally, setting t(n, k) := [zn][uk]Total(z, u), we have for n ⩾ 2, k ⩾ 1,
t(n, k) = t(n, k − 1) + t(n− 1, k)− t(n− 1, k − 2)− t(n− 2, k)− t(n− 2, k − 1),
and setting tn := t(n, 0), then we have t0 = t1 = 1, and for n ⩾ 2,
tn = tn−1 + tn−2 +
n−3∑
k=0
tktn−k−3 +
n−1∑
k=2
(tk − tk−1) tn−k−1.
6 Ars Math. Contemp. 24 (2024) #P3.08
Proof. Since Total(z, u) = F (u)+G(u)+H(u), the first two equalities are immediately
deduced from the previous results. The third equality is obtained using the Mathematica
package Guess.m (written by Manuel Kauers [6]) for guessing recurrence relations. After
this, it suffices to check algebraically:
Total(z, u) = (u+ z − u2z − z2 − uz2)Total(z, u)− u+ (z
2 − z + 1)(1 + rs− z)
r
.
Now, let us prove the last equality. Any length n MAP of the first kind is of the form
(i) HP , or (ii) UDP , or (iii) UPHDQ where P,Q are some MAP so that the length k of
P lies into [0, n− 3], and the length of Q is n− k − 3, or (iv) P ♯Q where P ♯ = UP ′Dℓ,
ℓ ⩾ 1, and P ′ is a PMAP such that P ′Dℓ−1 is a MAP of length k lying into [2, n− 1], and
the length of Q is n− k − 1. Taking into account all these cases, we obtain the result.
Let T be the infinite matrix T := [t(n, k)]n⩾0,k⩾0. The first few rows of the matrix T
are
T =

1 0 0 0 0 0 0 0 · · ·
1 1 0 0 0 0 0 0 · · ·
2 2 1 0 0 0 0 0 · · ·
5 5 3 1 0 0 0 0 · · ·
13 14 9 4 1 0 0 0 · · ·
36 40 28 14 5 1 0 0 · · ·
105 118 87 48 20 6 1 0 · · ·
317 359 273 161 75 27 7 1 · · ·
...
...
...
...
...
...
...
...
. . .

.
Corollary 2.2. The generating function that counts the PMAP in M1 with respect to the
length is given by
Total(z, 1) =
1
z(r − 1)
.
The first few terms of the series expansion of Total(z, 1) are 1 + 2z + 5z2 + 14z3 +
41z4 + 124z5 + 385z6 + 1220z7 + 3929z8 + 12822z9 + O(z10), which correspond
to the sequence A159771 in [13] counting the n-leaf binary trees that do not contain
(()((()())((()())()))) as a subtree (see [11]). See Figure 2 for an illustration of the 14
PMAP of length 3.
Corollary 2.3. The generating function that counts the MAP in M1 with respect to the
length is given by
Total(z, 0) =
1
zr
.
The first few terms of the series expansion of Total(z, 0) are 1 + z + 2z2 + 5z3 +
13z4+36z5+105z6+317z7+982z8+3105z9+O(z10) which correspond to the sequence
A114465 in [13] counting Dyck paths of length 2n having no ascents of length 2 that start
at an odd level. We leave open the question of finding a constructive bijection between
these sets.
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 7
Figure 2: The 14 PMAP of length three in M1. Notice that five paths end on the x-axis,
five paths end at height 1, three paths end at height 2, and one path ends at height 3, which
correspond to the fourth row of T .
2.2 PMAP in M′1 - From right to left
Here, we consider the paths of the previous section, but we read them from right to left. This
means that down steps become up steps and vice versa, and horizontal steps are unchanged,
which implies that two up steps cannot be consecutive now. See Definition 1.3 and Figure 3
for two examples of such paths.
Figure 3: The left drawing shows a Motzkin path with air pockets of length 18 in M′1. The
right drawing shows a partial Motzkin path with air pockets of length 18 ending at height
2 in M′1.
Let P be a length n PMAP in M′1 ending at height k ⩾ 0. If the last step of P is Ua,
a ⩾ 1, then k ⩾ a and we have P = QUa where Q is a length (n − 1) PMAP ending
at height ℓ = k − a with a horizontal step or a down step. So, we obtain the first relation
fk = z + z(g0 + g1 + . . . + gk−1) + z(h0 + h1 + . . . + hk−1) for k ⩾ 1, anchored with
f0 = 1 by considering the empty path. If the last step of P is a down step D, then we have
P = QD where Q is a length (n − 1) PMAP ending at height k + 1. So, we obtain the
second relation gk = zfk+1 + zgk+1 + zhk+1. If the last step of P is a horizontal step
H , then we have P = QH where Q is a length (n − 1) PMAP ending at height k, which
implies hk = zfk + zgk + zhk.
Therefore, we have to solve the following system of equations.

f0 = 1,
fk = z + z(g0 + g1 + . . .+ gk−1) + z(h0 + h1 + . . .+ hk−1), k ⩾ 1,
gk = zfk+1 + zgk+1 + zhk+1, k ⩾ 0,
hk = zfk + zgk + zhk, k ⩾ 0.
(2.2)
8 Ars Math. Contemp. 24 (2024) #P3.08
Summing the recursions in (2.2), we have:
F (u) = 1 +
zu
1− u
+ z
∑
k⩾1
(g0 + . . .+ gk−1)u
k + z
∑
k⩾1
(h0 + . . .+ hk−1)u
k
= 1 +
zu
1− u
+ z
∑
k⩾0
gk
uk+1
1− u
+ z
∑
k⩾0
hk
uk+1
1− u
= 1 +
zu
1− u
(1 +G(u) +H(u)),
G(u) = z
∑
k⩾0
fk+1u
k + z
∑
k⩾0
gk+1u
k + z
∑
k⩾0
hk+1u
k
=
z
u
(F (u)− F (0) +G(u)−G(0) +H(u)−H(0)),
H(u) = zF (u) + zG(u) + zH(u).
Notice that we have H(0) = z(1+G(0))1−z by considering the third equation and F (0) = 1.
Solving these functional equations using a := G(0), we obtain
F (u) =
−u2z3 + a uz2 + 3u2z2 − uz3 − 3u2z + 2uz2 + u2 + uz − z2 − u+ z
(1− z) (u2z2 − u2z + uz2 + u2 − u+ z)
,
G(u) =
z
(
a uz2 − a uz + a u+ a z + uz − a
)
(−1 + z) (u2z2 − u2z + uz2 + u2 − u+ z)
,
H(u) =
(
a uz2 + u2z2 − a uz − 2u2z + uz2 + a z + u2 − u+ z
)
z
(1− z) (u2z2 − u2z + uz2 + u2 − u+ z)
.
In order to compute a = G(0), we use the kernel method on G(u). We can write the
denominator (which is a polynomial in u of degree 2), as (z−1)(z2−z+1)(u−r)(u−s)
with
r =
1− z2 +
√
z4 − 4 z3 + 2 z2 − 4 z + 1
2(z2 − z + 1)
,
s =
1− z2 −
√
z4 − 4 z3 + 2 z2 − 4 z + 1
2(z2 − z + 1)
.
Replacing u with s (which have a Taylor expansion at z = 0) in order to cancel the numer-
ator of G(u), we obtain the equation
a(sz2 − sz + s+ z − 1) + sz = 0.
Using sr(z2 − z + 1) = z, we deduce
a = G(0) =
1− r
r
− sz.
Finally, after simplifying by the factor (u− s) in the numerators and denominators, we
obtain
F (u) = 1 +
sru
r − u
, G(u) =
s(1− r + rz)
r − u
, and H(u) =
sr − sru(1− z)
r − u
,
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 9
which implies that
[uk]F (u) := fk = [k = 0] + [k ̸= 0] ·
s
rk−1
,
[uk]G(u) := gk =
s(1− r + rz)
rk+1
,
[uk]H(u) := hk =
s
rk
− [k ̸= 0] · (1− z)s
rk−1
,
where [k = 0] (resp. [k ̸= 0]) equals 1 whenever k = 0 (resp. k ̸= 0), and 0 otherwise.
Theorem 2.4. The bivariate generating function for the total number of PMAP (read from
right to left) with respect to the length and the height of the end-point is given by
Total(z, u) = 1 +
s(1 + rz + ruz)
r − u
,
and we have
[uk]Total(z, u) = [k = 0] +
s(rz + 1)
rk+1
+ [k ̸= 0] · sz
rk−1
.
Finally, setting t(n, k) := [zn][uk]Total(z, u), we have for n ⩾ 2, k ⩾ 1,
t(n, k) = t(n− 2, k− 1) + t(n− 2, k)− t(n− 1, k− 1) + t(n− 1, k+ 1) + t(n, k− 1),
and setting tn := t(n, 0), we have t0 = t1 = 1, and for n ⩾ 2,
tn = tn−1 + tn−2 +
n−3∑
k=0
tktn−k−3 +
n−1∑
k=2
(tk − tk−1) tn−k−1.
Proof. The first two equalities are directly deduced from the previous results. Since we
have
(u− u2z2 − uz2 + zu2 − z − u2)Total(z, u) + u2(1− z)− (1 + s− sz)u+ s = 0,
we deduce the third relation. The last equality is already given in Theorem 2.1, since the
number of MAP in M′1 is obviously equal to the number of MAP in M1.
Let T be the infinite matrix T := [t(n, k)]n⩾0,k⩾0. The first few rows of the matrix T
are
T =

1 0 0 0 0 0 · · ·
1 1 1 1 1 1 · · ·
2 3 3 3 3 3 · · ·
5 8 10 12 14 16 · · ·
13 23 33 43 53 63 · · ·
36 69 107 149 195 245 · · ·
105 212 348 512 704 924 · · ·
317 665 1141 1753 2509 3417 · · ·
...
...
...
...
...
...
. . .

.
10 Ars Math. Contemp. 24 (2024) #P3.08
Since there is an infinite number of PMAP of length n, we do not provide an ordinary
generating function (with respect to the length) for these paths. So, we get around this by
counting PMAP ending on a point (x, n− x) for a given n ⩾ 0.
Corollary 2.5. The generating function that counts the partial PMAP ending on the line
y = n− x is given by
Total(z, z) = 1 +
s(1 + rz + rz2)
r − z
.
The first few terms of the series expansion of Total(z, z) are 1 + z + 3z2 + 9z3 +
25z4 + 73z5 + 223z6 + 697z7 + 2217z8 + 7161z9 + O(z10), which correspond to the
sequence A101499 in [13], which is a Chebyshev transform of the Catalan number that
counts peakless Motzkin paths of length n where horizontal steps at level at least one come
in 2 colors. See Figure 4 for an illustration of the 9 PMAP in M′1 ending on the line
y = 3− x.
Notice that, from Theorem 2.4 we have
Total(z, 0) = 1 +
s(1 + rz)
r
,
which is obviously equal to the expression derived in Corollary 2.3 that counts MAP of the
first kind with respect to the length.
Figure 4: The 9 PMAP ending on the line y = 3− x in M′1. Notice that five paths end on
the x-axis, three paths end at height 1, and one path ends at height 2, which correspond to
the fourth diagonal of T .
3 PMAP of the second kind
In this section, we focus on PMAP of the second kind. See Figure 5 for an illustration of
such paths. The first subsection considers paths in M2, while the second handles paths in
M′2. We yield enumerative results for these paths according to the length, the type of the
last step, and the height of the end-point.
3.1 PMAP in M2 - From left to right
In this part, we consider PMAP in M2, i.e. lattice paths in N2 starting at the origin,
consisting of steps U , Dk and H , and where any down step or horizontal step (except
for the last step of the path) is immediately followed by an up step. Figure 5 shows two
examples of such paths.
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 11
Figure 5: The left drawing shows a MAP of length 18 in M2. The right drawing shows a
PMAP of length 18 ending at height 3 in M2.
Let P be a length n PMAP in M2 ending at height k ⩾ 0. If the last step of P is U ,
then k ⩾ 1 and we have P = QU where Q is a length (n−1) PMAP ending at height k−1.
So, we obtain the first relation fk = zfk−1 + zgk−1 + zhk−1 for k ⩾ 1, anchored with
f0 = 1 by considering the empty path. If the last step of P is a down step Da, a ⩾ 1, then
we have P = QDa where Q is a length (n− 1) PMAP ending at height ℓ = a+ k ⩾ k+1
with an up step. So, we obtain the second relation gk = z
∑
ℓ⩾k+1 fℓ. If the last step of P
is a horizontal step H , then we have P = QH where Q is a length (n− 1) PMAP ending
at height k with an up step, which implies hk = zfk.
So, we have to solve the following system of equations.
f0 = 1, and fk = zfk−1 + zgk−1 + zhk−1, k ⩾ 1,
gk = z
∑
ℓ⩾k+1
fℓ, k ⩾ 0,
hk = zfk, k ⩾ 0.
(3.1)
Summing the recursions in (3.1), we have:
F (u) = 1 + z
∑
k⩾1
ukfk−1 + z
∑
k⩾1
ukgk−1 + z
∑
k⩾1
ukhk−1
= 1 + zuF (u) + zuG(u) + zuH(u),
G(u) = z
∑
k⩾0
uk
( ∑
ℓ⩾k+1
fℓ
)
= z
∑
k⩾1
uk − 1
u− 1
fk
=
z
u− 1
(F (u)− F (1)),
H(u) = zF (u).
Now, setting a := F (1) and solving these functional equations, we deduce
F (u) =
au z2 − u+ 1
u2z2 + u2z − uz − u+ 1
,
G(u) = −
z
(
au z2 + auz − a+ 1
)
u2z2 + u2z − uz − u+ 1
, H(u) =
z
(
au z2 − u+ 1
)
u2z2 + u2z − uz − u+ 1
.
In order to compute a = F (1), we use the kernel method on F (u). We can write the
denominator (which is a polynomial in u of degree 2), as (z2 + z)(u− r)(u− s) with
r =
1 + z +
√
−3z2 − 2z + 1
2z (z + 1)
, and s =
1 + z −
√
−3z2 − 2z + 1
2z (z + 1)
.
12 Ars Math. Contemp. 24 (2024) #P3.08
Replacing u with s (which have a Taylor expansion at z = 0) in order to cancel the numer-
ator of F (u), we obtain the equation
as z2 − s+ 1 = 0,
and thus
a = F (1) =
s− 1
sz2
.
Finally using z(1 + z)rs = 1 and simplifying by the factor (u − s) in the numerators
and denominators, we obtain
F (u) =
r
r − u
, G(u) =
s− 1
sz(r − u)
, and H(u) =
zr
r − u
,
which implies that
[uk]F (u) := fk =
1
rk
,
[uk]G(u) := gk = (1 + z) ·
s− 1
rk
,
[uk]H(u) := hk =
z
rk
.
Theorem 3.1. The bivariate generating function for the total number of PMAP with respect
to the length and the height of the end-point is given by
Total(z, u) =
1
z(r − u)
,
and we have
[uk]Total(z, u) =
1
zrk+1
.
Finally, setting t(n, k) = [zn][uk]Total(z, u), we have for n ⩾ 2, k ⩾ 1,
t(n, k) = t(n, k − 1) + t(n− 1, k − 1)− t(n− 1, k − 2)− t(n− 2, k − 2),
and setting tn := t(n, 0), we have t0 = 1, and for n ⩾ 1,
tn = tn−1 +
n−2∑
k=1
tktn−1−k.
Proof. The first two equalities are immediately deduced from the previous results. The
third equality is obtained using the Mathematica package Guess.m ([6]) for guessing
recurrence relations. After this, it suffices to check algebraically:
Total(z, u) = (u+ uz − u2z − u2z2)Total(z, u)− u(1 + z) + 1
zr
.
For the last equality, it suffices to remark that the generating function of the sequence
(tn)n⩾0, that is 1/(zr), generates a shift of the well known Motzkin sequence A001006
in [13].
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 13
Let T be the infinite matrix T := [t(n, k)]n⩾0,k⩾0. The first few rows of the matrix T
are
T =

1 0 0 0 0 0 0 0 · · ·
1 1 0 0 0 0 0 0 · · ·
1 2 1 0 0 0 0 0 · · ·
2 3 3 1 0 0 0 0 · · ·
4 6 6 4 1 0 0 0 · · ·
9 13 13 10 5 1 0 0 · · ·
21 30 30 24 15 6 1 0 · · ·
51 72 72 59 40 21 7 1 · · ·
...
...
...
...
...
...
...
...
. . .

.
Corollary 3.2. The generating function that counts the PMAP with respect to the length is
given by
Total(z, 1) =
1
z(r − 1)
.
The first few terms of the series expansion of Total(z, 1) are 1 + 2z + 4z2 + 9z3 +
21z4+51z5+127z6+323z7+835z8+2188z9+O(z10), which correspond to a shift of
the sequence A001006 in [13] that counts the Motzkin paths of a given length. See Figure 6
for an illustration of the 9 paths of length 3.
Corollary 3.3. The generating function that counts the MAP with respect to the length is
given by
Total(z, 0) =
1
zr
.
The first few terms of the series expansion of Total(z, 0) are 1+ z+ z2+2z3+4z4+
9z5+21z6+51z7+127z8+323z9+O(z10) which correspond to a shift of the sequence
A001006 in [13] that counts Motzkin paths of a given length.
Figure 6: The 9 PMAP of length three in M2. Notice that two paths end on the x-axis,
three paths end at height 1, three paths end at height 2, and one path ends at height 3, which
correspond to the fourth row of T .
14 Ars Math. Contemp. 24 (2024) #P3.08
3.2 PMAP in M′2 - From right to left
Here, we consider the paths of the previous section, but we read them from right to left.
This means that down steps become up steps and vice versa, and horizontal steps are un-
changed, which implies that any up step or horizontal step (except the first step of the path)
is preceded by a down step. See Definition 1.4 and Figure 7 for two examples of such
paths.
Figure 7: The left drawing shows a Motzkin path with air pockets of length 18 in M′2
(read from right to left). The right drawing shows a partial Motzkin path with air pockets
of length 18 ending at height 2 in M′2.
Let P be a length n PMAP in M′2 ending at height k ⩾ 0. If the last step of P is Ua, a ⩾
1, then k ⩾ a and we have P = QUa where Q is a length (n− 1) PMAP ending at height
ℓ = k−a with a down step. So, we obtain the first relation fk = z+z(g0+g1+. . .+gk−1)
for k ⩾ 1, anchored with f0 = 1 by considering the empty path. If the last step of P is a
down step D, then we have P = QD where Q is a length (n− 1) PMAP ending at height
k+1. So, we obtain the second relation gk = zfk+1+zgk+1+zhk+1. If the last step of P
is a horizontal step H , then we have P = QH where Q is a length (n− 1) PMAP ending
at height k with a down step whenever it is nonempty. If k ⩾ 1, then we have hk = zgk; if
k = 0 then we have h0 = z + zg0 where the monomial z corresponds to the path P = H .
So, we have to solve the following system of equations.
f0 = 1, and fk = z(1 + g0 + g1 + . . .+ gk−1), k ⩾ 1,
gk = zfk+1 + zgk+1 + zhk+1, k ⩾ 0,
h0 = z + zg0, and hk = zgk, k ⩾ 1.
(3.2)
Using the same notations as in the previous sections, and summing the recursions in
(3.2), we have:
F (u) = 1 +
∑
k⩾1
ukfk = 1 + z
∑
k⩾1
(1 + g0 + . . .+ gk−1)u
k
= 1 +
zu
1− u
(1 +G(u)),
G(u) = z
∑
k⩾0
(fk+1 + gk+1 + hk+1)u
k
=
z
u
(F (u)− F (0) +G(u)−G(0) +H(u)−H(0)),
H(u) = z + zG(u).
Notice that F (0) = 1 and H(0) = z + zG(0) by the third relation. Now, setting
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 15
a := G(0) and solving these functional equations, we deduce
F (u) =
a uz3 + a uz2 + uz3 − u2z + uz2 + u2 − uz + z2 − u+ z
u2 − uz + z2 − u+ z
,
G(u) = −z (a uz + a u− a z + uz − a)
u2 − uz + z2 − u+ z
,
H(u) = −
z
(
a uz2 + a uz − a z2 + uz2 − a z − u2 + uz − z2 + u− z
)
u2 − uz + z2 − u+ z
.
In order to compute a = G(0), we use the kernel method on F (u). We can write the
denominator (which is a polynomial in u of degree 2), as (u− r)(u− s) with
r =
1 + z +
√
−3 z2 − 2 z + 1
2
, and s =
1 + z −
√
−3 z2 − 2 z + 1
2
.
Replacing u with s (which have a Taylor expansion at z = 0) in oder to cancel the numer-
ator of F (u), we obtain the equation
a sz3 + a sz2 + sz3 − s2z + sz2 + s2 − sz + z2 − s+ z = 0.
Using rs = z(1 + z), we deduce
a = G(0) =
1− r
r
.
Finally, after simplifying by the factor (u − s) in the numerators and denominators, we
obtain
F (u) =
u(z − 1) + r
r − u
, G(u) =
1− r
r − u
, and H(u) =
z(1− u)
r − u
,
which implies that
[uk]F (u) := fk =
1
rk
+ [k ̸= 0] · z − 1
rk
,
[uk]G(u) := gk =
1− r
rk+1
,
[uk]H(u) := hk =
z
rk+1
− [k ̸= 0] · z
rk
.
Theorem 3.4. The bivariate generating function for the total number of PMAP with respect
to the length and the height of the end-point is given by
Total(z, u) =
1− u+ z
r − u
.
[uk]Total(z, u) =
z + 1
rk+1
− [k ̸= 0] · 1
rk
.
Finally, setting t(n, k) = [zn][uk]Total(z, u), we have for n ⩾ 1, k ⩾ 1,
t(n, k) = t(n, k − 1)− t(n− 1, k) + t(n− 2, k + 1) + t(n− 1, k + 1),
and setting tn := t(n, 0), we have t0 = 1, and for n ⩾ 2,
tn = tn−1 +
n−2∑
k=1
tktn−1−k.
16 Ars Math. Contemp. 24 (2024) #P3.08
Proof. The proof are obtained mutatis mutandis as for the previous theorems.
Let T be the infinite matrix T := [t(n, k)]n⩾0,k⩾0. The first few rows of the matrix T
are
T =

1 0 0 0 0 0 0 · · ·
1 1 1 1 1 1 1 · · ·
1 1 1 1 1 1 1 · · ·
2 3 4 5 6 7 8 · · ·
4 6 8 10 12 14 16 · · ·
9 15 22 30 39 49 60 · · ·
21 36 54 75 99 126 156 · · ·
51 91 142 205 281 371 476 · · ·
...
...
...
...
...
...
...
. . .

.
Since there is an infinite number of PMAP of length n, we do not provide an ordinary
generating function (with respect to the length) for these paths. So, we get around this by
counting PMAP ending on a point (x, n− x) for a given n ⩾ 0.
Corollary 3.5. The generating function that counts the partial PMAP ending on the line
y = n− x is given by
Total(z, z) =
1
r − z
.
The first few terms of the series expansion of Total(z, z) are 1 + z + 2z2 + 4z3 +
9z4+21z5+51z6+127z7+323z8+835z9+O(z10), which correspond to the sequence
A001006 in [13] that counts the Motzkin paths with respect to the length. See Figure 8 for
the illustration of the 9 PMAP in M′2 ending on the line y = 4− x.
Notice that we obviously retrieve the results of Corollary 3.3, i.e., the generating func-
tion Total(z, 0) that counts the MAP with respect to the length is also a shift of the
Motzkin sequence A001006 in [13].
Figure 8: The 9 PMAP ending on the line y = 4 − x in M′2. Notice that four paths end
on the x-axis, three paths end at height 1, one path ends at height 2, and one path ends at
height 3, which correspond to the fifth diagonal of T .
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 17
4 A Riordan array point of view
In this section, we make links between the previous matrices T = [tn,k]n⩾0,k⩾0 and some
Riordan arrays or almost Riordan arrays. We first give a short background on Riordan
arrays [4, 5, 12].
An infinite column vector (a0, a1, . . . )T has generating function f(z) if f(z) =∑
n⩾0 anz
n. A Riordan array is an infinite lower triangular matrix whose k-th column
has generating function g(z)f(z)k for all k ⩾ 0, for some formal power series g(z) and
f(z), with g(0) ̸= 0, f(0) = 0, and f ′(0) ̸= 0. Such a Riordan array is denoted by
(g(z), f(z)). If we multiply this matrix by a column vector (b0, b1, . . . )T having generat-
ing function h(z) =
∑
n⩾0 bnz
n, then the resulting column vector has generating function
g(z)h(f(z)). This property is known as the fundamental theorem of Riordan arrays.
The product of two Riordan arrays (g(z), f(z)) and (h(z), l(z)) is defined by
(g(z), f(z)) ∗ (h(z), l(z)) = (g(z)h(f(z)), l(f(z))) .
Under the operation “∗”, the set of all Riordan arrays is a group [12]. The identity element
is I = (1, z), and the inverse of (g(z), f(z)) is
(g(z), f(z))−1 =
(
1/
(
g ◦ f
)
(z), f(z)
)
,
where f(z) denotes the compositional inverse of f(z).
Moreover, if a matrix T = [tn,k]n⩾0,k⩾0 is a Riordan array (g(z), f(z)) then tn,k
equals the coefficient of znuk in the series expansion of the bivariate generating function
g(z)
1− uf(z)
,
and we say that this is the bivariate generating function of the matrix T .
An almost Riordan array T ′ is a matrix that consists of an initial column vector
(d0, d1, . . . )
T with generating function g0(z) =
∑
n⩾0 dnz
n, followed by a vertically
shifted Riordan array (g(z), f(z)) as illustrated below.
T ′ =

d0 0 · · · 0 0 · · ·
d1
d2
d3 (g(z), f(z))
d4
d5
...
...
...
...
...
...

Therefore, the bivariate generating function for this matrix is given by
g0(z) + zu
g(z)
1− uf(z)
.
Finally, we will say that a matrix M = [mn,k]n⩾0,k⩾0 is the rectification of the Riordan
array (g(z), f(z)) whenever mn,k equals the coefficient of znuk in the series expansion of
18 Ars Math. Contemp. 24 (2024) #P3.08
the bivariate generating function
g(z)
1− u f(z)z
.
In this section, C(z) = 1−
√
1−4z
2z will be the generating function where the coefficient
of zn in its series expansion is the Catalan number cn = 1n+1
(
2n
n
)
.
4.1 Comment on Section 2.1
Let T = [t(n, k)]n⩾0,k⩾0 be the matrix given in Section 2.1 where t(n, k) is the number
of length n PMAP in M1 ending at height k.
Proposition 4.1. The matrix T = [t(n, k)]n⩾0,k⩾0 is a Riordan array defined by
(
1
1− z2
C
(
z(1− z + z2)
(1− z2)2
)
,
z
1− z2
C
(
z(1− z + z2)
(1− z2)2
))
.
Proof. Considering r defined in Section 2.1, we have
[uk]Total(z, u) =
1
zrk+1
=
(
1
zr
)(
1
r
)k
=
2
1− z2 +
√
1− 4z + 2z2 − 4z3 + z4
(
2z
1− z2 +
√
1− 4z + 2z2 − 4z3 + z4
)k
.
Therefore, the array T satisfies
T =
(
2
1− z2 +
√
1− 4z + 2z2 − 4z3 + z4
,
2z
1− z2 +
√
1− 4z + 2z2 − 4z3 + z4
)
=
(
1− z2 −
√
1− 4z + 2z2 − 4z3 + z4
2z(1− z + z2)
,
1− z2 −
√
1− 4z + 2z2 − 4z3 + z4
2(1− z + z2)
)
=
(
1
1− z2
C
(
z(1− z + z2)
(1− z2)2
)
,
z
1− z2
C
(
z(1− z + z2)
(1− z2)2
))
.
Proposition 4.2. The general term t(n, k) equals
n−k∑
i=0
(
k + n−k−i2
n−k−i
2
)
1 + (−1)n−k−i
2
i∑
j=0
Ck+j,k
j∑
m=0
(
j
m
)
(−1)m
m∑
p=0
(
m
p
)
(−1)p
(
2j − 1 + i−j−m−p2
i−j−m−p
2
)
1 + (−1)i−j−m−p
2
,
where Cn,k = k+1n+1
(
2n−k
n−k
)
is the general term of the Catalan matrix (A033184 in [13]).
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 19
Proof. Setting Z = z(1−z+z
2)
(1−z2)2 , we have
t(n, k) = [zn]zk
1
(1− z2)k+1
C(Z)k+1
= [zn−k]
1
(1− z2)k+1
C(Z)k+1
=
n−k∑
i=0
[zn−k−i]
1
(1− z2)k+1
[zi]C(Z)k+1 (product rule [8])
=
n−k∑
i=0
[zn−k−i]
1
(1− z2)k+1
i∑
j=0
[zj ]C(z)k+1[zi]Zj (composition rule [8])
=
n−k∑
i=0
[zn−k−i]
1
(1− z2)k+1
i∑
j=0
[zj ]
1
zk
C(z)(zC(z))k[zi]Zj
=
n−k∑
i=0
(
k + n−k−i2
n−k−i
2
)
1 + (−1)n−k−i
2
i∑
j=0
Ck+j,k[z
i]Zj (see [8]).
Since we have
[zi]Zj = [zi]
(
z(1− z + z2)
(1− z2)2
)j
=
j∑
m=0
(
j
m
)
(−1)m
m∑
p=0
(
m
p
)
(−1)p
(
2j − 1 + i−j−m−p2
i−j−m−p
2
)
1 + (−1)i−j−m−p
2
,
the result follows.
4.2 Comment on Section 2.2
Let T = [t(n, k)]n⩾0,k⩾0 be the matrix given in Section 2.2 where t(n, k) is the number
of length n PMAP in M′1 ending at height k.
Proposition 4.3. The matrix T = [t(n, k)]n⩾0,k⩾0 can be written
T =

1 0 0 0 0 0 · · ·
1 1 1 1 1 1 · · ·
2 3 3 3 3 3 · · ·
5 8 10 12 14 16 · · ·
13 23 33 43 53 63 · · ·
36 69 107 149 195 245 · · ·
...
...
...
...
...
...
. . .

= A ·B
20 Ars Math. Contemp. 24 (2024) #P3.08
where
A =

1 0 0 0 0 0 · · ·
1 1 0 0 0 0 · · ·
2 3 0 0 0 0 · · ·
5 8 2 0 0 0 · · ·
13 23 10 0 0 0 · · ·
36 69 38 4 0 0 · · ·
...
...
...
...
...
...
. . .

and B =

1 0 0 0 0 0 · · ·
0 1 1 1 1 1 · · ·
0 0 1 2 3 4 · · ·
0 0 0 1 3 6 · · ·
0 0 0 0 1 4 · · ·
0 0 0 0 0 1 · · ·
...
...
...
...
...
...
. . .

are defined as follows:
• The matrix B = [bn,k]n,k⩾0 is defined by b0,0 = 1, and bn,0 = b0,n = 0 if n ⩾ 1,
and bn,k =
(
k−1
n−1
)
otherwise, which is a kind of Pascal matrix.
• The matrix A = [an,k]n,k⩾0 is the almost Riordan array with initial column of gen-
erating function
g0(z) =
1− z2 −
√
1− 4z + 2z2 − 4z3 + z4
2z(1− z + z2)
,
followed by the shifted Riordan array(
1− 3z + z2 − z3 − (1− z)
√
1− 4z + 2z2 − 4z3 + z4
2z3(1− z + z2)
,
1− 2z − z2 −
√
1− 4z + 2z2 − 4z3 + z4
2z
)
.
The second column of T 1, 3, 8, 23, 69, . . . with generating function
1− 3z + z2 − z3 − (1− z)
√
1− 4z + 2z2 − 4z3 + z4
2z3(1− z + z2)
is the convolution of the first column of T 1, 1, 2, 5, 13, 36, . . . (A114465 in [13]) and the
sequence 1, 2, 4, 10, 28, . . . (A187256 in [13]).
Proof. An almost Riordan array is represented by an initial column vector with generating
function g0(z), followed by a vertically shifted Riordan array (g(z), f(z)). The bivariate
generating function of this matrix is then given by g0(z) + zu
g(z)
1−uf(z) . In our case, for the
almost Riordan array A, we have
g0(z) =
1− z2 −
√
1− 4z + 2z2 − 4z3 + z4
2z(1− z + z2)
,
g(z) =
1− 3z + z2 − z3 − (1− z)
√
1− 4z + 2z2 − 4z3 + z4
2z3(1− z + z2)
,
f(z) =
1− 2z − z2 −
√
1− 4z + 2z2 − 4z3 + z4
2z
.
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 21
We let G(z, u) = g0(z) + zu
g(z)
1−uf(z) , the bivariate generating function of the almost Rior-
dan array. Now, it suffices to check that the generating function corresponding to the matrix
A ·B, that is
G(z,
u
1− u
) =
(1− u+ uz)(1− 2z + 2uz − (1 + 2u)z2 −
√
1− 4z + 2z2 − 4z3 + z4
2(1− z + z2)(u(u− 1) + (1− u2)z + u(u+ 1)z2)
,
coincides with the generating function Total(z, u) of the matrix T .
Proposition 4.4. The matrix
[t(n, k)]n⩾1,k⩾1 =

1 1 1 1 1 · · ·
3 3 3 3 3 · · ·
8 10 12 14 16 · · ·
23 33 43 53 63 · · ·
69 107 149 195 245 · · ·
...
...
...
...
...
. . .

is the rectification of the Riordan array (g(z), h(z)) with
h(z) =
1− z2 −
√
1− 4z + 2z2 − 4z3 + z4
2
, and
g(z) =
1− 3z + z2 − z3 − (1− z)
√
1− 4z + 2z2 − 4z3 + z4
2z3(1− z + z2)
.
Proof. It suffices to check that the generating function of T , i.e. Total(z, u), given in
Theorem 2.4, equals to
Total(z, 0) + zu
g(z)
1− uh(z)z
.
We can express h(z) and g(z), respectively, in the following form
h(z) =
z(1− z + z2)
1− z2
C
(
z(1− z + z2)
(1− z2)2
)
,
g(z) =
1
1− 3z + z2 − z3
C
(
z3(1− z + z2)
(1− 3z + z2 − z3)2
)
.
Then g(z) expands to give the first column 1, 3, 8, 23, . . ., whose n-th term vn can be
expressed
vn =
n∑
k=0
k∑
j=0
(
k
j
)
(−1)j
j∑
i=0
(
j
i
)
(−1)i
n−3k−j−i∑
ℓ=0
(
2k + ℓ
ℓ
) ℓ∑
m=0
(
ℓ
m
)
3ℓ−m(−1)m
(
m
n− 3k − j − i− ℓ−m
)
(−1)n−3k−j−i−ℓ−mck.
Using vn, we can deduce the following.
22 Ars Math. Contemp. 24 (2024) #P3.08
Proposition 4.5. The general term t(n, k) equals
n+k∑
i=0
vn+k−i
i∑
j=0
j∑
m=0
Mm,k
m∑
p=0
(
m
p
)
(−1)p
p∑
q=0
(
p
q
)
(−1)q
(
2m− 1 + j−m−p−q2
j−m−p−q
2
)
1 + (−1)j−m−p−q
2
(
k
i−j
2
)
(−1)
i−j
2
1 + (−1)i−j
2
,
where
Mn,k =
{
[k = 0] if n = 0,
n
k
(
2n−k−1
n−k
)
otherwise,
is the general term of Riordan array (1, zC(z)) (see A106566 in [13]).
4.3 Comment on Section 3.1
Let T = [t(n, k)]n⩾0,k⩾0 be the matrix given in Section 3.1 where t(n, k) is the number
of length n PMAP in M2 ending at height k.
Proposition 4.6. The matrix T = [t(n, k)]n⩾0,k⩾0 is the Riordan array
T = (1 + zM(z), z(1 + zM(z)))
=
(
C
(
z
1 + z
)
, zC
(
z
1 + z
))
,
where M(z) = 1−z−
√
1−2z−3z2
2z2 is the generating function of the Motzkin numbers (see
A001006 in [13]).
Proof. It suffices to check that Total(z, u) given in Theorem 3.1 satisfies
Total(z, u) =
C
(
z
1+z
)
1− uzC
(
z
1+z
) ,
and that 1 + zM(z) = C
(
z
1+z
)
.
This triangle T corresponds to A091836 in [13] where the coefficient of row n− 1 and
column k is the number of Motzkin paths of length n having k points on the horizontal axis
(besides the first and last point). As mentioned in [13], we obtain
t(n, k) =

1, if n = k,
k+1
n+1
n−k∑
j=1
j(−1)n−k−j
(
n+j
j
) n−k∑
i=0
1
n−k
(
i
n−k−i+j
)(
n−k
i
)
, otherwise.
A second expression for t(n, k) is given by the following proposition.
Proposition 4.7. The general term t(n, k) of the Riordan array (1+zM(z), z(1+zM(z)))
is given by
t(n, k) =
{
1 if n = k,
k+1
n−k
∑k
j=0
(
k
j
)∑n−k
i=0
(
n−k
i
)(
i
n−k−i−j−1
)
otherwise.
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 23
Proof. We prove this using Lagrange inversion, using the fact that
z
1 + z + z2
M
(
z
1 + z + z2
)
= z,
which means that the compositional inverse (zM(z))−1 of zM(z) is
(zM(z))−1 =
z
1 + z + z2
.
Thus we have
t(n, k) = [zn](1 + zM(z))(z(1 + zM(z)))k
= [zn−k](1 + zM(z))k+1
= [zn−k]G(zM(z)), with G(z) = (1 + z)k+1
=
1
n− k
[zn−k−1]G′(z)
(
z
(zM(z))−1
)n−k
(Lagrange inversion)
=
1
n− k
[zn−k−1](k + 1)(1 + z)k(1 + z + z2)n−k
=
k + 1
n− k
[zn−k]
k∑
j=0
(
k
j
)
zj
n−k∑
i=0
(
n− k
i
)
zi(1 + z)i
=
k + 1
n− k
[zn−k]
k∑
j=0
(
k
j
)
zj
n−k∑
i=0
(
n− k
i
)
zi
i∑
ℓ=0
(
i
ℓ
)
zℓ
=
k + 1
n− k
k∑
j=0
(
k
j
) n−k∑
i=0
(
n− k
i
)(
i
n− k − i− j − 1
)
.
Remark 4.8. The Riordan array (1 + zM(z), z(1 + zM(z))) is a pseudo-involution in
the Riordan group (see [5, Example 8]), that is, the matrix [(−1)ktn,k]n,k⩾0 is idempotent.
Thus, this work yields a significant lattice path interpretation of this array.
4.4 Comment on Section 3.2
Let T = [t(n, k)]n⩾0,k⩾0 be the matrix given in Section 3.2 where t(n, k) is the number
of length n PMAP in M′2 ending at height k.
Proposition 4.9. The matrix T = [t(n, k)]n⩾0,k⩾0 can be written
T =

1 0 0 0 0 0 · · ·
1 1 1 1 1 1 · · ·
1 1 1 1 1 1 · · ·
2 3 4 5 6 7 · · ·
4 6 8 10 12 14 · · ·
9 15 22 30 39 49 · · ·
...
...
...
...
...
...
. . .

= A ·B
24 Ars Math. Contemp. 24 (2024) #P3.08
where
A =

1 0 0 0 0 0 · · ·
1 1 0 0 0 0 · · ·
1 1 0 0 0 0 · · ·
2 3 1 0 0 0 · · ·
4 6 2 0 0 0 · · ·
9 15 7 1 0 0 · · ·
...
...
...
...
...
...
. . .

and B =

1 0 0 0 0 0 · · ·
0 1 1 1 1 1 · · ·
0 0 1 2 3 4 · · ·
0 0 0 1 3 6 · · ·
0 0 0 0 1 4 · · ·
0 0 0 0 0 1 · · ·
...
...
...
...
...
...
. . .

are defined as follows:
• The matrix B = [bn,k]n,k⩾0 is defined by b0,0 = 1, and bn,0 = b0,n = 0 if n ⩾ 1,
and bn,k =
(
k−1
n−1
)
otherwise, which is the same as in Proposition 4.3.
• The matrix A = [an,k]n,k⩾0 is the almost Riordan array with initial column whose
generating function is
g0(z) = 1 + zM(z) =
1 + z −
√
1− 2z − 3z2
2z
,
which is followed by the shifted Riordan array (g(z), z2g(z)) where
g(z) =
1− z − 2z2 −
√
1− 2z − 3z2
2z3(1 + z)
.
Proof. The almost Riordan array A has generating function
g0(z) + zu
g(z)
1− z2ug(z)
.
Setting G(z, u) = g0(z) + zu
g(z)
1−z2ug(z) , it suffices to check that the generating function
corresponding to the matrix A·B, that is G(z, u1−u ), coincides with the generating function
Total(z, u) of the matrix T given in Theorem 3.4.
Proposition 4.10. The matrix
[t(n, k)]n⩾1,k⩾1 =

1 1 1 1 1 · · ·
1 1 1 1 1 · · ·
3 4 5 6 7 · · ·
6 8 10 12 14 · · ·
15 22 30 39 49 · · ·
36 54 75 99 126 · · ·
...
...
...
...
...
. . .

is the rectification of the Riordan array (M(z), zR(z)) where M(z) = 1−z−
√
1−2z−3z2
2z2
is the generating function of the Motzkin numbers, and R(z) = 1+z−
√
1−2z−3z2
2z(1+z) is the
generating function of the Riordan numbers (A005043 in [13]).
J.-L. Baril and P. Barry: Two kinds of partial Motzkin paths with air pockets 25
Proof. It suffices to check that the generating function of T , i.e. Total(z, u), given in
Theorem 3.4, equals to g0(z) + zu
M(z)
1−u zR(z)z
.
We let mn denote the n-th Motzkin number mn =
∑⌊n2 ⌋
k=0
(
n
2k
)
ck where ck is the k-th
Catalan defined above.
Corollary 4.11. We have
t(n, k) =
{
[k = 0] if n = 0,
r(n− 1, k) otherwise,
where
r(n, k) =
n∑
i=0
mi · (k + [n = i])
n+ k − i+ [n = i]
n−i∑
j=0
(−1)n−i−j
(
n+ k − i+ j − 1
j
) n+k−i∑
ℓ=0
(
n+ k − i
ℓ
)(
ℓ
n− i− j − ℓ
)
.
Proof. We have (M(z), zR(z))−1 =
(
(1−x)2
1−x+x2 ,
x(1−x)
1−x+x2
)
. If we denote by (v(z), u(z))
this inverse Riordan array, then we obtain
(M(z), zR(z)) =
(
1
v(ū(z))
, ū(z)
)
,
where ū is the compositional inverse [8] of u. Using the definition of a Riordan array, and
Lagrange inversion, we find that the Riordan array (M(z), zR(z)) has general term r̃(n, k)
given by
n∑
i=0
mi · (k + [n = k + i])
n− i+ [n = k + i]
n−k−i∑
j=0
(−1)n−k−i−j
(
n− i+ j − 1
j
) n−i∑
ℓ=0
(
n− i
ℓ
)(
ℓ
n− k − i− j − ℓ
)
.
This array begins as follows:
1 0 0 0 0 0 · · ·
1 1 0 0 0 0 · · ·
2 1 1 0 0 0 · · ·
4 3 1 1 0 0 · · ·
9 6 4 1 1 0 · · ·
21 15 8 5 1 1 · · ·
...
...
...
...
...
...
. . .

.
To rectify this array and thus to obtain the array (M(z), R(z)), we change n to n+ k, and
we obtain r(n, k) above. To this array we must now prepend the row (1, 0, 0, 0, . . .), and
the result follows.
ORCID iDs
Jean-Luc Baril https://orcid.org/0000-0002-9811-8028
Paul Barry https://orcid.org/0000-0003-1909-8725
26 Ars Math. Contemp. 24 (2024) #P3.08
References
[1] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-
Beauchamps, Generating functions for generating trees, Discrete Math. 246 (2002), 29–55, doi:
10.1016/S0012-365X(01)00250-3, https://doi.org/10.1016/S0012-365X(01)
00250-3.
[2] J.-L. Baril, S. Kirgizov, R. Maréchal and V. Vajnovszki, Enumeration of Dyck paths with air
pockets, J. Integer Seq. 26 (2023), Article 23.3.2, 23 pp., https://cs.uwaterloo.ca/
journals/JIS/VOL26/Kirgizov/kirg5.html.
[3] J.-L. Baril, S. Kirgizov, R. Maréchal and V. Vajnovszki, Grand Dyck paths with air pockets, Art
Discrete Appl. Math. 7 (2024), Article #P1.07, doi:10.26493/2590-9770.1587.b2a, https:
//doi.org/10.26493/2590-9770.1587.b2a.
[4] P. Barry, Riordan Arrays: A Primer, Logic Press, Kilcock, Co. Kildare, 2017.
[5] A. Burstein and L. W. Shapiro, Pseudo-involutions in the Riordan group, J. Integer Seq. 25
(2022), Article 22.3.6, 54 pp., https://cs.uwaterloo.ca/journals/JIS/VOL25/
Burstein/burstein14.html.
[6] M. Kauers, Guessing Handbook, Version 0.32, 2009, Technical Report 09-07, RISC-Linz,
https://www3.risc.jku.at/research/combinat/software/ergosum/
RISC/Guess.html.
[7] A. Krinik, G. Rubino, D. Marcus, R. J. Swift, H. Kasfy and H. Lam, Dual processes to solve
single server systems, J. Stat. Plann. Inference 135 (2005), 121–147, doi:10.1016/j.jspi.2005.
02.010, https://doi.org/10.1016/j.jspi.2005.02.010.
[8] D. Merlini, R. Sprugnoli and M. C. Verri, The method of coefficients, Am. Math. Monthly 114
(2007), 40–57, doi:10.1080/00029890.2007.11920390, https://doi.org/10.1080/
00029890.2007.11920390.
[9] H. Prodinger, The kernel method: a collection of examples, Sémin. Lothar. Comb.
50 (2004), Article B50f, 19 pp., https://www.mat.univie.ac.at/%7Eslc/
wpapers/s50proding.html.
[10] H. Prodinger, Partial Dyck paths with air pockets, Integers 22 (2022), Paper A94, 8 pp., doi:10.
5281/zenodo.10997311, http://math.colgate.edu/˜integers/vol22.html.
[11] E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, J.
Théor. Nombres Bordeaux 27 (2015), 245–288, doi:10.5802/jtnb.901, https://doi.org/
10.5802/jtnb.901.
[12] L. W. Shapiro, S. Getu, W. J. Woan and L. C. Woodson, The Riordan group, Discrete Appl.
Math. 34 (1991), 229–239, doi:10.1016/0166-218X(91)90088-E, https://doi.org/10.
1016/0166-218X(91)90088-E.
[13] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis.org.