<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{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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Animals and 2-Motzkin Paths
}
\vskip 1cm
\large
Wen-jin Woan\footnote{Author's current address:
2103 Opal Ridge, Vista, CA 92081, USA.}\\
Department of Mathematics\\
Howard University\\
Washington, DC 20059 \\
USA\\
\href{mailto:wwoan@howard.edu}{\tt wwoan@howard.edu} \\
\end{center}

\vskip .4in

\begin{abstract}
We consider an animal $S$ as a set of points in the coordinate
plane that are reachable from the origin $(0,0)$ through points in $S$ by
steps from $\{(1,0),(0,1),(1,1),(-1,-1)\}$. In this paper, we give a
combinatorial bijection with 2-Motzkin paths, i.e., the Motzkin paths with
two different horizontal steps. 
\end{abstract}


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


%\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage[usenames]{color}
%\usepackage{graphicx}
%\usepackage{amscd}
%\usepackage{amsthm}
%\usepackage[colorlinks=true,linkcolor=webgreen,filecolor=webbrown, citecolor=webgreen]{hyperref}
%\usepackage{color}
%\usepackage{fullpage}
%\usepackage{float}
%\usepackage{psfig}
%\usepackage{graphics,amsmath,amssymb}
%\usepackage{latexsym}
%\usepackage{epsf}

%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{algorithm}[theorem]{Algorithm}

\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{remar}[theorem]{Remark}
\newenvironment{remark}{\begin{remar}\normalfont\quad}{\end{remar}}
\newtheorem{algo}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{algo}\normalfont\quad}{\end{algo}}



%\theoremstyle{definition}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
%\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
%\begin{document}


\section{Introduction}

We start by dividing the plane into eight equal octants. In this paper we
count animals $A_i,$ $1\leq i\leq 3,$ in the first $i$ octants . The count
of $A_1$ was first done by Gouyou-Beauchamps and Viennot \cite{GV} and the
idea of classifying it by the number of points lying on the $x$-axis is due
to Aigner \cite{A}. Bousquet-Melou \cite{B} includes the possibility of
diagonal steps, which changes the count of $A_3$ from $3^n$ to $4^n,$ and
that is the case we will consider here. In Theorems~\ref{theorem8},
\ref{theorem13}, and \ref{theorem18}
we give a bijection between animals and 2-Motzkin paths. For
definitions and references, see Stanley \cite{S}.

\begin{definition}
An \textbf{animal} $S$ is a set of points in the $xy$-plane with integer
coordinates that satisfy the following conditions:
\end{definition}

\ 1.$\;(0,0)\in S,$

\ 2.$\;$if$\;(a,b)\in S\;$and$\;b\neq -a,\;$let $C(a,b):=%
\{(a-1,b),(a,b-1),(a-1,b-1)\},$ then$\;C(a,b)\cap \;S$ $\neq \emptyset ,$

\ 3. if $(0,0)\neq (-b,b)\in S,$ then$\;(-(b-1),(b-1))\in S.$

For $A_1\;$we require also that $0\leq b\leq a,\;$i.e., the first octant. For
$A_2$\ we want $0\leq a,b,$ i.e., the first quadrant or the first two
octants. Then $A_3\;$is defined by $0\leq b\;$and $a+b\geq 0,$ i.e., the
first three octants.

\begin{definition}
We start with partial Motzkin paths beginning at $(0,0)$ with steps from $%
\{U=(1,1)$, $D=(1,-1)$, $H=(1,0)\}.$ Then bicoloring the horizontal steps we
have partial 2-Motzkin paths with steps from $\{U=(1,1)$, $D=(1,-1)$, $%
H_r=(1,0)$ and $H_g=(1,0)\},$ where $H_r\;$is a horizontal step colored red
and where $H_g\;$is a horizontal step colored green. Let $M(n)=M_3(n)$ be
the set of all partial 2-Motzkin paths of $n\;$steps, let $M_2(n)\subset
M_3(n)$ be the set of paths that never go below the $x$-axis and let $%
M_1(n)\subset M_2(n)$ denote the set of paths that end on $x$-axis at $(n,0)$
and let $m_i(n)=\left| M_i(n)\right| $ and $m_i(n,k)=\left| M_i(n,k)\right|$,
where $M_i(n,k)$\ is the set of partial 2-Motzkin paths that
end at $(n,k).$
\end{definition}

For $m,k\leq 6,$ the entries $\ (m_3(n,k))$ and $(m_2(n,k))$ are as follows:

\[
\ (m_3(n,k))=\left[
\begin{array}{cccccccccccc}
n/k &amp; -5 &amp; -4 &amp; -3 &amp; -2 &amp; -1 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 4 &amp; 6 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 0 &amp; 0 &amp; 1 &amp; 6 &amp; 15 &amp; 20 &amp; 15 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 0 &amp; 1 &amp; 8 &amp; 28 &amp; 56 &amp; 70 &amp; 56 &amp; 28 &amp; 8 &amp; 1 &amp; 0 \\
5 &amp; 1 &amp; 10 &amp; 45 &amp; 120 &amp; 210 &amp; 252 &amp; 210 &amp; 120 &amp; 45 &amp; 10 &amp; 1
\end{array}
\right] ,
\]

\begin{center}
\[
(m_2(n,k))=\left[ \
\begin{array}{ccccccc}
n/k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 5 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 14 &amp; 14 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 42 &amp; 48 &amp; 27 &amp; 8 &amp; 1 &amp; 0 \\
5 &amp; 132 &amp; 165 &amp; 110 &amp; 44 &amp; 10 &amp; 1
\end{array}
\right] .
\]
\end{center}

Let $A(n)$ be the set of all animals of size $n=\left| S-\{(0,0)\}\right| ,$
i.e., we do not count the origin $(0,0)$ for the size. Let $A_i(n)$ be the
set of animals in the first $i$ octants of size $n$ and $a_i(n)=\left|
A_i(n)\right| $ be the number of elements. We shall construct a bijection
between $A_i(n)$ and $M_i(n)$.

\bigskip

\begin{example}
For $n=2$, we illustrate the $5$ elements in $A_1(2),$ and their
counterparts in $M_1(2)$; $\times \;$ marks source points on the line $y=-x.$
Note that the lowest source point is the origin, $(0,0)$.\
\end{example}

\[
\frame{%
\begin{tabular}{lll}
$\times $ &amp; $\bullet $ &amp; $\bullet $%
\end{tabular}
}\rightarrow H_rH_r,\frame{%
\begin{tabular}{ll}
&amp; $\bullet $ \\
$\times $ &amp; $\bullet $%
\end{tabular}
}\rightarrow UD,\frame{%
\begin{tabular}{lll}
&amp;  &amp; $\bullet $ \\
$\times $ &amp; $\bullet $ &amp;
\end{tabular}
}\rightarrow H_rH_g,
\]
\

\[
\frame{%
\begin{tabular}{lll}
&amp; $\bullet $ &amp; $\bullet $ \\
$\times $ &amp;  &amp;
\end{tabular}
}\rightarrow H_gH_r,\frame{%
\begin{tabular}{lll}
&amp;  &amp; $\bullet $ \\
&amp; $\bullet $ &amp;  \\
$\times $ &amp;  &amp;
\end{tabular}
}\rightarrow H_gH_g.
\]
\

Both $A_2(2)$ and $M_2(2)$ have 10 elements. The following $5$ elements are
those not in $A_1(2)$:

\[
\frame{%
\begin{tabular}{ll}
&amp; $\bullet $ \\
&amp; $\bullet $ \\
$\times $ &amp;
\end{tabular}
}\rightarrow H_gU,\frame{%
\begin{tabular}{ll}
$\bullet $ &amp;  \\
$\times $ &amp; $\bullet $%
\end{tabular}
}\rightarrow H_rU,\frame{%
\begin{tabular}{ll}
$\bullet $ &amp; $\bullet $ \\
$\times $ &amp;
\end{tabular}
}\rightarrow UH_r\
\]

\[
\frame{%
\begin{tabular}{ll}
&amp; $\bullet $ \\
$\bullet $ &amp;  \\
$\times $ &amp;
\end{tabular}
}\rightarrow UH_g,\frame{%
\begin{tabular}{l}
$\bullet $ \\
$\bullet $ \\
$\times $%
\end{tabular}
}\rightarrow UU.
\]
\

We have 16 elements in $A_3(2),M_3(2).$ The following $6$ elements are those
not in $A_2(2)$\

\[
\frame{%
\begin{tabular}{lll}
&amp;  &amp;  \\
$\times $ &amp;  &amp;  \\
&amp; $\times $ &amp; $\bullet $%
\end{tabular}
}\rightarrow H_rD,\frame{%
\begin{tabular}{ll}
&amp;  \\
$\times $ &amp; $\bullet $ \\
&amp; $\times $%
\end{tabular}
}\rightarrow DH_r,\frame{%
\begin{tabular}{lll}
&amp;  &amp;  \\
$\times $ &amp;  &amp; $\bullet $ \\
&amp; $\times $ &amp;
\end{tabular}
}\rightarrow H_gD,\
\]

\[
\frame{%
\begin{tabular}{ll}
&amp; $\bullet $ \\
$\times $ &amp;  \\
&amp; $\times $%
\end{tabular}
}\rightarrow DH_g,\frame{%
\begin{tabular}{ll}
$\bullet $ &amp;  \\
$\times $ &amp;  \\
&amp; $\times $%
\end{tabular}
}\rightarrow DU,\frame{%
\begin{tabular}{lll}
$\times $ &amp;  &amp;  \\
&amp; $\times $ &amp;  \\
&amp;  &amp; $\times $%
\end{tabular}
}\rightarrow DD.\
\]

\begin{algorithm}
We describe
a decomposition method of an animal into two smaller parts, the top $%
T$ and the bottom $B$. The bottom part is an animal while the top part will
be an animal after we apply Algorithm 5. Let $S$ be an animal and start the
partition path at $P_S(a_0,a_0)$ at a point $(a_0,a_0)$ with the least 
$a_0&gt;0$.  If $(a_i,b_i)\in S$,  go $E=(1,0)$ one unit; otherwise go diagonally
$D=(1,1)$ one unit.  Keep going until there are no more points in $S$ with
larger first coordinate than this point. Let $T\subset S$ be the set of
points on or above the path and let $B\subset S$ denote the set of points
below the path.
\end{algorithm}

\begin{algorithm}
Let us define $T(i)\;$inductively: $T(1)=T$, and $T(i+1)$ is constructed from
$T(i)$ by replacing each $(a,b)\in T(i)$ with $(a-1,b-1)$ whenever 
$C(a,b)\cap T(i)=\emptyset $ and $a,b&gt;0$. Continue until $T(i+1)=T(i)=T^{^{%
\prime }}$.
\end{algorithm}

\bigskip

\begin{example}
For the following example $S$, we start with $(2,2)$ and by Algorithm 4 the
partition path of $S$ is $P=EEDEEDE,\ $i.e., $(2,2)\rightarrow
(3,2)\rightarrow (4,2)\rightarrow (5,3)\rightarrow (6,3)\rightarrow
(7,3)\rightarrow (8,4)\rightarrow (9,4),$
\end{example}

\[
\ S=\frame{%
\begin{tabular}{lllllllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 6$ &amp; $\circ 7$ \\
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 3$ &amp; $\circ 5$ &amp;  &amp;  \\
&amp;  &amp; $\circ 1$ &amp; $\circ 2$ &amp;  &amp; $\bullet $ &amp;  &amp;  &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
},
\]

The partition path partitions $S$ into $B,T$ 
as follows:

\[
B=\frame{%
\begin{tabular}{lllllllll}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp; $\bullet $ &amp;  &amp;  &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
},
\]

\[
T=\frame{%
\begin{tabular}{lllllllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 6$ &amp; $\circ 7$ \\
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 3$ &amp; $\circ 5$ &amp;  &amp;  \\
&amp;  &amp; $\circ 1$ &amp; $\circ 2$ &amp;  &amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\
$\times $ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
},
\]

Applying Algorithm 5 on $T$, we have
\[
T^{^{^{\prime }}}=\ \ \frame{%
\begin{tabular}{llllll}
&amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 6$ &amp; $\circ 7$ \\
$\circ 1$ &amp; $\circ 2$ &amp; $\circ 3$ &amp; $\circ 5$ &amp;  &amp;
\end{tabular}
}.
\]

\section{Animals $A_1(m)$ and 2-Motzkin Paths $M_1(m)$}

Here we construct a bijection between animals and 2-Motzkin paths.
For other bijections and partitions, see \cite{BL,BR}.

\bigskip

\begin{example}
For $m=1,$ $2$. $A_1(m)\Leftrightarrow M_1(m)$\
\end{example}

\[
\frame{%
\begin{tabular}{ll}
&amp;  \\
$\times $ &amp; $\bullet $%
\end{tabular}
}\rightarrow H_r,\ \frame{\
\begin{tabular}{ll}
&amp; $\bullet $ \\
$\times $ &amp;
\end{tabular}
}\rightarrow H_g\ ,
\]

\[
\frame{%
\begin{tabular}{lll}
&amp;  &amp;  \\
&amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp; $\bullet $%
\end{tabular}
}\rightarrow H_rH_r,\frame{%
\begin{tabular}{lll}
&amp;  &amp;  \\
&amp;  &amp; $\bullet $ \\
$\times $ &amp; $\bullet $ &amp;
\end{tabular}
}\ \rightarrow H_rH_g,\frame{%
\begin{tabular}{lll}
&amp;  &amp;  \\
&amp; $\bullet $ &amp;  \\
$\times $ &amp; $\bullet $ &amp;
\end{tabular}
}\rightarrow UD,\
\]

\[
\frame{%
\begin{tabular}{lll}
&amp;  &amp;  \\
&amp; $\bullet $ &amp; $\bullet $ \\
$\times $ &amp;  &amp;
\end{tabular}
}\rightarrow H_gH_r,\frame{%
\begin{tabular}{lll}
&amp;  &amp; $\bullet $ \\
&amp; $\bullet $ &amp;  \\
$\times $ &amp;  &amp;
\end{tabular}
}\rightarrow H_gH_g.
\]
\

\begin{theorem}
\label{theorem8}
The number of the animals in the first octant of size $n$ is given by 
$c_{n+1}$, the $(n+1)^{th}$ Catalan number.
\end{theorem}

\textbf{Proof}.\ \ By induction, assume that the theorem is true for
size less than $n$. Let $S\in A_1(n)$.$\ $We apply Algorithm 4 by starting
at the smallest $d&gt;0$ such that $(d,d)\in S$ to partition $S$ into $T,B$. We
apply Algorithm 5 to obtain the $T^{^{\prime }}$.  Let $B\ \rightarrow
B^{^{\prime }}\in A_1(k-1),$ by removing the first point (the origin). If $%
T^{^{\prime }}=\emptyset ,$ then $B^{^{\prime }}$ is of size $k-1=n-1$, the first
step is $H_r$ and by induction $S\rightarrow H_rB^{*}$. If $B^{^{\prime
}}=\emptyset ,$ then the first step is $H_g$ and by induction $S\rightarrow
H_gT^{*}$. Otherwise, the first step is $U$ and the $k^{th}$ step is $D$,
by induction fill in steps $2$ to $(k-1)$ by $B^{^{\prime }}\rightarrow
B^{*} $ and steps $(k+1)^{th}$ to the $n^{th}$ by $T^{^{\prime }}\rightarrow
T^{*}$, i.e., $S\rightarrow P=U(B^{*})D(T^{*})$.

Conversely, by induction let $P=a_1a_2 \cdots a_n$ $\in M_1(n)$. If $a_1=H_r,$
then $P^{^{\prime }} = a_2a_3 \cdots a_n$ is of size $m-1$, by induction $%
P^{^{\prime }}\rightarrow S^{*}$ and $S=(S^{*}+(1,0))\cup \{(0,0)\}\in
A_1(n)$ (shift $S^{*}$ to the right one unit). If $a_1=H_g,$ then $%
S=\{S^{*}+(1,1)$ $\cup (0,0)\}$ (shift $S^{*}$ diagonally up one unit). If $%
a_1$ is $U$, then find the first $k$ such that $a_1a_2 \cdots a_k
\in M(k)$, 
$B=a_2a_3 \cdots a_{k-1}$ and $T=a_{k+1}a_{k+2} \cdots a_n$.
By induction $T\rightarrow
T^{*},$ $B\rightarrow B^{*}\rightarrow B^{^{\prime }}=(B^{*}+(1,0))\cup
\{(0,0)\}$. Let $T^{^{\prime }}=T^{*}+(j+1,j+1),$ where $j=\max\{b:(a,b)\in $
$B\}$, and then apply Algorithm 5 by starting with the union of $B^{^{\prime
}}$ and $T^{^{\prime }}$.  
By induction the total count is
\begin{eqnarray*}
a_1(n) &amp;=&amp; a_1(n-1)+a_1(n-2)a_1(0)+a_1(n-3)a_1(1)+a_1(n-4)a_1(2)+ \cdots \\
 &amp;= &amp; c_nc_0+c_{n-1}c_1+c_{n-2}c_2+ \cdots +c_0c_{n-1} \\
 &amp;=&amp; \sum_{i=0}^nc_{n-i}c_i=c_{n+1},
\end{eqnarray*}
where the first term
represents the case that $T$ is empty and the second term represents
the case that $T$ is one point. Similarly, the last term represents the
case that $B$ is empty and next-to-last term represents the case
that $B$ is one point.

The generating function is
$\sum a_1(n)x^n= 1+2x+5x^2+14x^3+42x^4+ \cdots =C^2.$

\bigskip

\begin{example}
This\textbf{\ }example is for the first part of the proof in 
Theorem~\ref{theorem8}.
The partition path is $(2,2)\rightarrow (3,2)\rightarrow
(4,2)\rightarrow (5,3)\rightarrow (6,3),$ which partitions $S$ into two
animals $T,B$. By induction we produce 2-Motzkin paths $T^{*}$ and $B^{*}$,
and by Theorem~\ref{theorem8} we produce a 2-Motzkin path $P$ for $S$.
\end{example}

\[
S=\frame{%
\begin{tabular}{llllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\circ $ \\
&amp;  &amp;  &amp;  &amp;  &amp; $\circ $ \\
&amp;  &amp; $\circ $ &amp; $\circ $ &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ &amp; $\bullet $ \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;
\end{tabular}
}\rightarrow \ \ T=\ \frame{%
\begin{tabular}{lll}
&amp;  &amp; $\circ $ \\
$\times $ &amp; $\circ $ &amp; $\circ $%
\end{tabular}
},B=\frame{%
\begin{tabular}{lllll}
&amp;  &amp;  &amp;  &amp; $\bullet $ \\
&amp; $\bullet $ &amp;  &amp; $\bullet $ &amp; $\bullet $ \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;
\end{tabular}
}\ ,
\]

$P=U(B^{*})D(T^{*})\rightarrow U(UH_rH_gUDD)D(H_rUD).$ \

\bigskip

\begin{example}
This example is for the converse of the bijection. We start with a 2-Motzkin
path $P=U(UH_rDH_rH_rUD)D(H_rUH_rH_gH_rD)$, locate the first $D$ such that
the path $P$ comes back to $x$-axis. The subpath $B=UH_rDH_rH_rUD$ is the
section of $P$ between the first step($U$) and this $D$, the section after
this $D$ is the subpath $T=H_rUH_rH_gH_rD$. By induction we produce
subanimals $T^{*}$ and $B^{*},$\ using Theorem~\ref{theorem8}
we produce the animal $S$ for $P$.
\end{example}

\[
T\rightarrow T^{*}=\frame{%
\begin{tabular}{llllll}
&amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 6$ &amp; $\circ 7$ \\
$\times 1$ &amp; $\circ 2$ &amp; $\circ 3$ &amp; $\circ 5$ &amp;  &amp;
\end{tabular}
}\ ,\ \ \ \ \ B\rightarrow B^{*}\rightarrow \ B^{^{\prime }}=\frame{%
\begin{tabular}{llllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;
\end{tabular}
}\ ,
\]

\begin{center}
\[
\ B^{^{\prime }}\cup T^{^{\prime }}=\frame{%
\begin{tabular}{lllllllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 6$ &amp; $\circ 7$ \\
&amp;  &amp;  &amp; $\times 1$ &amp; $\circ 2$ &amp; $\circ 3$ &amp; $\circ 5$ &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp; $\bullet $ &amp;  &amp;  &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
},
\]
\end{center}

\[
P\rightarrow S=\frame{%
\begin{tabular}{lllllllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 6$ &amp; $\circ 7$ \\
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 3$ &amp; $\circ 5$ &amp;  &amp;  \\
&amp;  &amp; $\times 1$ &amp; $\circ 2$ &amp;  &amp; $\bullet $ &amp;  &amp;  &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
}.
\]

\bigskip

\begin{remark}
Let us partition $A_1(n)$\ by the number points on the line $y=x$.  Let
$A_1(n,k)=\{S\in A_1(n):\left| S\cap \{(x,x):x&gt;0\}\right| =k\}$ and
$a_1(n,k)=\left| A_1(n,k)\right|$.  Then the following is the matrix
$(a_1(n,k))$ for $n,k$ up to $5$:

\[
\left[
\begin{array}{ccccccc}
n\backslash k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 2 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 5 &amp; 5 &amp; 3 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 14 &amp; 14 &amp; 9 &amp; 4 &amp; 1 &amp; 0 \\
5 &amp; 42 &amp; 42 &amp; 28 &amp; 14 &amp; 5 &amp; 1
\end{array}
\right] .
\]

We say that an infinite lower triangular matrix $L=(g,f)$ is a {\it Riordan
matrix} if the generating function of the $k^{th}$ column is $gf^k$ for
all $k$.\ Here $(a_1(n,k))=(C,xC).$ For more about the
Riordan matrix, see \cite {SGWW}.
\end{remark}

\bigskip

\begin{remark}
By using the Lagrange Inversion Formula (Wilf \cite{W}) with some index
adjustment we derive the explicit formula 
$a_1(n,k)=\frac{k+1}{2n-k+1} {{2n-k+1} \choose {n-k}}.$
\end{remark}

\section{ Animals $A_2(m)$ and 2-Motzkin Paths$M_2(m)$}

Here we construct a bijection between animals and 2-Motzkin paths.
For other bijections and partitions, see \cite{BL,BR}.

\begin{theorem}
\label{theorem13}
There is a bijection between $M_2(m)$ and\ $A_2(m).$ Moreover, for all 
$m\geq 0$, we have $a_2(m)= {{2m+1}\choose m}.$
\end{theorem}

\textbf{Proof}.\ Let $S\in A_2(m),$ we apply Algorithm 4 by starting at $%
(0,1)$ to partition $S$ into $T$, $B$. Then $B\in A_1(k)$ and by applying$\ $%
Algorithm 5, $T$ $\rightarrow $ $T^{^{\prime }}.$ If $T=\emptyset ,$ then $S\in
A_1(m)$ and by Theorem~\ref{theorem8} we are done.
Otherwise, $T^{^{\prime }}\rightarrow
T^{*}=T^{^{\prime }}-(0,1),B \rightarrow B^{*}$; and $S\rightarrow
P=B^{*}UT^{*}.$

Conversely, by induction let $P=a_1a_2 \cdots a_m$ $\in M_2(m)-M_1(m)$. We look
for the largest $k$ such that $(k,0)\in P,$ i.e., the last time $P$ is on
the $x$-axis.
By induction $a_1a_2 \cdots a_k\rightarrow B$ and $a_{k+2} \cdots a_m%
\rightarrow T.$ $T\rightarrow T^{^{\prime }}=T+(0,1)\rightarrow
T^{*}=T^{^{\prime }}+(j+1,j+1),$ where $j=\max\{b:(a,b)\in B\}$.  Apply 
Algorithm 5 by starting with $B\cup T^{*}$; we have $P\rightarrow
S=(B\cup T^{*})^{^{\prime }}$.

The generating function of the counts of $A_2(m)$ is
\[
C^2(1+xC^2+(xC^2)^2+(xC^2)^3+ \cdots )=\frac{C^2}{1-xC^2}=\frac{C^2}{C\sqrt{1-4x}}%
=\frac C{\sqrt{1-4x}}.
\]

These numbers appear as the nonzero entries in column one in the
Pascal's Triangle.

\bigskip

\begin{example}
This example is for the first part of Theorem~\ref{theorem13}.
We start an animal $S$
with the partition path $(2,3)\rightarrow (3,3)\rightarrow (4,3)\rightarrow
(5,4)\rightarrow (6,4)\rightarrow (7,5)\rightarrow (8,5),$ which partitions
$S$ into $B,T.$ By induction $B\rightarrow B^{*},T\rightarrow T^{*}$\ we
derive the path $P$.
\[
S=\frame{%
\begin{tabular}{llllllll}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; $\circ 4$ \\
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; $\circ 3$ \\
&amp;  &amp;  &amp; $\circ $ &amp; $\circ $ &amp;  &amp;  &amp; $\circ 2$ \\
&amp;  &amp;  &amp; $\circ $ &amp;  &amp; $\circ 1$ &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\circ $ &amp; $\circ $ &amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\bullet $ &amp;  &amp;  &amp; $\bullet $ &amp; $\bullet $ &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
},
\]
\
\end{example}

\begin{eqnarray*}
B &amp;=&amp;\frame{%
\begin{tabular}{llllllll}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; $\bullet $ \\
&amp;  &amp;  &amp;  &amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\bullet $ &amp;  &amp;  &amp; $\bullet $ &amp; $\bullet $ &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;
\end{tabular}
}\rightarrow B^{*}=U(H_gH_rUH_gH_rH_gDH_r)D, \\
T &amp;=&amp;\frame{%
\begin{tabular}{lllll}
&amp; $\circ $ &amp; $\circ $ &amp; $\circ 4$ &amp;  \\
&amp; $\circ $ &amp;  &amp; $\circ 3$ &amp;  \\
$\times $ &amp; $\circ $ &amp; $\circ 1$ &amp; $\circ 2$ &amp;
\end{tabular}
}\rightarrow T^{*}=(U(H_rUD)D)UH_rH_r\rightarrow
\end{eqnarray*}
\

$P=(B^{*})U(T^{*})=(UH_gH_rUH_gH_rH_gDH_rD)U(UH_rUDDUH_rH_r).$

\bigskip

\begin{remark}
Let us partition $A_2(m)$\ by
$$A_2(m,k)=\{S\in A_2(m):k=\max \{b-a:(a,b)\in
S\}\}$$ and $ a_2(m,k)=\left| A_2(m,k)\right|$.   By using the Lagrange
Inversion Formula (Wilf \cite{W}) and simple algebraic operations we obtain
the explicit formula $a_2(m,k)=\frac{2k+2}{2m+2}
{{2m+2} \choose {m-k}} $. Then by Theorem~\ref{theorem13}
the following is the matrix
$(a_2(m,k))=(C^2,xC^2)$ for $m,k$ up to $5$:
\end{remark}

\[
\ \left[
\begin{array}{ccccccc}
m/k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 01 \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 5 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 14 &amp; 14 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 42 &amp; 48 &amp; 27 &amp; 8 &amp; 1 &amp; 0 \\
5 &amp; 132 &amp; 165 &amp; 110 &amp; 44 &amp; 10 &amp; 1
\end{array}
\right] .
\]

\bigskip

\begin{remark}
Let us partition $A_2(m)$\ by 
$$A_2^{*}(m,k)=\{S\in A_2(m):k=\max \{b\
:(0,b)\in S\}\}$$ and
$a_2^{*}(m,k)=\left| A_2^{*}(m,k)\right|$ .
The set $A_2^{*}(m,0)$ consists of
two copies of $A_2(m-1)$; one copy consists of
those with no points on $x$-axis except the origin and the other copy with
such points.
Hence the generating function is

\[
1+\frac{2xC}{\sqrt{1-4x}}=\frac{\sqrt{1-4x}+2xC}{\sqrt{1-4x}}=\frac{\frac{2-C%
}C+2xC}{\sqrt{1-4x}}=\frac 1{\sqrt{1-4x}}.
\]

Note that if $(0,1)\in S,$\ the partition is $T,B$ in Theorem~\ref{theorem13}
with $B$
containing no point on $y=x&gt;0$.   By using the Lagrange Inversion Formula
 (Wilf \cite{W})
and simple algebraic operations we can derive the explicit formula
$a_2^{*}(m,k)= {{2m-k} \choose {m-k}}$. 

The generating function
for $B$ is $C$ and the following is the matrix $(a_2^{*}(m,k))=(\frac 1{%
\sqrt{1-4x}},xC)$ for$\;m,k$ up to $5$:

\[
\left[
\begin{array}{ccccccc}
m/k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 6 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 20 &amp; 10 &amp; 4 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 70 &amp; 35 &amp; 15 &amp; 5 &amp; 1 &amp; 0 \\
5 &amp; 252 &amp; 126 &amp; 56 &amp; 21 &amp; 6 &amp; 1
\end{array}
\right] .
\]

\end{remark}

\bigskip

\begin{remark}
Let us go a step further. Let $D(m)=A_2(m,0),$ the set of animals in the
first quadrant containing no point on the $y$-axis except the origin and
partition $D(m)$ by the number of points on the $x$-axis $D(m,k)=\{S\in
D(m):(k,0)\in S,(k+1,0)\notin S\}$. Let $d(m,k)=\left| D(m,k)\right|$.  Then
by using the Lagrange Inversion Formula (Wilf \cite{W}) and simple algebraic
operations we can derive the explicit formula $d(m,k)=
{{2m-k-1} \choose {m-k}}$ for $k&gt;0$ and $d(m,0)= {{2m-1} \choose {m-1}}$.

The following is the matrix $(d(m,k))$ for $m,k$ up to $5$:
\end{remark}

\[
\mathbf{\ }\left[
\begin{array}{ccccccc}
m/k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 3 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 10 &amp; 6 &amp; 3 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 35 &amp; 20 &amp; 10 &amp; 4 &amp; 1 &amp; 0 \\
5 &amp; 126 &amp; 70 &amp; 35 &amp; 15 &amp; 5 &amp; 1
\end{array}
\right] =(\ 1+\frac{xC}{\sqrt{1-4x}},xC(x)).\mathbf{\ }
\]

\section{Animals $A_3(m)$ and 2-Motzkin Paths $M_3(m)$}


Here we construct a bijection between animals and 2-Motzkin paths.
For other bijections and partitions, please see \cite{BL,BR}.

\begin{theorem}
\label{theorem18}
There is a bijection between $M_3(m)=M(m)$ and $A_3(m)=A(m).$\ Moreover, the
number of animals in the first three octants of size $m$ is $4^m$, $m\geq 0.$
\end{theorem}

\textbf{Proof}.\ Let $S\in A_3(m),$ apply Algorithm 4 by starting at 
$(-1,1)$ to partition $S$ into $T$, $B$. Then $B\in A_1(k)$ and apply 
Algorithm 5 to $T\rightarrow T^{^{^{\prime }}}\in A_3(m-k-1).$ Then 
$T^{^{\prime }}\rightarrow T^{*}=T^{^{^{\prime }}}+(1,-1)$. If $S\in A_2(m),$
then by Theorem~\ref{theorem13} we are done.
Otherwise, by induction $S\rightarrow
(B^{*})D(T^{*})\in M_3(m)$.

Conversely, let $P=a_1a_2 \cdots a_m\in M_3(m).$ If $P\in M_2(m),$ then by
Theorem~\ref{theorem13}, we are done. Otherwise, we look for the first $k$ such that $%
(k,0)\in P\;$and $P$ goes under the $x$-axis after that. Then by induction $%
a_1a_2 \cdots a_k\rightarrow B^{*}$ and $a_{k+2} \cdots a_m\rightarrow $ $T$ $%
,\;T\rightarrow T^{^{\prime }}=T+(-1,1).\;T^{*}=E\cup ((T^{^{\prime
}}-E)+(j+1,j+1)),\;$where $E$ is the set of points in $T^{^{\prime }}$ that
are not in the first quadrant and $j=\max\{(b:(a,b)\in B\}$.  Apply Algorithm 5
by starting with $B^{*}\cup T^{*}$.\ We have $P\rightarrow S.$

In terms of generating functions we have
\[
\frac C{\sqrt{1-4x}}((1+xC^2+(xC^2)^2+(xC^2)^3+ \cdots )=\frac C{\sqrt{1-4x}%
}\frac 1{1-xC^2}=\frac C{\sqrt{1-4x}}\frac 1{C\sqrt{1-4x}}=\frac 1{1-4x}.
\]

\bigskip

\begin{example}
This example is the converse of the proof of Theorem~\ref{theorem18}.
Let 
$$P=(UUDH_rH_gH_gDH_gH_r)D(H_rH_rDH_rH_gH_gH_r)$$
be a 2-Motzkin path and
locate the first $D$ step, where the path goes below the $x$-axis. The section
of $P$ before the $D$ is $B$ and the section after the $D$ is $T$.  Then by
induction we derive the animal $S$ for $P$.
\end{example}

\[
B=U(UDH_rH_gH_g)D(H_gH_r)\rightarrow B^{*}=\frame{%
\begin{tabular}{llllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\bullet $ \\
&amp;  &amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ &amp;  \\
&amp;  &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  \\
$\times $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;
\end{tabular}
},
\]
\

\begin{eqnarray*}
\ (H_rH_r)D(H_rH_gH_gH_r) &amp;\rightarrow &amp;T=\frame{%
\begin{tabular}{lllll}
&amp;  &amp;  &amp; $\circ 4$ &amp; $\circ 5$ \\
&amp;  &amp; $\circ $ &amp;  &amp;  \\
$\times $ &amp; $\circ $ &amp;  &amp;  &amp;  \\
&amp; $\times 1$ &amp; $\circ 2$ &amp; $\circ 3$ &amp;
\end{tabular}
}, \\
T^{^{^{\prime }}} &amp;=&amp;\frame{%
\begin{tabular}{lllll}
&amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp; $\circ 4$ &amp; $\circ 5$ \\
&amp;  &amp; $\circ $ &amp;  &amp;  \\
$\times $ &amp; $\circ $ &amp;  &amp;  &amp;  \\
&amp; $\times 1$ &amp; $\circ 2$ &amp; $\circ 3$ &amp;  \\
&amp;  &amp; $\times $ &amp;  &amp;
\end{tabular}
},
\end{eqnarray*}
\

\
\[
P=(UUDH_rH_gH_gDH_gH_r)D(H_rH_rDH_rH_gH_gH_r)=(B^{*})D(T^{*}),
\]
\

\[
\rightarrow S=\frame{%
\begin{tabular}{llllllll}
&amp;  &amp;  &amp;  &amp;  &amp; $\circ 5$ &amp;  &amp; $\circ 3$ \\
&amp;  &amp;  &amp; $\circ 4$ &amp;  &amp; $\circ 2$ &amp;  &amp; $\bullet $ \\
&amp;  &amp; $\circ $ &amp;  &amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ \\
$\times $ &amp; $\circ $ &amp;  &amp;  &amp; $\bullet $ &amp;  &amp; $\bullet $ &amp;  \\
&amp; $\times 1$ &amp;  &amp;  &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  \\
&amp;  &amp; $\times $ &amp; $\bullet $ &amp; $\bullet $ &amp;  &amp;  &amp;
\end{tabular}
}.
\]
\

\bigskip

\begin{remark}
Let us  partition $A(m)$ by the number of source points on the line $y=-x&gt;0$.
Let $A(m,k)=\{S\in A(m):(-k,k)\in S,$ $(-(k+1),k+1)\notin S\}$ and $%
a(m,k)=\left| A(m,k)\right| .$ By using the Lagrange Inversion Formula
(Wilf \cite {W})
and simple algebraic operations we obtain the explicit formula 
$a(m,k)= {{2m+1} \choose {m-k}}$.

The following is the matrix 
$(a(m,k))$ for $m,k$ up to $5$:
\[
(a(m,k))=\left[
\begin{array}{ccccccc}
m/k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 10 &amp; 5 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 35 &amp; 21 &amp; 7 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 126 &amp; 84 &amp; 36 &amp; 9 &amp; 1 &amp; 0 \\
5 &amp; 462 &amp; 330 &amp; 165 &amp; 55 &amp; 11 &amp; 1
\end{array}
\right] =(\frac C{\sqrt{1-4x}},xC^2).
\]
\end{remark}

$\ $The $k^{th}$ column is the condensed version of the $(2k+1)^{th}\;$%
column of Pascal's Triangle. 

\section{Acknowledgment}

The author wishes to thank Lou Shapiro for introduction of the
subject and subsequent help and encouragement.

The author also would like to thank Emeric Deutsch for his helpful
discussions about this subject. 



\begin{thebibliography}{16}
\bibitem{A}  M. Aigner, Motzkin numbers, \textit{European J. Combin.}
{\bf 19} (1998), 663--675.

\bibitem{BL}  E. Barcucci, A. Del Lungo, E. Pergola and R. Panzani, Directed
animals, forests and permutations, \textit{Discrete Math.} {\bf 204}
(1999),  41--71.

\bibitem{B}  M. Bousquet-M\`elou, New enumerative results on two dimensional
directed animals, \textit{Discrete Math.} {\bf 180} (1998), 73--106.

\bibitem{BR}  M. Bousquet-Melou and A. Rechnitzer, Lattice animals and heaps
of dimers, \textit{Discrete Math.} {\bf 258} (2002), 235--274.

\bibitem{GV}  D. Gouyou-Beauchamps and G. Viennot, Equivalence of the two
dimensional animal problems to one dimensional path problems, \textit{Adv.
Appl. Math.} {\bf 9} (1988), 334--357.

\bibitem{SGWW}  L. W. Shapiro, Seyoum Getu, Wen-jin Woan and Leon C. Woodson,
The Riordan group, \textit{Discrete Appl. Math.} {\bf 34} (1991), 229--239.

\bibitem{S}  R. P. Stanley, \textit{Enumerative Combinatorics}, Vol. 2, 
Cambridge University Press, 1999.

\bibitem{W}  H. S. Wilf, \textit{Generatingfunctionology},
Academic Press, 1994.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15.

\noindent \emph{Keywords: } 
animals, directed animals, Motzkin paths, Catalan paths, binomial
coefficients.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000108}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  October 2 2005;
revised version received November 1 2005. 
Published in {\it Journal of Integer Sequences}, November 1 2005.

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