%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%A LaTex file for a 9 pages document%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \input{psfig.sty} \hsize=6in \vsize=9in %\textwidth 16.0cm %\textheight 24.0cm \topmargin -1.0cm \oddsidemargin 0.8cm \def\ZZ{{\rm Z\kern -4.0pt{\rm Z}}} \def\IN{\hbox{I\kern-.25em\hbox{N}}} \newcommand{\proof}{\ \\ {\bf Proof.}\ \ } \newcommand{\fineproof}{\hfill \fbox{} \\} \newtheorem{teor}{Theorem}[section] \newtheorem{defi}[teor]{Definition} \newtheorem{prop}[teor]{Proposition} \newtheorem{cor}[teor]{Corollary} \newtheorem{lem}[teor]{Lemma} \newtheorem{rem}{Remark}[section] \newtheorem{ex}{\rm \bf {Example}}[section] \def\theequation{\arabic{equation}} \begin{document} \setlength{\unitlength}{0.1cm} \title{\bf \LARGE{A Combinatorial Interpretation of the Area of Schr\"oder Paths }} \author{E. Pergola, R. Pinzani\\ {\small\texttt{Dipartimento di Sistemi e Informatica, Universit{\`a} di Firenze, }}\\ {\small\texttt{Via Lombroso 6/17, 50134 Firenze, Italy,}}\\ {\small\texttt{e-mail: elisa@dsi.unifi.it, pinzani@dsi.unifi.it}}\\ Submitted: September 3, 1999; Accepted: October 14, 1999.} \date{} \maketitle \begin{abstract} An elevated Schr\"oder path is a lattice path that uses the steps $(1,1)$, $(1,-1)$, and $(2,0)$, that begins and ends on the $x$-axis, and that remains strictly above the $x$-axis otherwise. The total area of elevated Schr\"oder paths of length $2n+2$ satisfies the recurrence $f_{n+1}=6f_n-f_{n-1}$, $n \geq 2$, with the initial conditions $f_0=1$, $f_1=7$. A combinatorial interpretation of this recurrence is given, by first introducing sets of unrestricted paths whose cardinality also satisfies the recurrence relation and then establishing a bijection between the set of these paths and the set of triangles constituting the total area of elevated Schr\"oder paths. \end{abstract} \section{Introduction}\ \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 6 (1999),\#R40\hfill} \thispagestyle{empty} In the plane \ZZ $\times$ \ZZ, we will use lattice paths with three steps types: a {\em rise step} defined by $(1,1)$, a {\em fall step} defined by $(1,-1)$, and a {\em horizontal step} defined by $(2,0)$. A Schr\"oder path is a sequence of rise, fall and horizontal steps running from $(0,0)$ to (2n,0) and remaining weakly above the $x$--axis. These paths are counted by the large Schr\"oder numbers, denoted by $r_n$. The first few entries of the sequence $\left\{r_n\right\}_{n \geq 0}$ are: $1,2,6,22,90,394,\ldots$ (sequence M1659 in \cite{10}) and their generating function is $\sum \limits_{n \geq 0} r_nt^n=\frac{1-t-\sqrt{1-6t+t^2}}{2t}$. For other combinatorial objects counted by the Schr\"oder numbers, see \cite{22,15,20,17,21,18,5,19}. An {\em elevated Schr\"oder path} is the path obtained from a Schr\"oder path by adding a rise step at its beginning and a fall step at its end. In the sequel, we denote ${\cal S}_{2n}$ the class of elevated Schr\"oder paths of length $2n$. We wish to use the area under Schr\"oder paths to consider the combinatorial significance of the recurrence: \begin{center} \vspace{-0.4in} \begin{equation} \label{equazione1} f_{n+1}=6f_n-f_{n-1},\ \ \ n \geq 2, \end{equation} \end{center} subject to the initial conditions $f_0=1$, $f_1=7$. This recurrence defines a sequence whose first terms are: $1,7,41,239,1393,\ldots$ (sequence M4423 in \cite{10}). These numbers are known as NSW numbers, and are related both to the order of simple groups \cite{11} and to the solutions of the Diophantine equation: $x^2+(x+1)^2=y^2$ \cite{12}. We will obtain a new bijective proof for this recurrence in terms of the area of Schr\"oder paths. In 1976 Kreweras \cite{13} proved that the sum of the areas of the regions lying under the elevated Schr\"oder paths satisfies recurrence (\ref{equazione1}). Specifically, \begin{prop} If $A_n$ denotes the total area of the regions lying below the elevated Schr\"oder paths of length $2n+2$ and the $x$-axis, then $A_n$ satisfies the recurrence $A_{n+1}=6A_n-A_{n-1}$, subject to the initial conditions $A_0=1$, $A_1=7$. \label{proposizione1} \end{prop} Bonin et al. \cite{2} asked for the combinatorial interpretation of $f_{n+1}=6f_n-f_{n-1}$ with the phrase: ``{\em The recurrence $f_{n+1}=6f_n-f_{n-1}$ cries out for a combinatorial interpretation}''. Barcucci et al. \cite{1} gave the first answer using a regular language defined so that the number of words having length $n$ is equal to $f_{n+1}$. Sulanke \cite{3} gave a combinatorial interpretation of the recurrence in terms of total area of elevated Schr\"oder paths. In this paper, we present another combinatorial interpretation proving Proposition \ref{proposizione1}. We remark that our analysis naturally applies to elevated Dyck paths of length $2n$ where the total area $A_n$ satisfies $A_n=4A_{n-1}$, and hence is $4^{n-1}$. \newpage \section{An auxiliary path class}\ Let ${\cal V}_n$ denote the set of all unrestricted lattice paths that run from $(0,0)$ to the line $x = 2n+1$ and that use the steps $(1,1)$, $(1,-1)$ , and $(2,0)$ and that do not end with a rise step. The first stage of our proof of Proposition \ref{proposizione1} will use \begin{prop} The cardinality $v_n$ of the set ${\cal V}_n$ satisfies the recurrence relation (\ref{equazione1}) subject to the given initial conditions. \label{proposizione2} \end{prop} \proof The initial conditions are trivial to check. To prove that $\left\{ v_n \right\}_{n \geq 0}$ increases according to the recurrence (\ref{equazione1}), we apply $6$ different operations to the paths in ${\cal V}_n$ and establish a construction for ${\cal V}_{n+1}$ if and only if some particular paths are removed. We pass from a path $P \in {\cal V}_n$ to a path $P^{'} \in {\cal V}_{n+1}$ by: \begin{enumerate} \item adding a pair of rise steps at the beginning of $P$ (see Figure \ref{figura4}, ({\it 1})), \item adding a rise step followed by a fall step at the beginning of $P$ (see Figure \ref{figura4}, ({\it 2})), \item adding a pair of fall steps at the beginning of $P$ (see Figure \ref{figura4}, ({\it 3})), \item adding a fall step followed by a rise step at the beginning of $P$ (see Figure \ref{figura4}, ({\it 4})), \item adding a horizontal step at the beginning of $P$ (see Figure \ref{figura4}, ({\it 5})), \item inserting a horizontal step after the first step of $P$ (see Figure \ref{figura4}, ({\it 6})). \end{enumerate} The paths obtained by performing the above described operations lie in ${\cal V}_{n+1}$, and moreover, each $P^{'} \in {\cal V}_{n+1}$ is obtained from some $P \in {\cal V}_{n}$. However, some paths in ${\cal V}_{n+1}$ are obtained twice. They are precisely those paths beginning with two consecutive horizontal steps obtained under operations 5 and 6. The proof is completed by seeing that the set of paths beginning in a horizontal step is immediately obtained by adding a first horizontal step to the paths in ${\cal V}_{n-1}$, which has cardinality $v_{n-1}$. \fineproof Next we partition ${\cal V}_n$ into three sets. The paths in ${\cal V}^{(-1)}_n$ have final ordinate $(-1)$ and end with a fall step, they are counted by the Delannoy numbers \cite[p. 81]{15}. Let ${\cal V}^{\uparrow}_n$ denote the subset of paths that have positive final ordinate. Let ${\cal V}^{\downarrow}_n$ denote the complement ${\cal V}_n - {\cal V}^{(-1)}_n - {\cal V}^{\uparrow}_n$ . \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura4bis.pstex,width=10cm}} \vspace{-0.1in} \caption{\label{figura4}The six different operations to pass from ${\cal V}_n$ to ${\cal V}_{n+1}$. } \end{center} \end{figure} Taking a path in ${\cal V}^{\uparrow}_n$ into consideration, we remove its last step, take the reflection in the horizontal axis and reinsert the removed last step (see Figure \ref{figura14}). Hence, \begin{lem} There is a bijection between ${\cal V}^{\uparrow}_n$ and ${\cal V}^{\downarrow}_n$. \label{lemma1} \end{lem} \section{A bijection between triangles and paths of \mbox{\boldmath ${\cal V}_n$}}\ Consider the region bounded by a path $P$ and the $x$--axis. Let $a(P)$ denote the area of that region. We will take as our measure unit a triangle whose vertex coordinates are either $(x,y)$, $(x+1,y+1)$, and $(x+2,y)$ or $(x,y)$, $(x-1,y+1)$, and $(x+1,y+1)$. We call the first type an {\it up triangle} and the second type a {\it down triangle}. Figure \ref{figura1} shows an elevated Schr\"oder path of length $16$ and area $25$. Let $A_n=\sum \limits_{P \in {\cal S}_{2n}} a(P)$, i.e., $A_n$ is the total area of elevated Schr\"oder paths having length $2n$ (see Figure \ref{figura2}). \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura14.pstex,width=10cm}} \vspace{-0.1in} \caption{\label{figura14}The bijection between ${\cal V}^{\uparrow}_n$ and $ {\cal V}^{\downarrow}_n$. } \end{center} \end{figure} \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura1.pstex,width=10cm}} \vspace{-0.1in} \caption{\label{figura1}An elevated Schr\"oder path. } \end{center} \end{figure} \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura2.pstex,width=15cm}} \vspace{-0.1in} \caption{\label{figura2}The $6$ elevated Schr\"oder paths of ${\cal S}_6$ and $A_3=41$. } \end{center} \end{figure} We can partition the triangles decomposing the total region of the $(2n+2)$--length elevated Schr\"oder paths into three sets. The set ${\cal T}_1^{(n)}$ contains the up triangles that touch the path by their right side. The set ${\cal T}_2^{(n)}$ contains the up triangles that do not touch the path by their right side, and the set ${\cal T}_3^{(n)}$ contains the down triangles (see Figure \ref{figura7}). \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura7.pstex,width=12cm}} \vspace{-0.1in} \caption{\label{figura7}The partition of the area of a $(2n+2)$--length elevated Schr\"oder path. } \end{center} \end{figure} It is easily seen that each triangle in ${\cal T}_2^{(n)}$ has on its right a triangle in ${\cal T}_3^{(n)}$, and that every triangle in ${\cal T}_3^{(n)}$ is so obtained. Hence, \begin{lem} There is a bijection between ${\cal T}_2^{(n)}$ and ${\cal T}_3^{(n)}$. \label{lemma2} \end{lem} We will now give constructions that establish: \begin{lem} There are bijections between the following pairs: \begin{itemize} \item ${\cal T}_1^{(n)}$ and ${\cal V}_n^{(-1)}$, \item ${\cal T}_2^{(n)}$ and ${\cal V}_n^{\uparrow}$, \item ${\cal T}_3^{(n)}$ and ${\cal V}_n^{\downarrow}$. \end{itemize} \end{lem} \proof \ {\bf A bijection from the triangles in \mbox{\boldmath ${\cal T}_1^{(n)}$} to the path in \mbox{\boldmath ${\cal V}^{(-1)}_n$}}\ Suppose that $(x,y)$, $(x+1,y+1)$, and $(x+2,y)$ are the vertices of a triangle in ${\cal T}_1^{(n)}$ under an elevated Schr\"oder path $P \in S_{2n+2}$. Let $Q$ denote the point $(x+2,y)$. To obtain the corresponding path in ${\cal V}^{(-1)}_n$ first delete the initial rise step of $P$ and then transpose the subpath of $P$ that follows $Q$ with the modified subpath that precedes $Q$. (see Figure \ref{figura8}). \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura8.pstex,width=10cm}} \vspace{-0.1in} \caption{\label{figura8}A pointed triangle in ${\cal T}_1^{(n)}$ and the corresponding path in ${\cal V}^{(-1)}_n$. } \end{center} \end{figure} \clearpage \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura11.pstex,width=12cm}} \vspace{-0.1in} \caption{\label{figura11}A path in ${\cal V}_n^{(-1)}$ and the corresponding pointed triangle in ${\cal T}_1^{(n)}$. } \end{center} \end{figure} \ This construction can be inverted as follows. For any path in ${\cal V}_n^{(-1)}$ (see Figure \ref{figura11} {\em (a)}), the leftmost point in the path having least ordinate, say $Q^{'}$, determines two paths, the one on its left and the one on its right. We place the desired triangle to lie just below the last step of the path as showed in Figure \ref{figura11} {\em (b)}. The two paths are transposed, together with the desired triangle, and a rise step is added at the beginning (see Figure \ref{figura11} {\em (c)}). \ \\ {\bf A bijection from the triangles in \mbox{\boldmath ${\cal T}_2^{(n)}$} to the paths in \mbox{\boldmath ${\cal V}^{\uparrow}_n$}}\ Suppose that $(x,y)$, $(x+1,y+1)$, and $(x+2,y)$ define a triangle in ${\cal T}_2^{(n)}$ under an elevated Schr\"oder path $P \in S_{2n+2}$. We draw a line of slope 1 from the point $(x+2,y)$. This line meets the path $P$ for the first time at a point on $P$, labeled $Q$. Next we draw $y+1$ horizontal rays to the right from the center of the chosen triangle and from the center of each triangle beneath it. Each of these rays meets, for the first time, a fall step in $P$ which we change into a rise step. We then delete the initial rise step and transpose the modified subpath following $Q$ with the modified subpath preceding $Q$ to obtain a path in ${\cal V}^{\uparrow}_n$. (see Figure \ref{figura9}). \begin{figure}[htp] \begin{center} \mbox{\psfig{file=figura9.pstex,width=10cm}} \vspace{-0.1in} \caption{\label{figura9}A pointed triangle in ${\cal T}_2^{(n)}$ and the corresponding path in ${\cal V}^{\uparrow}_n$. } \end{center} \end{figure} \ To see the inversion of this construction consider a path in ${\cal V}_n^{\uparrow}$ with final ordinate $2y+1$, $ y \geq 0$, (see Figure \ref{figura12} {\em (a)}). Let $q$ be the ordinate of the rightmost point in the path having least ordinate. {}From each of the points in the set $\{ ( 2n+2, q+ i-0.5 ) | 1 \leq i \leq y+1 \} $ draw a horizontal ray to the left. These rays hit the path for a first time at $y+1$ rise steps as shown in Figure \ref{figura12} {\em (b)}. The final end point of the $(y+1)$--th rise step, say $Q^{'}$, determines two paths: one on its left and one on its right (see Figure \ref{figura12} {\em (b)}). We place the desired up triangle with its rightmost vertex determined by the intersection of the horizontal line of ordinate $q+2y$ and the line of slope 1 passing from the final point of the original path (see Figure \ref{figura12} {\em (b)}). This triangle is rigidly attached to the path on the right of $Q^{'}$. In the particular case of $y=0$ the rise step which must be changed into fall step is the left side of the triangle, and the rise step that has to be added at the beginning of the path covers the left side of the triangle. Once the $y+1$ rise steps that were hit have been changed into fall steps, the two resulting subpaths are transposed, along with the desired triangle, as showed in Figure \ref{figura12} {\em (c)} and a rise step is added at the beginning. Simple geometric considerations show that the resulting path is an elevated Schr\"oder path. \ The third part of the lemma follows from the previous parts and Lemmas \ref{lemma1}, \ref{lemma2}. \fineproof Figure \ref{figura17} shows the bijection between the triangles constituing the total area of $2$-- and $4$--length Schr\"oder paths and the paths in ${\cal V}_0$ and ${\cal V}_1$, respectively. Proposition \ref{proposizione1} is now a consequence of Proposition \ref{proposizione2} and the above lemma. \begin{figure}[thb] \begin{center} \mbox{\psfig{file=figura12.pstex,width=12cm}} \vspace{-0.1in} \caption{\label{figura12}A path in ${\cal V}_n^{\uparrow}$ and the corresponding pointed triangle in ${\cal T}_2^{(n)}$. } \end{center} \end{figure} \begin{figure}[thb] \begin{center} \mbox{\psfig{file=figura17.pstex,width=10cm}} \vspace{-0.1in} \caption{\label{figura17}The bijection between triangles and paths in ${\cal V}_n$, $n=0,1$. } \end{center} \end{figure} \section*{Acknowledgements}\ The authors wish to thank R. A. Sulanke for carefully reading the manuscript and giving them many useful suggestions and the anonymous referee for his valuable remarks. \begin{thebibliography}{99} \bibitem{1} E. Barcucci, S. Brunetti, A. Del Lungo, F. Del Ristoro, A combinatorial interpretation of the recurrence $f_{n+1}=6f_n-f_{n-1}$, {\it Discrete Mathematics}, 190 (1998) 235--240. \bibitem{22} E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani, Some Combinatorial Interpretations of $q$--Analogs of Schr\"oder Numbers, {\it Annals of Combinatorics}, 3 (1999) 173--192. \bibitem{2} J. Bonin, L. Shapiro, R. Simion, Some $q$--analogues of the Schr\"oder numbers arising from combinatorial statistics on lattice paths, {\it Journal of Statistical Planning and Inference}, 34 (1993) 35--55. \bibitem{15} L. Comtet, {\it Advanced Combinatorics}, D. Reidel, Dordrecht (1974). %\bibitem{24} %A. Dvoretzky, T. Motzkin, A problem of arrangements, {\it Duke Mathematical %Journal}, 14 (1947) 305--313. %\bibitem{4} %I. P. Goulden, D. M. Jackson, {\it Combinatorial Enumerration}, John Wiley \& %Sons, New--York (1983). \bibitem{20} D. Gouyou--Beauchamps, B. Vauquelin, Deux propri\'et\'es combinatoires des nombres de Schr\"oder, {\it Theoretical Informatics and Applications}, 22 (1988) 361--388. \bibitem{17} D. Knuth, {\it The Art of Computer Programming}, Vol. 1: Fundamental Algorithms (second edition), Addison Wesley, Reading, MA (1973). \bibitem{13} G. Kreweras, Aires des chemins surdiagonaux a \'etapes obliques permises, {\it Cahiers du B.U.R.O.}, 24 (1976) 9--18. \bibitem{12} M. A. Gruber et al., Problem $47$, {\it American Mathematical Monthly}, 4 (1897) 24--28. \bibitem{11} M. Newman, D. Shanks, H. C. Williams, Simple groups of square order and an interesting sequence of primes, {\it Acta Aritmetica XXXVIII} (1980) 129--140. %\bibitem{d} %D. Merlini, R. Sprugnoli, M. C. Verri, The area determined by underdiagonal %lattice paths, {\it Discrete Mathematics},............. %\bibitem{7} %J. G. Penaud, E. Pergola, R. Pinzani, O. Roques, Chemins de Schr\"oder et %hi\'erarchies al\'eatoires, {\it Theoretical Computer Science} (to appear). \bibitem{21} E. Pergola, R. A. Sulanke, Schr\"oder triangles, paths, and parallelogram polyominoes, {\it Journal of Integer Sequences}, Vol. 1 (1998) \bibitem{18} D. G. Rogers, L. Shapiro, Some correspondences involving the Schr\"oder numbers and relations, {\it Lecture Notes in Mathematics}, Vol. 686, Springer--Verlag, New--York Heidelberg Berlin (1978) 267--274. \bibitem{5} D. G. Rogers, L. Shapiro, Deques, trees and lattice paths, {\it Lecture Notes in Mathematics}, Vol. 884, Springer--Verlag, New--York Heidelberg Berlin (1981) 293--303. \bibitem{19} L. Shapiro, A. B. Stevens, Bootstrap percolation, the Schr\"oder numbers, and the $n$--kings problem, {\it SIAM Journal on Discrete Mathematics}, 4 (1991) 275--280. \bibitem{10} N. J. A. Sloane, S. Plouffe, {\it The Encyclopedia of Integer Sequences}, Academic Press, New--York (1995). %\bibitem{6} %R. P. Stanley, Hipparchus, Plutarch, Schr\"oder, and Hough, {\it American %Mathematical Montly}, 104(4) (1997) 344-350. \bibitem{3} R. A. Sulanke, Bijective recurrences concerning Schr\"oder paths, {\it Electronic Journal of Combinatorics} \textbf{5} (1998), \# R47. \end{thebibliography} \end{document}