% This is a Latex file for Robert A. Sulanke's paper : % % Bijective Recurrences concerning Schr{\"o}der Paths % % %This file requires three additional files, which I am also emailing to McKay: % psfig.tex % sulankefig1.ps % sulankefig2.ps % % % \documentclass[12pt]{article} \usepackage{graphicx} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 47 (1998) \#R47\hfill} \thispagestyle{empty} \makeatletter \renewcommand\section{\@startsection {section}{1}{\z@}% {-3.5ex \@plus -1ex \@minus -.2ex}% {2.3ex \@plus.2ex}% {\normalfont\large\bfseries}} \makeatother % Note to editor: Please allow this section labeling font scheme. % I find the `standard' % latex section labeling to be unattractive because of its LARGE font size. % Thanks \oddsidemargin 10pt \evensidemargin 10pt \textheight 9in \textwidth 6in \topmargin -\headheight % \input psfig \renewcommand{\baselinestretch}{1.1} \newcommand{\map}{f} \newcommand{\MAP}{g} \newcommand{\tild}{TC} \newcommand{\hatt}{TD} \newcommand{\barr}{TI} \begin{document} \author{Robert A. Sulanke\\ Boise State University \\ Boise, Idaho, USA\\ {\small\texttt{sulanke@math.idbsu.edu}}} \title{ Bijective Recurrences concerning Schr{\"o}der Paths} \date{\small Submitted: April 7, 1998; Accepted: October 30, 1998} \maketitle \begin{abstract} Consider lattice paths in {\bf Z}$^2$ with three step types: the {\it up diagonal } $(1,1)$, the {\it down diagonal } $(1,-1)$, and the {\it double horizontal } $(2,0)$. For $n \geq 1$, let $S_n$ denote the set of such paths running from $(0,0)$ to $(2n,0)$ and remaining strictly above the x-axis except initially and terminally. It is well known that the cardinalities, $r_n = |S_n|$, are the large Schr{\"o}der numbers. We use lattice paths to interpret bijectively the recurrence $ (n+1) r_{n+1} = 3(2n - 1) r_{n} - (n-2) r_{n-1}$, for $n \geq 2$, with $r_1=1$ and $r_2=2$. We then use the bijective scheme to prove a result of Kreweras that the sum of the areas of the regions lying under the paths of $S_n$ and above the x-axis, denoted by $AS_n$, satisfies $ AS_{n+1} = 6 AS_n - AS_{n-1}, $ for $n \geq 2$, with $AS_1 =1$, and $AS_2 =7$. Hence $AS_n = 1, 7, 41, 239 ,1393, \ldots$. The bijective scheme yields analogous recurrences for elevated Catalan paths. Mathematical Reviews Subject Classification: 05A15 \end{abstract} \section{The paths and the recurrences} We will consider lattice paths in {\bf Z}$^2$ whose permitted step types are the {\it up diagonal } $(1,1)$ denoted by $U$, the {\it down diagonal } $(1,-1)$ denoted by $D$, and the {\it double horizontal } $(2,0)$ denoted by $H$. We will focus on paths that run from $(0,0)$ to $(2n,0)$, for $n \geq 1$, and that never touch or pass below the x-axis except initially and terminally. Let $C_n$ denote the set of such paths when only U-steps and D-steps are allowed, and let $S_n$ denote the set of such paths when all three types are allowed. It is well known that the cardinalities $c_n = |C_n|$ and $r_n = |S_n|$, for $n \geq 1$, are the Catalan numbers and the large Schr{\"o}der numbers, respectively. (See Section 4, particularly Notes 2 and 4.) Hence, here one might view the elements of $S_n$ as {\it elevated Schr{\"o}der paths}. Let $AC_n$ denote the sum of the areas of the regions lying under the paths of $C_n$ and above the x-axis. Likewise, let $AS_n$ denote the sum of the areas of the regions lying under the paths of $S_n$ and above the x-axis. \begin{figure}[h] \begin{center} \vspace{12pt} %\leavevmode\psfig{figure=sulankefig1.ps,width=5.6in} \includegraphics[width=5.6in]{sulankefig1.eps} \end{center} \caption{ The 6 elevated Schr{\"o}der paths of $S_3$ bound 41 triangles of unit area.} \label{figure1} \end{figure} \vspace{12pt} \begin{center} \begin{tabular}{r|rrrrrr} $n$ & \quad$1$\quad &\quad$2$\quad &\quad$3$\quad &\quad$4$\quad&5\quad & \ldots \\ \hline $c_n$ & 1 &1 & 2 &5 &14 & \ldots \\ $r_n$ & 1 &2 &6 &22 &90 & \ldots \\ $AC_n$ & 1 &4 & 16 &64 &256 & \ldots \\ $AS_n$ & 1 &7 & 41 & 239 & 1393 & \ldots \\ \end{tabular} \end{center} \ The Catalan numbers and the Schr{\"o}der numbers have been studied extensively; Section 4 references some studies related to lattice paths. In our notation their explicit formulas are, for $n \geq 1$, $$ c_n = \frac{1}{n}{{2n-2}\choose{n-1}} \mbox{ \quad and \quad } r_n = \sum_{k=1}^n \frac{1}{k} {{n-2}\choose{k-1}}{{n-1}\choose{k-1}}2^k. $$ It is known that these sequences satisfy the recurrences \begin{eqnarray} (n+1) c_{n+1}& =& 2(2n - 1) c_{n} \label{equ1} \\ (n+1) r_{n+1}& =& 3(2n - 1) r_{n} - (n-2) r_{n-1} \label{equ2} \end{eqnarray} for $n \geq 2$, with initial conditions $c_1=1$, $c_2=1$, $r_1=1$, and $r_2=2$. We will give a bijective proof for (\ref{equ1}) and (\ref{equ2}) when the sequences $c_n$ and $r_n$ are defined in terms of the sets of lattice paths. We will then employ this bijective construction to obtain a combinatorial interpretation that the sequences for the total areas satisfy \begin{eqnarray} AC_{n+1}& =& 4 AC_n \label{equ3} \\ AS_{n+1}& =& 6 AS_n - AS_{n-1} \label{equ4} \end{eqnarray} for $n \geq 2$ with initial conditions $AC_1 =1$, $AC_2 = 4$, $AS_1 =1$, and $AS_2 =7$. Using binary trees, R{\'e}my \cite{Remy} gave a combinatorial proof of recurrence (\ref{equ1}). Recently, Foata and Zeilberger \cite{FZ} showed bijectively, using well-weighted binary plane trees,\ that the small Schr{\"o}der numbers satisfy (\ref{equ2}) with initial conditions $r_1=1$ and $r_2=1$. (See Section 4 for ``well-weighted'' and ``small''.) Kreweras \cite{KreAires}, using lattice paths equivalent to those of $S_n$ showed $AS_n = \sum_{0 \leq k < n} 2^{k} {{2n-1} \choose {2k} }$ and derived recurrence (\ref{equ4}). Following his results, Bonin, Shapiro, and Simion \cite{BSS} proved (\ref{equ4}) using generating functions and then wrote that ``This recurrence cries out for a combinatorial interpretation.'' Section 3 comes to the rescue. \section{The proof of recurrences (1) and (2)} We will focus on recurrence (\ref{equ2}) rearranged as $3(2n - 1) r_{n} = (n+1) r_{n+1} + (n-2) r_{n-1}$. In $S_n$ replicate each path, defined as a sequence of steps, $3(2n-1)$ times as follows: First repeatedly tag each path $P$ by appending the symbol $a$, $b$, or $c$. Next, for each tagged path $P$, consecutively index its steps, as positioned in $P$, with the integers 1 through $2n-1$ so that each U-step and each non final D-step receives one integer and each H-step receives two consecutive integers. Then mark each path $P$ by selecting an integer from $\{1,\ldots,2n-1\}$ and marking the corresponding step on $P$ \begin{itemize} \item[--] by the superscript $x$ if the step is $U$ or if the step is $H$ with odd index, and \item[--] by the superscript $y$ if the step is $D$ or if the step is $H$ with even index. \end{itemize} We write the set of such replications as $ \{a,b,c\} \times \{1, \ldots , 2n-1\} \times S_n = \{a,b,c\} \times [2n-1] \times S_n $, where, in general, $[n]$ denotes $\{1, \ldots ,n\}$. For instance, for $S_2 = \{ UUDD, UHD \}$, $$ \begin{tabular}{rccccl} $\{a,b,c\} \times [3] \times S_2 = $ & & & &\\ $\{ U^xUDDa,$ & $UU^xDDa,$ & $UUD^yDa,$ & $U^xHDa,$ & $UH^yDa,$ & $UH^xDa,$ \\ $ U^xUDDb,$ & $UU^xDDb,$ & $UUD^yDb,$ & $U^xHDb,$ & $UH^yDb,$ & $UH^xDb,$ \\ $ U^xUDDc,$ & $UU^xDDc,$ & $UUD^yDc,$ & $U^xHDc,$ & $UH^yDc,$ & $UH^xDc\}.$ \\ \end{tabular} $$ Next in $S_{n+1}$ replicate each path $n+1$ times by sequentially marking one of its U-steps or H-steps by the symbol $z$. This replicated set is denoted as $[n+1] \times S_{n+1}$. Similarly, in $S_{n-1}$ replicate each path $n-2$ times by sequentially marking one of its H-steps or non final D-steps by the symbol $z$. This replicated set is denoted as $[n-2] \times S_{n-1}$. For $n \geq 2$, we now define the desired bijection, \begin{equation}\label{map} \map : \{a,b,c\} \times [2n-1] \times S_n \rightarrow [n+1] \times S_{n+1} \ \bigcup\ [n-2] \times S_{n-1}. \end{equation} Suppose \begin{equation}\label{suppose} P = p_1 \cdots p_i \cdots p_j \cdots p_k \cdots p_m. \end{equation} denotes a typical replicated path in $[2n-1] \times S_n$ for which the following four items hold. \begin{itemize} \item[--] The positions $i$, $j$, and $k$ satisfy $1 \leq i \leq j < k \leq m.$ \item[--] The step $p_j$ is the step that is marked by $x$ or $y$. \item[--] The step $p_i$ is the last U-step preceding $p_{j+1}$ for which $\mbox{\sc lev}(p_i) = \mbox{\sc lev}(p_{j})$. Here the {\it level} of arbitrary step $p_{\ell}$, denoted $\mbox{\sc lev}(p_{\ell})$, is the ordinate of its final point. When $p_j = U^x$, $i = j$. \item[--] The step $p_k$ is the first D-step after $p_{j}$ for which $\mbox{\sc lev}(p_k) = \mbox{\sc lev}(p_{j}) - 1$. \end{itemize} \noindent {\bf Case 1a}: If $p_j = U^x$, $H^x$, or $D^y$, $\map(Pa) = p_1 \cdots p_i \cdots p_j U^zD p_{j+1} \cdots p_k \cdots p_m$. (Here, $\map(Pa)$ is obtained by inserting the pair $U^zD$ immediately after $ p_j$. The tags $x$, $y$, and $a$ are erased here; the tags $b$ and $c$ are erased in the following cases. If $P$ appears in Fig. 2, $\map(Pa)$ appears in Fig. 3. In the figures the dots pertain to an illustration for the proof of the next section.) \ \noindent {\bf Case 1b}: If $p_j = U^x$, $H^x$, or $D^y$, $\map(Pb) = p_1 \cdots p_i^z \cdots p_j U R D p_k \cdots p_m$, where $R = p_{j+1} \cdots p_{k-1}$. ({\it Observation 1: In the path $Q = q_1q_2 \cdots q_{m+2} = \map(Pb)$ a D-step immediately precedes the D-step $q_{k+2}$, which is the translation of the step $p_k$.} The step $q_{k+2}$ is the first step after $q_i^z=p_i^z$ for which $\mbox{\sc lev}(q_{k+2}) = \mbox{\sc lev}(q_i) - 1$; $q_j=p_j$ is now the last step before $q_{k+2}$ such that $ \mbox{\sc lev}(q_j)= \mbox{\sc lev}(q_{k+2} )-1 $. The path $R $ may be empty.) %\newpage \vspace{24pt} \begin{center} {\small \begin{tabular}{|l|l|l|l|} \hline If $P $ & $ U U U D H^x H U D D D$ & $ U H U H^y U H D D D$ & $ U U U D H^y H U D D D$ \\ \hline then & & & \\ $f(Pa) $ &$ U U U D H \underline{U^z D} H U D D D$ & $ U H U \underline{U^z} H \underline{D} U H D D D$ & $ U U U D \underline{U^z} H \underline{D} U D D D $ \\ $f(Pb) $ &$ U U^z U D H \underline{U} H U D \underline{D} D D $ & $ U H U^z H U H D \underline{H} D D$ & $ U U^z U D \underline{U} H U D \underline{D} U D D D$ \\ $f(Pc) $ &$ U U U D H \underline{H^z} H U D D D$ & $ U H U^z U H D H \underline{H} D D$ & $ U U U D^z H U D D D$ \\ \hline \end{tabular} } \vspace{12pt} \end{center} \begin{center} {\bf Table 1:} This table spells out the examples of the Figures 1 to 9 and 11 to 14. Underlining identifies inserted steps. \end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vspace{24pt} \noindent {\bf Case 1c}: If $p_j = U^x$, $H^x$, or $D^y$, $\map(Pc) = p_1 \cdots p_i \cdots p_j H^z p_{j+1} \cdots p_k \cdots p_m$. \ \noindent {\bf Case 2a}: If $ p_j = H^y$, $\map(Pa) = p_1 \cdots p_{j-1} U^z H D p_{j+1} \cdots p_m$. \ \noindent {\bf Case 2b}: If $p_j = H^y$, $\map(Pb) = p_1 \cdots p_i^z \cdots p_{j-1} UR DH p_k \cdots p_m$, where $R$ is the subpath $p_{j+1} \cdots p_{k-1}$. (Here a U-step and a D-step are inserted and the step $p_j = H$ is moved. {\it Observation 2: In the path $ Q = \map(Pb)$ {\em exactly} one H-step immediately precedes $q_{k+2}$, the translation of $p_k$.} The step $q_{j-1 } =p_{j-1 } $ is now the last step before $q_k q_{k+1} q_{k+2} = DHp_k$ such that $ \mbox{\sc lev}(q_{j-1}) = \mbox{\sc lev}(q_{k+2}) +1.$ $R $ may be empty.) \ \noindent {\bf Case 2c}: If $p_{j-1} p_j = UH^y$, $\map(Pc) = p_1 \cdots p_i^z \cdots p_{j-1} R HH p_k \cdots p_m$, where $R$ is the subpath $p_{j+1} \cdots p_{k-1}$. ({\it Observation 3: In the path $Q = \map(Pc)$, {\em at least two} H-steps immediately precede the D-step $q_{k+1}$, the translation of $p_k$.}) \ \noindent {\bf Case 3}: If $p_{j-1} p_j = HH^y$ or $DH^y$, $\map(Pc) = p_1 \cdots p_{j-1}^zp_{j+1} \cdots p_m.$ (Here $\map(Pc) \in [n-2] \times S_{n-1}$ with the marked H-step being deleted.) \ Table 1 and Figures 1 to 9 and 11 to 14 illustrate the map $\map$. By giving special attention to the three {\it Observations} in the preceding, it is straight forward to check the necessary cases to show that $\map$ is a bijection. Assigning cardinalities to the sets in the bijection given in (\ref{map}) yields the recurrence (\ref{equ2}). To prove recurrence (\ref{equ1}), simply remove all reference to the H-steps and to the tag $c$ in the proof. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The proof of recurrences (3) and (4)} Retaining the previous notions, consider the recurrence (\ref{equ4}). One can partition the region under a path and above the x-axis by copies of two isosceles right triangles whose hypotenuses have length 2 and are parallel to the x-axis. Figure 1 illustrates how these triangles of {\it unit area} uniquely partition the regions under the paths. A triangle is called an {\it up triangle} if its right angle is above its hypotenuse; otherwise, it is called a {\it down triangle}. An {\it up-triangle-strip} ({\it down-triangle-strip}, respectively) under a path of $S_n$ is a maximal array of up (down, respectively) triangles having the centers of their hypotenuses on a single line of slope $-1$ (slope $1$, respectively). It is easily seen that each path in $S_n$ has $n$ up-triangle-strips and $n-1$ down-triangle-strips. The marked triangles in Figure 2 illustrate an up-triangle-strip; those in Figure 6 illustrate a down-triangle-strip. Each {\it marked} path $P \in [2n-1] \times S_n$ determines a unique strip under $P$ as follows: If the step $p_j$ is marked by $x$, then the corresponding strip is the up-triangle-strip whose line of centers of its triangles intersects the step $p_j$. If $p_j$ is marked by $y$, then the corresponding strip is the down-triangle-strip whose line of centers of its triangles intersects the step $p_j$. In either case we designate by $6T_{P}$ six copies of the strip corresponding to the step $p_j$. \begin{figure}[p] \begin{center} \vspace{12pt} % \leavevmode\psfig{figure=sulankefig2.ps,width=5.6in} \includegraphics[width=5.6in]{sulankefig2.eps} \end{center} \vspace{12pt} \begin{center} {\bf Figures 2 through 14.} \end{center} \vfill \end{figure} In the region under any path in $S_{n+1}$ a {\it contiguous-strip}\ is a maximal array of up and down triangles having the centers of their hypotenuses on a single line of slope $-1$. Each marked path $P \in [n+1] \times S_{n+1}$ determines a unique strip under $P$, namely that contiguous-strip whose line of hypotenuse centers intersects the marked step of $P$. We designate this strip by $\tild_{P}$. The marked triangles of Figure 3 indicate a contiguous-strip. In the region under any path in $S_{n-1}$ each down triangle can always be paired with the contiguous up triangle on its right, but not visa-versa. A {\it diamond-strip}\ is a maximal array of such pairs of triangles whose common sides lie on a line of slope $1$. The marked step of each path $P \in [n-2] \times S_{n-1}$ determines a unique diamond-strip under $P$, namely the diamond-strip whose line of common sides intersects the final point of the z-marked step of $P$. We designate this diamond-strip by $\hatt_{P}$. The marked triangles of Figure 14 indicate a diamond-strip. Under a path $P \in [n-2] \times S_{n-1}$, any up triangle that is not contiguous along its left side with a down triangle is viewed as an {\it isolated-triangle}. Figure 10 illustrates an isolated-triangle. Since the left side of each isolated-triangle is a U-step of $P$ and conversely, each U-step, say $p_h$, uniquely matches an isolated-triangle that we designate by $\barr_{P,h}$. The disjoint collection of strips and isolated-triangles $$\left( \bigcup_{P \in [n-2] \times S_{n-1}} \{ \hatt_{P} \} \right) \bigcup \left( \bigcup_{P \in S_{n-1}}\bigcup_{ h \in u(P)} \{ \barr_{P,h} \} \right)$$ partitions the total region under the paths in $S_{n-1}$, where $u(P)$ is the set of the positions of the U-steps on $P$. To construct a function that yields a combinatorial proof of recurrence (\ref{equ4}), consider defining $$ \MAP :\bigcup_{P \in [2n-1] \times S_n } \{6T_{P} \} \rightarrow \cal{T} \bigcup \cal{Q} $$ where the elements of $\cal{T}$ and $\cal{Q}$ will be ordered triples and ordered quadruples, respectively, of mutually non overlapping strips partitioning the total region lying under the paths of $S_{n+1}$ and $S_{n-1}$. With $P$ being an arbitrary path as in (\ref{suppose}), the bijection $\map$ induces a function $\MAP$ so that \noindent {\bf Case i:} if $p_j = U^x$, $H^x$, or $D^y$, define $$\MAP(6T_{P}) = (\tild_{\map(Pa)}, \tild_{\map(Pb)} , \tild_{\map(Pc)}) . $$ \noindent {\bf Case ii:} if $p_{j-1} p_j = p_ip_j = UH^y$, define $$\MAP(6T_{P}) =( \tild_{\map(Pa)} , \tild_{\map(Pb)} , \tild_{\map(Pc)}, \barr_{R, i }), $$ where $R = p_1 \cdots p_{i} p_{i + 2} \cdots p_m$. \noindent {\bf Case iii:} if $p_{j-1} p_j = HH^y$ or $DH^y$, define $$\MAP(6T_{P}) = ( \tild_{\map(Pa)} , \tild_{\map(Pb)}, \hatt_{\map(Pc)} ). $$ The mapping of six copies of the strip of Figure 2 to those of Figures 3 to 5 illustrates Case i. Likewise Figure 6 with Figures 7 to 10 illustrates Case ii, and Figure 11 with Figures 12 to 14 illustrates Case iii. Notice that each column of the array of figures shows the 6-fold transfer of area. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5 The function $\map$ being bijective implies $\MAP$ is bijective. The following three items can be routinely checked to show that $\MAP$ transfers area as claimed. Here $\mbox{A}(T)$ denotes the area of an arbitrary strip $T$. For \noindent {\bf Case i}, $(\mbox{A}(\tild_{\map(Pa)}), \mbox{A}(\tild_{\map(Pb)}), \mbox{A}( \tild_{\map(Pc)})) = (2\mbox{A}(T_{P}) +1 , 2\mbox{A}( T_{P}) - 1, 2\mbox{A}( T_{P}) )$; \noindent {\bf Case ii}, $(\mbox{A}( \tild_{\map(Pa)}), \mbox{A}( \tild_{\map(Pb)} ), \mbox{A}(\tild_{\map(Pc)}), \mbox{A}( \barr_{R,j})) = (2\mbox{A}(T_{P}) +1 , 2\mbox{A}( T_{P}) - 1, 2\mbox{A}( T_{P}) - 1, 1 )$; \noindent {\bf Case iii}, $(\mbox{A}( \tild_{\map(Pa)}), \mbox{A}(\tild_{\map(Pb)}), \mbox{A}( \hatt_{\map(Pc)})) = (2\mbox{A}(T_{P}) +1 , 2\mbox{A}( T_{P}) - 1, 2\mbox{A}( T_{P}) )$; \ Finally to prove recurrence (\ref{equ3}) we remove all reference to H-steps and the tag c in this proof. \section{Notes} 1. The following corollary of the construction of the function $\map$ originated as a fortuitous observation resulting in the definition for the crucial Case 3: {\it For $n \geq 2$, there are $(n-2)r_{n-1}$ step pairs of the form $DH$ or $HH$ on the totality of paths of $S_n$.} 2. One of the more interesting of the many references to the Catalan numbers is Stanley's \cite{StanleyBook} collection of 66 combinatorial interpretations of these numbers. His book \cite{StanleyBook} lists other primary references in the vast literature for these numbers. 3. In lieu of the three step types employed in this paper, the step types $(0,1)$, $(1,0)$, and $(1,1)$ are the usual step types defining Schr{\"o}der paths. For the latter three types, clearly the Schr{\"o}der number $r_n$ counts the paths running from $(0,0)$ to $(n-1,n-1)$ and never passing below the line $y=x$. In an early paper on paths with such step types Moser and Zayachkowski \cite{Moser}, realizing that the number of unrestricted paths from $(0,0)$ to $(n,n)$ is a Legendre polynomial evaluated at 3, used a recurrence for these polynomials to derive essentially recurrence (\ref{equ2}). 4. We use ``$r_n$'' for the large (or {\it double} as in \cite{KreAires}) Schr{\"o}der numbers since $s_n = r_n/2$ for $n\geq 2$ with $s_1 = 1$ is reserved for the so-called {\it small Schr{\"o}der numbers}: $1, 1, 3, 11, 45,\ldots$. Ernst Schr{\"o}der formulated these numbers in the second problem of his 1870 paper \cite{Schroder}: In how many ways can one or more pairs of brackets be legally placed in $z_1, z_2 \cdots z_n $? For instance, when $n = 3$, there are the three bracketings, $(z_1 z_2 z_3)$, $((z_1 z_2) z_3)$, and $(z_1( z_2 z_3)) $. The problem of enumerating bracketings is equivalent both to the problem of enumerating dissections of convex polygons and to the problem of enumerating Schr{\"o}der trees with a fixed number of leaves. (A Schr{\"o}der tree is a plane trees whose internal nodes have at least two children.) As noted in \cite{StanleyMon}, David Hough discovered that the small Schr{\"o}der numbers were apparently known to Hipparchus in the second century B.C. as counting certain logical propositions. The papers \cite{BSS,PergolaSul,RogersLadder,rogersSchTri,RogersShapiro,StanleyMon,SulCat} form a selection of the studies concerning the Schr{\"o}der numbers. Of particular interest is the result of Rogers and Shapiro, appearing implicitly in \cite{RogersLadder,RogersShapiro}, and later the result of Bonin, Shapiro, and Simion \cite{BSS}, that give combinatorial maps relating the enumeration of bracketings to the enumeration of lattice paths of $S_n$. 5. A {\it well-weighted binary plane tree} is a binary tree where each node having a right internal child is labeled with a 1 or a 2. Foata and Zeilberger \cite{FZ}, after giving a rather simple bijection between Schr{\"o}der trees and well-weighted binary plane trees, showed bijectively that the small Schr{\"o}der numbers satisfy $(n+1) s_{n+1} = 3(2n- 1) s_{n} - (n-2) s_{n-1}$ with the conditions $s_1=1$, and $s_2=1$. Their proof is not isomorphic to our proof of (\ref{equ2}); this is not surprising since the bijections mentioned at the end of Note 3 between bracketings and $S_n$ do not seem to be trivial. 6. In this and the next note define sequence $AS_n$ purely as the one satisfying the formal recurrence (\ref{equ4}), not specifically in terms of lattice paths. Barcucci, Brunetti, Del Lungo, and Del Rietoro \cite{BarcucciNew} recently gave a combinatorial interpretation of formal recurrence (\ref{equ4}) in terms of a regular language. In \cite{Martin} the sequence $AS_n$ is related to solutions of the diophantine equation, $x^2 +(x+1)^2 = y^2$, with $x = (AS_n-1)/2$. Newman, Shanks, and Williams \cite{NSW} found that the numbers $AS_n$ correspond to the orders of certain simple groups. 7. The author \cite{Sul3Rec} has considered the formal recurrences (\ref{equ1}) to (\ref{equ4}) bijectively in terms of parallelogram polyominoes. For $n\geq 2$, let $p_{\alpha,n}(w) = \sum_k p_{\alpha,n,k}w^k $, where $p_{0,n,k} $ denotes the number of parallelogram polyominoes with perimeter $2n$ and width $k$, and where $(n-1)p_{1,n,k}$ denotes the total area of such polyominoes. The paper \cite{Sul3Rec} shows that the sequences $p_{0,n}(w)$ and $p_{1,n}(w)$ satisfy the recurrences $$(n +1-\alpha)p_{\alpha,n+1}(w) = (2n-1 -\alpha)(1+w)p_{\alpha,n}(w) - ( n-2 ) (1-w)^2 p_{\alpha,n-1}(w), $$ with initial conditions $p_{\alpha,2}(w) = w$, $p_{\alpha,3}(w) = w+w^2$. The proof for the case $\alpha = 0$ in \cite{Sul3Rec} is isomorphic to the proof in \cite{FZ}, but not to the proof of Section 2. More specifically, the total area $ (n-1)p_{1,n}(1)$ is $4^{n-2}$; this result was recently derived by interesting generating-function argument by Woan, Shapiro, and Rogers \cite{WSR}. The product $ (n-1)p_{1,n}(2)$, corresponding to the sum of the areas of polyominoes having bi-colored columns, satisfies the recurrence $ np_{1,n+1}(2) = 6(n-1)p_{1,n}(2)- (n-2)p_{1,n-1}(2)$ with early values $(n-1)p_{1,n}(2) = 1, 6, 35, 204, 1189, \ldots$, for $n= 2,3,4,5,6 \ldots$. These polynomial sequences, $p_{\alpha,n}(w)$, generalize other well-known sequences: e.g., $\{ p_{0,n}(1) \}_{n \geq 2 }$ are the Catalan numbers, $\{ p_{0,n}(2) \}_{n \geq 2 } $ are the large Schr{\"o}der numbers, $\{((n-1) p_{1,n}(2)/2)^2 \}_{n \geq 2 }$ are the square-triangular numbers, and $\{ p_{2,n}(1) \}$ are the central binomial coefficients. 8. Recently, Merlini, Sprugnoli, and Verri \cite{MSV} used generating function methods in determining the sum of the areas bounded by constrained lattice paths belonging to sets that essentially generalize $C_n$ and $S_n$. The paper \cite{MSV} also contains additional relevant references to the literature. \bibliographystyle{plain} \begin{thebibliography}{1} \bibitem{BarcucciNew} E. Barcucci, S. Brunetti, A. Del Lungo, and F. Del Rietoro, A combinatorial interpretation of the recurrence $f_{n+1} = 6f_{n} - f_{n-1}$, {\it Discrete Math.}, 190 (1998) 235-240. \bibitem{BSS} J. Bonin, L. Shapiro, and R. Simion, Some {\it q}-analogues of the Schr{\"o}der numbers arising from combinatorial statistics on lattice paths, {\it J. Statistical Planning and Inference} 34 (1993) 35-55. \bibitem{FZ} D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, {\it J. Comb. Theor., Ser. A.}, 80 (1997), 380-384.\\ Available at http://www.math.temple.edu/\~{}zeilberg/papers1.html. \bibitem{KreAires} G. Kreweras, Aires des chemins surdiagonaux a {\'e}tapes obliques permises. {\it Cahier du B.U.R.O.} 24 (1976) 9-18. \bibitem{Martin} A. Martin, Diophantine analysis (Solutions of Problems), {\it Am. Math. Monthly}, 4 (1897) 24-25. \bibitem{MSV} D. Merlini, R. Sprugnoli, and M. C. Verri, The area determined by underdiagonal lattice paths, {\it Discrete Math.,} to appear. \bibitem{Moser} L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, {\it Scripta Math.}, 26 (1963) 223-229. \bibitem{NSW} M. Newman, D. Shanks and H. C. Williams, Simple groups of square order and an interesting sequence of primes, {\it Acta Aritmetica} XXXVIII (1980) 129-140. \bibitem{PergolaSul} E. Pergola and R. A. Sulanke, Schr{\"o}der triangles, paths, and parallelogram polyominoes, {\it Journal of Integer Sequences}, Vol. 1 (1998), Available at http://www.research.att.com/\~{}njas/sequences/JIS/ \bibitem{Remy} J-L R{\'e}my, Un proc{\'e}d{\'e} it{\'e}ratif de d{\'e}nombrement d'arbres binaires et son application {\`a} leur g{\'e}n{\'e}ration al{\'e}atpoire, {\it RAIRO Inform. Th{\'e}or.,} vol 19 (1985) 179 - 195. \bibitem{rogersSchTri} D. G. Rogers, A Schr{\"o}der triangle, {\it Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference. Lecture Notes in Mathematics,} vol 622, Springer-Verlag, Berlin (1977) 175-196. \bibitem{RogersLadder} D. G. Rogers, The enumeration of a family of ladder graphs part II: Schr{\"o}der and superconnective relations, {\it Quart. J. Math. Oxford} (2) 31 (1980) 491-506. \bibitem{RogersShapiro} D. G. Rogers and L. Shapiro, Some correspondences involving the Schr{\"o}der numbers, {\it Combinatorial Mathematics: Proceedings of International Conference, Canberra, 1977. Lecture Notes in Math.} 686, Springer-Verlag (1978) 267-276. \bibitem{Schroder} E. Schr{\"o}der, Vier kombinatorische probleme, {\em Z. Math. Phys.} 15 (1870) 361 - 376. \bibitem{StanleyBook} R. P. Stanley, {\it Enumerative Combinatorics}, Vol. 2, Cambridge University Press, 1999 (tentative) \bibitem{StanleyMon} R. P. Stanley, Hipparchus, Plutarch, Schr{\"o}der, Hough, {\it Am. Math. Monthly}, 104 (1997) 344 - 350. \bibitem{SulCat} R. A. Sulanke, A recurrence restricted by a diagonal condition: generalized Catalan array, {\it Fibonacci Q.}, 27 (1989) 33 - 46. \bibitem{Sul3Rec} R. A. Sulanke, Three recurrences for parallelogram polyominoes, {\it J. of Difference Eq. and its Appl.}, (1998 tentative)\\ Available at http://diamond.idbsu.edu/\~{}sulanke/recentpapindex.html \bibitem{WSR} W-J Woan, L. Shapiro, and D. G. Rogers, The Catalan numbers, the Lebesgue integral and $4^{n-2}$, {\it Am. Math. Monthly}, 104 (1997) 926 - 931. \end{thebibliography} \end{document}