\documentclass[12pt]{article}
\usepackage{psfig}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}

\textheight 23cm
\textwidth 16.5cm
\topmargin -2cm
\oddsidemargin -0.5cm

\begin{document}
\title{ECO method and hill-free generalized Motzkin paths}
\author{Elena Barcucci $^*$ \and Elisa Pergola $^*$ \and  Renzo Pinzani $^*$ \and Simone Rinaldi
\thanks{Dipartimento di Sistemi e Informatica, Via Lombroso 6/17, 50134 Firenze, Italy
{ \{ \tt barcucci, elisa, pinzani, rinaldi\}@dsi.unifi.it } }}
\date{}

\maketitle

\newcommand{\qed}{\hfill\square\medskip}
\newtheorem{definizione}{Definition}
\newtheorem{osservazione}{Osservazioni}
\newtheorem{proprieta}{Propriet\`a}
\newtheorem{teorema}{Theorem}
\newtheorem{proposizione}{Proposition}
\newtheorem{esempio}{Example}
\newtheorem{lemma}{Lemma}
\newcommand{\proof}{\bf Proof.}
\newtheorem{remark}{Remark}
\newtheorem{nota}{Note}
\newtheorem{corollario}{Corollary}

\begin{abstract}
In this paper we study the class of generalized Motzkin paths with no hills
and prove some of their combinatorial properties in a bijective way; as a particular
case we have the Fine numbers, enumerating Dyck paths with no hills. Using the
ECO method, we define a recursive construction for Dyck paths such that the number of local
expansions performed on each path depends on the number of its hills. We then
extend this construction to the set of generalized Motzkin paths.
\end{abstract}

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 46 \rms (2001), Article~B46b\hfill}
\def\thepage{}
%
%

\section{Introduction} \

Let $k$ be any fixed positive integer. In the plane $\mathbb Z \times \mathbb Z$ we consider
lattice paths using three step types:
a {\em rise step} defined by $(1,1)$, a {\em fall step} defined by $(1,-1)$ and a
{\em $k$-length horizontal step} defined by $(k,0)$, and usually called $k$-horizontal step.
A {\em generalized Motzkin path} is a sequence of rise, fall and $k$-horizontal
steps, running from $(0,0)$ to $(n,0)$, and remaining weakly above the $x$-axis.
Let ${\cal M}$ be the set of generalized Motzkin paths, and  ${\cal M}_n$ the
set of these paths terminating at $(n,0)$. The classes of Motzkin, Schr\"oder and  Dyck paths
are obtained as particular cases for $k=1$, $k=2$ and $k=\infty$, respectively.
The generating function for generalized Motzkin paths according to the their length is:
\begin{equation}\label{eq}
M(x)=\sum _{n\geq 0} \left | {\cal M}_n \right | x^n = \frac{1-x^k-\sqrt{1-2x^k+x^{2k}-4x^2}}{2x^2}.
\end{equation}

A {\em hill} of a generalized Motzkin path is a pair of consecutive
rise and fall steps giving a peak of height $1$. Dyck
paths with no hills, according to the semi-length of the path, are counted
by {\em Fine numbers}: $1,0,1,2,6,18,57, \ldots $ (sequence M1624 of \cite{sloane}).
These numbers are extensively studied in the literature
\cite{de1, de2, f1, sha, shar},  as they are intimately related to Catalan numbers,
and have many combinatorial interpretations; the main results are collected
in a survey by Deutsch and Shapiro \cite{sur}. In particular, the
Fine numbers enumerate Dyck paths with the leftmost peak of
even height, ordered trees with no leaves at level $1$, ordered trees with root of even degree,
standard Young tableaux of shape $(n,n)$, without  columns
of the form
\begin{tabular}{|c|}
\hline
$k$ \\
\hline
$k+1$ \\
\hline
\end{tabular}.

\bigskip

In the first part of this work we study the class of {\em hill-free}  generalized Motzkin paths,
that is, generalized Motzkin paths with no hills, and  extend some properties already known
for Dyck paths with no hills. In particular, we bijectively prove the following linear recurrence relation:
\begin{equation}\label{eq2}
f_n=2 s_n + s_{n-2} - s_{n-k}, \qquad n>k,
\end{equation}
where $s_n$ is the number of paths of ${\cal M}_n$ with no hills and $f_n=\left | {\cal M}_n \right |$.
For $k=\infty$, (\ref{eq2}) reduces to the known, but not well-known, recurrence $f_n=2 s_n + s_{n-2}$ involving Catalan and Fine numbers.

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\small }{\small }
%
%

In Section 3 we apply the ECO method to Dyck paths. ECO (Enumerating Combinatorial Objects) \cite{Eco1} is a method
for the enumeration and the recursive construction of a class of combinatorial objects, $\cal O$, by means of an operator
$\vartheta$ which performs ``local expansions" on the objects of $\cal O$.
More precisely, let $p$ be a parameter on $\cal O$, such that $\left | {\cal O}_n \right |
= \left | \{ O\in {\cal O}:p(O)=n \} \right |$ is finite.
An operator $\vartheta$ on the class ${\cal O}$ is a function from ${\cal O}_n$ to $2^{{\cal
O}_{n+1}}$, where $2^{{\cal O}_{n+1}}$ is the power set of ${{\cal O}_{n+1}}$.

\begin{proposizione}\label{eco}
Let $\vartheta$ be an operator on $\cal O$. If $\vartheta$ satisfies the following conditions:
\begin{description}
\item[1.]  for each $O' \in {\cal O}_{n+1}$, there exists  $O\in {\cal O}_n$ such that $O'\in \vartheta (O)$,
\item [2.] for each $O,O'\in {\cal O}_n$ such that $O\neq O'$, then $\vartheta (O) \cap \vartheta(O') = \emptyset $,
\end{description}
then the family of sets ${\cal F}_{n+1}=\{ \vartheta (O): O\in {\cal O}_n \}$ is a partition of
${\cal O}_{n+1}$.
\end{proposizione}

We refer to \cite{Eco1} for further details, proofs and definitions. Once the parameter $p$ is fixed, if we are able to define an operator $\vartheta$ which satisfies
conditions $1.$ and $2.$, then Proposition \ref{eco} allows us to construct each object $O'\in
{\cal O}_{n+1}$ from an object $O\in {\cal O}_n$, and each object $O'\in {\cal O}_{n+1}$ is
obtained from one and only one $O\in {\cal O}_n$.

The recursive construction determined by $\vartheta$ can be described by a {\em generating tree} \cite{cg},
whose vertices are objects of $\cal O$. The objects having the same value of the parameter $p$
lie at the same level, and the sons of  an object are the objects it produces through $\vartheta$; the
branches that join $O$ with its sons have length $1$.  A generating tree can be described by means of a succession rule of the form:

$$
\left\{
\begin{array}{l}
(b) \\
 \\
(h) \rightsquigarrow (c_1)(c_2)\ldots (c_h),
\end{array}
\right.
$$

\noindent where $b, h, c_i \in \mathbb N$, meaning that the root object has $b$ sons, and the $h$ objects
$O'_1, \ldots ,O'_h$,
produced by an object $O$ are such that $\left | \vartheta (O'_i) \right | = c_i$, $1 \leq i \leq h$.

The construction we propose for Dyck paths is determined by an operator $\vartheta$ which
works on the set of hills of the paths. Therefore the set of paths obtained from a path $P$
through $\vartheta$ entirely depends on the number of hills of $P$.
The new succession rule defining Catalan numbers has the form:

$$
\left\{
\begin{array}{l}
(1) \\
  \\
(1) \leadsto (2) \\
  \\
(2^k) \leadsto (1)^{2^{k-1}} (2)^{2^{k-2}} (4)^{2^{k-3}} \ldots (2^{k-2})^2 (2^{k-1}) (2^{k+1}).
\end{array}
\right.
$$

In the last section we slighly extend the main concepts of ECO method, allowing the operator $\vartheta$ to produce objects of different sizes through a local expansion, that is, from
$O\in {\cal O}_n$, $\vartheta$ can produce objects in ${\cal O}_{n+i}$, $i\geq 1$.
This idea is then  suitably applied  in order to generalize the construction given in Section 3 for Dyck paths to the class of generalized Motzkin paths.

\section{Hill-free paths} \

The generating function $S(x)$ for the sequence $\{ s_n \}$ of generalized Motzkin paths with no hills is easily determined.
Indeed, all of these paths are constructed by means of the unambiguous object grammar
in Fig.1, $S$ being a generalized Motzkin path with no hills, and $\overline{M}$
a non-empty  generalized Motzkin path.

\bigskip

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=gram.eps,width=6in,clip=}}}
\caption{The object grammar generating generalized Motzkin paths with no hills.}
\end{figure}

\bigskip

Thus we have:
\begin{equation}\label{free}
S(x)=1+x^2(M(x)-1)S(x)+x^kS(x),
\end{equation}
and from (\ref{eq}), we get:
\begin{equation}
S(x)=\frac{1-x^k+2x^2-\sqrt{1-2x^k+x^{2k}-4x^2}}{2x^2(2+x^2-x^k)}.
\end{equation}
Conversely, let $M$ be a generalized Motzkin path, we have two cases:

\begin{enumerate}
\item $M$ is a hill-free path;
\item there are a hill-free path $S$ and a generalized Motzkin path $M'$, possibly empty, such that $M=Sx\bar{x}M'$,
 where $x$ and $\bar{x}$ encode rise and fall steps, respectively.
\end{enumerate}

These considerations suggest an unambiguous construction for generalized Motzkin paths, from which the following functional equation arises:
\begin{equation}\label{mo}
M(x)=S(x)+x^2M(x)S(x).
\end{equation}
From (\ref{mo}) we get:
\begin{equation}\label{sum}
M(x)= \frac{S(x)}{1-x^2S(x)} = \sum _{n\geq0} x^{2n}S^{n+1}(x).
\end{equation}
which can be combinatorially explained by observing that each term $x^{2n}S^{n+1}(x)$ in (\ref{sum})
counts the generalized Motzkin paths having exactly $n$ hills.

\begin{esempio}
Schr\"oder paths with no hills {\em are enumerated by the} small Schr\"oder numbers,
{\em  whose first terms are
$1,1,3,11,45,197,903, \ldots $ (sequence M2898 in \cite{sloane}). Let us prove the same
result by establishing a bijection $\Phi$
between the Schr\"oder paths with no hills and those having at least one hill (see Fig.2).
We recall that Schr\"oder paths are counted by} large Schr\"oder numbers, {\em $S_n$: $S_0=1$,
$S_n=2s_n$, $n>0$ (sequence M1659 in \cite{sloane}).

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=scr.eps,width=4.2in,clip=}}}
\caption{The bijection between Schr\"oder paths having at least one hill and those with no hills.}
\end{figure}

\noindent Let $R$ be a Schr\"oder path having at least one hill. We distinguish the following two cases:

\begin{enumerate}
\item the path $R$ has exactly one hill and the path begins with that hill.
Therefore $R$ can be represented as $R=x\bar{x}R'$, where $R'$ is a Schr\"oder path with no hills. The path  $\Phi(R)$ is  obtained from $R$ by
replacing its hill with a horizontal step $(2,0)$, that is, $\Phi(R)=aaR'$, where $aa$ encodes
a $2$-length horizontal step;

\item otherwise, we take into consideration the rightmost hill of $R$. Therefore, $R$
can be represented as $R'x\bar{x}R''$, where $R'$ is a not empty Sch\"roder path, and
$R''$ is a hill-free Schr\"oder path.
The path $\Phi(R)$ is obtained from $R$ by moving the rise step of the hill to the beginning of the
path, that is $\Phi(R)=xR'\bar{x}R''$ $\qed$.
\end{enumerate} }
\end{esempio}

The sequences obtained for $k=1$, $k=3$, $k=4$ are not mentioned in Sloane's Enciclopedia
of Integer Sequences \cite{sloane}:

\bigskip

\centerline{\begin{tabular}{|c|c|c|}
\hline
 & & \\
$\; k \;$ &Generating function &First terms of the sequence  \\
  & & \\
\hline
 & & \\
$\; 1 \;$ &$\frac{1-x+2x^2-\sqrt{1-2x-3x^2}}{2x^2(2-x+x^2)}$    &$1,1,1,2,5,12,29,72,183,473,1239,...$ \\
 &  & \\
$\; 2 \;$ &$\frac{1+x^2-\sqrt{1-6x^2+x^4}}{4x^2}$    &$1,0, 1, 0 , 3,0 , 11, 0, 45,0 , 197, 0, 903, 0, 4279,...$ \\
 &  & \\
$\; 3 \;$ &$\frac{1-x^3+2x^2-\sqrt{1-2x^3+x^6-4x^2}}{2x^2(2+x^2-x^3)}$ &$1,0,0,1,1,1,3,5,9,17,34,64,128,...$  \\
 &  & \\
$\; 4 \;$ &$\frac{1-x^4+2x^2+\sqrt{1-2x^4+x^8-4x^2}}{2x^2(2+x^2-x^4)}$ &$1,0,0, 0,2,0, 3,0, 12,0, 37,0, 132,0, 473,...$  \\
 &  & \\
$\; \infty \;$ &$\frac{1+2x^2-\sqrt{1-4x^2}}{4+2x^2}$    &$1,0,0,0, 1,0, 2,0, 6,0, 18,0,  57,0, 186,0, 622,...$ \\
 &  & \\
\hline
\end{tabular}}

\bigskip


For any fixed $k\in \mathbb N$ and length $n$, the set of generalized $k$-Motzkin paths  without hills is in bijection with the set of generalized $k$-Motzkin paths beginning  with a horizontal step
or having the first peak at even height. This bijection generalizes
a result holding for Dyck paths \cite{sur}.
Let $S$ be a hill-free generalized Motzkin path, the bijection $\varphi$ works as follows:

\begin{enumerate}
\item if $S$ begins  with a horizontal step or its first peak has even height, then $\varphi (S)=S$;
\item otherwise $S$ can be represented as  $S=xA\bar{x}B$, where $A$ and $B$ are
generalized $k$-Motzkin paths and
$B$ has no hills. Therefore, $\varphi(S)=Ax\bar{x}B$ is a generalized Motzkin path having the
first peak at even height (see Fig. 3).
\end{enumerate}


\noindent The function $\varphi$ can be trivially inverted.

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=even.eps,width=5.6in,clip=}}}
\caption{The bijection between hill-free paths and those whose first peak has even height.}
\end{figure}

\subsection{A linear recurrence for the number of hill-free paths} \

Equations (\ref{free}) and (\ref{mo}) yield
\begin{equation}\label{ww}
M(x)=2S(x)+x^2S(x)-x^kS(x)-1,
\end{equation}
therefore the numbers $f_n$ of generalized Motzkin paths
and $s_n$ of hill-free paths are related by the linear recurrence relation:
\begin{equation}\label{22}
f_n=2 s_n + s_{n-2} - s_{n-k}, \qquad n>k.
\end{equation}

We wish to give a proof of (\ref{22}) in a bijective way. For this purpose, we partition the paths of ${\cal M}_n$ into
the following three sets:

\begin{enumerate}
\item the first set contains the paths of ${\cal M}_n$ without hills, which are counted by
$s_n$;
\item the second set contains the paths of ${\cal M}_n$ having exactly one hill, and
beginning with such hill. These paths
can be obtained from the paths without hills of length ${n-2}$ simply by adding the initial hill.
Therefore their number is $s_{n-2}$;
\item the third set contains the remaining paths. We show that their number is
$s_n - s_{n-k}$ by establishing a bijection with the paths having no hills and not beginning with a
horizontal step; a path $S$ of such type can be represented as $S=xA\bar{x}B$,
where $A$ is a non-empty path and $B$ is a path without hills. The path $S'=Ax\bar{x}B$ has
at least one hill, but not a unique initial one (see Fig. 4).
\end{enumerate}

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=rec.eps,width=7.0in,clip=}}}
\caption{The bijection described in step 3.}
\end{figure}

\begin{esempio}
{\em The recurrence relation (\ref{22}) reduces to $f_n=2s_n-s_{n-1}+s_{n-2}$, $n>1$, for
Motzkin paths ($k=1$).
Following the previous argument, for $n=4$ we have $f_4=s_4+s_2+(s_4-s_3)$, being
$f_4=9$ and $s_4=5$, $s_3=2$, $s_2=1$. The corresponding combinatorial interpretation is
given in  Fig. 5. $\qed$}

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=ex.eps,width=6.0in,clip=}}}
\caption{A combinatorial interpretation for $f_n=2s_n-s_{n-1}+s_{n-2}$, $n>1$ for $n=4$.}
\end{figure}
\end{esempio}

\section{Eco method and hill-free Dyck paths} \

The succession rule:
\begin{equation}\label{esse}
\left\{
\begin{array}{l}
(1) \\
  \\
(1) \leadsto (2) \\
  \\
(2^h) \leadsto (1)^{2^{h-1}} (2)^{2^{h-2}} (4)^{2^{h-3}} \ldots (2^{h-2})^2 (2^{h-1}) (2^{h+1}),
\end{array}
\right.
\end{equation}
is equivalent to:
\begin{equation}
\left\{
\begin{array}{l}
(1) \\
  \\
(1) \leadsto (2) \\
   \\
(h) \leadsto (2) (3) (4) \ldots (h) (h+1),
\end{array}
\right.
\end{equation}
in the sense that the number of nodes at corresponding levels of their generating trees are Catalan numbers \cite{Eco1}. Instead of proving this equivalence by means of generating functions we show that (\ref{esse}) corresponds to a construction for Dyck paths.
Moreover,
the number $f_{n,h}$ of labels $2^h$ at level $n$ of the tree we obtain from (\ref{esse}) equals the
number of Dyck paths of length $2n$ and with exactly $h$ hills. The reader can check this property
in the following table:

\hspace{.3cm}

\centerline{\begin{tabular}{|c|c|cccccc|}
\hline
 & & & & & & & \\
$\; n \; $ &$\; C_n \;$ &$2^0$ &$2^1$ &$2^2$ &$2^3$ &$2^4$ &$2^5$ \\
 & & & & & & & \\
\hline
 & & & & & & & \\
$0$ &$1$   &$1$   &$0$   &$0$   &$0$   &$0$   &$0$   \\
$1$ &$1$   &$0$   &$1$   &$0$   &$0$   &$0$   &$0$   \\
$2$ &$2$   &$1$   &$0$   &$1$   &$0$   &$0$   &$0$   \\
$3$ &$5$   &$2$   &$2$   &$0$   &$1$   &$0$   &$0$   \\
$4$ &$14$  &$6$   &$4$   &$3$   &$0$   &$1$   &$0$   \\
$5$ &$42$  &$18$  &$13$   &$6$   &$4$   &$0$   &$1$   \\
 & & & & & & & \\
\hline
\end{tabular}}

\hspace{.3cm}

The infinite lower triangular matrix $(f_{n,h})_{n,h\geq 0}$ is a Riordan array \cite{shap}.
We recall that an infinite lower triangular matrix is called Riordan array if its
bivariate generating
function $G(t,z)=\sum f_{n,h}t^nz^h$ has the form $G(t,z)=\frac{g(z)}{1-tj(z)}$.
The Riordan array $(f_{n,h})_{n,h\geq 0}$ has been studied in \cite{sur}.
There $G(t,z)=\frac{F(z)}{1-tzF(z)}$, with $F(z)$ being the
generating function for the Fine numbers. The number sequence defined by the $i$-th column
of $(f_{n,h})_{n,h\geq 0}$ has $x^iF(z)^{i+1}$ as generating function, since
each path of length $2n$ with $i$ hills has the form
$U_0 x\bar{x} U_1 x\bar{x} U_2 \ldots U_{h-1} x\bar{x} U_i$, where
$U_j$, $0\leq j \leq i$ is a hill-free path.

Since the number of nodes having label $(2^h)$ at level $n$ in the generating tree obtained
through
(\ref{esse}) is equal to the number of Dyck paths having length $2n$
and exactly $h$ hills, then
it is possible to use ECO method and determine an operator $\vartheta _D$ which
satisfies Proposition \ref{eco} and produces $2^h$ Dyck paths from a path having $h$ hills,
such that:

\begin{description}
\item[-] only one path has $h+1$ hills;
\item[-] for each $j=1, \ldots , h$,  there are exactly $2^{j-1}$ paths, having $h-j$ hills,
\end{description}

\noindent according to the succession rule (\ref{esse}).
In order to determine such a construction, let $D$ be a Dyck path of length $2n$ and $h$ hills.
We can represent it as

$$ D=U_0c_1U_1c_2U_2 \ldots U_{h-2}c_{h-1}U_{h-1}c_hU_h, $$

\noindent where $c_i=x\bar{x}$ denotes the
$i$-th hill and $U_j$ is a hill-free Dyck path. The operator $\vartheta _D$ works on $D$
and produces $2^{h}$ paths of length $2(n+1)$ in the following way (see Fig.6):

\begin{enumerate}
\item one Dyck path with $h+1$ hills is obtained from $D$ by adding a hill at its end.
\item $2^{j-1}$ paths with $h-j$ hills, $j=1, \ldots , h$ are obtained as
described below, in agreement with the fact that there are $2^{j-1}$ combinations
from a set of $j-1$ elements, i.e.,
$$ 2^{j-1}=\sum _{i=0}^{j-1} {{j-1} \choose i}.$$

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=eco.eps,width=3.1in,clip=}}}
\caption{The operator $\vartheta _D$ applied to a path with three hills, according to
$(2^3)\leadsto (1)(1)(1)(1)(2)(2)(2^2)(2^4)$}
\end{figure}

Let $j$ be fixed. We take into consideration the $(h-j+1)$-th hill, we add a rise
step before $c_{h-j+1}$, and a fall step at the end of $D$, thus obtaining a Dyck path $D'$ of
length $2(n+1)$ with $h-j$ hills:
$$D'=U_0c_1U_1c_2U_2 \ldots U_{h-j}xc_{h-j+1}U_{h-j+1} \ldots c_hU_h\bar{x}.$$
For each $i=0, \ldots ,j-1$, we consider the $\left( \begin{array}{c} {j-1} \\ i \end{array}\right)$
combinations of the $j-1$ hills
on the right of $c_{h-j+1}$, and, for each combination, say $c_{l_1}, \ldots , c_{l_i}$,
$h-j < l_1 < \ldots < l_i \leq h$ we modify the path $D'$ by adding $i$ rise steps before
$c_{h-j+1}$, and replacing each $c_{l_r}$, $r=1, \ldots ,i$, with a fall step.
The path we obtain has $h-j$ hills, and its form is:

$$ U_0c_1U_1c_2U_2 \ldots U_{h-j}x^{i+1} c_{h-j+1}U_{h-j+1}
\ldots U_{l_1-1}\bar{x} \ldots U_{l_i-1}\bar{x} \ldots c_hU_h\bar{x}. $$
\end{enumerate}

It is easy to verify that $\vartheta _D$ satisfies Proposition \ref{eco}, and then
it recursively constructs Dyck paths of length $2(n+1)$, starting from those
of length $2n$.

\section{A construction for generalized Motzkin paths} \

In this section we extend the ECO method in order to obtain a construction for generalized
Motzkin paths basing on the same method explained in the previous section. Let $\cal O$ be a class of combinatorial
objects, and $r$ and $s$, $s \leq r$,  positive integers. Let $\vartheta _r$, $\vartheta _s$ be two operators
on $\cal O$:

$$\vartheta _s : {\cal O}_n \to 2^{{\cal O}_{n+s}}, \qquad \qquad  \vartheta _r : {\cal O}_n \to 2^{{\cal O}_{n+r}}, $$

\noindent and:

$$ \forall O,O'\in {\cal O}_n, \; \; O\neq O' \qquad \vartheta _s(O) \cap \vartheta _s(O') = \emptyset , \qquad \vartheta _r(O) \cap \vartheta_r (O') = \emptyset . $$

\noindent Moreover, let $\vartheta$ be an operator on $\cal O$:

$$\vartheta : {\cal O}_n \to 2^{{\cal O}_{n+s}\cup {\cal O}_{n+r}} . $$

\noindent We say that $\vartheta$ is the {\em direct sum} of $\vartheta _s$ and $\vartheta _r$,
and write $ \vartheta = \vartheta _s \oplus \vartheta _r$, if

\begin{enumerate}
\item $\forall O \in {\cal O}_n$, $\vartheta (O)= \vartheta _s(O) \cup \vartheta _r(O)$;
\item $\forall O \in {\cal O}_n$, $\vartheta _s(O) \cap \vartheta _r(O) = \emptyset$;
\item $\forall O \in {\cal O}_{n-r}, \; \forall O' \in {\cal O}_{n-s}$, $\vartheta _r (O) \cap \vartheta _s (O') =
 \emptyset$.
\end{enumerate}

\noindent If the above conditions are satisfied, and

$$ \forall O' \in  {\cal O}_n \qquad \exists O\in  {\cal O}_{n-r}\cup  {\cal O}_{n-s} \mbox{ such that } O'\in \vartheta
 (O) \qquad n> r, $$

\noindent then the set

$$ \{ \vartheta _s (O), \vartheta _r (O'): O\in {\cal O}_{n-s}, O'\in {\cal O}_{n-r} \}, \qquad n\geq r , $$

\noindent is a partition of ${\cal O}_n$. The {\em generating tree} associated to $\vartheta _s \oplus
\vartheta _r$ is a rooted tree whose edges can have length  $s$ or $r$. The {\em level} $l(N)$ of a
node $N$ in the generating tree is defined as follows:

\begin{enumerate}
\item $l(N)=0$, if $N$ is the root of the tree;
\item otherwise, let $F$ be the father of $N$, in the tree, and $w$ be the length of the branch joininig $F$ to $N$: then $l(N)=l(F)+w$.
\end{enumerate}

In this generating tree the objects having the same value of the parameter lie at the same level, and the sons of each node at level $n$ are the objects it produces through $\vartheta _s$
(lying on level $n+s$), and the ones it produces through $\vartheta _r$ (lying on level $n+r$).
Therefore a succession rule describing that generating tree has the form:

\begin{eqnarray}
\left\{ \begin{array}{lll}
(b) & & \\
    & & \\
(h) &\stackrel{s}{\rightsquigarrow} &(e_{1}(h))\ldots (e_{g}(h))\\
    & & \\
    &\stackrel{r}{\rightsquigarrow} &(e_{g+1}(h))\ldots (e_{h}(h)).
\end{array} \right.
\end{eqnarray}

Such a  succession rule defines a number sequence $\{ f_n \} _n$, $f_n$ being   the total number of nodes at level $n$ in the associated generating tree.

\bigskip

Let us consider the following succession rule:

\begin{eqnarray}\label{stork}
\Omega _k \left\{ \begin{array}{lll}
(2) & & \\
 & & \\
(2^h) &\stackrel{2}{\rightsquigarrow}  &(2)^{2^{h-2}} (4)^{2^{h-3}} (8)^{2^{h-4}} \ldots (2^{h-2})^2 (2^{h-1}) (2^{h+1})\\
 &  & \\
      &\stackrel{k}{\rightsquigarrow}  &(2)^{2^{h-2}} (4)^{2^{h-3}} (8)^{2^{h-4}} \ldots (2^{h-2})^2 (2^{h-1}) (2^{h}).
\end{array} \right.
\end{eqnarray}

Figure \ref{motzkin} shows the first levels of the generating tree associated to the succession rule $\Omega _1$, which gives the Motzkin numbers.

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=motzkin.eps,width=3in,clip=}}}
\caption{The first levels of the generating tree associated to $\Omega _1$.}
\label{motzkin}
\end{figure}

We define an ECO operator $\vartheta$ which constructs generalized Motzkin paths according to their length, and follows the succession rule $\Omega _k$. Each path having exactly $h$ hills produces  exactly $2^{h+1}$ paths through $\vartheta$. As a neat consequence of this fact we have a combinatorial proof that the
number of labels $2^{h+1}$, $h\geq 0$, at level $n$ in the generating tree associated to $\Omega _k$ is equal to the number of generalized Motzkin paths of length $n$ with exactly $h$ hills. The operator

$$ \vartheta : {\cal O}_n \to 2^{{\cal O}_{n+2}\cup {\cal O}_{n+k}}, $$

\noindent is the direct sum of two ECO operators:

$$ \vartheta : \vartheta _D \oplus \vartheta _k. $$

The first operator, namely $\vartheta _D$, works on Motzkin paths exactly like the operator defined in the previous
section for Dyck paths, however, now with edges of length 2. More precisely, if $M$ is a generalized Motzkin path of length $n$ having exactly
$h$ hills, then $\vartheta _D (M) $ is a set of $2^h$ paths of length $n+2$. On the other side, $\vartheta _k(M)$ is
a set of $2^h$ paths of length $n+k$, such that:

\begin{enumerate}
\item one path is obtained from $M$ by adding a horizontal step at the end of $M$;
\item for $j=1, \ldots , h$ we consider the $(h-j)$-th hill of $M$, namely $c_{h-j+1}$:

$$ M= U_0 c_1 U_1 c_2 \ldots U_{h-j} c_{h-j+1} U_{h-j+1} \ldots c_h U_h, $$

\noindent where the $U_i$ are hill-free paths, and the $c_i$ are hills.
We add a rise step before $c_{h-j+1}$ and a fall step at the end of the path, then replace $c_{h-j+1}$ with a
horizontal step. The $(n+k)$-length obtained path, which we call $M'$, has exactly $h-j$ hills.

$$ M'= U_0 c_1 U_1 c_2 \ldots U_{h-j} x a^k U_{h-j+1} \ldots c_h U_h \bar{x} ,$$

\noindent where $a^k$ encodes the horizontal step. For $i=0,1, \ldots ,j-1$, we
consider the $j-1$ hills (i.e., $x\bar{x}$ pairs that were hills on $M$) on the right of the added horizontal step. For each of these combinations, say

$$ c_{l_1}, \ldots , c_{l_i}, \qquad h-j < l_1 < \ldots < l_i \leq h ,$$

\noindent we have a path, obtained from $M'$ by adding $i$ rise steps before the added horizontal step, and replacing
each $c_{l_t}$, $t=1, \ldots ,i$ with a fall step:

$$ U_0 c_1 U_1 c_2 \ldots U_{h-j} x^{i+1} e^k U_{h-j+1} \ldots \bar{x} U_{l_1} \ldots \bar{x} U_{l_1} \ldots c_h U_h
\bar{x}. $$

\noindent Performing these operations, each $j$ gives

$$ \sum _{i=0} ^{j-1} {{j-1} \choose i} = 2^{j-1} $$

\noindent paths, each of them having $h-j$ hills.
\end{enumerate}

Figure \ref{gen} shows the application of $\vartheta $ to a path having two hills, $k=3$.

\begin{figure}[htb]
\centerline{\hbox{\psfig{figure=ecogen.eps,width=6in,clip=}}}
\caption{The application of $\vartheta$ to a path having $2$ hills, $k=3$.}
\label{gen}
\end{figure}


\begin{esempio}\label{hhhi}
{\em For $k=1$, we have the succession rule:

\begin{eqnarray}\label{441}
\left\{ \begin{array}{lll}
(2) & &  \\
    &  & \\
(2^h)  &\stackrel{1}{\rightsquigarrow}  &(2)^{2^{h-2}} (4)^{2^{h-3}} (8)^{2^{h-4}} \ldots (2^{h-2})^2 (2^{h-1}) (2^{h}) \\
    & & \\
    &\stackrel{2}{\rightsquigarrow}  &(2)^{2^{h-2}} (4)^{2^{h-3}} (8)^{2^{h-4}} \ldots (2^{h-2})^2 (2^{h-1}) (2^{h+1})
\end{array} \right.
\end{eqnarray}


\noindent defining the Motzkin numbers. Let $f_{n,h}$ be the number
of nodes having label $(2^{h})$ at level $n$ in the generating tree of the rule in
(\ref{441}). The array $(f_{n,h})_{n,h\geq 0}$, is a Riordan array:

\bigskip

\centerline{\begin{tabular}{|c|cccc|}
\hline
 & & &  &  \\
$\; n \:$  &$2^1$ &$2^2$ &$2^3$ &$2^4$ \\
 & & & &  \\
\hline
 & &  & & \\
$1$   &$1$   &$0$   &$0$   &$0$         \\
$2$   &$1$   &$0$   &$0$   &$0$         \\
$3$   &$1$   &$1$   &$0$   &$0$         \\
$4$   &$2$   &$2$   &$0$   &$0$        \\
$5$   &$5$   &$3$   &$1$   &$0$       \\
$6$   &$12$   &$6$  &$3$   &$0$       \\
 & & & &  \\
\hline
\end{tabular}}

\bigskip

The number of labels $(2^{h+1})$ at level $n$
is the number of Motzkin paths having length $n$ and exactly $h$ hills. $\qed$}
\end{esempio}

\begin{esempio}
{\em For $k=2$, the succession rule form (\ref{stork}) simplifies to:
\begin{equation}\label{44}
\left\{
\begin{array}{l}
(2) \\
   \\
(2^h) \leadsto (2)^{2^{h-1}} (4)^{2^{h-2}} (8)^{2^{h-3}} \ldots (2^{h-1})^2 (2^{h}) (2^{h+1}),
\end{array}
\right.
\end{equation}
defining the Schr\"oder numbers.
As in Example \ref{hhhi}, let $f_{n,h}$ be the number
of nodes having label $(2^{h})$ at level $n$ in the generating tree of the rule in
(\ref{44}). The array $(f_{n,h})_{n,h\geq 0}$, is a Riordan array:

\bigskip

\centerline{\begin{tabular}{|c|ccccc|}
\hline
 & & &  & & \\
$\; n \:$  &$2^1$ &$2^2$ &$2^3$ &$2^4$ &$2^5$ \\
 & & & &  & \\
\hline
 & &  & & & \\
$1$   &$1$   &$0$   &$0$   &$0$   &$0$      \\
$2$   &$1$   &$1$   &$0$   &$0$   &$0$      \\
$3$   &$3$   &$2$   &$1$   &$0$   &$0$      \\
$4$   &$11$   &$7$   &$3$   &$1$   &$0$     \\
$5$   &$45$   &$28$   &$12$  &$4$   &$1$    \\
 & & & & & \\
\hline
\end{tabular}}

\bigskip

The number of labels $(2^{h+1})$ at level $n$
is the number of Schr\"oder paths having length $2n$ and exactly $h$ hills. $\qed$}
\end{esempio}



\begin{esempio}
{\em For $k=4$, we have the succession rule:

\begin{eqnarray}\label{442}
\left\{ \begin{array}{lll}
(2) & &  \\
 &  & \\
(2^h) &\stackrel{2}{\rightsquigarrow}  &(2)^{2^{h-2}} (4)^{2^{h-3}} (8)^{2^{h-4}} \ldots (2^{h-2})^2 (2^{h-1})
 (2^{h+1}) \\
    &  & \\
&\stackrel{1}{\rightsquigarrow}  &(2)^{2^{h-2}} (4)^{2^{h-3}} (8)^{2^{h-4}} \ldots (2^{h-2})^2 (2^{h-1}) (2^{h}) \\
\end{array} \right.
\end{eqnarray}

\noindent
Let us now fill up a table with the numbers $f_{n,h}$, where as usual  $f_{n,h}$ denotes the number
of nodes having label $(2^{h})$ at level $n$ in the generating tree of this rule.
The array $(f_{n,h})_{n,h\geq 0}$, is again a Riordan array:

\bigskip

\centerline{\begin{tabular}{|c|ccccc|}
\hline
 & & &  & & \\
$\; n \:$  &$2^1$ &$2^2$ &$2^3$ &$2^4$ &$2^5$ \\
 & & & &  & \\
\hline
 & &  & & & \\
$1$   &$1$   &$0$   &$0$   &$0$   &$0$      \\
$2$   &$0$   &$0$   &$0$   &$0$   &$0$      \\
$3$   &$0$   &$1$   &$0$   &$0$   &$0$      \\
$4$   &$1$   &$0$   &$0$   &$0$   &$0$     \\
$5$   &$1$   &$0$   &$1$   &$0$   &$0$    \\
$6$   &$1$   &$2$   &$0$   &$0$   &$0$    \\
$7$   &$3$   &$2$   &$0$   &$1$   &$0$    \\
$8$   &$5$   &$2$   &$2$   &$0$   &$0$    \\
 & & & & & \\
\hline
\end{tabular}}

\bigskip

}
\end{esempio}


\begin{thebibliography}{11}
\bibliographystyle{plain}

\bibitem{Eco1}
E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani,
\newblock {\rm ECO: a methodology for the Enumeration of Combinatorial Objects,}
\newblock {\it Journal of Difference Equations and Applications,} Vol.5 (1999) 435-490.


\bibitem{cg}
F. R. K. Chung,  R. L. Graham, V. E. Hoggatt, M. Kleimann,
\newblock {\rm The number of Baxter permutations},
\newblock {\it Journal of Combinatorial Theory Ser. A,  } 24  (1978) 382-394.

\bibitem{de1}
E. Deutsch,
\newblock {\rm An involution on Dyck paths and its consequences},
\newblock {\it Discrete Mathematics,} 204 (1999) 163-166.


\bibitem{de2}
E. Deutsch,
\newblock {\rm Dyck path enumeration},
\newblock {\it Discrete Mathematics, } 204 (1999) 167-202.


\bibitem{sur}
E. Deutsch, L. Shapiro,
\newblock {\rm A survey of the Fine numbers},
\newblock (preprint).

\bibitem{f1}
T. Fine,
\newblock {\rm Extrapolation when very little is known about the source},
\newblock {\it Inform. and Control,  } 16  (1970) 331-359.

\bibitem{sha}
D. G. Rogers, L. Shapiro,
\newblock {\rm Deques, trees and lattice paths,}
\newblock {\it Lecture Notes in Mathematics,} Vol.884, Springer-Verlag, New York Heidelberg Berlin (1981)
293-303.

\bibitem{shar}
L. Shapiro,
\newblock {\rm A Catalan triangle,}
\newblock {\it Discrete Mathemathics,} 14 (1976) 83-90.

\bibitem{shap}
L. Shapiro,
S. Getu, W-J. Woan, L. C. Woodson,
\newblock {\rm The Riordan group,}
\newblock {\it Discrete Applied Mathemathics,} 34 (1991) 229-239.


\bibitem{sloane}
N. J. A. Sloane, S. Plouffe,
\newblock {\it The Encyclopedia of Integer Sequences,}
\newblock {\rm Academic Press,} New York (1995).

\end{thebibliography}
\end{document}