\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&u_0&0&0&0&0&\ldots\\ d_0&h_1&u_1&0&0&0&\ldots\\ 0&d_1&h_2&u_2&0&0&\ldots\\ 0&0&d_2&h_3&u_3&0&\ldots\\ \ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\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&u_0d_0&0&0&0&0&\ldots\\ 1&h_1&u_1d_1&0&0&0&\ldots\\ 0&1&h_2&u_2d_2&0&0&\ldots\\ 0&0&1&h_3&u_3d_3&0&\ldots\\ \ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\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&u&0&0&0&0&\ldots\\ 1&h&u&0&0&0&\ldots\\ 0&1&h&u&0&0&\ldots\\ 0&0&1&h&u&0&\ldots\\ \ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\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}&1&0&\cdots &0\\ a_{20}&a_{21}&1&\cdots &0\\ \cdots&\cdots&\cdots&\ddots&\cdots\\ a_{n-1,0}&a_{n-1,1}&a_{n-1,2}&\cdots&1\\ a_{n0}&a_{n1}&a_{n2}&\cdots&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}&=-ua_{n-2,0}-ha_{n-1,0}\\ a_{n1}&=-ua_{n-2,1}+a_{n-1,0}-ha_{n-1,1}\\ a_{n2}&=-ua_{n-2,2}+a_{n-1,1}-ha_{n-1,2}\\ &\vdots\\ a_{n,n-2}&=-ua_{n-2,n-2}+a_{n-1,n-3}-ha_{n-1,n-2}\\ a_{n,n-1}&=a_{n-1,n-2}-h\\ a_{nn}&=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} &a_{n,0}=-ua_{n-2,0}-ha_{n-1,0}\\ &= -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}\\ &=\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}\\ &=(-1)^{n}\binom{n}{0}h^{n}+\sum_{j\geq 1} (-1)^{n-j}\binom{n-j}{j}h^{n-2j}u^{j}\\ &=\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}&=-ua_{n-2,t}+a_{n-1,t-1}-ha_{n-1,t}\\ &=-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}\\ &+\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}\\ &-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} &=\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}\\ &+\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}\\ &+\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} &=\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}\\ &+\sum_{j\geq 1} (-1)^{n-t-j}\binom{n-1-j}{j+t}\binom{j+t}{t}h^{n-t-2j}u^{j}\\ &+ (-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} &=(-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}\\ &=\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}&=-h+a_{n-1,n-2}\\ &=-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&u_0&0&0&\ldots\\ d_0&h_1+1&u_1&0&\ldots\\ 0&d_1&h_2+1&u_2&\ldots\\ 0&0&d_2&h_3+1&\ldots\\ \vdots&\vdots&\vdots&\vdots&\ddots& \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)&\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>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>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>0$; \item $i_1-i_0\geq 0$ provided $f>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}> 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 $(00$ 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>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}