<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{amscd}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://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  Dyck Paths, Motzkin Paths, \\
\vskip .12in and the Binomial Transform}  \vskip 1cm
\large
Stefano Capparelli and Alberto Del Fra\\
Dept SBAI\\
Universit\`a di Roma La Sapienza\\
Italy\\
\href{mailto:stefano.capparelli@uniroma1.it}{\tt stefano.capparelli@uniroma1.it} \\
\href{mailto:alberto.delfra@uniroma1.it}{\tt alberto.delfra@uniroma1.it}
\end{center}
\vskip .2 in


\begin{abstract}
 We study the moments of orthogonal polynomial sequences (OPS) arising
 from tridiagonal matrices.  We  obtain combinatorial information about
 the sequence of moments of some OPS in terms of Motzkin and Dyck
 paths, and also in terms of the binomial transform. We then introduce
 an equivalence relation on the set of Dyck paths and some operations
 on them. We determine a formula for the cardinality of those
 equivalence classes, and use this information to obtain a combinatorial
 formula for the number of Dyck and Motzkin paths of a fixed length.
\end{abstract}

\section{Introduction and preliminaries}\label{intro}

In the papers \cite{CM1} and \cite{CM2} the first author studied certain combinatorial properties of orthogonal polynomial sequences arising from special matrices. Savo \cite{SAV} used some results of \cite{CM1}. Here we systematically study the sequence of moments arising from a generalization of the matrices studied there.

We use a combinatorial interpretation of the action of the binomial transform on the sequence of moments of orthogonal polynomials arising from a tridiagonal matrix to obtain  relations that tie together different well-known sequences of integers.

We also obtain a recursive formula for the moments.

The object of our study is also the set of Dyck paths. We introduce an equivalence relation on the set of Dyck paths, we compute the cardinality of the equivalence classes and use this information to give a combinatorial formula for the number of Dyck and Motzkin paths of a fixed length.

 We recall the definition of orthogonal polynomial sequence (OPS) \cite{CHI}. Let $(\mu_n)_{\mu=0}^\infty$ be a sequence of complex numbers and $\mathcal L$ the complex valued linear functional defined on the vector space of polynomials $\mathbb C[x]$ by
\begin{equation}
      \mathcal L(x^n)=\mu_n, n=0,1,2,\ldots\\
  \end{equation}
  The functional $\mathcal L$ is called the moment functional, $(\mu_n)$ the moment sequence, and the number $\mu_n$ the moment of order $n$.
A sequence $(P_n(x))_{n=0}^\infty$ is called an orthogonal polynomial sequence with respect to $\mathcal L$ if the following conditions hold for all nonnegative integers $m$ and $n$:
\begin{enumerate}
  \item $P_n(x)$ is a polynomial of degree $n$,
  \item $\mathcal L(P_m(x)P_n(x))=0$ for $m\ne n$,
  \item $\mathcal L(P_n^2(x))\ne 0$.
\end{enumerate}
The following is a well known result \cite{CHI}:
\begin{theorem}
  The sequence of monic polynomials $(P_n(x))_{n=0}^\infty$ is an orthogonal polynomial sequence if and only if there exist two sequences $(h_n)_{n=1}^\infty$ and $(u_n)_{n=1}^\infty$ such that the following recurrence holds:

  \begin{equation}\label{ricorrenza}
    \begin{split}
      P_n(x)=(x-h_n)P_{n-1}(x)-u_{n}P_{n-2}(x), n=1,2,3,\ldots\\
      P_{-1}(x)=0, P_0(x)=1.
    \end{split}
  \end{equation}
\end{theorem}


We will be interested in the moment sequence. One way to compute the moment sequence of a monic OPS is the following, cf.\  \cite{VIE,VIE1}.
Consider the infinite matrix $A$ whose $n$-th row is formed by taking the coefficients of the $n$-th (monic) polynomial of the OPS so that the entry $a_{nk}$ is the coefficient of $x^k$ of the polynomial. Since $a_{nn}=1$, this is an infinite matrix with 1 on the main diagonal.  We then consider the sequence of the leading principal minors, namely the submatrices obtained by taking the first $n$ rows and the first $n$ columns of this infinite matrix. These are all invertible matrices. Consider the sequence of the inverse matrices: these are the leading principal minors of the infinite matrix $A^{-1}$. The sequence of the first column in $A^{-1}$ is the required moment sequence.



\section{A recursive formula for moments}\label{recursivemoments}
\begin{definition}
 A {\it Motzkin path} of length $n$ is a path on the integral lattice $\mathbb{Z}\times \mathbb{Z}$ starting from $(0,0)$ and ending in $(k,0)$ using $n$ steps according to the vectors  $(1,1)$, $(1,0)$, $(1,-1)$ and never going below the $x$-axis, \cite{AIG}.
\end{definition}

\begin{definition}
 A Motzkin path with no $(1,0)$ steps is called a {\it Dyck path}, \cite{DEU}.
\end{definition}

There is a close relationship between  the moment of order $n$ and the  number of Motzkin paths suitably weighted (or ``colored''). We will examine some special cases and draw some interesting conclusions.

Given three sequences  $$(h_0,h_1,h_2,\ldots),(u_0,u_1,u_2,\ldots),(d_0,d_1,d_2,\ldots)$$  we may  consider colored Motzkin paths
 where, for any index $i$,  $h_i$ is the number of colors of the  horizontal step at level $i$,
$u_i$ is the number of colors of the up step starting from level $i$,
$d_i$ is the number of colors of the down step arriving at level $i$. For example,

\vskip 0.1in
\begin{center}

$\begin{picture}(300,-70)(-50,30)
\setlength{\unitlength}{.7mm}


\put(2,1){$h_0$}
\put(13,1.7){$u_0$}
\put(17,9){$h_1$}
\put(28,9.7){$u_1$}
\put(33,17){$h_2$}
\put(37.5,9.7){$d_1$}
\put(46.5,9){$h_1$}
\put(52,1.7){$d_0$}
\put(62,1){$h_0$}
\put(73,1.7){$u_0$}
\put(79,9){$h_1$}
\put(82,1.7){$d_0$}
\put(0,0){\line(1,0){10}}
\put(10,0){\line(2,3){5}}
\put(15,7.5){\line(1,0){10}}
\put(25,7.5){\line(2,3){5}}
\put(30,15){\line(1,0){10}}
\put(40,15){\line(2,-3){5}}
\put(45,7.5){\line(1,0){10}}
\put(55,7.5){\line(2,-3){5}}
\put(60,0){\line(1,0){10}}
\put(70,0){\line(2,3){5}}
\put(75,7.5){\line(1,0){10}}
\put(85,7.5){\line(2,-3){5}}

\end{picture}$

\end{center}

\vskip 0.5in



On the other hand one may consider the  infinite tridiagonal matrix
\begin{equation}\label{tridiaginf}
\begin{pmatrix}
  h_0&amp;u_0&amp;0&amp;0&amp;0&amp;0&amp;\ldots\\
  d_0&amp;h_1&amp;u_1&amp;0&amp;0&amp;0&amp;\ldots\\
  0&amp;d_1&amp;h_2&amp;u_2&amp;0&amp;0&amp;\ldots\\
  0&amp;0&amp;d_2&amp;h_3&amp;u_3&amp;0&amp;\ldots\\
  \ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots
\end{pmatrix}
\end{equation}
and the sequence of the leading principal minors of order $n=1,2,3,\ldots$. For each such minor we may compute the monic characteristic polynomial. It is well known that the sequence of polynomials thus obtained is an OPS.
Notice that the same sequence of polynomials is obtained if we consider the matrix
\begin{equation}
\begin{pmatrix}
  h_0&amp;u_0d_0&amp;0&amp;0&amp;0&amp;0&amp;\ldots\\
  1&amp;h_1&amp;u_1d_1&amp;0&amp;0&amp;0&amp;\ldots\\
  0&amp;1&amp;h_2&amp;u_2d_2&amp;0&amp;0&amp;\ldots\\
  0&amp;0&amp;1&amp;h_3&amp;u_3d_3&amp;0&amp;\ldots\\
  \ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots
\end{pmatrix}
\end{equation}
hence in this section we may assume, without loss of generality, that $d_i=1$ for all $i$.

Let $\mu_n$ be the moments of this sequence of orthogonal polynomials.
As a consequence of a  theorem of Flajolet \cite{FLA} (also see \cite{VIE} and \cite{VIE1}), we have
\begin{theorem}\label{interpretazione}
  The element $\mu_n$ of the moment sequence $(\mu_0, \mu_1, \mu_2,\ldots)$  determined by the matrix {\rm \eqref{tridiaginf}} counts the  number of  Motzkin paths of length n colored with $h_i, u_i,d_i$, $i=0,1,2,\ldots$
\end{theorem}

We want to study the special case where  $h_i=h, u_i=u$ are constant sequences:
\begin{equation}\label{consttridiaginf}
T=\begin{pmatrix}
  h&amp;u&amp;0&amp;0&amp;0&amp;0&amp;\ldots\\
  1&amp;h&amp;u&amp;0&amp;0&amp;0&amp;\ldots\\
  0&amp;1&amp;h&amp;u&amp;0&amp;0&amp;\ldots\\
  0&amp;0&amp;1&amp;h&amp;u&amp;0&amp;\ldots\\
  \ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots&amp;\ldots
\end{pmatrix}
\end{equation}

A formula for the moment sequence in this case is well known:
\begin{equation}\label{formulachiusa}
  \mu_n=\sum_{i\geq 0} C_i \binom{n}{2i}h^{n-2i}u^{i}
\end{equation}
 and  $C_i=\frac{1}{i+1}\binom{2i}{i}$ is the  $i$-th term of the Catalan sequence. We wish to obtain a recurrence for this sequence.



We shall need the following  general property of matrices:


\begin{proposition}\label{propmatrix}
   Let $A=(a_{ij}), i,j=0,\ldots, n$ be a unipotent $(n+1)\times (n+1)$  lower triangular matrix, and let $B$ be the matrix obtained by erasing the first row and the last column of $A$:
   $$
B=\begin{pmatrix}
  a_{10}&amp;1&amp;0&amp;\cdots &amp;0\\
  a_{20}&amp;a_{21}&amp;1&amp;\cdots &amp;0\\
  \cdots&amp;\cdots&amp;\cdots&amp;\ddots&amp;\cdots\\
  a_{n-1,0}&amp;a_{n-1,1}&amp;a_{n-1,2}&amp;\cdots&amp;1\\
  a_{n0}&amp;a_{n1}&amp;a_{n2}&amp;\cdots&amp;a_{n,n-1}
\end{pmatrix}
$$
 Let  $\alpha_{ij}$ denote the cofactor in $A$ of the element $a_{ij}$, and set $P_0=1$, $P_i, 1\leq i\leq n-1$, the determinant of the leading principal minor of $B$ of order $i$.  Then $\alpha_{00}=1=P_0, \alpha_{01}=-P_1, \alpha_{02}=P_2$, $\alpha_{03}=-P_3, \ldots, \alpha_{0n}=(-1)^{n}P_{n}$. Moreover,
  \begin{equation}\label{leggeric}
  \det B=P_{n}=\sum_{i=0}^{n-1}a_{ni} (-1)^{n+i-1}P_{i}\end{equation}

\end{proposition}


\begin{lemma}\label{coefformula}
   Consider the matrix $A=(a_{st})$ formed by the coefficients of the characteristic polynomials
   \begin{equation}
  p_n(x)=a_{n0}+a_{n1}x+\cdots +a_{n,n-1}x^{n-1}+x^{n}
\end{equation}
of the leading principal minor of order $n$ of the tridiagonal matrix \eqref{consttridiaginf}. Its entries are,  for $s,t \in\{0,1,2,\ldots\}$,
\begin{equation}\label{formula}
  a_{st}=\sum_{j=0}^{s} (-1)^{s-t-j}\binom{s-j}{j+t}\binom{j+t}{t}h^{s-t-2j}u^{j}
\end{equation}
\end{lemma}
\begin{proof}
  To prove this formula we recall that the characteristic polynomials form an OPS and therefore satisfy the recurrence \eqref{ricorrenza} with $h_n=h$ and $u_n=u$, for all $n$. Hence we may proceed by induction as follows.

Define
\begin{equation}
  p_n(x)=a_{n0}+a_{n1}x+\cdots +a_{n,n-1}x^{n-1}+x^{n}
\end{equation}
to be the monic characteristic polynomial of the $n\times n$ tridiagonal matrix \eqref{consttridiaginf}.  It is straightforward, using \eqref{ricorrenza}, to check that the coefficients of $p_n(x)$ are related to the coefficients of $p_{n-1}(x)$ and $p_{n-2}(x)$ as follows:

\begin{equation}\label{relazioni}
  \begin{split}
    a_{n0}&amp;=-ua_{n-2,0}-ha_{n-1,0}\\
    a_{n1}&amp;=-ua_{n-2,1}+a_{n-1,0}-ha_{n-1,1}\\
    a_{n2}&amp;=-ua_{n-2,2}+a_{n-1,1}-ha_{n-1,2}\\
    &amp;\vdots\\
    a_{n,n-2}&amp;=-ua_{n-2,n-2}+a_{n-1,n-3}-ha_{n-1,n-2}\\
    a_{n,n-1}&amp;=a_{n-1,n-2}-h\\
    a_{nn}&amp;=1
  \end{split}
\end{equation}
Now assume that \eqref{formula} holds for $s$ up to $n-1$.

For $t=0$ we have
\footnotesize
\begin{equation}
\begin{split}
  &amp;a_{n,0}=-ua_{n-2,0}-ha_{n-1,0}\\
  &amp;= -u \sum_{j\geq 0} (-1)^{ n - 2 - j }\binom{ n - 2 - j }{j}h^{ n - 2 - 2j }u^{j} - h \sum_{j\geq 0} ( -1 )^{ n - 1 - j }\binom{ n - 1 - j }{ j }h^{ n - 1 - 2j }u^{j}\\
    &amp;=\sum_{j\geq 1} (-1)^{n-j}\binom{ n - 1 - j }{ j - 1 }h^{n-2j}u^{j}+\sum_{j\geq 0} (-1)^{n-j}\binom{ n - 1 - j }{ j }h^{n-2j}u^{j}\\
  &amp;=(-1)^{n}\binom{n}{0}h^{n}+\sum_{j\geq 1} (-1)^{n-j}\binom{n-j}{j}h^{n-2j}u^{j}\\
  &amp;=\sum_{j\geq 0} (-1)^{n-j}\binom{n-j}{j}h^{n-2j}u^{j}
  \end{split}
\end{equation}
\normalsize

For $1\leq t\leq n-2$ we have
\begin{equation*}
\begin{split}
  a_{n,t}&amp;=-ua_{n-2,t}+a_{n-1,t-1}-ha_{n-1,t}\\
  &amp;=-u \sum_{j\geq 0} (-1)^{n-2-t-j}\binom{n-2-j}{j+t}\binom{j+t}{t}h^{n-2-t-2j}u^{j}\\
  &amp;+\sum_{j\geq 0} (-1)^{n-t-j}\binom{n-1-j}{j+t-1}\binom{j+t-1}{t-1}h^{n-t-2j}u^{j}\\
  &amp;-h\sum_{j\geq 0} (-1)^{n-1-t-j}\binom{n-1-j}{j+t}\binom{j+t}{t}h^{n-1-t-2j}u^{j}
  \end{split}
\end{equation*}
\begin{equation*}
\begin{split}
     &amp;=\sum_{j\geq 1} (-1)^{n-t-j}\binom{n-1-j}{j+t-1}\binom{j+t-1}{t}h^{n-t-2j}u^{j}\\
  &amp;+\sum_{j\geq 0} (-1)^{n-t-j}\binom{n-1-j}{j+t-1}\binom{j+t-1}{t-1}h^{n-t-2j}u^{j}\\
  &amp;+\sum_{j\geq 0} (-1)^{n-t-j}\binom{n-1-j}{j+t}\binom{j+t}{t}h^{n-t-2j}u^{j}
  \end{split}
\end{equation*}

  The terms for $j\geq 1$ in the first two summations can be added using the Stiefel formula
 \footnotesize
  \begin{equation*}
\begin{split}
   &amp;=\sum_{j\geq 1} (-1)^{n-t-j}\binom{n-1-j}{j+t-1}\binom{j+t}{t}h^{n-t-2j}u^{j}\\
  &amp;+\sum_{j\geq 1} (-1)^{n-t-j}\binom{n-1-j}{j+t}\binom{j+t}{t}h^{n-t-2j}u^{j}\\
  &amp;+ (-1)^{n-t}\binom{n-1}{t-1}h^{n-t}+ (-1)^{n-t}\binom{n-1}{t}h^{n-t}
  \end{split}
\end{equation*}
\normalsize
  and applying Stiefel's formula again we get
  \begin{equation*}
\begin{split}
   &amp;=(-1)^{n-t}\binom{n}{t}h^{n-t}+\sum_{j\geq 1} (-1)^{n-t-j}\binom{n-j}{j+t}\binom{j+t}{t}h^{n-t-2j}u^{j}\\
  &amp;=\sum_{j\geq 0} (-1)^{n-t-j}\binom{n-j}{j+t}\binom{j+t}{t}h^{n-t-2j}u^{j}
  \end{split}
\end{equation*}
as required.

Finally, case $t=n-1$:

\begin{equation}
\begin{split}
  a_{n,n-1}&amp;=-h+a_{n-1,n-2}\\
  &amp;=-h+\sum_{j\geq 0} (-1)^{1-j}\binom{n-1-j}{n+j-2}\binom{n+j-2}{n-2}h^{1-2j}u^{j}
  \end{split}
\end{equation}
In the summation the only nonzero term is the one with $j=0$ and we have
\begin{equation}
  -h-\binom{n-1}{n-2}h=-nh
\end{equation}
as required.
\end{proof}

\begin{proposition}\label{recformula}
   The sequence of moments $(\mu_n)$ corresponding to the matrix \eqref{consttridiaginf} satisfies  the following recursive formula:
   $\mu_0=1$ and, for $n\geq 1$,
\begin{equation}\label{leggericorsiva}
  \mu_{n}=\sum_{i=0}^{n-1}a_{ni} (-1)^{n+i}\mu_{i}\end{equation}
where
$$a_{ni}=\sum_{j=0}^{n} (-1)^{n-i-j}\binom{n-j}{j+i}\binom{j+i}{i}h^{n-i-2j}u^{j}$$
\end{proposition}

\begin{proof}

Consider the matrix $A$ formed by the coefficients of the characteristic polynomials of the leading principal minors of the tridiagonal matrix \eqref{consttridiaginf}. Lemma \ref{coefformula} implies that its entries are,  for $s,t \in\{0,1,2,\ldots\}$,

$$a_{st}=\sum_{j=0}^{s} (-1)^{s-t-j}\binom{s-j}{j+t}\binom{j+t}{t}h^{s-t-2j}u^{j}.$$

The moments are computed by taking the first column of the inverse matrix of $A$.
When computing an inverse matrix one must compute the cofactors.  We are interested, in particular, in the cofactors of the first row  (those that give the first column of the inverse matrix). Since $A$ is lower triangular with 1 on the main diagonal we may use Proposition \ref{propmatrix}.
We then have
$$
\mu_n=\alpha_{0n},
$$
and by \eqref{leggeric}
we have the conclusion.
\end{proof}

\section{The binomial transform}\label{binomialtransform}

We recall the definition of binomial transform \cite{KNU}:
\begin{definition}
  Given a sequence of integers $(a_n)_{n\geq 0}$ one defines its {\it binomial transform} to be the sequence $(s_n)=\mathcal{T}((a_n))$ defined by
  $$
  s_n=\sum_{h=0}^n\binom{n}{h}a_h
  $$
  \end{definition}
\begin{example}
  If  $a_n=1$ for all $n$, then $s_n=2^n$.
\end{example}
 The operator $\mathcal{T}$ is invertible. The inverse binomial transform is given by the formula
  $$
  a_n=\sum_{h=0}^n(-1)^{n-h}\binom{n}{h}s_h
  $$


The following nice result is well known and easy to prove:
\begin{proposition}
   The binomial transform of the moment sequence of {\rm \eqref{tridiaginf}} is the moment sequence of
  \begin{equation}\label{tridiag1}
  \begin{pmatrix}
    h_0+1&amp;u_0&amp;0&amp;0&amp;\ldots\\
    d_0&amp;h_1+1&amp;u_1&amp;0&amp;\ldots\\
    0&amp;d_1&amp;h_2+1&amp;u_2&amp;\ldots\\
    0&amp;0&amp;d_2&amp;h_3+1&amp;\ldots\\
    \vdots&amp;\vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;
  \end{pmatrix}
  \end{equation}

  \end{proposition}

\begin{proof}
To compute $s_n$, we choose $k\leq n$ horizontal steps to be colored with the new color. This can be done in $\binom{n}{k}$ ways. Once we remove these $k$ horizontal steps, we get Motzkin paths with the old colors. There are $a_{n-k}$ such paths. Therefore
$$
s_n=\sum_{k=0}^n \binom{n}{k}a_{n-k}=\sum_{k=0}^n \binom{n}{n-k}a_{k}=\sum_{k=0}^n \binom{n}{k}a_{k}
$$
\end{proof}




One may  use this theorem to obtain a relation between different integer sequences.

Consider all the sequences of moments that can be obtained starting from two parameters $(h,u)$ as follows:
$$
\mu:\mathbb{R}\times \mathbb{R} \rightarrow \mathbb{R}^{\mathbb{N}}
$$
defined by  associating with every pair of real numbers $(h,u)$ the sequence of moments of the  tridiagonal matrices \eqref{consttridiaginf},
 hence
\begin{equation}\label{map}
\begin{split}
(h,u)&amp;\mapsto \mu[h,u]=(\mu_n=\mu_n[h,u])
\end{split}
\end{equation}
where $\mu_n=\sum_{i\geq 0} C_i \binom{n}{2i}h^{n-2i}u^{i}$
and  $C_i=\frac{1}{i+1}\binom{2i}{i}$ is the  $i$-th term of the Catalan sequence (cf.\  \eqref{formulachiusa}).

Define the multiplication of a scalar $k\in \mathbb R$ and a sequence $(\mu_n)_{n\geq 0}$ to mean the sequence $(k^{\frac n2}\mu_n)_{n\geq 0}$.
\begin{proposition}
For $h,h'\in \mathbb{N}, u,u'\in \mathbb{R}_{+}$, the following formula holds
\begin{equation}
  \mathcal{T}^{h'}\left(\frac{u'}{u}\right)\mathcal{T}^{-h}\mu[h,u]=\mu[h',u']
\end{equation}
\end{proposition}
\begin{proof} By applying  the inverse binomial transform $\mathcal{T}^{-1}$  $h$ times to the sequence $\mu[h,u]$  one gets the sequence $\mu[0,u]$ which counts Dyck paths. Then, by multiplying this sequence by  $\frac{u'}{u}$, we suitably color the up steps, thus obtaining $\mu[0,u']$. Finally, by applying  $\mathcal{T}^{h'}$ we obtain the sequence $\mu[h',u']$.


\end{proof}

This formula allows one to relate the sequence of numbers of Motzkin paths of length $n$ with weights $h,u$ with the analogous sequence with weights $h',u'$.
For example, the sequence $\mu[2,2]=(1,2,6,20,72,272,\ldots)$  counts  Motzkin paths where the up and horizontal steps have two fixed colors.  Computing $\mathcal{T}^{-2}$ we get the sequence $\mu[0,2]=(1,0,2,0,8,0,40,0,\ldots)$ which  counts  Dyck paths with two-colored up step. Divide the sequence by $2$ thus obtaining the sequence counting Dyck paths with a single color. Now multiply by $3$ and finally  apply  $\mathcal T$. The result is the sequence
$  \mathcal{T}\left(\frac{3}{2}\right)\mathcal{T}^{-2}\mu[2,2]=\mu[1,3]=(1,1,4,10,37,121,\ldots )$  counting  Motzkin paths whose up step has 3 colors and the horizontal steps a single color. Explicitly we have the following formula

\begin{equation}
  \mu_n[1,3]=\sum_{k=0}^n\binom{n}{k}\left(\frac 32\right)^{\frac k2}\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}\sum_{i=0}^j(-1)^{j-i}\binom{j}{i}\mu_i[2,2]
\end{equation}
or
\begin{equation}
  \mu_n[1,3]=\sum_{k=0}^n\sum_{j=0}^k\sum_{i=0}^j\binom{n}{k}\binom{k}{j}\binom{j}{i}\left(\frac 32\right)^{\frac k2}(-1)^{k-i}\mu_i[2,2]
\end{equation}

\begin{remark}
$\mu[1,2]$ is the sequence  \seqnum{A025235} in \cite{OEI}. This is presented there, for example, with the formula
  \begin{equation}\label{tentativo1}
  \sum_{h=0}^n \binom{n}{h}2^{h/2}C_{h/2} \frac{1+(-1)^h}{2},
  \end{equation}
where $C_{n}$ is the $n$-th  Catalan number. From our point of view, this formula is an example of our proposition relating $\mu[1,2]$ and $\mu[0,2]$. This last one is the sequence \seqnum{A151374} in \cite{OEI}.
\end{remark}










\section{Frames of Dyck paths}\label{frames}
Here we want to study the structure of the set of Dyck paths. This will also allow us to give a combinatorial formula that counts Dyck and Motzkin paths.

First, we wish to classify Dyck paths according to the number of feet  at each level, defining a {\it foot at level $k$} to be a point where the path touches  level $k$.
The well known formula for the Catalan numbers:
 \begin{equation}\label{leggeCatalan}
C(n)=\sum_{k=0}^{n-1}C(n-1-k)C(k).
\end{equation}
suggests that any length $2n$  Dyck path can be obtained by a combination of two operations. The first operation consists in adding to each path of length  $2(n-1-k)$ an up step at the beginning and a down step at the end. We  call this operation {\it lifting}. The second operation consists in {\it gluing} at the end of it any path of length  $2k$,  $k=0,\ldots, n-1$.


Next, we observe that every  Dyck path is obtained by a sequence of up and down steps, indicated by   U and D, respectively, in such a way that the total number of  U's is equal to the number of  D's and that at each  step the number of  U's be not less than the number of D's. Let's associate with each   U the number  1 and to each D the number $-1$. Starting from  0, let's sum at each step the numbers  1 and $-1$ up to that point. For a length $2n$ path, the {\it associated } sequence thus obtained starts and ends with   0 and the maximum number appearing is at most $n$. For each integer  $i\ge 0$, let  $p(i)$ denote the number of times that  $i$ appears in the sequence; we shall say that the path  is {\it $p(i)$-ped} at the level $i$. As an example, the length 14 path UUDUUDDUUDUDDD has the associated sequence 012123212323210 which is  simply the sequence of the $y$ coordinate of the points touched by the path. The path is therefore  biped at level 0, quadruped at level 1, 6-ped at level 2, 3-ped at level 3, 0-ped at higher levels.
We may sometimes identify a path with its associated sequence.


For our purposes, we need to know the number of Dyck paths that have a fixed ``frame'' $(i_0,i_1,\ldots)$, according to the definition we are about to give.

Given a  Dyck path $D$, with $i_k$ feet at level $k$, $k=0,1,\ldots$, we call the sequence  $(i_0,i_1,\ldots)$, which is zero from a certain index on, the  {\it frame} of $D$. In other words, the sequence tells us how many feet there are at each level.
This sequence is zero from a certain index on, since, if the length of $D$ is $2n$, one has $i_{n+j}=0$, for $j\ge 1$, namely, the maximum reachable level for a Dyck path of length $2n$ is $n$.

Given an eventually zero sequence $\mathbf{I} =(i_0,i_1, \ldots)$,  we shall call the integer
  $ -1+\sum_{k=0}^{\infty}i_k $
  the {\it length} of $\mathbf{I}$ .

We shall say that an eventually zero sequence is  {\it admissible} if it is the frame of some  Dyck path.  For an admissible frame $\mathbf{I}$, its length is the same as the length of a path with that frame and is necessarily even.

For example, frames of Dyck paths of length 0,2,4 are, respectively:
\begin{itemize}

\item $(1,0,0,\ldots) $,

\item $(2,1,0,\ldots)$,

\item $(2,2,1,0,\ldots), (3,2,0,\ldots)$.
\end{itemize}

Notice that two distinct paths with the same length may have the same frame. For example, the two paths
\begin{center}
\vspace{.3cm}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,0) {};
      \node (D) at (3,1) {};
      \node (E) at (4,2) {};
      \node (F) at (5,1) {};
      \node (G) at (6,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
      \node (A1) at (10,0) {};
       \node (B1) at (11,1)  {} ;
      \node (C1) at (12,2) {};
      \node (D1) at (13,1) {};
      \node (E1) at (14,0) {};
      \node (F1) at (15,1) {};
      \node (G1) at (16,0) {};
       \draw (A1)--(B1);
      \draw (B1)--(C1);
      \draw (C1)--(D1);
      \draw (D1)--(E1);
      \draw (E1)--(F1);
      \draw (F1)--(G1);
       \end{tikzpicture}

\end{center}
\noindent have the same frame $(3,3,1,0,0,\ldots)$.


\vspace{.3cm}

Obviously, ``having the same frame'' is an equivalence relation on the set of   Dyck paths. Notice that lifting two equivalent paths  we still get two equivalent  paths. This is true also if we glue together two paths: if $\mathbf p_i$ is equivalent to $\mathbf q_i$, $i=1,2$, then gluing  $\mathbf p_1$ and $\mathbf p_2$ gives a path that is equivalent to gluing $\mathbf q_1$ and $\mathbf q_2$.
This observation allows us to speak of  {\it lifting a frame} and  {\it gluing two frames}.

It is easy to construct recursively the frames associated with Dyck paths of various lengths, using the same recursive law as for the paths.

Lifting the frame $(i_0,i_1,i_2,\ldots)$ one gets the frame  $(2,i_0,i_1,i_2,\ldots)$.
While gluing two frames  $(j_0,j_1,j_2,\ldots)$ and $(i_0,i_1,i_2,\ldots)$, we get a frame $(i_0+j_0-1,i_1+j_1,i_2+j_2,\ldots)$.


For the lifting and gluing operations we shall use the following symbols:
$$s(i_0,i_1,i_2,\ldots) = (2,i_0,i_1,i_2,\ldots),$$ $$(i_0,i_1,i_2,\ldots)\wedge (j_0,j_1,j_2,\ldots) = (i_0+j_0-1,i_1+j_1,i_2+j_2,\ldots)$$

It is not difficult to check, for example, that the frames with length 4 can be obtained in this fashion from those with shorter lengths.

The gluing operation on paths is associative but not commutative: in general, $\mathbf u\wedge \mathbf v \ne \mathbf v\wedge \mathbf u$. The same operation on frames however is commutative, namely,  $\mathbf u\wedge \mathbf v$ and $\mathbf v\wedge \mathbf u$ have the same frame.

Actually, any frame can be obtained by the combination of two elementary operations: {\it lifting} of frame $(i_0,i_1,i_2,\ldots)$, which turns  $(i_0,i_1,i_2,\ldots)$ into $s(i_0,i_1,i_2,\ldots)=(2,i_0,i_1,i_2,\ldots)$ and the gluing $(i_0,i_1,i_2,\ldots)$ to the frame of length  2, which we call {\it extension}, that turns  $(i_0,i_1,i_2,\ldots)$ into $a(i_0,i_1,i_2,\ldots)=(i_0,i_1,i_2,\ldots)\wedge (2,1,0,\ldots)=(i_0+1,i_1+1,i_2,\ldots)$. Indeed, we have:


\begin{theorem}\label{costruzione}
Every frame can be obtained by a combination of a lifting and a suitable number of extensions.

\end{theorem}



\begin{proof}
 Consider any path $U\cdots D$ that is not a lifting, i.e., with a frame starting with  $i_0\ge 3$. It follows that its sequence is of the form $01\cdots 101\cdots 10$, with at least one subsequence  $101$ inside. The first triple  $101$ inside comes from an ordered pair  DU. If we eliminate such a pair inside and add instead the pair  $UD$ at the end of the frame, we get a new path with the same frame as the previous one. Iterating such a procedure we get a Dyck path with the same frame as the starting path obtained by gluing a lifting of a suitable path and a finite number, possibly zero, of length 2 paths.
\end{proof}

\begin{theorem}
  The number of frames of length  $2n$, with $n&gt;0$, is $2^{n-1}$.
\end{theorem}



\begin{proof}
The frames of length $2n$ are obtained from those of length  $2(n-1)$ by constructing for each of them, say $\mathbf{I}$, the lifting $s(\mathbf{I})$ or the extension $a(\mathbf{I})$. The frame $s(\mathbf{I})$ is different from  $a(\mathbf{I})$ if $n&gt;1$. It follows that the number of frames with length  $2n$ is twice the number of the frames of length $2(n-1)$.
\end{proof}

Natural generalizations of the extension $a$ and lifting  $s$ operations  can be defined on any sequence of integers eventually zero. The operation $a$ is a bijection on the set of such sequences. Its inverse operation  $b$ is defined by:
 $$
b(i_0,i_1,i_2,\ldots)=(i_0-1,i_1-1,i_2,\ldots).
 $$
The operation $s$ is injective and can be inverted on its image, via an operation $r$ defined by:
$$
 r(2,i_{1},i_{2},\ldots)=(i_{1},i_{2},\ldots).
 $$


It is easy to see if a given sequence, which is eventually zero,  is admissible. Indeed, we can, starting from it, trace back the elementary steps that generated it from the basic frame  $(1,0,0,\ldots)$.
The rules can be summed up as follows: every time there is a 2 we erase it by using  $r$, otherwise we subtract 1 from the first two elements, by applying $b$.

\begin{example}\label{esempio1}
Consider the sequence $(3,6,6,3,1,0,\ldots)$. We wish to see if it is admissible for a path of length  $18=3+6+6+3+1-1$. Tracing backwards we have : $(2,5,6,3,1,0,\ldots)$, $(5,6,3,1,0,\ldots)$, $(4,5,3,1,0,\ldots)$, $(3,4,3,1,0,\ldots)$, $(2,3,3,1,0,\ldots)$, $(3,3,1,0,\ldots)$, $(2,2,1,0,\ldots)$, $(2,1,0,\ldots)$, finally $(1,0,\ldots)$. So the given sequence is admissible.
\end{example}

\begin{example}\label{esempio2}
If we take  $(4,5,2,3,1,0,\ldots)$, and we  trace backwards, we get:\footnotesize $$(3, 4, 2, 3, 1, 0,\ldots), (2, 3, 2, 3, 1, 0,\ldots), (3, 2, 3, 1, 0,\ldots), (2, 1, 3, 1, 0,\ldots), (1, 3, 1, 0,\ldots),$$ \normalsize  and finally $(0, 2, 1, 0,\ldots)$, which is clearly not admissible since there are no Dyck paths of length 2 without feet at the zero level.
\end{example}
In the preceding arguments, we have implicitly used the following two lemmas whose proof is straightforward:


\begin{lemma}\label{one}
  Given an eventually zero integer sequence  $\mathbf{I}$, with $i_0=2$,  $r(\mathbf{I})$ is  admissible if and only if  $\mathbf{I}$ is.
\end{lemma}


\begin{lemma}\label{two}

    Given an eventually zero integer sequence  $\mathbf{I}$, with  $i_0\ne2$, $b(\mathbf{I})$  is  admissible if and only if  $\mathbf{I}$ is.
\end{lemma}

Given an eventually zero integer sequence $(i_0,i_1,i_2,\ldots)$, let $i_f$ denote the last nonzero element and call  $f$ the {\it degree} of the frame.


\begin{theorem}\label{CNES}
 An eventually zero sequence of nonnegative integers  $$\mathbf{I}=(i_0,i_1,\ldots,i_f,0,\ldots),$$  with length  $2n$, is admissible if and only if the following conditions are satisfied:
  \begin{itemize}

    \item $i_0=1$, if $f=0$ and $i_0\geq 2$ if $f&gt;0$;
    \item $i_1-i_0\geq 0$ provided $f&gt;1$;
    \item $i_2-i_1+i_0\geq 2$;
    \item $i_3-i_2+i_1-i_0\geq 0$;
    \item $i_4-i_3+i_2-i_1+i_0\geq 2$;
    \item $\cdots$
    \item  $i_f-i_{f-1}+i_{f-2}+\cdots = -1$ when $f$ is odd;
    \item  $i_f-i_{f-1}+i_{f-2}+\cdots = 1$ when $f$ is even.
  \end{itemize}
\end{theorem}

\begin{proof}   The proof uses induction and it is a straightforward, though somewhat lengthy, computation, cf.\ \cite{CD}.
\end{proof}

The following proposition is an immediate consequence of the previous theorem.


\begin{proposition}\label{immediate}
 If a frame  $\mathbf{I}=(i_0,i_1,i_2,\ldots,i_f,\ldots)$ with length $2n$ is admissible, then:

\begin{enumerate}
\item
$i_{f-1}&gt; i_f$;
\item
 $i_0= i_1+1\Longleftrightarrow i_1=i_f$;
\item
$2\le i_j\le i_{j-1}+i_{j+1}-2$\quad $(0&lt;j&lt;f-1)$

\end{enumerate}
\end{proposition}

\section{Cardinality of a frame}\label{cardinality}

Recall the two operations defined on the set of Dyck paths:
\begin{itemize}
\item the lifting $s(\mathbf u)$ of a path  $\mathbf u$;
\item the gluing $\mathbf u\wedge \mathbf v$ of two paths $\mathbf u$ and $\mathbf v$.
\end{itemize}

With these two operations one may construct any Dyck path starting from shorter Dyck paths.

Therefore, every Dyck path may be expressed as
$$s^{j_1}(\mathbf x_1)\wedge s^{j_2}(\mathbf x_2)\wedge\cdots \wedge s^{j_t}(\mathbf x_t)$$
where each  $\mathbf x_i$ is again expressible in the same way, with the condition that after a finite number of steps one arrives at expressions of the form $$s^{k_1}(\mathbf 0)\wedge s^{k_2}(\mathbf 0)\wedge\cdots \wedge s^{k_r}(\mathbf 0),$$
where  $\mathbf 0$ is the unique Dyck  path of length  0.
For example, let's consider the path  $$UUDUUDDDUDUUUDUDDDUUDD$$ with length 22:
\begin{center}
\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,2) {};
      \node (D) at (3,1) {};
      \node (E) at (4,2) {};
      \node (F) at (5,3) {};
      \node (G) at (6,2) {};
      \node (H) at (7,1) {};
      \node (I) at (8,0) {};
      \node (J) at (9,1) {};
      \node (K) at (10,0) {};
      \node (L) at (11,1) {};
      \node (M) at (12,2) {};
      \node (N) at (13,3) {};
      \node (O) at (14,2) {};
      \node (P) at (15,3) {};
      \node (Q) at (16,2) {};
      \node (R) at (17,1) {};
      \node (S) at (18,0) {};
      \node (T) at (19,1) {};
      \node (U) at (20,2) {};
      \node (V) at (21,1) {};
      \node (W) at (22,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
      \draw (G)--(H);
      \draw (H)--(I);
      \draw (I)--(J);
      \draw (J)--(K);
      \draw (K)--(L);
      \draw (L)--(M);
      \draw (M)--(N);
      \draw (N)--(O);
      \draw (O)--(P);
      \draw (P)--(Q);
      \draw (Q)--(R);
      \draw (R)--(S);
      \draw (S)--(T);
      \draw (T)--(U);
      \draw (U)--(V);
      \draw (V)--(W);
       \end{tikzpicture}
\vspace{.3cm}
\end{center}
The corresponding sequence is $$01212321010123232101210$$ and it may be expressed as
$$s(\mathbf x_1)\wedge s(\mathbf x_2)\wedge s(\mathbf x_3)\wedge s(\mathbf x_4),$$
where $s(\mathbf x_1)=012123210$, $s(\mathbf x_2)=010$, $s(\mathbf x_3)=012323210$, $s(\mathbf x_4)=01210$, with $\mathbf x_1=0101210$, $\mathbf x_2=\mathbf 0$, $\mathbf x_3=0121210$, $\mathbf x_4=010$.
One  has therefore:


$\mathbf x_1=s(\mathbf y_1)\wedge s(\mathbf y_2)$, $\mathbf x_3=s(\mathbf y_3)$, $\mathbf x_4 =s(\mathbf 0)$,
with $\mathbf y_1=\mathbf 0$, $\mathbf y_2=010$, $\mathbf y_3=01010$ and so $\mathbf y_2=s(\mathbf 0)$, $\mathbf y_3=s(\mathbf z_1)\wedge s(\mathbf z_2)$,
with
$\mathbf z_1=\mathbf 0$, $\mathbf z_2=\mathbf 0$.

Finally, the assigned path can be expressed as
$$s(s(\mathbf 0)\wedge s^2(\mathbf 0))\wedge s(\mathbf 0)\wedge s^2(s(\mathbf 0)\wedge s(\mathbf 0))\wedge s^2(\mathbf 0).$$

Since a frame is an eventually zero integer sequence, we may think of it as a polynomial. The constant polynomial  1 corresponds to the null frame. Thus  $s(1)$ is the frame of the unique path with length 2, while  $s^2(1)$ and $s(1)\wedge s(1)$ are the frames of the length 4 paths, and so on. It is easy to check that, denoting by  $p(x)$ a frame, one has:
\begin{proposition}\label{polinomi}
$s(p(x)) = 2+xp(x), \quad p(x)\wedge q(x) = p(x) + q(x) -1$.
\end{proposition}
The procedure to determine the admissibility of a sequence, see Examples \ref{esempio1}, \ref{esempio2}, can be used to determine a ``canonical'' representative of a frame.
\begin{example}
Consider the frame $(3,4,3,1,0,\ldots)$ and apply to it  the functions $r$ and $b$. We obtain the sequence of frames  \footnotesize $$(2,3,3,1,0,\ldots), (3,3,1,0,\ldots), (2,2,1,0,\ldots), (2,1,0,\ldots), (1,0,\ldots),$$\normalsize thus getting to the null frame. There is, of course, only one path corresponding to the null frame: the null path.

We may now trace this procedure backwards with the operations $s$ and $a$ on the paths, eventually getting the desired canonical representative of the  frame $(3,4,3,1,0,\ldots)$.

 We start form the null path
 \begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \end{tikzpicture}
\vspace{.3cm}

this lifted gives:


\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
       \end{tikzpicture}
\vspace{.3cm}
with frame $s(1)=(2,1,0,\ldots)$,

lifted gives:


\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,2) {};
      \node (D) at (3,1) {};
      \node (E) at (4,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
       \end{tikzpicture}
\vspace{.3cm}
with frame $s^2(1)=(2,2,1,0,\ldots)$,

extended  gives:


\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,2) {};
      \node (D) at (3,1) {};
      \node (E) at (4,0) {};
      \node (F) at (5,1) {};
      \node (G) at (6,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
       \end{tikzpicture}
\vspace{.3cm}
with frame
$s^2(1)\wedge s(1)=(3,3,1,0,\ldots)$,

lifted gives:

\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,2) {};
      \node (D) at (3,3) {};
      \node (E) at (4,2) {};
      \node (F) at (5,1) {};
      \node (G) at (6,2) {};
      \node (H) at (7,1) {};
      \node (I) at (8,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
      \draw (G)--(H);
      \draw (H)--(I);
       \end{tikzpicture}
\vspace{.3cm}
with frame
$s(s^2(1)\wedge s(1))=(2,3,3,1,0,\ldots)$,

extended  gives:


\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,2) {};
      \node (D) at (3,3) {};
      \node (E) at (4,2) {};
      \node (F) at (5,1) {};
      \node (G) at (6,2) {};
      \node (H) at (7,1) {};
      \node (I) at (8,0) {};
      \node (J) at (9,1) {};
      \node (K) at (10,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
      \draw (G)--(H);
      \draw (H)--(I);
      \draw (I)--(J);
      \draw (J)--(K);
       \end{tikzpicture}
\vspace{.3cm}

with frame
$s(s^2(1)\wedge s(1)) \wedge s(1)=(3,4,3,1,0,\ldots)$.
\end{example}

Applying this procedure to any frame $(i_0, i_1,\ldots,i_f,0,\ldots)$, we reach a particular path belonging to this frame. This path is called the  {\it  canonical representative } of the frame $(i_0, i_1,\ldots,i_f,0,\ldots)$. In the preceding example the canonical representative is therefore  $s(s^2(\mathbf 0)\wedge s(\mathbf 0)) \wedge s(\mathbf 0)$.

The procedure is such that any time in a canonical representative there is a product of the form  $s^{j_1}(\mathbf x_1) \wedge s^{j_2}(\mathbf x_2) \wedge \cdots\wedge s^{j_t}(\mathbf x_t)$, then $s^{j_2}(\mathbf x_2)=\cdots=s^{j_t}(\mathbf x_t) =s(\mathbf 0)$.

In other words, a canonical path is of the form
\footnotesize
$$s^{j_1} (s^{j_2} (\cdots (s^{j_{t-1}} (s^{j_t}(\mathbf 0)\wedge \underbrace{s(\mathbf 0)\wedge\cdots\wedge s(\mathbf 0)}_{k_t})\wedge \underbrace{s(\mathbf 0)\wedge\cdots\wedge s(\mathbf 0)}_{k_{t-1}})\cdots)\wedge \underbrace{s(\mathbf 0)\wedge\cdots\wedge s(\mathbf 0)}_{k_1}.$$
\normalsize
Another way to describe the canonical path is to observe that in the corresponding sequence  of  U and D, after any sequence of one or more  D there is at most one  U.

\begin{example} Assume  the frame $(3,6,6,3,1,0,\ldots)$ is given.
By the preceding remarks to reach level 4 one must necessarily begin with a sequence of 4  U. Since there is a single foot at level 4 we must go down with at least  2 D. If we go down with  3 D, we could not go back to level  3, where there should be  3 feet. Hence we go down exactly two steps D and go back up with one  U. So far the sequence is  UUUUDDU. Since we do not need to go back to level 3 any longer, we go down with at least 2 more  D's. Again in this case, considering that at level 2 we have 6 feet, we must go down exactly with  2 D, then go up with one  U, then go down with one  D and climb back up with one  U two more times. We thus obtain  UUUUDDUDDUDUDU so far. Having exhausted the level 2 feet, we must go down with  2 D to level 0. Having obtained so far only 5 feet at level 1, we must still go up with  U and the concluding with a  D. The sequence is therefore UUUUDDUDDUDUDUDDUD.
\end{example}

The following  property is often  useful in computations.

\begin{proposition}\label{identita}
 $s(p(x)\wedge q(x))\wedge s(1) = s(p(x))\wedge s(q(x))$.
\end{proposition}

\begin{proof} Use  Proposition \ref{polinomi}: $s(p(x)\wedge q(x))\wedge s(1) = s(p(x)+q(x)-1)\wedge (2+x) = (2+x(p(x)+q(x)-1)) \wedge (2+x) = 2+x(p(x)+q(x)-1) +(2+x) -1 = 2+xp(x)+2+xq(x)-1 = s(p(x))\wedge s(q(x))$.
\end{proof}
 From this, it immediately follows:


\begin{corollary}\label{stessoschema} Given two Dyck paths $\mathbf x_1$, $\mathbf x_2$, the two paths $s(\mathbf x_1)\wedge s(\mathbf x_2)$, $s(\mathbf x_1\wedge \mathbf x_2)\wedge s(\mathbf 0)$ have the same frame.
\end{corollary}

\begin{theorem}\label{canonical}
     It is possible to obtain  the canonical representative of a frame $(i_0,i_1,\ldots,i_f,0,\ldots)$ in a finite number of steps starting from any representative path $\mathbf x$ using the commutativity property of the gluing operation and  Corollary \ref{stessoschema}.
\end{theorem}

\begin{proof} If   $\mathbf x$ is a representative of the frame, suppose that $\mathbf x$ contains a  product $s(\mathbf 0)\wedge s^i(\mathbf y)$, then this can be transformed into   $s^i(\mathbf y)\wedge s(\mathbf 0)$.
If it contains a product $s^i(\mathbf y)\wedge s^j(\mathbf z)$, with $s^i(\mathbf y)\ne s(\mathbf 0), s^j(\mathbf z)\ne s(\mathbf 0)$, this can be transformed into  $s(s^{i-1}(\mathbf y)\wedge s^{j-1}(\mathbf z))\wedge s(\mathbf 0)$. After a finite number of steps of these two types, one gets to the canonical path when none of these two steps is any longer possible.
\end{proof}



Using Theorem \ref{canonical}, we are now able to count the number of paths in a given frame.

\begin{example} Consider the frame  $(3,4,3,1,0,\ldots)$ as before. We already saw that its canonical representative is $\mathbf u=s(s^2(\mathbf 0)\wedge s(\mathbf 0)) \wedge s(\mathbf 0)$. From this canonical representative, using commutativity of the wedge operation, we have a total of 4 paths, including $\mathbf u$, precisely:


$s(s^2(\mathbf 0)\wedge s(\mathbf 0)) \wedge s(\mathbf 0)$,\, $s(s(\mathbf 0)\wedge s^2(\mathbf 0)) \wedge s(\mathbf 0)$,\, $s(\mathbf 0)\wedge s(s^2(\mathbf 0)\wedge s(\mathbf 0))$,\, $s(\mathbf 0)\wedge s(s(\mathbf 0)\wedge s^2(\mathbf 0))$:
\vspace{1cm}
\begin{center}
\begin{tikzpicture}[scale=0.2]
     \tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
       \node (A) at (0,0) {};
       \node (B) at (1,1)  {} ;
      \node (C) at (2,2) {};
      \node (D) at (3,3) {};
       \node (E) at (4,2) {};
       \node (F) at (5,1) {};
       \node (G) at (6,2) {};
       \node (H) at (7,1) {};
       \node (I) at (8,0) {};
       \node (J) at (9,1) {};
       \node (K) at (10,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
      \draw (G)--(H);
      \draw (H)--(I);
      \draw (I)--(J);
      \draw (J)--(K);


      \node (A1) at (12,0) {};
       \node (B1) at (13,1)  {} ;
      \node (C1) at (14,2) {};
      \node (D1) at (15,1) {};
       \node (E1) at (16,2) {};
       \node (F1) at (17,3) {};
       \node (G1) at (18,2) {};
       \node (H1) at (19,1) {};
       \node (I1) at (20,0) {};
       \node (J1) at (21,1) {};
       \node (K1) at (22,0) {};
       \draw (A1)--(B1);
      \draw (B1)--(C1);
      \draw (C1)--(D1);
      \draw (D1)--(E1);
      \draw (E1)--(F1);
      \draw (F1)--(G1);
      \draw (G1)--(H1);
      \draw (H1)--(I1);
      \draw (I1)--(J1);
      \draw (J1)--(K1);


      \node (A2) at (24,0) {};
       \node (B2) at (25,1)  {} ;
      \node (C2) at (26,0) {};
      \node (D2) at (27,1) {};
       \node (E2) at (28,2) {};
       \node (F2) at (29,3) {};
       \node (G2) at (30,2) {};
       \node (H2) at (31,1) {};
       \node (I2) at (32,2) {};
       \node (J2) at (33,1) {};
       \node (K2) at (34,0) {};
       \draw (A2)--(B2);
      \draw (B2)--(C2);
      \draw (C2)--(D2);
      \draw (D2)--(E2);
      \draw (E2)--(F2);
      \draw (F2)--(G2);
      \draw (G2)--(H2);
      \draw (H2)--(I2);
      \draw (I2)--(J2);
      \draw (J2)--(K2);


      \node (A3) at (36,0) {};
       \node (B3) at (37,1)  {} ;
      \node (C3) at (38,0) {};
      \node (D3) at (39,1) {};
       \node (E3) at (40,2) {};
       \node (F3) at (41,1) {};
       \node (G3) at (42,2) {};
       \node (H3) at (43,3) {};
       \node (I3) at (44,2) {};
       \node (J3) at (45,1) {};
       \node (K3) at (46,0) {};
       \draw (A3)--(B3);
      \draw (B3)--(C3);
      \draw (C3)--(D3);
      \draw (D3)--(E3);
      \draw (E3)--(F3);
      \draw (F3)--(G3);
      \draw (G3)--(H3);
      \draw (H3)--(I3);
      \draw (I3)--(J3);
      \draw (J3)--(K3);
       \end{tikzpicture}

\end{center}

Using  Corollary \ref{stessoschema} we have also  $\mathbf v= s^3(\mathbf 0)\wedge s^2(\mathbf 0)$, which gives rise, by the  commutativity of $\wedge$, to a total of  2 paths, including $\mathbf v$:


$s^3(\mathbf 0)\wedge s^2(\mathbf 0)$, \quad $s^2(\mathbf 0)\wedge s^3(\mathbf 0)$.

\begin{center}
\vspace{1cm}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=2pt,inner sep=0pt,radius=1pt]
      \node (A) at (13,0) {};
       \node (B) at (14,1)  {} ;
      \node (C) at (15,2) {};
      \node (D) at (16,3) {};
       \node (E) at (17,2) {};
       \node (F) at (18,1) {};
       \node (G) at (19,0) {};
       \node (H) at (20,1) {};
       \node (I) at (21,2) {};
       \node (J) at (22,1) {};
       \node (K) at (23,0) {};
       \draw (A)--(B);
      \draw (B)--(C);
      \draw (C)--(D);
      \draw (D)--(E);
      \draw (E)--(F);
      \draw (F)--(G);
      \draw (G)--(H);
      \draw (H)--(I);
      \draw (I)--(J);
      \draw (J)--(K);

      \node (A3) at (33,0) {};
       \node (B3) at (34,1)  {} ;
      \node (C3) at (35,2) {};
      \node (D3) at (36,1) {};
       \node (E3) at (37,0) {};
       \node (F3) at (38,1) {};
       \node (G3) at (39,2) {};
       \node (H3) at (40,3) {};
       \node (I3) at (41,2) {};
       \node (J3) at (42,1) {};
       \node (K3) at (43,0) {};
       \draw (A3)--(B3);
      \draw (B3)--(C3);
      \draw (C3)--(D3);
      \draw (D3)--(E3);
      \draw (E3)--(F3);
      \draw (F3)--(G3);
      \draw (G3)--(H3);
      \draw (H3)--(I3);
      \draw (I3)--(J3);
      \draw (J3)--(K3);
       \end{tikzpicture}


\end{center}


\noindent We have therefore a total of 6 paths belonging to the frame $(3,4,3,1,0,\ldots)$.
\end{example}

We wish to compute an explicit formula for the number  $p^{2n}_{\mathbf{I}}$ of paths having frame  $\mathbf{I}=(i_0,i_1,\ldots)$ with length $2n$.


\begin{definition}
  We define a {\it right frame} to be a frame of the form $$(2,i_1,i_2,i_3,\ldots)$$ and a {\it left frame} any other frame.
\end{definition}

\begin{definition}
  Given a frame $(i_0,i_1,i_2,\ldots)$, with $i_0\geq 2$, we define its {\it right progenitor} to be the frame $(2,i_1-i_0+2,i_2,\ldots)$. If the frame has $i_0=i_1=\ldots =i_{t-1}=2$ and $i_t\ne 2$   we define its {\it left progenitor} to be $(i_t,i_{t+1},\ldots)$. If $i_0\ne 2$ its left progenitor is itself.
\end{definition}

\begin{remark}
  Every frame has a right and left progenitor except for the null frame  which has only itself as a left progenitor and no right progenitor.
\end{remark}
We can prove two propositions describing how the cardinality of a frame $\mathbf{I}$ is related to the one of its progenitors.
\begin{proposition}
  The cardinality of a frame $\mathbf{I}$ is the same as that of its left progenitor.
\end{proposition}

\begin{proof}
  It is easy to see that there is a bijection between the set of paths realizing the frame $\mathbf{I}$ and those realizing the frame $s(\mathbf{I})$. Indeed, if $\mathbf p$ is a path of the frame $\mathbf{I}$ then $s(\mathbf p)$ is a path of the frame $s(\mathbf{I})$, moreover $s$ is an invertible operation. By repeatedly applying this argument we reach its left progenitor.
\end{proof}
Obviously,
\begin{lemma}\label{sega}
  The cardinality of the frame $(u+1,u,0,\ldots)$, $\forall u \in \mathbb N$, is $1$.
\end{lemma}

\begin{proposition}\label{card1}
  Given a frame of the form $\mathbf X=(2+n,a,b\ldots)$ with $n\geq 0$, let $\mathbf Y=(2,a-n,b,\ldots)$ be its right  progenitor and  $k$ the cardinality of $\mathbf Y$. Then the cardinality of $\mathbf X$ is
  $
  k\binom{a-1}{a-n-1}.
  $
\end{proposition}

  \begin{proof}
  If $b=0$, the frame $\mathbf{X}$ is of the form  $(u+1,u,0,\ldots)$ by Theorem \ref{immediate}.  The right progenitor is $(2,1,0,\ldots)$ with cardinality $k=1$ and the formula holds by Lemma \ref{sega}.
  If $b&gt;0$ then  $a\geq 2+n$, by Theorem \ref{CNES}.
There is a bijection between the set of paths realizing the frame $\mathbf X$ and the weak compositions of $n$ into $a-n$ parts. Hence the formula.
In fact, there are $a-n$  positions  in $\mathbf Y$, ($a-n-2$ feet at level 1 of the path plus the two end-points at level 0) in which one can distribute the $n$ paths $s(\mathbf 0)$,  using Proposition \ref{identita} or the commutativity property. This means that each of the $n$ ``hats'' must be located in $a-n$ positions.

In other words, any path in $\mathbf Y$ gives rise to a path in the frame $\mathbf X$ by inserting $n$ pairs $01$. These pairs may be distributed
 either at the beginning, in the order $01$, or at the end  as $10$, or in the interior  for every possible pair $12$ as $1012$.
We are left to prove that if we take two different paths $\mathbf p$ and $\mathbf p'$ in the frame $\mathbf Y$  they give rise to different paths in $\mathbf X$.
Notice that there are no 0's in the middle of the associated sequences with $\mathbf p$ and $\mathbf p'$.
In the first position where they differ, one has the pair $a, a+1$ and the other has $a,a-1$ where $a\geq 2$. If $a&gt;2$,  a pair $01$ or $10$ cannot be inserted after $a$ so the paths remain different. If $a=2$ then we have the sequence $\cdots abc21\cdots$ and $\cdots abc23\cdots$. The insertion of pairs $1,0$ or $0,1$ cannot turn these two sequences into equal ones.


  \end{proof}

With these propositions it is easy to prove (cf.~\cite{CD}):

\begin{theorem}
 Given the frame $\mathbf{I}=(i_0,i_1,\ldots,i_f,0\ldots)$, setting:

$j_1=i_0-2,j_2=i_1-i_0,j_3=i_2-i_1+i_0-2,j_4=i_3-i_2+i_1-i_0,$ and so on,
the  cardinality of $\mathbf{I}$ is

$$\binom{i_1-1}{i_1-j_1-1}\binom{i_2-1}{i_2-j_2-1} \cdots \binom{i_f-1}{i_f-j_f-1}.$$

\end{theorem}

\begin{example}
  The cardinality of the frame $\mathbf{I}=(5,8,7,3)$ is
  $$
  \binom{7}{4}\binom{6}{3}\binom{2}{0}=700.
  $$
\end{example}

\section{Colored  Dyck paths}\label{colored}
For any fixed frame  $(i_0,\ldots, i_f,\,\ldots)$ with length $2n$, let   $v_k$  denote the number of U steps joining the levels  $k$, $k+1$ ($k=0,\ldots,f-1$). This number is clearly equal to the number of the D steps joining the same two levels.



\begin{theorem}
Using the notation above, we have
 $$v_k= i_k-i_{k-1}+\cdots+(-1)^k i_0+ (-1)^{k+1},\quad k=0,\ldots,f-1.$$

\end{theorem}
\begin{proof} Since at level  0 from the first node we have a  U step, and we also have a D step in the final node, while in all the others we certainly have a U and a D, we have a total of $2(i_0-1)$ steps joining level 0 and level 1. Since there are as many U as D we must have:
$v_0=i_0-1$.
Assume we proved the formula up to  $v_{k-1}$, we prove it for  $v_k$. From the  $i_k$ nodes at level  $k$ we have  $2i_k$ steps, half of which are  U and half are D. Of these,  $2v_{k-1}$ come from the lower level. It follows that $v_k= i_k -v_{k-1} =i_k - (i_{k-1}-\cdots+(-1)^{k -1}i_0+ (-1)^{k})$, hence the result.
\end{proof}

Notice that the number $v_k$ depends only on the given frame and not on the particular path in that frame.

Let   $I_{2n}$ denote the set of frames  with length $2n$. Suppose that we can color with $u_k$ colors the  U steps joining level $k$ and level $k+1$ and with  $d_k$ colors the D steps joining the same levels ($k=0,\ldots,n-1$). The number of colored paths of a given frame  $\mathbf{I}=(i_0,i_1,\ldots)$ with length $2n$, is clearly
$p^{2n}_{\mathbf{I}}u_0^{v_0}\cdots u_{n-1}^{v_{n-1}}d_0^{v_0}\cdots d_{n-1}^{v_{n-1}}$, recalling that $p^{2n}_{\mathbf{I}}$ denotes the number of elements in the frame  $\mathbf{I}=(i_0,i_1,\ldots)$ with length $2n$. We immediately have


\begin{theorem}
 The number of Dyck paths with length  $2n$, that can be colored with  $u_k$ and $d_k$ colors from level  $k$ to level $k+1$ ($k=0,\ldots,n-1$) is
$$ \sum_{\mathbf{I} \in I_{2n}} p^{2n}_{\mathbf{I}}u_0^{v_0}\cdots u_{n-1}^{v_{n-1}}d_0^{v_0}\cdots d_{n-1}^{v_{n-1}}.$$
\end{theorem}

Notice that, the number  $v_k$ depends also on the frame $\mathbf I$. However, to explicitly indicate such a relation in the notation would make for a quite cumbersome symbol such as $v_k(p^{2n}_{\mathbf{I}})$.





\section{Colored Motzkin paths}\label{coloredMotzkin}


\begin{proposition}
  If $m^{(n)}$ is the number of Motzkin paths with length  $n$, and we set $\nu={\lfloor {\frac{n}{2}}\rfloor}$, then
  \begin{equation}\label{motzkin1}
m^{(n)}= \sum_{j=0}^{\nu}\sum_{\mathbf{I} \in  I_{2j}} p^{2j}_{\mathbf{I}} \binom{n}{n-2j}.
\end{equation}

\end{proposition}
\begin{proof}

A Motzkin path with length $n$ may be obtained from a Dyck path  $\mathbf p$ with length  $2j$, $0\le 2j\le n$, by adding  $n-2j$ horizontal steps at the feet at various levels of $\mathbf p$. If $\mathbf p$ has frame $\mathbf{I}=(i_0,\ldots)$, we may distribute the $n-2j$ horizontal steps at each of the $2j+1$ nodes of $\mathbf p$. So this can be done in as many ways as the  possibility to express  $n-2j$ as a sum of  $2j+1$  integers between  0 and $n-2j$, that is,  in $\binom{n-2j+(2j+1)-1}{n-2j}=\binom{n}{n-2j}$ ways.  The statement follows.
\end{proof}

 The $n-2j$ horizontal steps can be distributed as follows: $k_0$ steps at each of the $i_0$ nodes of level 0, $k_1$ steps  at  the $i_1$ nodes of level 1, and so on. The number of such possible arrangements are counted by weak compositions of suitable integers.  If at each level  $r$ one uses  $h_{r}$ colors on the horizontal steps and sets $\mathcal H=(h_0,\ldots, h_{\nu})$, the formula becomes
 \begin{proposition}
$$m_{\mathcal H}^{(n)}  =  \sum_{j=0}^{\nu}\sum_{\mathbf{I} \in  I_{2j}} p^{2j}_{\mathbf{I}} \sum_{k_0+\cdots +k_\nu=n-2j} \binom{k_0+ i_{0} - 1}{k_0} \cdots  \binom{k_\nu + i_{\nu} - 1}{k_\nu}h^{k_0}_{0} \cdots \!h^{k_{\nu}}_{\nu}.$$
\end{proposition}

It may happen that in the summation  corresponding to a   frame, the frame is too ``low'' to allow adding horizontal steps, for example at level $\nu$. In this case the corresponding binomial coefficient  $\binom{k_\nu+ i_{\nu} - 1}{k_\nu}$  has  $i_{\nu}=0$ and is therefore zero.

If we add to this the possibility of coloring the U and D steps with  $u_k$ and $d_k$ colors from level $k$ to level $k+1$ ($k=0,\ldots,\nu-1$),
and we set $\mathcal{U}=(u_0, \ldots, u_{\nu -1}),\mathcal{D}=(d_0, \ldots, d_{\nu -1})$,
we get

\begin{theorem} Let  $m_{\mathcal{H},\mathcal{U},\mathcal{D}}^{(n)}$ denote the number of Motzkin paths colored with colors determined by $\mathcal{H},\mathcal{U},\mathcal{D}$. Then we have
\scriptsize\begin{equation}\label{motzkin2}
  m_{\mathcal{H},\mathcal{U},\mathcal{D}}^{(n)} = \sum_{j=0}^{\nu}\sum_{\mathbf{I} \in  I_{2j}} p^{2j}_{\mathbf{I}} u_0^{v_0}\cdots u_{j-1}^{v_{j-1}}d_0^{v_0}\cdots d_{j-1}^{v_{j-1}}\sum_{\substack{k_0+\cdots +k_{\nu}\\=n-2j}}\binom{k_0+i_{0}-1}{k_0}\cdots \binom{k_{\nu}+i_{{\nu}}-1}{k_{\nu}}h^{k_0}_{0}\cdots h^{k_{\nu}}_{{\nu}}.
\end{equation}
\normalsize
\end{theorem}

Notice that such formula makes sense  if we set $h_k=0$ for all those levels $k$ where there are no horizontal steps provided we  attribute value  1 to the expression $h_j^{k_j}$, if $h_j=0$ and $k_j=0$.

\begin{remark}
Comparing formula \eqref{motzkin1} with \eqref{motzkin2} written in the case of all $h_k=u_k=d_k=1$ yields the following identity for binomial coefficients, where we made obvious changes of symbols:
$$\binom{m+{i_0}+\cdots +i_\nu -1}{m}  = \sum_{k_0+\cdots +k_\nu=m} \binom{k_0+ {i_0} - 1}{k_0} \cdots  \binom{k_\nu+ {i_\nu} - 1}{k_\nu}.$$
\end{remark}


\begin{thebibliography}{99}

\bibitem{AIG} M. Aigner, Motzkin numbers, \textit{ European J. Combin.} \textbf{19} (1998), 663--675.
\bibitem{CM1} S. Capparelli and P. Maroscia,   On two sequences of orthogonal polynomials related to  Jordan blocks, \textit{ Mediterr.\  J. Math.} \textbf{10} (2013), 1609--1630.
\bibitem{CM2} S. Capparelli and P. Maroscia,   Some results on a class of polynomials related to convolutions of the Catalan sequence, \textit{ Mediterr.\  J. Math.} \textbf{11} (2014), 255--271.
\bibitem{CD} S. Capparelli and A. Del Fra, Some results on Dyck paths and Motzkin paths, preprint, 2015.  Available at \url{http://arxiv.org/abs/1505.01961}.
\bibitem{CHI} T. S. Chihara, \textit{An Introduction to Orthogonal
Polynomials}, Gordon and Breach, 1978.
\bibitem{DEU} E. Deutsch, Dyck path enumeration, \textit{Discrete Math.} \textbf{204} (1999), 167--202.
\bibitem{FLA} P. Flajolet,  Combinatorial aspects of continued fractions, \textit{Discrete Math.} \textbf{32} (1980), 125--161.
\bibitem{KNU} D. E. Knuth, \textit{The Art of Computer Programming}, Addison-Wesley, 1973.
\bibitem{OEI} N. J. A. Sloane, \textit{The On--Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}.
\bibitem{SAV} A. Savo, Heat flow, heat content and the isoparametric property, 
preprint, 2014.  Available at
\url{http://arxiv.org/abs/1406.2835}.
\bibitem{VIE1} G. Viennot,  Une th\'eorie combinatoire des polyn\^{o}mes orthogonaux g\'en\'eraux,  \textit{Lecture Notes LACIM, UQAM, Montr\'eal}, 1984.  Available at \url{http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html}.
\bibitem{VIE} G. Viennot,  A combinatorial theory for general orthogonal polynomials with extensions and applications,
in \textit{Polyn\^omes Orthogonaux et Leurs Applications}, Lecture Notes
in Math., Vol.\ 1171, Springer, 1985, pp.\ 139--157.

\end{thebibliography}

\bigskip \hrule \bigskip

\noindent
2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A99.
\\
\noindent \emph{Keywords:}
Dyck path, Motzkin path, binomial transform.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A025235},
\seqnum{A025237},
\seqnum{A063376}, and
\seqnum{A151374}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 19 2015;
revised versions received  July 19 2015; July 27 2015.
Published in {\it Journal of Integer Sequences}, July 29 2015.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>