\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 & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 \\ 4 & 0 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 \\ 5 & 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 \end{array} \right] , \] \begin{center} \[ (m_2(n,k))=\left[ \ \begin{array}{ccccccc} n/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 14 & 6 & 1 & 0 & 0 \\ 4 & 42 & 48 & 27 & 8 & 1 & 0 \\ 5 & 132 & 165 & 110 & 44 & 10 & 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 $ & $\bullet $ & $\bullet $% \end{tabular} }\rightarrow H_rH_r,\frame{% \begin{tabular}{ll} & $\bullet $ \\ $\times $ & $\bullet $% \end{tabular} }\rightarrow UD,\frame{% \begin{tabular}{lll} & & $\bullet $ \\ $\times $ & $\bullet $ & \end{tabular} }\rightarrow H_rH_g, \] \ \[ \frame{% \begin{tabular}{lll} & $\bullet $ & $\bullet $ \\ $\times $ & & \end{tabular} }\rightarrow H_gH_r,\frame{% \begin{tabular}{lll} & & $\bullet $ \\ & $\bullet $ & \\ $\times $ & & \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} & $\bullet $ \\ & $\bullet $ \\ $\times $ & \end{tabular} }\rightarrow H_gU,\frame{% \begin{tabular}{ll} $\bullet $ & \\ $\times $ & $\bullet $% \end{tabular} }\rightarrow H_rU,\frame{% \begin{tabular}{ll} $\bullet $ & $\bullet $ \\ $\times $ & \end{tabular} }\rightarrow UH_r\ \] \[ \frame{% \begin{tabular}{ll} & $\bullet $ \\ $\bullet $ & \\ $\times $ & \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} & & \\ $\times $ & & \\ & $\times $ & $\bullet $% \end{tabular} }\rightarrow H_rD,\frame{% \begin{tabular}{ll} & \\ $\times $ & $\bullet $ \\ & $\times $% \end{tabular} }\rightarrow DH_r,\frame{% \begin{tabular}{lll} & & \\ $\times $ & & $\bullet $ \\ & $\times $ & \end{tabular} }\rightarrow H_gD,\ \] \[ \frame{% \begin{tabular}{ll} & $\bullet $ \\ $\times $ & \\ & $\times $% \end{tabular} }\rightarrow DH_g,\frame{% \begin{tabular}{ll} $\bullet $ & \\ $\times $ & \\ & $\times $% \end{tabular} }\rightarrow DU,\frame{% \begin{tabular}{lll} $\times $ & & \\ & $\times $ & \\ & & $\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>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>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} & & & & & $\circ 4$ & & $\circ 6$ & $\circ 7$ \\ & & & & & $\circ 3$ & $\circ 5$ & & \\ & & $\circ 1$ & $\circ 2$ & & $\bullet $ & & & \\ & & $\bullet $ & $\bullet $ & $\bullet $ & $\bullet $ & & & \\ $\times $ & $\bullet $ & $\bullet $ & $\bullet $ & & & & & \end{tabular} }, \] The partition path partitions $S$ into $B,T$ as follows: \[ B=\frame{% \begin{tabular}{lllllllll} & & & & & & & & \\ & & & & & & & & \\ & & & & & $\bullet $ & & & \\ & & $\bullet $ & $\bullet $ & $\bullet $ & $\bullet $ & & & \\ $\times $ & $\bullet $ & $\bullet $ & $\bullet $ & & & & & \end{tabular} }, \] \[ T=\frame{% \begin{tabular}{lllllllll} & & & & & $\circ 4$ & & $\circ 6$ & $\circ 7$ \\ & & & & & $\circ 3$ & $\circ 5$ & & \\ & & $\circ 1$ & $\circ 2$ & & & & & \\ & & & & & & & & \\ $\times $ & & & & & & & & \end{tabular} }, \] Applying Algorithm 5 on $T$, we have \[ T^{^{^{\prime }}}=\ \ \frame{% \begin{tabular}{llllll} & & $\circ 4$ & & $\circ 6$ & $\circ 7$ \\ $\circ 1$ & $\circ 2$ & $\circ 3$ & $\circ 5$ & & \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} & \\ $\times $ & $\bullet $% \end{tabular} }\rightarrow H_r,\ \frame{\ \begin{tabular}{ll} & $\bullet $ \\ $\times $ & \end{tabular} }\rightarrow H_g\ , \] \[ \frame{% \begin{tabular}{lll} & & \\ & & \\ $\times $ & $\bullet $ & $\bullet $% \end{tabular} }\rightarrow H_rH_r,\frame{% \begin{tabular}{lll} & & \\ & & $\bullet $ \\ $\times $ & $\bullet $ & \end{tabular} }\ \rightarrow H_rH_g,\frame{% \begin{tabular}{lll} & & \\ & $\bullet $ & \\ $\times $ & $\bullet $ & \end{tabular} }\rightarrow UD,\ \] \[ \frame{% \begin{tabular}{lll} & & \\ & $\bullet $ & $\bullet $ \\ $\times $ & & \end{tabular} }\rightarrow H_gH_r,\frame{% \begin{tabular}{lll} & & $\bullet $ \\ & $\bullet $ & \\ $\times $ & & \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>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) &=& 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 \\ &= & c_nc_0+c_{n-1}c_1+c_{n-2}c_2+ \cdots +c_0c_{n-1} \\ &=& \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} & & & & & $\circ $ \\ & & & & & $\circ $ \\ & & $\circ $ & $\circ $ & & $\bullet $ \\ & & $\bullet $ & & $\bullet $ & $\bullet $ \\ $\times $ & $\bullet $ & $\bullet $ & $\bullet $ & & \end{tabular} }\rightarrow \ \ T=\ \frame{% \begin{tabular}{lll} & & $\circ $ \\ $\times $ & $\circ $ & $\circ $% \end{tabular} },B=\frame{% \begin{tabular}{lllll} & & & & $\bullet $ \\ & $\bullet $ & & $\bullet $ & $\bullet $ \\ $\times $ & $\bullet $ & $\bullet $ & & \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} & & $\circ 4$ & & $\circ 6$ & $\circ 7$ \\ $\times 1$ & $\circ 2$ & $\circ 3$ & $\circ 5$ & & \end{tabular} }\ ,\ \ \ \ \ B\rightarrow B^{*}\rightarrow \ B^{^{\prime }}=\frame{% \begin{tabular}{llllll} & & & & & $\bullet $ \\ & & $\bullet $ & $\bullet $ & $\bullet $ & $\bullet $ \\ $\times $ & $\bullet $ & $\bullet $ & $\bullet $ & & \end{tabular} }\ , \] \begin{center} \[ \ B^{^{\prime }}\cup T^{^{\prime }}=\frame{% \begin{tabular}{lllllllll} & & & & & $\circ 4$ & & $\circ 6$ & $\circ 7$ \\ & & & $\times 1$ & $\circ 2$ & $\circ 3$ & $\circ 5$ & & \\ & & & & & $\bullet $ & & & \\ & & $\bullet $ & $\bullet $ & $\bullet $ & $\bullet $ & & & \\ $\times $ & $\bullet $ & $\bullet $ & $\bullet $ & & & & & \end{tabular} }, \] \end{center} \[ P\rightarrow S=\frame{% \begin{tabular}{lllllllll} & & & & & $\circ 4$ & & $\circ 6$ & $\circ 7$ \\ & & & & & $\circ 3$ & $\circ 5$ & & \\ & & $\times 1$ & $\circ 2$ & & $\bullet $ & & & \\ & & $\bullet $ & $\bullet $ & $\bullet $ & $\bullet $ & & & \\ $\times $ & $\bullet $ & $\bullet $ & $\bullet $ & & & & & \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>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 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 2 & 1 & 0 & 0 & 0 \\ 3 & 5 & 5 & 3 & 1 & 0 & 0 \\ 4 & 14 & 14 & 9 & 4 & 1 & 0 \\ 5 & 42 & 42 & 28 & 14 & 5 & 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} & & & & & & & $\circ 4$ \\ & & & & & & & $\circ 3$ \\ & & & $\circ $ & $\circ $ & & & $\circ 2$ \\ & & & $\circ $ & & $\circ 1$ & & $\bullet $ \\ & & $\circ $ & $\circ $ & & $\bullet $ & & $\bullet $ \\ & & $\bullet $ & & & $\bullet $ & $\bullet $ & \\ & & $\bullet $ & $\bullet $ & $\bullet $ & & & \\ $\times $ & $\bullet $ & & & & & & \end{tabular} }, \] \ \end{example} \begin{eqnarray*} B &=&\frame{% \begin{tabular}{llllllll} & & & & & & & $\bullet $ \\ & & & & & $\bullet $ & & $\bullet $ \\ & & $\bullet $ & & & $\bullet $ & $\bullet $ & \\ & & $\bullet $ & $\bullet $ & $\bullet $ & & & \\ $\times $ & $\bullet $ & & & & & & \end{tabular} }\rightarrow B^{*}=U(H_gH_rUH_gH_rH_gDH_r)D, \\ T &=&\frame{% \begin{tabular}{lllll} & $\circ $ & $\circ $ & $\circ 4$ & \\ & $\circ $ & & $\circ 3$ & \\ $\times $ & $\circ $ & $\circ 1$ & $\circ 2$ & \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 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 01 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 14 & 6 & 1 & 0 & 0 \\ 4 & 42 & 48 & 27 & 8 & 1 & 0 \\ 5 & 132 & 165 & 110 & 44 & 10 & 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>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 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 6 & 3 & 1 & 0 & 0 & 0 \\ 3 & 20 & 10 & 4 & 1 & 0 & 0 \\ 4 & 70 & 35 & 15 & 5 & 1 & 0 \\ 5 & 252 & 126 & 56 & 21 & 6 & 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>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 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 2 & 1 & 0 & 0 & 0 \\ 3 & 10 & 6 & 3 & 1 & 0 & 0 \\ 4 & 35 & 20 & 10 & 4 & 1 & 0 \\ 5 & 126 & 70 & 35 & 15 & 5 & 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} & & & & & $\bullet $ \\ & & & $\bullet $ & & $\bullet $ \\ & & $\bullet $ & & $\bullet $ & \\ & & $\bullet $ & $\bullet $ & & \\ $\times $ & $\bullet $ & $\bullet $ & & & \end{tabular} }, \] \ \begin{eqnarray*} \ (H_rH_r)D(H_rH_gH_gH_r) &\rightarrow &T=\frame{% \begin{tabular}{lllll} & & & $\circ 4$ & $\circ 5$ \\ & & $\circ $ & & \\ $\times $ & $\circ $ & & & \\ & $\times 1$ & $\circ 2$ & $\circ 3$ & \end{tabular} }, \\ T^{^{^{\prime }}} &=&\frame{% \begin{tabular}{lllll} & & & & \\ & & & $\circ 4$ & $\circ 5$ \\ & & $\circ $ & & \\ $\times $ & $\circ $ & & & \\ & $\times 1$ & $\circ 2$ & $\circ 3$ & \\ & & $\times $ & & \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} & & & & & $\circ 5$ & & $\circ 3$ \\ & & & $\circ 4$ & & $\circ 2$ & & $\bullet $ \\ & & $\circ $ & & & $\bullet $ & & $\bullet $ \\ $\times $ & $\circ $ & & & $\bullet $ & & $\bullet $ & \\ & $\times 1$ & & & $\bullet $ & $\bullet $ & & \\ & & $\times $ & $\bullet $ & $\bullet $ & & & \end{tabular} }. \] \ \bigskip \begin{remark} Let us partition $A(m)$ by the number of source points on the line $y=-x>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 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 10 & 5 & 1 & 0 & 0 & 0 \\ 3 & 35 & 21 & 7 & 1 & 0 & 0 \\ 4 & 126 & 84 & 36 & 9 & 1 & 0 \\ 5 & 462 & 330 & 165 & 55 & 11 & 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}