Motzkin and Catalan Tunnel Polynomials

Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo

Dipartimento di Matematica Università di Bologna Bologna, 40126 Italy

              marilena.barnabei@unibo.it
                flavio.bonetti@unibo.it
             niccolo.castronuovo2@unibo.it

Matteo Silimbani SSPG “M. Marinelli” Forlimpopoli, 47034 Italy

              matteo.silimbani4@unibo.it

Abstract

We define sequences MT_{n} and CT_{n} of polynomials associated with Motzkin and Catalan paths, respectively. We show that these polynomials satisfy recurrence relations similar to the one satisfied by Motzkin and Catalan numbers. We study in detail many different specializations of these polynomials, which turn out to be sequences of great interest in combinatorics, such as the Schröder numbers, Fibonacci numbers, q-Catalan polynomials, and Narayana polynomials. We show a connection between the polynomials CT_{n} and the family of binary trees, which allows us to find another specialization for our polynomials in term of path length in these trees. In the last section we extend the previous results to partial and free Motzkin paths.

1 Introduction

Catalan and Motzkin numbers (sequences \underline{A000108} and \underline{A001006} in [25]) are well known in mathematics. They both appear in many different contexts, from the enumeration of lattice paths to that of permutation classes, trees, partitions (see e.g., [26, 27] for Catalan numbers and [2, 8, 10, 21] for Motzkin numbers).

Due to their importance in enumerative combinatorics, several generalizations for Catalan numbers are present in the literature. Most of such generalizations consist of polynomials in one or two variables that reduce to Catalan numbers under appropriate specializations. For example, there are at least three different objects that share the name q-Catalan numbers, due to Mac Mahon, Carlitz and Riordan, and Polya and Gessel, respectively. All these are q-analogs of Catalan numbers, i.e., polynomials that yield Catalan numbers when q = 1 (see [13] for an overwiew of these three families). Similarly, in the case of two variables, different families of q,t-Catalan polynomials that specialize to Catalan numbers for q = t = 1 were defined both by Garsia and Haiman in connection with the theory of diagonal harmonics (see [14, 15] for further details), and by Adin and Roichman in connection with maximal chains in the non-crossing partition lattice (see [1]).

Even if generalizations of Motzkin numbers are less studied, it is possible to find some of them in the literature. For example, Flajolet [11] introduced a family of polynomials defined as the generating functions of appropriate weighted Motzkin paths, and studied their properties with an emphasis on the relation with continued fractions. In [22] the authors generalize these polynomials and studied their properties in terms of recurrence relations. On the other hand, in [4], the authors introduce three families of q-analogs of Motzkin numbers. All the three families of polynomials are defined by recursions and are shown to be the generating functions for particular sets of polyominoes and Dyck words according to various parameters (area, perimeter, width, inversions).

The main goal of this paper is to define and study two new families of polynomials defined in terms of Motzkin and Dyck paths, respectively. To this aim, we associate a weight with each step of a Motzkin or Dyck path. Using these weights we define polynomials MT_{n} and CT_{n} in a number of variables that increases with the length n of the paths. Our approach is similar to the one proposed in [11], even if in that paper the weight of a step depends only on its height. On the contrary, our definition of weight takes into account the lengths of the weak tunnels of the path, namely, a slightly modified version of the tunnels defined in [9].

The polynomials MT_{n} and CT_{n} satisfy recurrence relations analogous to the classical recursions for Motzkin and Catalan numbers. While under trivial specialization polynomials MT_{n} and CT_{n} give Motzkin and Catalan numbers, under more subtle specialization they produce a plethora of well known sequences such as Schröder numbers, Fibonacci numbers, Carlitz-Riordan q-Catalan polynomials, Narayana polynomials. Combining different specializations we get also joint distributions of various parameters over the sets of Motzkin and Dyck paths. The recurrence relations for MT_{n} and CT_{n} allow us to deduce continued fraction expressions for the generating functions of such parameters. Note that our continued fraction is different from that obtained in [11] and in other works (see e.g., [4]).

The outline of the work is the following.

In Section 2, we define the Motzkin tunnel polynomial MT_{n} by assigning to each step S of a Motzkin path a weight that depends on the length t(S) of the maximal weak tunnel whose ending point is the starting point of S. We show that the polynomials MT_{n} satisfy a recurrence relation similar to the one that defines Motzkin numbers. Moreover we prove a symmetry property for these polynomials. In the last part of the section we exhibit some specializations of Motzkin tunnel polynomials and deduce a continued fraction expansion for the multi-variate generating function of Motzkin paths that takes into account the parameters length, area, peaks, occurrences of UHD, and number of horizontal steps. In a particular case we are able to compute the Hankel determinant of a sequence of these polynomials.

In Section 3 we associate a polynomial CT_{n} with the set of Dyck paths of a given semilength n in a way similar to that of previous Section. Since each weak tunnel of a Dyck path has even length, in this case we label each step S with t(S)/2. Let CT_{n} denote the n-th Catalan tunnel polynomial. As above, we find specializations for CT_{n} and deduce a continued fraction expansion for the generating function that takes into account length, area, peaks and occurrences of UUDD of Dyck paths.

In Section 4 we show that the polynomials CT_{n} have an interpretation in terms of suitable labellings of binary trees. This allows us to deduce a further specialization for Catalan tunnel polynomial that coincides with the generating function of binary trees with the parameters “number of internal nodes” and “internal path length”.

In Section 5 we introduce multi-variable polynomials associated with partial Motzkin paths (prefixes of Motzkin paths) and to free Motzkin paths (lattice paths in the plane that consist of n steps arbitrarily chosen among up, down and horizontal steps), study their properties and specializations and derive a matrix identity that generalizes the one appearing in [6].

2 Motzkin tunnel polynomials

2.1 Basic definitions

A Motzkin path of length n is a lattice path in the plane from (0, 0) to (n, 0) consisting of up steps U = (1, 1), down steps D = (1, −1) and horizontal steps H = (1, 0), that never goes below the x-axis. A Dyck path of semilength k is a Motzkin path of length 2k with no horizontal steps. We let ℳ_{n} denote the set of Motzkin paths of length n and by 𝒞_{k} the set of Dyck paths of semilength k.

One can encode a Motzkin path in ℳ_{n} by a Motzkin word of length n in the letters U, H, and D. A return of a Motzkin path p is a point of p different from (0, 0) and belonging to the x-axis.

Notice that a Motzkin path p is either of the form p′ H, or p′ U p′′ D, where p′ and p′′ are Motzkin paths (last return decomposition).

A weak tunnel in a Motzkin path p is a horizontal segment between two lattice points of p lying always weakly below p. A weak tunnel can consist of a single point. The length of a weak tunnel is the difference between the x-coordinates of its ending and starting points. For every non-horizontal step S of p we let t(S) denote the length of the maximal weak tunnel ending at the initial point of S.

Now we associate with every Motzkin path p of length n a monomial m(p) in the 2n − 1 variables {x_{0}, x_{1}, …, x_{n−2}, y_{0}, y_{1}, …, y_{n−2}, z} as follows. We assign to every step S the weight x_{t(S)} if S is an up step, the weight y_{t(S)} if S is an down step, and the weight z if S is a horizontal step. We define the monomial m(p) as the product of the weights of each step of p.

Example 1. Consider the following Motzkin path

\begin{matrix}x_{0} \\ x_{0} \\ x_{3} \\ z \\ z \\ x_{0} \\ y_{1} \\ y_{0} \\ y_{3} \\ y_{8} \end{matrix}

where every step has been labelled with its weight. Then, the corresponding monomial is x_{0}^{3}x_{3}y_{0}y_{1}y_{3}y_{8}z^{2}.

Notice that different Motzkin paths can have the same associated monomial. For example, if p = HHUUDD and q = UDUHHD, then m(p) = m(q) = x_{0}x_{2}y_{0}y_{2}z^{2}.

Moreover,

• the exponent of x_{0} in m(p) equals the number of occurrences of UU, increased by one if p begins with U.

• The exponent of x_{1} equals the number of occurrences of UHU, increased by one if p begins with HU.

• The exponent of y_{0} in m(p) equals the number of peaks in p, namely, occurrences of UD. In fact, a down step D of a Motzkin path has label 0 whenever the maximal tunnel ending at the first point of D reduces to a single point. This happens if and only if D is the down step of a peak.

• Similarly, the exponent of y_{1} equals the number of occurrences of UHD in p.

For every integer n, we define the polynomial

MT_{n} = MT_{n}(x_{0}, x_{1}, …, x_{n−2}; y_{0}, y_{1}, …, y_{n−2}; z) = ∑_{p∈ℳ_{n}} m(p).

For 0 ≤ n ≤ 5, these polynomials are

MT_{0} = 1
MT_{1} = z
MT_{2} = x_{0}y_{0} + z^{2}
MT_{3} = x_{0}y_{0}z + x_{1}y_{0}z + x_{0}y_{1}z + z^{3}
MT_{4} = x_{0}x_{2}y_{0}^{2} + x_{0}^{2}y_{0}y_{2} + x_{0}y_{0}z^{2} + x_{1}y_{0}z^{2} + x_{2}y_{0}z^{2} + x_{0}y_{1}z^{2} + x_{1}y_{1}z^{2} + x_{0}y_{2}z^{2} + z^{4}
MT_{5} = x_{0}x_{2}y_{0}^{2}z + x_{0}x_{3}y_{0}^{2}z + x_{1}x_{3}y_{0}^{2}z + x_{0}x_{2}y_{0}y_{1}z + x_{0}x_{3}y_{0}y_{1}z + x_{0}^{2}y_{0}y_{2}z
+ x_{0}x_{1}y_{0}y_{2}z + x_{0}^{2}y_{0}y_{3}z + x_{0}x_{1}y_{0}y_{3}z + x_{0}^{2}y_{1}y_{3}z + x_{0}y_{0}z^{3} + x_{1}y_{0}z^{3} + x_{2}y_{0}z^{3}
+ x_{3}y_{0}z^{3} + x_{0}y_{1}z^{3} + x_{1}y_{1}z^{3} + x_{2}y_{1}z^{3} + x_{0}y_{2}z^{3} + x_{1}y_{2}z^{3} + x_{0}y_{3}z^{3} + z^{5}.

The polynomials MT_{n} have a particular symmetry, namely, they are invariant under the permutation σ that exchanges every x_{i} with the corresponding y_{i} and leaves z unchanged. In order to prove this assertion, we need to define a bijection on the set ℳ_{n} inspired by the map defined by Deutsch [7]. Consider a path p and decompose it as p = p′ U p′′ D p′′′, where p′′′ is a maximal (and possibly empty) sequence of horizontal steps and p′ U p′′ D is the last return decomposition of the path obtained from p by removing p′′′. Then we recursively define the map E as follows:

• for every k ≥ 0, E(H^{k}) = H^{k};

• E(p′ U p′′ D p′′′) = E(p′′) U E(p′) D p′′′.

Example 2. Consider the following Motzkin path

p =

where p′ = HUUDD, p′′ = UHDH, and p′′′ = H. Since

⟶^{E}

⟶^{E}

the path E(p) is

E(p) =

Theorem 3. For every integer n, the map E is an involution over the set ℳ_{n}.

Proof. Straightforward.

Let f be a polynomial in the variables x_{0}, x_{1}, …, y_{0}, y_{1}, …, z. Set

f^{σ}(x_{0}, x_{1}, …; y_{0}, y_{1}, …; z) = f(y_{0}, y_{1}, …; x_{0}, x_{1}, …; z).

Theorem 4. MT_{n} = MT_{n}^{σ}.

Proof. We show that, for every p ∈ ℳ_{n}, the two monomials m(E(p)) and m^{σ}(p) coincide. We can prove this assertion by induction. In fact we have

• if p = H^{k}, we have m(E(p)) = m(p) = m^{σ}(p);

• suppose now the assertion true for every Motzkin path of length n′ < n. Let p be a Motzkin path of length n decomposed as p = p′ U p′′ D p′′′, where p′′′ = H^{k}. The definition of m(p) implies that t(U) = r and t(D) = s, where r and s are the lengths of p′ and p′′, respectively. Hence m(p) = x_{r}y_{s}m(p′)m(p′′)z^{k}. Then, the path

E(p) = E(p′ U p′′ D p′′′) = E(p′′) U E(p′) D p′′′

corresponds to the monomial

m(E(p)) = x_{s}y_{r}m(E(p′))m(E(p′′))z^{k}.

By the induction hypothesis, this last monomial equals

x_{s}y_{r}m^{σ}(p′)m^{σ}(p′′)z^{k} = m^{σ}(p).

Theorem 5. The polynomials MT_{n} satisfy the recurrence

MT_{n} = z MT_{n−1} + ∑_{i=0}^{n−2} x_{i} y_{n−2−i} MT_{i} MT_{n−2−i},  n ≥ 1  (1)

with initial value

MT_{0} = 1.

Proof. Consider a Motzkin path p of length n. If the last step of p is horizontal, this leaves a remaining path p′ of length n − 1, and m(p) = z m(p′). If the last step of p is a down step, consider the last return decomposition p = p′ U p′′ D, where p′ has length i and p′′ has length n − 2 − i. Then, t(U) = i and t(D) = n − 2 − i, and hence m(p) = x_{i} y_{n−2−i} m(p′) m(p′′).

2.2 Specializations

The polynomials MT_{n} give rise to many specializations, which turn out to be related to be some well-known combinatorial sequences. The specializations where z = 0 give rise to combinatorial sequences related to Dyck paths, and they will be studied in detail in Section 3.

a. Needless to say, MT_{n}(1, 1, …; 1, 1, …; 1) is the n-th Motzkin number (see sequence \underline{A001006} in [25]).

b. MT_{n}(1, 1, …; 1, 1, …; 2) is the number of Motzkin paths of length n where horizontal steps have two possible colors. This number equals the (n + 1)-th Catalan number c_{n+1} = \frac{1}{n+2} \binom{2n+2}{n+1} (see sequence \underline{A000108} in [25]).

c. The coefficient of y_{0}^{j} in MT_{n}(1, 1, …; y_{0}, 1, …; 1) (or, equivalently, the coefficient of x_{0}^{j} in MT_{n}(x_{0}, 1, …; 1, 1, …; 1)) is the number of Motzkin paths of length n with j peaks, namely, occurrences of UD (see sequence \underline{A097860} in [25]).

d. The coefficient of y_{1}^{j} in MT_{n}(1, 1, …; 1, y_{1}, 1, …; 1) (or, equivalently, the coefficient of x_{1}^{j} in MT_{n}(1, x_{1}, 1, …; 1, 1, …; 1)) is the number of Motzkin paths of length n with j occurences of UHD (see sequence \underline{A114583} in [25]).

e. The coefficient of z^{j} in MT_{n}(1, 1, …; 1, 1, …; z) is the number of Motzkin paths of length n with j horizontal steps (see sequence \underline{A097610} in [25]).

f. The area A(p) of a path p is defined to be the area of the trapezoid under the path and above the x-axis. The coefficient of q^{j} in

MT_{n}(1, 1, …; q, q^{2}, …; 1) = MT_{n}(q, q^{2}, …; 1, 1, …; 1)

is the number of Motzkin paths of length n and area j (see sequence \underline{A129181} in [25]). In fact, the label of every down step D is y_{t(D)}, where t(D) is the maximal length of a weak tunnel ending at the initial point of D, or, equivalently, the area of the trapezoid lying between the maximal weak tunnels ending at the initial and final point of D, minus one. Replacing y_{t(D)} by q^{t(D)+1}, we obtain m(p) = q^{A(p)}.

Example 6. The Motzkin path of Example 1

q^{2} qq^{4} q^{9}

has area 16.

2.3 A joint distribution

Consider the polynomials

T_{n} = T_{n}(q, z, x_{0}, x_{1}) = MT_{n}(x_{0}q, x_{1}q^{2}, q^{3}, q^{4}, …; 1, 1, …; z)

which take into account area, peaks, occurrences of UHD, and number of horizontal steps. The study of this joint distribution encompasses the specializations c., d., e., and f. of the previous section. We will deduce a continued fraction expression for the generating function

F (w) = F (q, z, w, x_{0}, x_{1}) = ∑_{n≥0} T_{n}w^{n}.

Formula (1) yields the following recurrence for the polynomials T_{n}:

T_{n} = z T_{n−1} + x_{0}q T_{n−2} + x_{1}q^{2}zT_{n−3} + ∑_{i=2}^{n−2} q^{i+1} T_{i} T_{n−2−i}, n ≥ 1

with initial value T_{0} = 1.

Now we multiply the previous identity by w^{n} and sum up for n ≥ 1:

∑_{n≥1} T_{n}w^{n} = ∑_{n≥1} z T_{n−1}w^{n} + x_{0}q ∑_{n≥2} T_{n−2}w^{n}

+ x_{1}q^{2}z ∑_{n≥3} T_{n−3}w^{n} + q ∑_{n≥2} ∑_{i=2}^{n−2} q^{i} T_{i} T_{n−2−i}w^{n},

hence getting

F (w) − 1 = wzF (w) + w^{2}x_{0}qF (w) + w^{3}q^{2}x_{1}zF (w) + w^{2}q(F (qw) − 1 − qwz) · F (w).

From the previous equality we have

F (w) = \frac{1}{1 − wz − qw^{2}(x_{0} − 1) + zq^{2}w^{3}(1 − x_{1}) − w^{2}qF (qw)}.

This yields the following continued fraction expansion for F (w):

F (w) = \frac{1}{1 + a_{0}(w)w − \frac{b_{1}w^{2}}{1 + a_{1}(w)w − \frac{b_{2}w^{2}}{1 + a_{2}(w)w − ⋯}}},

where

a_{i}(w) = −zq^{i} + q^{2i+1}w(1 − x_{0}) + zq^{3i+2}w^{2}(1 − x_{1}) and b_{i} = q^{2i−1}.

Specializing x_{0} = x_{1} = 1 we get

F (q, z, w, 1, 1) = \frac{1}{1 − wz − \frac{qw^{2}}{1 − qwz − \frac{q^{3}w^{2}}{1 − q^{2}wz − \frac{q^{5}w^{2}}{1 − q^{3}wz − ⋯}}}}.

Note that the last expression can be obtained also from Formula (10.48) in [19] setting b_{h} = zq^{h}w and λ_{k} = q^{2k−1}w^{2}.

We recall that the Hankel matrix H_{n} of order n + 1 of a sequence (u_{n})_{n∈ℕ} is the (n + 1) × (n + 1) matrix whose (i, j)-th entry is u_{i+j} where the indices range between 0 and n. The Hankel transform of the sequence (u_{n}) is the sequence (v_{n})_{n∈ℕ} where

v_{n} = det H_{n} = det [\begin{matrix}u_{0} & u_{1} & … & u_{n} \\ u_{1} & u_{2} & … & u_{n+1} \\ ⋯ & ⋯ & ... & ⋯ \\ u_{n} & u_{n+1} & … & u_{2n} \end{matrix}] .

Many different evaluations of Hankel transforms are known in the literature. An exhaustive review of different methods for determinant evaluations, including Hankel determinants, is given in the papers by Krattenthaler [17] and [18].

Now, [18, Theorem 29] implies, after a trivial calculation, that the Hankel matrix H_{n} of the sequence (T_{n}(q, z, 1, 1))_{n∈ℕ} has determinant given by

det H_{n} = q^{\frac{n(n+1)(2n+1)}{6}} .

In particular the previous determinant does not depend on z.

Note that for q = z = 1 the previous result reduces to the well known fact that the Hankel transform of the sequence of Motzkin numbers is the sequence identically equal to 1.

3 Catalan tunnel polynomials

In this section we consider the polynomials

CT_{n}(λ_{0}, λ_{1}, … λ_{n−1}; μ_{0}, μ_{1}, …, μ_{n−1}) := MT_{2n}(λ_{0}, 0, λ_{1}, 0, …, λ_{n−1}; μ_{0}, 0, μ_{1}, 0, … μ_{n−1}; 0).

For 0 ≤ n ≤ 4 these polynomials are

CT_{0} = 1
CT_{1} = λ_{0}μ_{0}
CT_{2} = λ_{0}λ_{1}μ_{0}^{2} + λ_{0}^{2}μ_{0}μ_{1}
CT_{3} = λ_{0}λ_{1}λ_{2}μ_{0}^{3} + λ_{0}^{2}λ_{1}μ_{0}^{2}μ_{1} + λ_{0}^{2}λ_{2}μ_{0}^{2}μ_{1} + λ_{0}^{2}λ_{1}μ_{0}^{2}μ_{2} + λ_{0}^{3}μ_{0}μ_{1}μ_{2}
CT_{4} = λ_{0}λ_{1}λ_{2}λ_{3}μ_{0}^{4} + λ_{0}^{2}λ_{1}λ_{2}μ_{0}^{3}μ_{1} + λ_{0}^{2}λ_{1}λ_{3}μ_{0}^{3}μ_{1} + λ_{0}^{2}λ_{2}λ_{3}μ_{0}^{3}μ_{1} + λ_{0}^{3}λ_{2}μ_{0}^{2}μ_{1}^{2} + λ_{0}^{2}λ_{1}^{2}μ_{0}^{3}μ_{2}

+ λ_{0}^{2}λ_{1}λ_{3}μ_{0}^{3}μ_{2} + λ_{0}^{3}λ_{1}μ_{0}^{2}μ_{1}μ_{2} + λ_{0}^{3}λ_{3}μ_{0}^{2}μ_{1}μ_{2} + λ_{0}^{2}λ_{1}λ_{2}μ_{0}^{3}μ_{3} + λ_{0}^{3}λ_{1}μ_{0}^{2}μ_{1}μ_{3} + λ_{0}^{3}λ_{2}μ_{0}^{2}μ_{1}μ_{3} + λ_{0}^{3}λ_{1}μ_{0}^{2}μ_{2}μ_{3} + λ_{0}^{4}μ_{0}μ_{1}μ_{2}μ_{3}.

Theorem 4 implies

CT_{n}(λ_{0}, λ_{1}, … λ_{n−1}; μ_{0}, μ_{1}, …, μ_{n−1}) = CT_{n}(μ_{0}, μ_{1}, …, μ_{n−1}; λ_{0}, λ_{1}, … λ_{n−1}). (2)

In the following the polynomial CT_{n}(λ_{0}, λ_{1}, … λ_{n−1}; μ_{0}, μ_{1}, …, μ_{n−1}) will be denoted by CT_{n}, for short.

Formula (1) gives the following recurrence for the polynomials CT_{n}:

CT_{n} = ∑_{i=0}^{n−1} λ_{i} μ_{n−1−i} CT_{i} CT_{n−1−i},  n ≥ 1,  (3)

with initial value

CT_{0} = 1.

As in the case of Motzkin polynomials, the above recurrence can be seen as a consequence of the last return decomposition of a Dyck path.

Notice that the polynomial CT_{n} can be defined as a sum of monomials

CT_{n} = ∑_{p∈𝒞_{n}} m̂(p),

where 𝒞_{n} is the set of Dyck paths of semilength n and m̂(p) is defined as follows. We associate with every step S either the variable λ_{\frac{t(S)}{2}} if S is an up step, or the variable μ_{\frac{t(S)}{2}} if S is an down step (this definition is well posed, since in a Dyck path a weak tunnel is always of even length). Then, the associated monomial m̂(p) is the product of the variables of every step of p. Notice that

• the exponent of λ_{0} in m̂(p) exceeds by one the number of occurrences of UU in p, since an up step such that the weak tunnel preceding it of length 0 is either the initial up step or the second up step of a double rise.

• Similarly, the exponent of μ_{0} in m̂(p) is the number of peaks in p. As a consequence, denoting by i the exponent of λ_{0} and by j the exponent of μ_{0} in m̂(p), we have i + j = n + 1.

• The exponent of λ_{1} in m̂(p) is the number occurrences of UUDU in p increased by one if p begins with UDU.

• The exponent of μ_{1} in m̂(p) is the number occurrences of UUDD in p.

3.1 Catalan specializations

As in the case of the polynomials MT_{n}, we consider many specializations of the polynomials CT_{n}, which give rise to some well-known combinatorial sequences.

a. Obviously, CT_{n}(1, 1, …; 1, 1, …) is the n-th Catalan number c_{n} (see sequence \underline{A000108} in [25]).

b. CT_{n}(1, 1, …; q, 1, 1, 1, …) is the n-th Narayana polynomial, namely, the generating polynomial of sequence N_{n,k}, where N_{n,k} is the number of Dyck paths of semilength n with k peaks (see sequence \underline{A001263} in [25]). On the other hand, by identity (2), we have CT_{n}(1, 1, …; q, 1, 1, 1, …) = CT_{n}(q, 1, …; 1, 1, 1, 1, …), namely, N_{n,k} is also the number of Dyck paths of semilength n with k − 1 double rises. Recalling that in every Dyck path the sum of the numbers of peaks and double rises equals the semilength, the symmetry of the Catalan tunnel polynomials gives a further combinatorial proof of the identity N_{n,k} = N_{n,n+1−k}.

c. The coefficient of μ_{1}^{i} in CT_{n}(1, 1, …; 1, μ_{1}, 1, 1, 1, …) is the number of Dyck paths of semilength n with i occurrences of UUDD, and also the number of Łukasiewicz paths of length n with i peaks (see sequence \underline{A098978} in [25]). We recall that a Łukasiewicz path of length n is a lattice path starting at the origin and ending at (n, 0) whose steps are of the type (1, j), j = 1, 0, −1, −2, …, with the restriction that these paths cannot go below the x-axis. It is known that the number of all Łukasiewicz paths of length n is the n-th Catalan number (see [12]).

d. If n ≥ 2, CT_{n}(1, 1, …; 1, 1, 0, 0, …) is the (n − 2)-th Fibonacci number (see sequence \underline{A000045} in [25]), since it counts Dyck paths that are obtained by juxtaposing subpaths either of the form UD, or UUDD. Moreover, if we consider CT_{n}(1, 1, …; a, b, 0, 0, …) = F_{n}(a, b), we obtain a family of polynomials in two variables satisfying the recurrence

F_{n}(a, b) = aF_{n−1}(a, b) + abF_{n−2}(a, b),

with the initial conditions F_{0}(a, b) = 1 and F_{1}(a, b) = a. In [3, p. 542], the authors consider a slightly different family {n}_{s,t} of Fibonacci polynomials. More precisely,

\{n + 1\}_{s,t} = F_{n} (s, \frac{t}{s}) .

e. Recall that a Schröder path from (0, 0) to (2n, 0) is a lattice path starting at (0, 0), ending at (2n, 0), consisting of up steps, down steps, and double horizontal steps, and never going below the x-axis. Such paths are counted by the large Schröder numbers (see sequence \underline{A006318} in [25]). CT_{n}(1, 1, …; 2, 1, 1, …) is the n-th large Schröder number. In fact, define a blue/red Dyck path to be a Dyck path where every peak is colored either blue or red. A blue/red Dyck path of semilength n can be bijectively associated with a Schröder path from (0, 0) to (2n, 0) as follows. Replace every blue peak with a double horizontal step and let all other steps unchanged. More generally, CT_{n}(1, 1, …; k, 1, 1, …) counts large Schröder paths where double horizontal steps may have a color taken from the set {1, 2, …, k − 1}.

f. The normalized area Ã(d) of a Dyck path d is equal to

Ã(d) = \frac{A(d) − n}{2},

where A(d) is the area between the path d and the x-axis defined above.

For example, the normalized area of the Dyck path

is 4,

while its area is 12.

The arguments of Section 2.2 imply that the coefficient of q^{k} in CT_{n}(1, 1, …; 1, q, q^{2}, …) is the number of Dyck paths of semilength n with normalized area equal to k. Hence, the polynomial CT_{n}(1, 1, …; 1, q, q^{2}, …) is nothing but the Carlitz-Riordan q-analogue of Catalan numbers (see [13]).

g. The polynomials ℭ_{n}(q, t) = CT_{n}(1, q, q^{2}, …; 1, t, t^{2}, …) are the q, t-generalization of the Carlitz-Riordan polynomials appearing in [1]. In fact, by Formula (3) we have the following recurrence for such polynomials:

ℭ_{n}(q, t) = ∑_{k=0}^{n−1} q^{k}t^{n−1−k}ℭ_{k}(q, t)ℭ_{n−1−k}(q, t), n ≥ 1,

with ℭ_{0}(q, t) = 1.

This recurrence is precisely the same that defines the q, t-polynomials in [1]. In the same work the authors describe a combinatorial interpretation for these polynomials in terms of maximal chains in the non-crossing partition lattice.

3.2 A joint Catalan distribution

Consider the polynomials ĈT_{n}(q, μ_{0}, μ_{1}) = CT_{n}(1, 1, …; μ_{0}, μ_{1}q, q^{2}, …) which take into account the distribution of normalized area, peaks and occurrences of UUDD. Proceeding as above, we consider the generating function

G(q, w, μ_{0}, μ_{1}) = ∑_{n≥0} ĈT_{n}(q, μ_{0}, μ_{1})w^{n},

and we get the following continued fraction expansion for G(q, w, μ_{0}, μ_{1}):

G(q, w, μ_{0}, μ_{1}) = \frac{1}{1 + a_{0}(w)w − \frac{b_{1}w}{1 + a_{1}(w)w − \frac{b_{2}w}{1 + a_{2}(w)w − \frac{b_{3}w}{⋯}}}},  (4)

where a_{i}(w) = −μ_{0}q^{i} + q^{i} + μ_{0}q^{2i+1}w(1 − μ_{1}) and b_{i} = q^{i−1}.

Note that, setting μ_{0} = 1, μ_{1} = 1 and w = −aq in (4), we get a continued fraction studied by Ramanujan (see [5, p. 30]).

4 Binary trees

It is well known that Catalan numbers enumerate also binary trees. The relationship between Dyck paths and binary trees yields a further specialization of Catalan Tunnel polynomials.

A binary tree is a rooted, unlabeled tree where every node is either a leaf (node without children) or an internal node having two children (see [16, p. 312]).

Let t be a binary tree. We associate with every internal node v of t the pair (a_{ℓ}(v), a_{r}(v)), where a_{ℓ}(v) (respectively a_{r}(v)) is the number of internal nodes of the left (right) subtree of v. Let Int(t) denote the set of internal nodes of t.

For every binary tree t, the (internal) path length l(t) is defined to be the sum of the length of the paths from the root to each internal node (see [16, p. 405]). In symbols, denoting by ṽ the root of t,

l(t) = ∑_{v∈Int(t)} d(v, ṽ).

We have Proposition 7. For every binary tree t,

l(t) = ∑_{v∈Int(t)}(a_{ℓ}(v) + a_{r}(v)).

Proof. We proceed by induction on the number n of internal nodes of t. If n = 0 the proposition is trivial. Otherwise, let v_{r} and v_{ℓ} be the right and the left child of ṽ, respectively. Then

l(t) = ∑_{v∈Int(t)} d(v, ṽ) = ∑_{v∈Int(t_{ℓ})}(d(v, v_{ℓ}) + 1) + ∑_{v∈Int(t_{r})}(d(v, v_{r}) + 1)

= ∑_{v∈Int(t_{ℓ})} d(v, v_{ℓ}) + ∑_{v∈Int(t_{r})}(d(v, v_{r}) + a_{l}(ṽ) + a_{r}(ṽ)).

By the inductive hypothesis we have

∑_{v∈Int(t_{ℓ})} d(v, v_{ℓ}) = l(t_{ℓ}) = ∑_{v∈Int(t_{ℓ})}(a_{ℓ}(v) + a_{r}(v)),

and similarly for t_{r}. This gives the assertion.

It is well known (see [16]) that binary trees with n internal nodes are enumerated by the n-th Catalan number c_{n}, hence, they are in bijection with Dyck paths of semilength n.

A bijection f between these two sets can be defined as follows. Let t be a binary tree. Denote by t_{ℓ} and t_{r} the left and right subtree of the root. Then the image of the tree t is defined recursively as

f(t) = \begin{cases}the empty path, & if t is the empty tree; \\ f(t_{r})Uf(t_{ℓ})D, & otherwise. \end{cases}

This definition implies that at every internal node of t corresponds a pair of steps Ū and D̄ that face each other (namely, the segment joining the last point of Ū and the first point of D̄ is a weak tunnel). It is possible to determine the weights of Ū and D̄ directly from t. In fact, we obtain the following proposition.

Proposition 8. Let t be a binary tree and p = f(t). Consider an internal node v and let Ū and D̄ denote the steps of p corresponding to v. Then the weights of Ū and D̄ are λ_{a_{r}(v)} and μ_{a_{ℓ}(v)}. In particular

m̂(p) = ∏_{v∈Int(t)} λ_{a_{ℓ}(v)}μ_{a_{r}(v)}.

Proof. By the recursive definition of the map f, it suffices to prove the assertion for the root ṽ of t. Note that, since f(t) = f(t_{r})Ūf(t_{ℓ})D̄, the root ṽ corresponds precisely to the pair of steps Ū and D̄. On the other hand, the step Ū has weight λ_{h}, where h is the semilength of the path f(t_{r}), namely, the number of internal nodes of the tree t_{r}. Similarly, the step D̄ has weight λ_{i}, where i is the number of internal nodes of the tree t_{ℓ}.

Example 9. Consider the binary tree t given by

(4,1) (3,0) (1,1) {(0,0) \atop (0,0)} (0,0)

where the internal nodes are circled and the leaves are squared. In each internal node we indicate the pair (a_{ℓ}(v), a_{r}(v)). This tree corresponds to the Dyck path p

\begin{matrix}x_{0} \\ y_{0} \\ x_{1} \\ x_{0} \\ x_{0} \\ y_{0} \\ x_{1} \\ x_{0} \\ y_{0} \\ y_{1} \\ y_{3} \\ y_{4} \end{matrix}

As an immediate consequence of the previous results we get

Theorem 10. The coefficient of q^{k} in the polynomial CT_{n}(1, q, q^{2}, …; 1, q, q^{2}, …) is the number of binary trees with n internal nodes and path length k.

Observe that the number of binary trees with n internal nodes and path length k is sequence \underline{A138157} in [25].

Let H(q, w) = ∑_{n≥0} CT_{n}(1, q, q^{2}, …; 1, q, q^{2}, …)w^{n} be the generating function of these polynomials. Recurrence (3) yields

\begin{matrix}CT_{n}(1, q, q^{2}, …, 1, q, q^{2}, …) = \\ q^{n−1} ∑_{i=0}^{n−1} CT_{i}(1, q, q^{2}, …, 1, q, q^{2}, …) · CT_{n−1−i}(1, q, q^{2}, …, 1, q, q^{2}, …). \end{matrix}

The previous identity allows us to deduce the following functional equation for H(q, w):

H(q, w) = w · H(q, qw)^{2} + 1.

Note that this functional equation is the same obtained directly by Knuth in [16, p. 595].

5 Partial and free Motzkin paths

In [6], Chen et al. introduce the notions of partial Motzkin path and free Motzkin path with the aim to generalize a matrix identity due to Shapiro (see [24]).

In this section we introduce multi-variable polynomials associated with a partial Motzkin path and to a free Motzkin path, study their properties and specializations and derive a matrix identity that further generalizes that of Chen et al.

First of all we recall the definitions of partial Motzkin path and free Motzkin path, following [6]. A partial Motzkin path of length n is a prefix of length n of a Motzkin path, namely, a Motzkin path in which one drops the requirement that the last point lies on the x-axis. A free Motzkin path of length n is a lattice path in the plane that starts at (0, 0) and consists of n steps arbitrarily chosen among up, down and horizontal steps, in other terms, it is a partial Motzkin path without the restriction to lie above the x-axis. Let 𝒫ℳ _{n} and ℱ ℳ _{n} denote the sets of partial Motzkin paths and free Motzkin paths of length n, respectively.

Suppose that the last point of a partial Motzkin path d has height j. Then the path d contains j up steps, one for each level, such that to their right there are no other steps having the same level. These up steps are called R-visible in [6]. Now we associate with each partial Motzkin path d a monomial m(d), as follows. Each R-visible up step of d is labelled with the weight x_{∞}. Each other step in d is labelled considering the corresponding weak tunnel as done in Section 2 (the notion of weak tunnel makes sense also in this case). The monomial m(d) is the product of the weights of the steps of d.

Example 11. In the following partial Motzkin path

\begin{matrix}x_{∞} \\ x_{0} \\ x_{3} \\ z \\ x_{0} \\ y_{1} \\ y_{0} \\ y_{2} \\ x_{∞} \\ x_{∞} \end{matrix}

every step has been labelled with its weight. Here the first up step and the last two up steps are the R-visible ones, and m(d) = x_{∞}^{3}x_{0}^{2}x_{3}y_{0}y_{1}y_{2}z.

Now consider a free Motzkin path d. In this path there can be both R-visible up steps and L-visible down steps, where an L-visible down step is a down step with no other steps to its left. We associate with each free Motzkin path a monomial in the usual way assigning to each L-visible down step the weight y_{∞} and labelling all the other steps as done for partial Motzkin paths.

Let d be a partial Motzkin path whose last point has height j. An elevation line for d is any line of the form y = h with 0 ≤ h ≤ j.

We have the following.

Proposition 12. There is a bijection El between partial Motzkin paths with a specified elevation line and free Motzkin paths. If d is a partial Motzkin path with elevation line y = h and associated monomial m(d) then

m(El(d)) = (\frac{y_{∞}}{x_{∞}} )^{h} m(d).

Proof. The map El is the same considered in [6] and called elevation. Consider a partial Motzkin path d with an elevation line y = h. Then El(d) is the free Motzkin path obtained from d by replacing each R-visible up step below the elevation line with a down step. The map is clearly invertible and the second assertion follows from the fact that all the new down steps created in this way are L-visible.

Example 13. Consider the same partial path d of the previous example and the elevation line y = 2. Then El(d) is given by

\begin{matrix}y_{∞} \\ x_{0} \\ x_{3} \\ z \\ x_{0} \\ y_{1} \\ y_{0} \\ y_{2} \\ y_{∞} \\ x_{∞} \end{matrix}

Now we associate with the sets 𝒫ℳ _{n} and ℱ ℳ _{n} the polynomials P T_{n} and F T_{n} defined in the following way

P T_{n} = ∑_{d∈𝒫ℳ _{n}} m(d),

and

F T_{n} = ∑_{d∈ℱ ℳ _{n}} m(d).

We need to further refine the polynomials P T_{n}. Let 𝒫ℳ _{n}^{(j)} be the subset of 𝒫ℳ _{n} consisting of those partial Motzkin paths whose last point has height j. We set P T_{n}^{(j)} to be the polynomial

P T_{n}^{(j)} = ∑_{d∈𝒫ℳ _{n}^{(j)}} m(d).

As a consequence we have

P T_{n} = ∑_{j=0}^{n} P T_{n}^{(j)}.

Note that P T_{n}^{(0)} = MT_{n} .

Now we are in position to prove the main result of this Section.

Theorem 14. Set R = \frac{y_{∞}}{x_{∞}} . Then

[\begin{matrix}MT_{0} & 0 & 0 & 0 & 0 & … \\ MT_{1} & P T_{1}^{(1)} & 0 & 0 & 0 & … \\ MT_{2} & P T_{2}^{(1)} & P T_{2}^{(2)} & 0 & 0 & … \\ MT_{3} & P T_{3}^{(1)} & P T_{3}^{(2)} & P T_{3}^{(3)} & 0 & … \\ MT_{4} & P T_{4}^{(1)} & P T_{4}^{(2)} & P T_{4}^{(3)} & P T_{4}^{(4)} & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] × [  1 ; 1 + R ; 1 + R + R^{2} ; 1 + R + R^{2} + R^{3} ; 1 + R + R^{2} + R^{3} + R^{4} ; ⋮] = [F T_{0} ; F T_{1} ; F T_{2} ; F T_{3} ; F T_{4} ; ⋮] . (5)

Proof. As in [6], we write the previous identity in a one-row-form:

∑_{j=0}^{n} P T_{n}^{(j)}(1 + R + … + R^{j}) = F T_{n}, ∀n ∈ ℕ.

Since each partial Motzkin path whose last point has height j can have elevation lines y = 0, y = 1, … y = j, Proposition 12 implies that the left hand side of the previous identity gives precisely the polynomial associated with free Motzkin paths of length n, as the right hand side does.

The first few lines of the previous matrix identity read

[\begin{matrix}1 & 0 & 0 \\ z & x_{∞} & 0 \\ x_{0}y_{0} + z^{2} & 2x_{∞}z & x_{∞}^{2} \end{matrix}]×[\begin{matrix}1 \\ 1 + R \\ 1 + R + R^{2} \end{matrix}] = [\begin{matrix}1 \\ x_{∞} + y_{∞} + z \\ x_{∞}^{2} + y_{∞}^{2} + x_{∞}y_{∞} + 2x_{∞}z + 2y_{∞}z + x_{0}y_{0} + z^{2} \end{matrix}] .

Observe that when the polynomials

MT_{n} = MT_{n}(x_{0}, x_{1}, x_{2}, …, x_{n−2}; y_{0}, y_{1}, y_{2}, …, y_{n−2}; z),
P T_{n}^{(j)} = P T_{n}^{(j)}(x_{0}, x_{1}, x_{2}, …, x_{n−2}, x_{∞}; y_{0}, y_{1}, y_{2}, …, y_{n−2}; z),

and

F T_{n} = F T_{n}(x_{0}, x_{1}, x_{2}, …, x_{n−2}, x_{∞}; y_{0}, y_{1}, y_{2}, …, y_{n−2}, y_{∞}; z),

are evaluated at z = k − t − 1, x_{i} = 1 for every 0 ≤ i ≤ ∞ and y_{i} = t for every 0 ≤ i ≤ ∞ Equation (5) reduces to the formula proved in [6]. This last formula further reduces to the Shapiro identity [24] when k = 4 and t = 1.

Now we study the polynomials P T_{n}^{(j)} and F T_{n} in their own right.

First of all it is easy to see, considering the last return decomposition, that the polynomials P T_{n}^{(j)} satisfy the following recurrence relation involving the Motzkin tunnel polynomials:

P T_{n}^{(j)} = \begin{cases}MT_{n}, & if j = 0; \\ ∑_{i=0}^{n−1} x_{∞} MT_{i} P T_{n−i−1}^{(j−1)}, & otherwise. \end{cases} .  (6)

Hence for the generating function P^{(j)}(w) = ∑_{n≥0} P T_{n}^{(j)}w^{n} and P (w) = ∑_{n≥0} P T_{n}w^{n} we have

P^{(j)}(w) = wx_{∞} MT(w)P^{(j−1)}(w) = (wx_{∞})^{j} MT(w)^{j+1},  (7)

and

P (w) = \frac{MT(w)}{1 − x_{∞}w MT(w)},  (8)

where MT(w) = ∑_{n≥0} MT_{n} w^{n}.

As a consequence the matrix [P T_{i}^{(j)}]_{i,j≥0} is a Riordan array. In the notation of [23] it is the Riordan array R(MT(w), x_{∞} MT(w)) .

Since the generating function of the column vector in the left hand side of Equation (5) is

R(w) = ∑_{j≥0}(1 + R + … + R^{j})w^{j} = \frac{1}{1 − R} (\frac{1}{1 − w} − \frac{R}{1 − Rw}) = \frac{1}{(1 − w)(1 − Rw)},

we deduce immediately that the generating function F (w) = ∑_{n≥0} F_{n}w^{n} of the column vector of the right hand side of Equation (5) is

F (w) = \frac{MT(w)}{(1 − wx_{∞} MT(w))(1 − wRx_{∞} MT(w))} = \frac{MT(w)}{(1 − wx_{∞} MT(w))(1 − wy_{∞} MT(w))}.

As an application we can find the multivariate generating function F̂(w) (P̂(w)) for the joint distribution of peaks, occurrences of UHD, number of R-visible and L-visible steps and length over free Motzkin paths (partial Motzkin paths, respectively). We recall that the coefficient of y_{0}^{j} in MT_{n}(1, …, 1; y_{0}, 1, …, 1; 1) is the number of Motzkin paths of length n with j peaks, while the coefficient of y_{1}^{j} in MT_{n}(1, 1, …; 1, y_{1}, 1, …; 1) is the number of Motzkin paths of length n with j occurences of UHD. As a consequence the generating functions we are looking for are

F̂(w) = ∑_{n≥0} F T_{n}(1, …, 1, x_{∞}; y_{0}, y_{1}, 1, …, 1, y_{∞}; z)w^{n},

and

P̂(w) = ∑_{n≥0} P T_{n}(1, …, 1, x_{∞}; y_{0}, y_{1}, 1, …, 1; z)w^{n}.

From the results of Subsection 2.3 and recalling that MT_{n}(1, …, 1; y_{0}, y_{1}, …, 1; z) = MT_{n}(x_{0}, x_{1}, …, 1; 1, 1, …, 1; z) we deduce that

∑_{n≥0} MT_{n}(1, …, 1; y_{0}, y_{1}, …, 1; z)w^{n} = \frac{−b − \sqrt{b^{2} − 4w^{2}}}{2w^{2}} ,

where b = −1 + wz + w^{2}y_{0} − w^{2} + w^{3}y_{1}z − w^{3}z.

Hence

P̂(w) = \frac{−b − \sqrt{b^{2} − 4w^{2}}}{2w^{2} + x_{∞}wb + x_{∞}w\sqrt{b^{2} − 4w^{2}}} ,  (9)

and

F̂(w) = \frac{2(−b − \sqrt{b^{2} − 4w^{2}})}{(2w + x_{∞}b + x_{∞}\sqrt{b^{2} − 4w^{2}})(2w + y_{∞}b + y_{∞}\sqrt{b^{2} − 4w^{2}})}.  (10)

For example, specializing (9) and (10) in x_{∞} = 1, y_{∞} = 1, y_{1} = 1, we get the generating function of the distribution of peaks over partial Motzkin paths and free Motzkin paths (see sequences \underline{A132893} and \underline{A181371} in [25]).

Consider now the polynomials A_{n}(x_{∞}, z) = P T_{n}(1, 1, …, 1, x_{∞}; 1, …, 1; z). Our aim is to evaluate the Hankel transform of the sequence (A_{n})_{n∈ℕ} .

Theorem 15. The sequence (A_{n})_{n∈ℕ} has Hankel transform (1)_{n∈ℕ}.

Proof. Let H_{m} and Ĥ_{m}, m ≥ 0, be the Hankel matrices of the sequences (M_{n})_{n∈ℕ} and (A_{n})_{n∈ℕ} , respectively, where M_{n} = MT_{n}(1, 1, …, 1; 1, …, 1; z) and let B_{m} = [b_{i,j}]_{i,j≥0} the m × m matrix defined as follows:

b_{i,j} = \begin{cases}1, & if i = j; \\ x_{∞}A_{j−i−1}, & if j > i; \\ 0, & otherwise. \end{cases} .

By the recurrence (6) we have

A_{n} = M_{n} + ∑_{j=0}^{n−1} M_{j}x_{∞}A_{n−1−j} = ∑_{j=0}^{n} M_{j}b_{j,n}.  (11)

As a consequence of the previous identity, we have that the (i, j − 1)-th element of the product B_{m}^{T} · H_{m} · B_{m} is

∑_{0≤h≤j−1} ∑_{0≤k≤i} b_{k,i}M_{k+h}b_{h,j−1} = ∑_{0≤h≤j−1} ∑_{0<k≤i} b_{k,i}M_{k+h}b_{h,j−1} + b_{0,i} ∑_{0≤h≤j−1} M_{h}b_{h,j−1}

= ∑_{0≤h≤j−1} ∑_{0≤k≤i−1} b_{k+1,i}M_{k+1+h}b_{h,j−1} + b_{0,i}A_{j−1}

= ∑_{0<h≤j} ∑_{0≤k≤i−1} b_{k+1,i}M_{k+1+h−1}b_{h−1,j−1} + x_{∞}A_{i−1}A_{j−1}

= ∑_{0<h≤j} ∑_{0≤k≤i−1} b_{k,i−1}M_{k+h}b_{h,j} + A_{i−1}b_{0,j}

= ∑_{0≤h≤j} ∑_{0≤k≤i−1} b_{k,i−1}M_{k+h}b_{h,j},

that is the (i−1, j)-th element of B_{m}^{T}·H_{m}·B_{m}, showing that this last matrix is constant along antidiagonals. Moreover the first row of this matrix is easily seen to be equal to (A_{i})_{i≥0}.

Hence we have the matrix identity

Ĥ_{m} = B_{m}^{T} · H_{m} · B_{m}.

Since det B_{m} = 1 ∀m ≥ 0, det Ĥ_{m} = det H_{m} = 1 and we get the assertion.

Note that the previous result can be also obtained as a consequence of the results contained in [20].

6 Acknowledgments

We thank the anonymous referee for his very detailed revision and his valuable suggestions.

This work was partially supported by University of Bologna, funds for selected research topics.

References

[1] R. M. Adin and Y. Roichman, On maximal chains in the non-crossing partition lattice, J. Combin. Theory Ser. A 125 (2014), 18–46.

[2] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[3] T. Amdeberhan, X. Chen, V. H. Moll, and B. E. Sagan, Generalized Fibonacci polynomials and Fibonomial coefficients, Ann. Comb. 18 (2014), 541–562.

[4] E. Barcucci, A. D. Lungo, J. M. Fédou, and R. Pinzani, Steep polyominoes, q-Motzkin numbers and q-Bessel functions, Discrete Math. 189 (1998), 21–42.

[5] B. C. Berndt, Ramanujan’s Notebooks. Part III, Springer-Verlag, 1991.

[6] W. Y. C. Chen, N. Y. Li, L. W. Shapiro, and S. H. F. Yan, Matrix identities on weighted partial Motzkin paths, European J. Combin. 28 (2007), 1196–1207.

[7] E. Deutsch, An involution on Dyck paths and its consequences, Discrete Math. 204 (1999), 163–166.

[8] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A 23 (1977), 291–301.

[9] S. Elizalde and E. Deutsch, A simple and unusual bijection for Dyck paths and its consequences, Ann. Comb. 7 (2003), 281–297.

[10] S. Elizalde and T. Mansour, Restricted motzkin permutations, motzkin paths, continued fractions, and chebyshev polynomials, Discrete Math. 305 (2005), 170–189.

[11] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

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

[13] J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), 248–264.

[14] A. M. Garsia and M. Haiman, A remarkable q, t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5 (1996), 191–244.

[15] J. Haglund, The q, t-Catalan Numbers and the Space of Diagonal Harmonics, Vol. 41 of University Lectures Series, AMS, 2008.

[16] D. E. Knuth, The Art of Computer Programming, Vol. 1, Addison-Wesley, 1969.

[17] C. Krattenthaler, Advanced determinant calculus., Séminaire Lotharingien de Combinatoire 42 (1999), B42q, 67 p.

[18] C. Krattenthaler, Advanced determinant calculus: A complement, Linear Algebra Appl. 411 (2005), 68–166.

[19] C. Krattenthaler, Lattice path enumeration. In Handbook of Enumerative Combinatorics, Discrete Math. Appl., pp. 589–678. CRC Press, 2015.

[20] C. Krattenthaler and D. Yaqubi, Some determinants of path generating functions, II.

    Available at https://arxiv.org/abs/1802.05990, 2018.

[21] T. Mansour and M. Shattuck, Pattern avoiding partitions and Motzkin left factors, Central European Journal of Mathematics 9 (2011), 1121–1134.

[22] R. Oste and J. V. der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, Electron. J. Combin. 22,#P2.8 (2015), 19pp.

[23] L. W. Shapiro, S. Getu, W. J. Woan, and L. C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[24] L. W. Shapiro, W. J. Woan, and S. Getu, Runs, slides and moments, SIAM J. Algebraic Discrete Methods 4(4) (1983), 459–466.

[25] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org/.

[26] R. P. Stanley, Enumerative Combinatorics, Vol. 2 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2001.

[27] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2010 Mathematics Subject Classification: Primary 05A15, Secondary 05A05, 05A19. Keywords: Motzkin number, Catalan number, binary tree, continued fraction, Dyck path.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A001006}, \underline{A001263}, \underline{A006318}, \underline{A097610}, \underline{A097860}, \underline{A098978}, \underline{A114583}, \underline{A129181}, \underline{A132893}, \underline{A138157}, and \underline{A181371}.)

Received March 28 2018; revised versions received September 7 2018; December 3 2018. Published in Journal of Integer Sequences, December 5 2018.

Return to Journal of Integer Sequences home page.