\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'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}