\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{mathrsfs}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\DeclareMathOperator{\MT}{MT}
\DeclareMathOperator{\CT}{CT}

\usepackage{tikz}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Motzkin and Catalan Tunnel Polynomials
}
\vskip 1cm
\large
Marilena Barnabei, Flavio Bonetti, and Niccol\`o Castronuovo \\
Dipartimento di Matematica\\
Universit\`a di Bologna \\
Bologna, 40126 \\
Italy \\
\href{mailto:marilena.barnabei@unibo.it}{\tt marilena.barnabei@unibo.it} \\
\href{mailto:flavio.bonetti@unibo.it}{\tt flavio.bonetti@unibo.it} \\
\href{mailto:niccolo.castronuovo2@unibo.it}{\tt niccolo.castronuovo2@unibo.it} \\
\ \\
Matteo Silimbani\\
SSPG ``M. Marinelli'' \\
Forlimpopoli, 47034 \\
Italy\\
\href{mailto:matteo.silimbani4@unibo.it}{\tt matteo.silimbani4@unibo.it} \\
\end{center}

\vskip .2 in

\begin{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\"{o}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.
\end{abstract}



\section{Introduction}

Catalan and Motzkin numbers (sequences \seqnum{A000108} and \seqnum{A001006} in \cite{Sl}) 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., \cite{St2, St3}
for Catalan numbers and \cite{AignerMotzkin, DONAGHEY, EliMan, ManSha} 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$\textit{-Catalan numbers,} due to
Mac Mahon,  Carlitz and Riordan, and Polya and Gessel, respectively.
All these are $q$-\textit{analogs} of Catalan numbers, i.e., polynomials that yield Catalan numbers when $q=1$  (see \cite{FUR} for an overwiew of these three families).
Similarly, in the case of two variables, different families of \textit{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 \cite{GarsiaHaiman, HG} for further details),
and by Adin and Roichman in connection with maximal chains in the non-crossing partition lattice (see \cite{ADIN}).

Even if generalizations of Motzkin numbers are less studied, it is possible to find some of them in the literature.
For example, Flajolet \cite{flaj} 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 \cite{Oste} the authors generalize these polynomials and studied their properties in terms of recurrence
relations. On the other hand, in \cite{BARCUCCI}, 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 \cite{flaj}, 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 \cite{ED}.

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\"{o}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 \cite{flaj} and in other works (see e.g., \cite{BARCUCCI}).

The outline of the work is the following.

In Section \ref{sectone}, 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 \ref{catalan} 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 \ref{fbt} 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 \ref{Partialfree} 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 \cite{CHEN}. 


\section{Motzkin tunnel polynomials}\label{sectone}

\subsection{Basic definitions}

A \textit{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 \textit{Dyck path} of semilength $k$ is a Motzkin path of length $2k$ with no horizontal steps.
We let $\mathscr{M}_n$ denote the set of Motzkin paths of length $n$ and by $\mathscr{C}_k$ the set of Dyck paths of semilength $k$. 

One can encode a Motzkin path in $\mathscr{M}_n$  by a Motzkin word of length $n$ in the letters $U$, $H$, and $D$.
A \emph{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 (\textit{last return decomposition}). 

A \textit{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 \textit{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,\ldots,x_{n-2},y_0,y_1,\ldots,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$. 

\begin{example} \label{esempio1} Consider the following Motzkin path
$$\begin{tikzpicture}
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \node[label={\small $x_0$}] at (0, 0) {};
   \node[label={\small $x_0$}] at (1/2,1/2) {};
   \node[label=below:{\small $x_3$}] at (5/2, 2/2) {};
   \node[label={\small $z$}] at (5/4, 2/2) {};	
   \node[label=below:{\small $z$}] at (15/4, 2/2) {};	
   \node[label={\small $x_0$}] at (5/2, 2/2) {};
   \node[label=below:{\small $y_1$}] at (3/2,2/2) {};
   \node[label={\small $y_0$}] at (7/2, 2/2) {};
   \node[label={\small $y_3$}] at (9/2, 1/2) {};
   \node[label={\small $y_8$}] at (5, 0) {};
\draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (10);
\end{tikzpicture}
$$
where every step has been labelled with its weight. Then, the corresponding monomial is $x_0^3x_3y_0y_1y_3y_8z^2$.
\end{example}

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, 
\begin{itemize}
\item the exponent of $x_0$ in $m(p)$ equals the number of occurrences of $UU,$ increased by one if $p$ begins with $U.$ 
\item The exponent of $x_1$ equals the number of occurrences of $UHU,$ increased by one if $p$ begins with $HU.$ 
\item 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.
\item Similarly, the exponent of $y_1$  equals the number of occurrences of $UHD$ in $p.$
\end{itemize}

For every integer $n$, we define the polynomial $$\MT_n=\MT_n(x_0,x_1,\ldots, x_{n-2};y_0,y_1,\ldots, y_{n-2};z)=\sum_{p\in\mathscr{M}_n} m(p).$$ 

For $0\leq n\leq 5$, these polynomials are 
\begin{align*}
\MT_0 &=1 \\
\MT_1 &=z \\
\MT_2 &=x_0y_0 + z^2 \\
\MT_3 &= x_0y_0z + x_1y_0z + x_0y_1z + z^3 \\
\MT_4 &= x_0x_2y_0^2 + x_0^2y_0y_2 + x_0y_0z^2 + x_1y_0z^2 + x_2y_0z^2 + x_0y_1z^2 + x_1y_1z^2 + x_0y_2z^2 + z^4 \\
\MT_5 & = x_0x_2y_0^2z + x_0x_3y_0^2z + x_1x_3y_0^2z + x_0x_2y_0y_1z + x_0x_3y_0y_1z + x_0^2y_0y_2z \\
& + x_0x_1y_0y_2z + x_0^2y_0y_3z+ x_0x_1y_0y_3z  + x_0^2y_1y_3z+x_0y_0z^3 + x_1y_0z^3 + x_2y_0z^3 \\
& + x_3y_0z^3 + x_0y_1z^3 + x_1y_1z^3 + x_2y_1z^3 + x_0y_2z^3 + x_1y_2z^3 + x_0y_3z^3 + z^5.
\end{align*}

The polynomials $\MT_n$ have a particular symmetry, namely, they are invariant under the permutation $\sigma$ 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 $\mathscr{M}_n$ inspired by the map defined by Deutsch \cite{D2}. 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:
\begin{itemize}
\item for every $k\geq 0$, $E(H^k)=H^k$;
\item $E(p'\,U\,p''\,D\,p''')=E(p'')\,U\,E(p')\,D\,p'''.$
\end{itemize}


\begin{example} Consider the following Motzkin path
$$p=\begin{tikzpicture}
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (12) at (12/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (11) at (11/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \draw[ultra thick] (0) -- (1) -- (2) -- (3) -- (4) -- (5);  
   \draw[ultra thick] (6) -- (7) -- (8) -- (9) -- (10) (11) -- (12);
   \draw[dashed] (5) -- (6);
   \draw[dashed]     (10) -- (11);
\end{tikzpicture}
$$
where $p'= HUUDD$, $p''=UHDH$, and $p'''=H$.
Since 
$$\begin{tikzpicture}
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,0) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \draw[] (0) -- (1) -- (2) -- (3) -- (4);  
\end{tikzpicture}\quad \xrightarrow{E} \quad \begin{tikzpicture}
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,0) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \draw[] (0) -- (1) -- (2) -- (3) -- (4);  
\end{tikzpicture}
$$
$$\begin{tikzpicture}
     \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5);  
\end{tikzpicture}\quad \xrightarrow{E} \quad \begin{tikzpicture}    \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,0) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5);  
\end{tikzpicture}
$$
the path $E(p)$ is
$$E(p)=\begin{tikzpicture}
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (12) at (12/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (11) at (11/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,0) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \draw[ultra thick] (0) -- (1) -- (2) -- (3) -- (4);  
   \draw[ultra thick] (5) -- (6) -- (7) -- (8) -- (9) -- (10) (11) -- (12);
   \draw[dashed] (4) -- (5);
   \draw[dashed]     (10) -- (11);
\end{tikzpicture}
$$

\end{example}


\begin{theorem}
For every integer $n$, the map $E$ is an involution over the set $\mathscr{M}_n.$
\end{theorem}
\begin{proof}
Straightforward.
\end{proof} 

Let $f$ be a polynomial in the variables $x_0,x_1,\ldots, y_0,y_1,\ldots,z$.  Set $$ f^{\sigma}(x_0,x_1,\ldots;y_0,y_1,\ldots;z)=f(y_0,y_1,\ldots;x_0,x_1,\ldots;z).$$

\begin{theorem}\label{simmetria}
$\MT_n=\MT^{\sigma}_n$.
\end{theorem}

\begin{proof}
We show that, for every $p\in\mathscr{M}_n$, the two monomials $m(E(p))$ and $m^{\sigma}(p)$ coincide.  We can prove this assertion by induction. In fact we have
\begin{itemize}
\item if $p=H^k$, we have $m(E(p))=m(p)=m^{\sigma}(p)$;   
\item 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_ry_sm(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_sy_rm(E(p'))m(E(p''))z^k.$$ By the induction hypothesis, this last monomial equals $$x_sy_rm^{\sigma}(p')m^{\sigma}(p'')z^k=m^{\sigma}(p).$$
\end{itemize}
\end{proof} 

\begin{theorem}
The polynomials $\MT_n$ satisfy the recurrence
\begin{equation}\label{fond}
\MT_n=z\,\MT_{n-1}+\sum_{i=0}^{n-2} x_i\,y_{n-2-i}\, \MT_i\, \MT_{n-2-i},\quad\quad n\geq 1
\end{equation}
with initial value
$$\MT_0=1.$$
\end{theorem}

\begin{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'')$. 
\end{proof}


\subsection{Specializations}
\label{specmot}

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 \ref{catalan}.

\begin{itemize}
\item[a.] Needless to say, $\MT_n(1,1,\ldots;1,1,\ldots;1)$ is the $n$-th Motzkin number (see sequence \seqnum{A001006} in \cite{Sl}). 
\item[b.] $\MT_n(1,1,\ldots;1,1,\ldots;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 \seqnum{A000108} in \cite{Sl}).   
\item[c.] The coefficient of $y_0^j$ in $\MT_n(1,1,\ldots;y_0,1,\ldots;1)$ (or, equivalently, the coefficient of $x_0^j$ in $\MT_n(x_0,1,\ldots;1,1,\ldots;1)$) is the number of Motzkin paths of length $n$ with $j$ peaks, namely, occurrences of $UD$ (see sequence \seqnum{A097860} in \cite{Sl}). 
\item[d.] The coefficient of $y_1^j$ in $\MT_n(1,1,\ldots;1,y_1,1,\ldots;1)$ (or, equivalently, the coefficient of $x_1^j$ in $\MT_n(1,x_1,1,\ldots;1,1,\ldots;1)$) is the number of Motzkin paths of length $n$ with $j$ occurences of $UHD$ (see sequence \seqnum{A114583} in \cite{Sl}).
\item[e.] The coefficient of $z^j$ in $\MT_n(1,1,\ldots;1,1,\ldots;z)$ is the number of Motzkin paths of length $n$ with $j$ horizontal steps (see sequence \seqnum{A097610} in \cite{Sl}). 
\item[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,\ldots;q,q^2,\ldots;1)=\MT_n(q,q^2,\ldots;1,1,\ldots;1)$$ is the number of Motzkin paths of length $n$ and area $j$ (see sequence \seqnum{A129181} in \cite{Sl}).
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)}.$ 

\begin{example} The Motzkin path of Example \ref{esempio1} 
$$\begin{tikzpicture}]
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (19) at (9/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (18) at (8/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (17) at (7/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (16) at (6/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (15) at (5/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (14) at (4/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (13) at (3/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (12) at (2/2,0) {};
   \node[draw,shape=circle,minimum size=.5mm, inner sep=0mm, fill=black] (11) at (1/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
    \node[label={\small $q^2$}] at (4/2,1/2) {};
   \node[label={\small $q$}] at (7/2, 2/2) {};
   \node[label={\small $q^4$}] at (9/2, 1/2) {};
   \node[label={\small $q^9$}] at (5, 0) {};
\draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (10);
\draw[dashed] (1) -- (11) (2) -- (12) (3) -- (13) (4) -- (14) (5) -- (15) (6) -- (16) (7) -- (17) (8) -- (18) (9) -- (19)  (0) -- (10)  (1) -- (9)  (5) -- (7);
\end{tikzpicture}
$$
has area $16$.
\end{example}

\end{itemize}

\subsection{A joint distribution}
\label{jointd}


Consider the polynomials $$T_n= T_n(q,z,x_0,x_1)=\MT_n(x_0q,x_1q^2,q^3,q^4,\ldots;1,1,\ldots;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)=\sum_{n\geq 0} T_n w^n.$$


Formula (\ref{fond}) yields the following recurrence for the polynomials  $T_n$: 
$$T_n=z\,T_{n-1}+x_0q\,T_{n-2}+x_1q^2zT_{n-3} +\sum_{i=2}^{n-2} q^{i+1}\, T_i\, T_{n-2-i},\quad\quad n\geq 1 $$
with initial value $T_0=1.$

Now we multiply the previous identity by $w^n$ and sum up for $n\geq 1$:
\begin{align*}
\sum_{n\geq 1}T_nw^n\, &= \sum_{n\geq 1}\,z\,T_{n-1}w^n+x_0q\sum_{n\geq 2}\,T_{n-2}w^n \\
& +x_1q^2z\sum_{n\geq 3} T_{n-3}w^n +q\sum_{n\geq 2}\,\sum_{i=2}^{n-2} q^{i}\, T_i\, T_{n-2-i}w^n, 
\end{align*} 
 hence getting
 
 $$F(w)-1=wzF(w)+w^2x_0qF(w)+ w^3q^2x_1zF(w)+w^2q(F(qw)-1-qwz)\cdot F(w) .$$
 
From the previous equality we have
 
$$F(w)=\frac{1}{1-wz-qw^2(x_0-1)+zq^2w^3(1-x_1)-w^2qF(qw)} .$$



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

$$F(w)=\cfrac{1}{1+a_0(w)w-\cfrac{b_1w^2}{1+a_1(w)w-\cfrac{b_2w^2}{1+a_2(w)w-\cdots}}},$$
where 
$$a_i(w)=-zq^i+q^{2i+1}w(1-x_0)+zq^{3i+2}w^2(1-x_1)\quad \text{and} \quad b_i=q^{2i-1}.$$

Specializing $x_0=x_1=1$ we get

$$F(q,z,w,1,1)=\cfrac{1}{1-wz-\cfrac{qw^2}{1-qwz-\cfrac{q^3w^2}{1-q^2wz-\cfrac{q^5w^2}{1-q^3wz-\cdots}}}}.$$

 

Note that the last expression can be obtained also from Formula (10.48) in \cite{KraLattice} setting $b_h=zq^hw$ and $\lambda_k=q^{2k-1}w^2.$  


We recall that the Hankel matrix $H_{n}$ of order $n+1$ of a sequence $(u_n)_{n\in\mathbb N}$ is the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $u_{i+j}$ where the indices range between $0$ and $n.$ The \emph{Hankel transform} of the sequence $(u_n)$ is the sequence $(v_n)_{n\in\mathbb N}$ where $$v_n=\det H_{n}=\det \left[\begin{matrix} u_0 & u_1 & \dots & u_n \\ u_1 & u_2 & \dots & u_{n+1} \\ \cdots & \cdots & \ddots & \cdots  \\ u_n & u_{n+1} & \dots &  u_{2n}  \end{matrix}\right].$$ 

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 \cite{KraDet} and \cite{KraDetCom}.


Now, \cite[Theorem 29]{KraDetCom} implies, after a trivial calculation, that the Hankel matrix $H_n$ of the sequence $(T_n(q,z,1,1))_{n\in\mathbb 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.$


\section{Catalan tunnel polynomials}
\label{catalan}


In this section we consider the polynomials $$\CT_n(\lambda_0,\lambda_1,\ldots\lambda_{n-1};\mu_0,\mu_1,\ldots,\mu_{n-1}):=\MT_{2n}(\lambda_0,0,\lambda_1,0,\ldots,\lambda_{n-1};\mu_0,0,\mu_1,0,\ldots\mu_{n-1};0).$$

For $0\leq n\leq 4$ these polynomials are
\begin{align*}
\CT_0 &=1 \\
\CT_1 &=\lambda_0 \mu_0 \\
\CT_2 &=\lambda_0\lambda_1\mu_0^2 + \lambda_0^2\mu_0\mu_1 \\
\CT_3 &= \lambda_0\lambda_1\lambda_2\mu_0^3 + \lambda_0^2\lambda_1\mu_0^2\mu_1 + \lambda_0^2\lambda_2\mu_0^2\mu_1 + \lambda_0^2\lambda_1\mu_0^2\mu_2 + \lambda_0^3\mu_0\mu_1\mu_2 \\
\CT_4 & =
\lambda_0\lambda_1\lambda_2\lambda_3\mu_0^4 + \lambda_0^2\lambda_1\lambda_2\mu_0^3\mu_1 + \lambda_0^2\lambda_1\lambda_3\mu_0^3\mu_1 + \lambda_0^2\lambda_2\lambda_3\mu_0^3\mu_1 + \lambda_0^3\lambda_2\mu_0^2\mu_1^2 + \lambda_0^2\lambda_1^2\mu_0^3\mu_2 \\ & +\lambda_0^2\lambda_1\lambda_3\mu_0^3\mu_2 + \lambda_0^3\lambda_1\mu_0^2\mu_1\mu_2 + \lambda_0^3\lambda_3\mu_0^2\mu_1\mu_2 + \lambda_0^2\lambda_1\lambda_2\mu_0^3\mu_3 + \lambda_0^3\lambda_1\mu_0^2\mu_1\mu_3 + \lambda_0^3\lambda_2\mu_0^2\mu_1\mu_3 \\ & +\lambda_0^3\lambda_1\mu_0^2\mu_2\mu_3 + \lambda_0^4\mu_0\mu_1\mu_2\mu_3.
\end{align*}

Theorem \ref{simmetria} implies  
\begin{equation}\label{simm}
\CT_n(\lambda_0,\lambda_1,\ldots\lambda_{n-1};\mu_0,\mu_1,\ldots,\mu_{n-1})=\CT_n(\mu_0,\mu_1,\ldots,\mu_{n-1};\lambda_0,\lambda_1,\ldots\lambda_{n-1}).
\end{equation}

In the following the polynomial $\CT_n(\lambda_0,\lambda_1,\ldots\lambda_{n-1};\mu_0,\mu_1,\ldots,\mu_{n-1})$ will be denoted by $\CT_n$, for short.

Formula (\ref{fond}) gives the following recurrence for the polynomials $\CT_n$: 
\begin{equation}\label{ricorrcat}
\CT_n=\sum_{i=0}^{n-1} \lambda_i\, \mu_{n-1-i}\, \CT_i\, \CT_{n-1-i},\quad\quad n\geq 1, \end{equation}
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=\sum_{p\in\mathscr{C}_n}\hat{m}(p),$$
where $\mathscr{C}_n$ is the set of Dyck paths of semilength $n$ and $\hat{m}(p)$ is defined as follows. We associate with every step $S$  either the variable $\lambda_{\frac{t(S)}{2}}$ if $S$ is an up step, or the variable $\mu_{{\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 $\hat{m}(p)$ is the product of the variables of every step of $p$. 
Notice that 

\begin{itemize}
\item the exponent of $\lambda_0$ in $\hat{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.  
\item Similarly, the exponent of $\mu_0$ in $\hat{m}(p)$  is the number of peaks in $p$. As a consequence, denoting by $i$ the exponent of $\lambda_0$ and by $j$ the exponent of $\mu_0$ in $\hat{m}(p)$, we have $i+j=n+1$.
\item The exponent of $\lambda_1$ in $\hat{m}(p)$ is the number occurrences of $UUDU$ in $p$ increased by one if $p$ begins with $UDU$.
\item The exponent of $\mu_1$ in $\hat{m}(p)$  is the number occurrences of $UUDD$ in $p$.
\end{itemize}


\subsection{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. 

\begin{itemize}
\item[a.] Obviously, $\CT_n(1,1,\ldots;1,1,\ldots)$ is the $n$-th Catalan number $c_n$ (see sequence \seqnum{A000108} in \cite{Sl}). 
\item[b.] $\CT_n(1,1,\ldots; q,1,1,1,\ldots) $ is the $n$-th \emph{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 \seqnum{A001263} in \cite{Sl}). On the other hand, by identity (\ref{simm}), we have $\CT_n(1,1,\ldots; q,1,1,1,\ldots) =\CT_n(q,1,\ldots; 1,1,1,1,\ldots), $ 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}$.
\item[c.] The coefficient of $\mu_1^i$ in $\CT_n(1,1,\ldots; 1,\mu_1,1,1,1,\ldots) $ is the number of Dyck paths of semilength $n$ with $i$ occurrences of $UUDD$, and also the number of \L{}ukasiewicz paths of length $n$ with $i$ peaks  (see sequence \seqnum{A098978} in \cite{Sl}). We recall that a \L{}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,\ldots$, 
 with the restriction that these paths cannot go below the 
$x$-axis. It is known that the number of all \L{}ukasiewicz paths of length $n$ is the $n$-th Catalan number (see \cite{Fl}). 
\item[d.] If $n\geq 2,$ $\CT_n(1,1,\ldots; 1,1,0,0,\ldots) $ is the $(n-2)$-th Fibonacci number (see sequence \seqnum{A000045} in \cite{Sl}), 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,\ldots; a,b,0,0,\ldots) =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 \cite[p.\ 542]{ACMS}, the authors consider a slightly different family $\{n\}_{s,t}$ of Fibonacci polynomials. More precisely, 
$$\{n+1\}_{s,t}=F_n\left(s,\frac{t}{s}\right).$$
\item[e.] Recall that a Schr\"oder 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\"oder numbers (see sequence \seqnum{A006318} in \cite{Sl}). $\CT_n(1,1,\ldots;2,1,1,\ldots)$ is the $n$-th large Schr\"oder 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\"oder 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,\ldots;k,1,1,\ldots)$ counts  large Schr\"oder paths where double horizontal steps may have a color taken from the set $\{1,2,\ldots,k-1\}$.
\item[f.] The normalized area $\tilde A(d)$ of a Dyck path $d$ is equal to $$\tilde A(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 
$$\begin{tikzpicture}%[every node/.style={draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black}]
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,0/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (d) at (2/2,0) {};   
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (c) at (4/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (b) at (6/2,0) {};   
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (a) at (5/2,1/2) {};   
\draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8);
\draw[dashed] (1) -- (d) -- (3) -- (c) -- (a) -- (b) -- (7)  (4) -- (a) -- (6);
 \end{tikzpicture}
$$
is $4$,  
$$\begin{tikzpicture}%[every node/.style={draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black}]
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,0/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,1/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
 
\node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (d) at (2/2,0) {};   
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (c) at (4/2,0) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (b) at (6/2,0) {};   
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (a) at (5/2,1/2) {};   
\draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8);
\draw[dashed] (1) -- (d) -- (3) -- (c) -- (a) -- (b) -- (7)  (4) -- (a) -- (6);
\draw[dashed] (0) -- (d)  -- (c)  -- (b) -- (8) (1) -- (3) -- (a) -- (7) (4) -- (6);
 \end{tikzpicture}
$$
while its area is $12$. 



The arguments of Section \ref{specmot} imply that the coefficient of $q^k$ in $\CT_n(1,1,\ldots;1,q,q^2,\ldots)$ is the number of Dyck paths of semilength $n$ with \emph{normalized area} equal to $k$. Hence, the polynomial $\CT_n(1,1,\ldots;1,q,q^2,\ldots)$
is nothing but the Carlitz-Riordan q-analogue of Catalan numbers (see \cite{FUR}).


\item [g.]The polynomials $\mathfrak{C}_n(q,t)=\CT_n(1,q,q^2,\ldots;1,t,t^2,\ldots)$
are the $q,t$-generalization of the Carlitz-Riordan polynomials appearing in \cite{ADIN}.
In fact, by Formula  (\ref{ricorrcat})
we have the following recurrence for such polynomials:
$$ \mathfrak{C}_n(q,t)=\sum_{k=0}^{n-1}q^kt^{n-1-k}\mathfrak{C}_k(q,t)\mathfrak{C}_{n-1-k}(q,t),\quad \quad n\geq 1,$$
with
$$\mathfrak C_0(q,t)=1.$$
This recurrence is precisely the same that defines the $q,t$-polynomials in \cite{ADIN}.
In the same work the authors describe a combinatorial interpretation for these polynomials in terms of maximal chains in the non-crossing partition lattice.

\end{itemize}

\subsection{A joint Catalan distribution}

Consider the polynomials $\widehat{\CT}_n(q,\mu_0,\mu_1)=\CT_n(1,1,\ldots;\mu_0,\mu_1q,q^2,\ldots)$ 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,\mu_0,\mu_1)=\sum_{n\geq 0} \widehat{\CT}_n(q,\mu_0,\mu_1) w^n,$$ and we get the following
continued fraction expansion for $G(q,w,\mu_0,\mu_1)$:

\begin{equation} \label{Rama}
G(q,w,\mu_0,\mu_1)=\cfrac{1}{1+a_0(w)w-\cfrac{b_1w}{1+a_1(w)w-\cfrac{b_2w}{1+a_2(w)w-\cfrac{b_3w}{\cdots}}}},
\end{equation}
where $a_i(w)=-\mu_0q^i+q^i+\mu_0q^{2i+1}w(1-\mu_1)$ and $b_i=q^{i-1}$.

Note that, setting $\mu_0=1,$ $\mu_1=1$ and $w=-aq$ in (\ref{Rama}),  we get a continued fraction  studied by Ramanujan
(see \cite[p.\ 30]{Ramanujan3}).



\section{Binary trees}\label{fbt}

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 \cite[p.\ 312]{Kn1}). 

Let $t$ be a binary tree. We associate with every internal node $v$ of $t$ the pair $(a_{\ell}(v),a_r(v))$, where $a_{\ell}(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 \cite[p.\ 405] {Kn1}). In symbols, denoting by $\tilde v$ the root of $t$,
$$l(t)=\sum_{v\in Int(t)}d(v, \tilde v).$$

We have

\begin{proposition}
For every  binary tree $t$, 
$$l(t)=\sum_{v\in Int(t)} (a_{\ell}(v)+a_r(v)).$$
\end{proposition}

\begin{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_{\ell}$ be the right and the left child of $\tilde v,$ respectively.
Then \begin{align*}
l(t) =\sum_{v\in Int(t)}d(v, \tilde v) & =\sum_{v\in Int(t_{\ell})}(d(v,v_{\ell})+1)+\sum_{v\in Int(t_r)}(d(v,v_r)+1)\\ & =
\sum_{v\in Int(t_{\ell})}d(v,v_{\ell})+\sum_{v\in Int(t_r)}(d(v,v_r)+a_{l}(\tilde v)+a_r(\tilde v)).\end{align*}
By the inductive hypothesis we have  $$\sum_{v\in Int(t_{\ell})}d(v,v_{\ell})=l(t_{\ell})=\sum_{v\in Int(t_{\ell})} (a_{\ell}(v)+a_r(v)),$$ and similarly for $t_r$. This gives the assertion. 
\end{proof}

It is well known (see \cite{Kn1}) 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_{\ell}$ 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} \text{ the empty path,} & \text{ if }$t$\text{ is the empty tree;}\\
f(t_r)Uf(t_{\ell})D,  & \text{ otherwise.}
\end{cases}$$

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

\begin{proposition}
Let $t$ be a binary tree and $p=f(t).$
Consider an internal node $v$ and let $\bar U$ and $\bar D$ denote the steps of $p$ corresponding to $v.$ Then the weights of $\bar U$ and $\bar D$ are $\lambda_{a_r(v)}$ and  $\mu_{a_{\ell}(v)}.$
In particular $$\hat m(p)=\prod_{v\in Int(t)}\lambda_{a_{\ell}(v)}\mu_{a_r(v)}.$$
\end{proposition}
\begin{proof}
By the recursive definition of the map $f,$
it suffices to prove the assertion for the root $\tilde v$ of $t.$
Note that, since $f(t)=f(t_r)\bar Uf(t_{\ell})\bar D $, the root $\tilde v$ corresponds precisely to the pair of steps $\bar U$ and $\bar D.$ On the other hand, the step $\bar U$ has  weight $\lambda_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 $\bar D$ has  weight $\lambda_i$, where $i$ is the number of internal nodes of the tree $t_{\ell}.$
\end{proof}

\begin{example}
Consider the  binary tree $t$ given by
$$
\begin{tikzpicture}[level 1/.style={sibling distance=30mm},level 2/.style={sibling distance=15mm},level 3/.style={sibling distance=15mm},level 4/.style={sibling distance=7mm}]
\node [circle, draw] at (6, 0)  {(4,1)}
    child{node [circle, draw]  {(3,0)}
    child{node [circle, draw]  {(1,1)}
        child{node [circle, draw]  {(0,0)}
            child{node[rectangle,draw]  {}}
            child{node[rectangle,draw]  {}}
            }
     child{node [circle, draw]  {(0,0)}
        child{node[rectangle,draw] {}}
         child{node[rectangle,draw]  {}}
         }
           }
    child{node [rectangle,draw]  {}}
    }
    child{node [circle, draw]  {(0,0)}
    child{node [rectangle,draw]  {}}
    child{node[rectangle,draw]  {}}
      }
         ;
\end{tikzpicture}$$
where the internal nodes are circled and the leaves are squared. In each internal node we indicate the pair $(a_{\ell}(v),a_r(v)).$ This tree corresponds to the Dyck path $p$


$$\begin{tikzpicture}%[every node/.style={draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black}]
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (12) at (12/2,0/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (11) at (11/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,4/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,0/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \node[label={\small $x_0$}] at (0, 0) {};
   \node[label={\small $y_0$}] at (1,0) {};
   \node[label=below:{\small $x_1$}] at (3/2, 1/2) {};
   \node[label=below:{\small $x_0$}] at (4/2, 2/2) {};
   \node[label=below:{\small $x_0$}] at (5/2, 3/2) {};
   \node[label={\small $y_0$}] at (6/2,2/2) {};
   \node[label=below:{\small $x_1$}] at (7/2, 3/2) {};
   \node[label=below:{\small $x_0$}] at (8/2, 4/2) {};
   \node[label={\small $y_0$}] at (9/2, 3/2) {};
   \node[label={\small $y_1$}] at (10/2, 2/2) {};
   \node[label={\small $y_3$}] at (11/2, 1/2) {};
   \node[label={\small $y_4$}] at (12/2, 0/2) {};
\draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (10) -- (11) -- (12);
\end{tikzpicture}
$$
\end{example}


As an immediate consequence of the previous results we get

\begin{theorem}
The coefficient of $q^k$ in the polynomial $\CT_n(1,q,q^2,\ldots;1,q,q^2,\ldots)$ is the number of  binary trees with $n$ internal nodes and path length $k$.
\end{theorem}

Observe that the number of binary trees with $n$ internal nodes and path length $k$ is sequence \seqnum{A138157} in \cite{Sl}.

Let $H(q,w)=\sum_{n\geq 0} \CT_n(1,q,q^2,\ldots;1,q,q^2,\ldots)w^n$ be the generating function of these polynomials. 
Recurrence (\ref{ricorrcat}) yields 

$$\begin{array}{l}
\CT_n(1,q,q^2,\ldots,1,q,q^2,\ldots)=\\ \\ q^{n-1}\sum_{i=0}^{n-1}\CT_i(1,q,q^2,\ldots,1,q,q^2,\ldots)\cdot \CT_{n-1-i}(1,q,q^2,\ldots,1,q,q^2,\ldots).
\end{array}
$$
The previous identity allows us to deduce the following functional equation for $H(q,w)$:
$$H(q,w)=w\cdot H(q,qw)^2+1.$$ 
Note that this functional equation is the same obtained directly by Knuth in \cite[p.\ 595]{Kn1}.


\section{Partial and free Motzkin paths}\label{Partialfree}

In \cite{CHEN}, Chen et al. introduce the notions of \textit{partial Motzkin path} and \textit{free Motzkin path} with the aim to generalize
a matrix identity due to Shapiro (see \cite{Shapiro}).

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 \cite{CHEN}.
A \textit{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 \textit{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 $\mathscr{PM}_n$ and $\mathscr{FM}_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 \textit{R-visible} in \cite{CHEN}.
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_{\infty}.$ Each other step in $d$ is labelled considering the corresponding
weak tunnel  as done in Section \ref{sectone} (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$.

\begin{example} In the following partial Motzkin path
$$\begin{tikzpicture}%[every node/.style={draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black}]
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,2/2) {};
\node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,0) {};
   \node[label={\small $x_\infty$}] at (0, 0) {};
   \node[label={\small $x_0$}] at (1/2,1/2) {};
   \node[label=below:{\small $x_3$}] at (5/2, 2/2) {};
   \node[label={\small $z$}] at (5/4, 2/2) {};	
   \node[label={\small $x_0$}] at (5/2, 2/2) {};
   \node[label=below:{\small $y_1$}] at (3/2,2/2) {};
   \node[label={\small $y_0$}] at (7/2, 2/2) {};
   \node[label=below:{\small $y_2$}] at (7/2, 2/2) {};
   \node[label={\small $x_\infty$}] at (8/2, 1/2) {};
   \node[label={\small $x_\infty$}] at (9/2, 2/2) {};
   \draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (10);
\end{tikzpicture}
$$
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_{\infty}^3x_0^2x_3y_0y_1y_2z$.
\end{example}

Now consider a free Motzkin path $d.$ In this path there can be both R-visible up steps and \textit{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_\infty$ 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 \textit{elevation line} for $d$ is any line of the form $y=h$ with
$0\leq h\leq j.$

We have the following.
\begin{proposition}\label{bijectionpartialfree}
 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))=\left(\frac{y_\infty}{x_\infty}\right)^h m(d).$$
\end{proposition}
\begin{proof}
The map $El$ is the same considered in \cite{CHEN} and called \textit{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. 
\end{proof}


\begin{example}
 Consider the same partial path $d$ of the previous example and the elevation line $y=2.$ Then $El(d)$ is given by
$$\begin{tikzpicture}%[every node/.style={draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black}]
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (10) at (10/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (9) at (9/2,0/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (8) at (8/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (7) at (7/2,2/2) {};
\node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (6) at (6/2,3/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (5) at (5/2,2/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (4) at (4/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (3) at (3/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (2) at (2/2,2/2) {}; 
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (1) at (1/2,1/2) {};
   \node[draw,shape=circle,minimum size=1mm, inner sep=0mm, fill=black] (0) at (0,1) {};
   \node[label=below:{\small $y_\infty$}] at (0, 2/2) {};
   \node[label={\small $x_0$}] at (1/2,1/2) {};
   \node[label=below:{\small $x_3$}] at (5/2, 2/2) {};
   \node[label={\small $z$}] at (5/4, 2/2) {};	
   \node[label={\small $x_0$}] at (5/2, 2/2) {};
   \node[label=below:{\small $y_1$}] at (3/2,2/2) {};
   \node[label={\small $y_0$}] at (7/2, 2/2) {};
   \node[label=below:{\small $y_2$}] at (7/2, 2/2) {};
   \node[label={\small $y_\infty$}] at (9/2, 0/2) {};
   \node[label=below:{\small $x_\infty$}] at (10/2, 1/2) {};
   \draw[] (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (10);
\end{tikzpicture}
$$
\end{example}


Now we associate with the sets $\mathscr{PM}_n$ and $\mathscr{FM}_n$ the polynomials $PT_n$ and $FT_n$
defined in the following way
$$PT_n=\sum_{d\in \mathscr{PM}_n }m(d),$$
and 
$$FT_n=\sum_{d\in \mathscr{FM}_n }m(d).$$

We need to further refine the polynomials $PT_n.$
Let $\mathscr{PM}^{(j)}_n$ be the subset of $\mathscr{PM}_n$ consisting of those partial Motzkin paths whose last point has height $j.$
We set $PT^{(j)}_n$ to be the polynomial
$$PT^{(j)}_n=\sum_{d\in \mathscr{PM}^{(j)}_n}m(d).$$
As a consequence we have $$PT_n=\sum_{j=0}^n PT^{(j)}_n.$$
Note that $PT^{(0)}_n=\MT_n.$


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

\begin{theorem}
Set $R=\dfrac{y_\infty}{x_\infty}.$ Then

\begin{equation}\label{matrixeq}
\begin{bmatrix}
    \MT_{0} & 0 & 0 & 0 & 0 & \dots   \\
    \MT_{1} & PT^{(1)}_{1} & 0 & 0 & 0 &   \dots   \\
    \MT_{2}  & PT^{(1)}_{2} & PT^{(2)}_{2} & 0 & 0 & \dots   \\
    \MT_{3}  & PT^{(1)}_{3} & PT^{(2)}_{3} & PT^{(3)}_3 & 0 &\dots   \\
    \MT_{4}  & PT^{(1)}_{4} & PT^{(2)}_{4} & PT^{(3)}_4 & PT^{(4)}_4 &\dots   \\
    \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\
    
\end{bmatrix}\times
\begin{bmatrix}
    1\\
    1+R  \\
1+R+R^2 \\
1+R+R^2+R^3 \\
1+R+R^2+R^3 +R^4 \\
    \vdots \\
\end{bmatrix}=
\begin{bmatrix}
    FT_0\\
    FT_1  \\
   FT_2 \\
   FT_3  \\
   FT_4 \\
    \vdots \\
\end{bmatrix}.
\end{equation}

\end{theorem}
\begin{proof}
As in \cite{CHEN}, we write the previous identity in a one-row-form:

$$\sum_{j=0}^n PT^{(j)}_n(1+R+\ldots+R^j)=FT_n,\qquad \forall n\in\mathbb{N}.$$

Since each partial Motzkin path whose last point has height $j$ can have elevation lines $y=0,$ $y=1,$ $\ldots$ $y=j,$  Proposition \ref{bijectionpartialfree} 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.
\end{proof}

The first few lines of the previous matrix identity read

$$
\begin{bmatrix}
    1 & 0 & 0    \\
    z & x_\infty & 0 \\
    x_0y_0+z^2  & 2x_\infty z & x^2_\infty  \\
\end{bmatrix}\times
\begin{bmatrix}
    1\\
    1+R  \\
1+R+R^2 \\
\end{bmatrix}=
\begin{bmatrix}
    1\\
    x_\infty+ y_\infty + z \\
   x^2_\infty +y^2_\infty + x_\infty y_\infty +2x_\infty z+2y_\infty z +x_0y_0+z^2 \\
\end{bmatrix}.
$$



Observe that when the polynomials 
$$\MT_n=\MT_n(x_0,x_1,x_2,\ldots,x_{n-2};y_0,y_1,y_2,\ldots,y_{n-2};z),$$
$$PT^{(j)}_n=PT^{(j)}_n(x_0,x_1,x_2,\ldots,x_{n-2},x_\infty ;y_0,y_1,y_2,\ldots,y_{n-2};z),$$
and
$$FT_n=FT_n(x_0,x_1,x_2,\ldots,x_{n-2},x_\infty ;y_0,y_1,y_2,\ldots,y_{n-2},y_\infty ;z),$$
are evaluated at $z=k-t-1,$ $x_i=1$ for every $0\leq i\leq \infty$ and $y_i=t$ for every $0\leq i\leq \infty$
Equation (\ref{matrixeq}) reduces to the formula proved in \cite{CHEN}. This last formula further reduces to the Shapiro identity \cite{Shapiro}  when $k=4$ and $t=1.$


Now we study the polynomials $PT^{(j)}_n$ and $FT_n$ in their own right.

First of all it is easy to see, considering the last return decomposition, that the polynomials $PT^{(j)}_n$ satisfy the following recurrence relation involving
the Motzkin tunnel polynomials:
\begin{equation}\label{equazionericorrenza}
PT^{(j)}_n=\begin{cases}
          \MT_n, & \text{ if }j=0;\\
         \sum_{i=0}^{n-1}x_\infty \MT_i PT^{(j-1)}_{n-i-1}, & \text{ otherwise.}
         \end{cases}.
\end{equation}

Hence for the  generating function $P^{(j)}(w)=\sum_{n\geq 0 }PT^{(j)}_n w^n$ and $P^{}(w)=\sum_{n\geq 0 }PT^{}_n w^n$ we have
\begin{equation}
P^{(j)}(w)=w x_\infty \MT(w) P^{(j-1)}(w)=(w x_\infty)^j\MT(w)^{j+1} ,
\end{equation}

and 

\begin{equation}\label{generpartial}
P^{}(w)=\frac{\MT(w)}{1-x_\infty w \MT(w)},
\end{equation}

where $\MT(w)=\sum_{n\geq 0 }\MT_n w^n.$

As a consequence the matrix $[PT^{(j)}_{i}]_{i,j \geq 0}$ is a Riordan array. In the notation of \cite{ShapGetu} it is the Riordan array $\mathcal R (\MT(w),x_\infty \MT(w))$ . 

Since the generating function of the column vector in the left hand side of Equation (\ref{matrixeq}) is $$R(w)=\sum_{j\geq 0 }(1+R+\ldots+R^j) w^j=\frac{1}{1-R}\left(\frac{1}{1-w}-\frac{R}{1-R w} \right)=\frac{1}{(1-w)(1-R w)}, $$ we deduce immediately that 
the generating function $F(w)=\sum_{n\geq 0 }F_n w^n$ of the column vector of the right hand side of Equation (\ref{matrixeq}) is 
$$F(w)=\frac{\MT(w)}{(1-w x_\infty \MT(w))(1- w R x_\infty \MT(w))}=\frac{\MT(w)}{(1-w x_\infty \MT(w))(1- w y_\infty \MT(w))}.$$

As an application we can find the multivariate generating function $\widehat{F}(w)$ ($\widehat{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,\ldots,1;y_0,1,\ldots,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,\ldots;1,y_1,1,\ldots;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 $$\widehat{F}(w)=\sum_{n\geq 0}FT_n(1,\ldots,1,x_\infty;y_0,y_1,1,\ldots,1,y_\infty;z)w^n, $$
and $$\widehat{P}(w)=\sum_{n\geq 0}PT_n(1,\ldots,1,x_\infty;y_0,y_1,1,\ldots,1;z)w^n .$$

From the results of Subsection \ref{jointd} and recalling that $\MT_n(1,\ldots,1;y_0,y_1,\ldots,1;z)=\MT_n(x_0,x_1,\ldots,1;1,1,\ldots,1;z)$
we deduce that 
$$\sum_{n\geq 0 }\MT_n(1,\ldots,1;y_0,y_1,\ldots,1;z) w^n=\frac{-b-\sqrt{b^2-4w^2}}{2w^2},$$
where $b=-1+wz+w^2y_0-w^2+w^3y_1z-w^3z.$

Hence \begin{equation}\label{mat}
\widehat{P}(w)=\frac{-b-\sqrt{b^2-4w^2}}{2w^2+x_\infty w b +x_\infty w \sqrt{b^2-4w^2}},\end{equation}
and 
\begin{equation}\label{mat2}
\widehat{F}(w)=\frac{2(-b-\sqrt{b^2-4w^2})}{(2w+x_\infty  b +x_\infty  \sqrt{b^2-4w^2})(2w+y_\infty  b +y_\infty  \sqrt{b^2-4w^2})}.\end{equation}



For example, specializing (\ref{mat}) and (\ref{mat2}) in $x_\infty=1,\,y_\infty=1,y_1=1,$ we get the generating function of the distribution of peaks over partial Motzkin paths 
and free Motzkin paths (see sequences \seqnum{A132893} and \seqnum{A181371}  in \cite{Sl}).




 
 
Consider now the polynomials $A_n(x_\infty,z)=PT_n(1,1,\ldots,1,x_\infty;1,\ldots,1;z).$ Our aim is to evaluate the Hankel transform of the sequence $\left(A_n\right)_{n\in \mathbb N}.$

\begin{theorem}
 The sequence $\left(A_n\right)_{n\in \mathbb N}$ has Hankel transform $(1)_{n\in \mathbb N}.$
\end{theorem}

\begin{proof}
Let $H_m$ and $\widehat H_m,$ $m\geq 0,$ be the Hankel matrices of the sequences $\left(M_n\right)_{n\in \mathbb N}$ and  $\left(A_n\right)_{n\in \mathbb N},$
respectively, where $M_n=\MT_n(1,1,\ldots,1;1,\ldots,1;z)$ and let $B_m=[b_{i,j}]_{i,j\geq 0}$ the $m\times m$ matrix defined as follows:
$$b_{i,j} =\begin{cases} 1, & \text{ if }i=j;\\
x_\infty A_{j-i-1}, & \text{ if }j>i;\\
0, & \text{ otherwise.}
\end{cases}.$$

By the recurrence (\ref{equazionericorrenza}) we have 
\begin{equation}\label{recurrence2}
A_n=M_n+\sum_{j=0}^{n-1}M_j x_\infty A_{n-1-j}=\sum_{j=0}^{n}M_j b_{j,n}. 
\end{equation}

As a consequence of the previous identity, we have that the  $(i,j-1)\mbox{-th}$ element of the product $B_m^T\cdot H_m\cdot B_m$ is
\begin{align*}
\sum_{0\leq h\leq j-1}\sum_{0\leq k\leq i}b_{k,i}M_{k+h}b_{h,j-1} &=\sum_{0\leq h\leq j-1}\sum_{0< k\leq i}b_{k,i}M_{k+h}b_{h,j-1}+b_{0,i}\sum_{0\leq h\leq j-1}M_{h}b_{h,j-1}\\
& = \sum_{0\leq h\leq j-1}\sum_{0\leq  k\leq i-1}b_{k+1,i}M_{k+1+h}b_{h,j-1}+b_{0,i}A_{j-1}\\
& =\sum_{0< h\leq j}\sum_{0\leq  k\leq i-1}b_{k+1,i}M_{k+1+h-1}b_{h-1,j-1}+x_\infty A_{i-1} A_{j-1}\\
& =\sum_{0< h\leq j}\sum_{0\leq  k\leq i-1}b_{k,i-1}M_{k+h}b_{h,j}+ A_{i-1} b_{0,j}\\ & =\sum_{0\leq  h\leq j}\sum_{0\leq  k\leq i-1}b_{k,i-1}M_{k+h}b_{h,j},
\end{align*}
that is the $(i-1,j)\mbox{-th}$ element of $B_m^T\cdot H_m\cdot 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\geq 0}.$

Hence we have the matrix identity $$\widehat{H}_m= B_m^T\cdot H_m\cdot B_m. $$
Since $\det B_m=1$ $\forall m\geq 0,$ $\det\widehat H_m=\det H_m=1$ and we get the assertion.
\end{proof}

Note that the previous result can be also obtained as a consequence of the results contained in \cite{KraArchive}.


\section{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.

\bibliographystyle{dersh-jis}
\bibliography{barnabei5}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15, Secondary 05A05, 05A19.

\noindent \emph{Keywords: }
Motzkin number, Catalan number, binary tree, continued fraction, Dyck path.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 28 2018;
revised versions received  September 7 2018; December 3 2018.
Published in {\it Journal of Integer Sequences}, December 5 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}