% This paper uses figures created with TikZ % (http://www.texample.net/tikz/examples/), which not everyone has % available in their TeX setup. I've included precompiled .eps and .pdf % files, though, so you can typeset this whether or not you have TikZ. % % The advantage to using TikZ instead of the included .eps and .pdf % files is that the font used in the figures will precisely match the % text and the generated Postscript and PDF files will be smaller. % % If your TeX setup doesn't have TikZ, you can use the .eps and .pdf % files as usual. \newif\ifhavetikz % Uncomment exactly one line below, as appropriate: %\havetikztrue \havetikzfalse % Rest of preamble follows...you shouldn't need to change anything % below. \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{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{xspace} \usepackage{subfig} \usepackage{ifthen} \usepackage{geometry} %\usepackage[pdfauthor={Dan Drake}, pdftitle={Bijections from weighted % Dyck paths to Schroeder paths}]{hyperref} \ifhavetikz \usepackage{tikz} \usetikzlibrary{decorations,decorations.pathmorphing,arrows} % for drawing lattice paths: \pgfdeclarelayer{background} \pgfsetlayers{background,main} \tikzset{pathfragment/.style={scale=1.0, local bounding box=bbox, execute at end scope= {\begin{pgfonlayer}{background} \draw[help lines] (bbox.south west) grid (bbox.north east); \end{pgfonlayer}}}} \tikzset{pathstep/.style={thick}} \newcommand{\startpathat}[2]{ \pgfmathsetmacro{\x}{#1} \pgfmathsetmacro{\y}{#2}} \newcommand{\up}{ \filldraw (\x,\y) circle (2pt); \draw[pathstep] (\x,\y) -- ++(1,1); \pgfmathsetmacro{\x}{\x + 1} \pgfmathsetmacro{\y}{\y + 1} \filldraw (\x, \y) circle (2pt);} \newcommand{\down}{ \filldraw (\x,\y) circle (2pt); \draw[pathstep] (\x,\y) -- ++(1,-1); \pgfmathsetmacro{\x}{\x + 1} \pgfmathsetmacro{\y}{\y - 1} \filldraw (\x, \y) circle (2pt);} \newcommand{\spdown}{ \filldraw[green] (\x,\y) circle (2pt); \draw[pathstep,green] (\x,\y) -- ++(1,-1); \pgfmathsetmacro{\x}{\x + 1} \pgfmathsetmacro{\y}{\y - 1} \filldraw[green] (\x, \y) circle (2pt);} \newcommand{\horiz}{ \filldraw (\x,\y) circle (2pt); \draw[pathstep] (\x,\y) -- ++(2,0); \pgfmathsetmacro{\x}{\x + 2} \filldraw (\x, \y) circle (2pt);} % for matchings: \tikzstyle{vertex}=[circle, draw=black, fill=black, inner sep=1] \newcommand{\drawedge}[3][]{\draw (#2) to [out=75, in=105, looseness=1.5, #1] (#3);} % common optional args to \drawedge: "dashed"; "in=nnn", out=nnn", (degrees) % "looseness=x" % for "externalizing" graphics; section 63 of manual \pgfrealjobname{dyck-schroeder} \else \usepackage{graphicx} \usepackage{color} \fi \newcommand{\inputtikz}[1]{ \ifhavetikz \input{tikz/#1.tex} \else \includegraphics{tikz/#1-out} \fi} \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}}} % amsmath claims that \MR provides hyperlinks to MathSciNet, but it doesn't. \newcommand{\MR}[1]{\href{http://www.ams.org/mathscinet-getitem?mr=#1}{MR~#1}} % make \autoref work with subfigures \newcommand{\subfigureautorefname}{\figureautorefname} % hypergeometric functions \newcommand{\twofone}[3]{{}_{2}F_1\left(\begin{matrix}#1\\\end{matrix}\right)} \newcommand{\threeftwo}[6]{% {}_{3}F_2\left(\begin{matrix}#1\\\end{matrix}\,;#6\right)} % \autoref for a corollary gives "Theorem N" so make a function to work % around that but still link the reference: \nonthemref{blah} defaults % to Lemma, \nonthemref[foo]{labelname} uses "foo" for the name. \newcommand{\nonthmref}[2][Lemma]{\hyperref[#2]{#1~\ref*{#2}}} % I use green text for special things, mostly edges in paths \newcommand{\spthing}[1]{\textcolor{green}{#1}} \newcommand{\N}{\mathbb{N}} \newcommand{\Sch}{Schr\"oder\xspace} \DeclareMathOperator{\pathlen}{pathlen} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Bijections from Weighted Dyck Paths \\ \vskip .1in to Schr\"oder Paths } \vskip 1cm \large Dan Drake\\ Department of Mathematical Sciences\\ Korea Advanced Institute of Science and Technology\\ Daejeon 305-701\\ Korea\\ \href{mailto:ddrake@member.ams.org}{\tt ddrake@member.ams.org} \\ {\tt http://mathsci.kaist.ac.kr/\char'176drake} \\ \end{center} \vskip .2 in \begin{abstract} Kim and Drake used generating functions to prove that the number of $2$-distant noncrossing matchings, which are in bijection with little \Sch paths, is the same as the weight of Dyck paths in which downsteps from even height have weight $2$. This work presents bijections from those Dyck paths to little Schr\"oder paths, and from a similar set of Dyck paths to big Schr\"oder paths. We show the effect of these bijections on the corresponding matchings, find generating functions for two new classes of lattice paths, and demonstrate a relationship with $231$-avoiding permutations. \end{abstract} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \section{Introduction and preliminaries} \label{sec:intro} This work begins with the work of Kim and the present author \cite{drake.kim:k-distant} in which they studied, among other things, $2$-distant noncrossing matchings. Such matchings---which will be defined shortly---are naturally enumerated by little \Sch paths. In the process of describing connections between $k$-distant noncrossing matchings and orthogonal polynomials, Drake and Kim used generating functions to show that little \Sch paths are equinumerous with a certain set of labeled Dyck paths. We present here a bijective proof of that fact; the bijection has a number of interesting properties and is a consequence of a bijection between big \Sch paths and a similar set of labeled Dyck paths. We begin with definitions of the combinatorial objects mentioned above. The notation $[n]$ refers to the set of positive integers from $1$ to $n$. A \textsl{matching of $[n]$} is a set of vertex-disjoint edges in the complete graph on $n$ vertices so that every vertex is adjacent to exactly one edge. For our purposes, a matching can also be viewed as a permutation whose cycles all have length $2$, or a set partition whose blocks all have size $2$. We will draw matchings by arranging the vertices horizontally and drawing arcs, as in \autoref{fig:matching-example}. \begin{figure}[h] \centering \inputtikz{matching-example} \caption{A matching of $[12]$.} \label{fig:matching-example} \end{figure} Drake and Kim \cite{drake.kim:k-distant} define a \textsl{$k$-distant crossing} as a pair of arcs $(i_{1}, j_{1})$ and $(i_{2}, j_{2})$, with $i_{1} < i_{2} < j_{1} < j_{2}$ and $j_{1} - i_{2} \ge k$. The arcs $(6, 11)$ and $(8,12)$ of the matching in \autoref{fig:matching-example} form a $3$-distant crossing; the arcs $(1,4)$ and $(3,7)$ form a $1$-distant crossing. A \textsl{$k$-distant noncrossing matching} is simply a matching with no $k$-distant crossing. The matching in \autoref{fig:matching-example} is $4$-distant noncrossing. (This notion of $k$-distant crossing is different from the $k$-crossings of matchings studied by, for example, Chen et al.\ \cite{chen.deng.ea:crossings}; their work concerns sets of $k$ mutually crossing edges, and ignores the distance between vertices.) In a $2$-distant noncrossing matching, crossing edges are allowed as long as the right vertex of the left edge is adjacent to the left vertex of the right edge. This fact allows us to describe a bijection from $2$-distant noncrossing matchings to a certain class of lattice paths. A lattice path of length $n$ is a sequence $(p_{0}, p_{1},\dots,p_{n})$ of points in $\N \times \N$; the $k$th step of the path is the pair $(p_{k-1}, p_{k})$. A step is called an \textsl{upstep} if the component-wise difference of $p_{k} - p_{k-1}$ is $(1,1)$, and a \textsl{downstep} if the difference is $(1, -1)$. In this work, we will use paths with \textsl{double horizontal steps}, which is a pair of adjacent steps whose component-wise differences are both $(1,0)$. By a minor abuse of terminology, a double horizontal step will usually be called a horizontal step. A \textsl{little \Sch path} is a lattice path consisting of upsteps, downsteps, and horizontal steps, such that no horizontal step occurs at height zero. See \autoref{fig:2dnc-matching-little-sch} for an example of such a path. It is not difficult to describe a bijection from $2$-distant noncrossing matchings to little \Sch paths: convert every vertex at the left end of an arc to an upstep and every vertex at the right end of an arc to a downstep---except for adjacent vertices involved in a crossing: convert those vertices into a horizontal step. This operation is a bijection because, given a little \Sch path, one can recover the matching by drawing an opening half edge at every upstep, two crossing half edges at every horizontal step, and a closing half edge at every downstep. Then connect every closing half-edge to the nearest opening half-edge to create a matching. See \autoref{fig:2dnc-matching-little-sch} for an example of this correspondence. \begin{figure}[h] \centering \inputtikz{2dncr-matching-little-sch} \caption{An example of the bijection between $2$-distant noncrossing matchings and little \Sch paths (left), and the correspondence between the edges incident to vertices of the matching and steps in the little \Sch path (right). } \label{fig:2dnc-matching-little-sch} \end{figure} The \textsl{little \Sch numbers} $s_{n}$ (sequence \seqnum{A001003} in the OEIS \cite{sloane:on-line}) count $2$-distant noncrossing matchings of $[2n]$ and also little \Sch paths of length~$2n$. If horizontal steps on the $x$-axis are allowed, one has a \textsl{big \Sch path}; the number of such paths of length $2n$ is $S_{n}$, the \textsl{big \Sch number} (sequence \seqnum{A006318}) and it is well known that $S_{n} = 2s_{n}$ for $n > 0$; see the next section and also Deutsch's bijective proof \cite{deutsch:bijective}. We need several more definitions related to lattice paths. The first is the step that \textsl{matches} a step. For an upstep $u$, the matching step is the rightmost downstep to the left of $u$ that leaves from the same height at which the upstep ends; the definition for a downstep is similar. For a horizontal step $h$ not on the $x$-axis, the matching step is the leftmost downstep to the right of $h$ that leaves from the same height as $h$; in the corresponding $2$-distant noncrossing matching, the matching downstep corresponds to the rightmost vertex involved in the two crossing edges. For example, the step matching the first horizontal step in \autoref{fig:2dnc-matching-little-sch} is the last downstep. We will write paths using ``U'' for upsteps, ``HH'' for horizontal steps, ``D'' for regular downsteps, and ``d'' for special downsteps, which will be defined in \autoref{sec:descr-biject}. The path in \autoref{fig:2dnc-matching-little-sch} is UUDHHUHHDUUDDD. \subsection{Orthogonal polynomials and weighted Motzkin paths} \label{sec:orth-polyn-weight} When one has a sequence of positive numbers, in many cases it is possible to describe that sequence as the moments of a sequence of orthogonal polynomials. In other words, given $\{\mu_{n}\}_{n \ge 0}$, define a measure (or a linear functional on polynomials; the two are equivalent here) by $\int x^{n} \,\mathrm{d} \mu = \mu_{n}$ and find polynomials $\{P_{n}(x)\}_{n \ge 0}$ so that the integral \begin{displaymath} \int P_{n}(x) P_{m}(x) \,\mathrm{d} \mu = 0 \end{displaymath} when $n \ne m$ and is nonzero when $n = m$. Many classical combinatorial sequences produce sequences of orthogonal polynomials: the Catalan numbers produce Chebyshev polynomials of the second kind, matching numbers produce Hermite polynomials, factorials produce Laguerre polynomials, and so on. Viennot described a completely combinatorial theory of orthogonal polynomials \cite{viennot:theorie,viennot:combinatorial} in which the moments of a sequence of orthogonal polynomials are expressed as weighted Motzkin paths. A Motzkin path is a lattice path that consists of upsteps, downsteps and single horizontal steps (steps that move $(1,0)$); a weighted Motzkin path has a weight $\lambda_ {n}$ associated with every downstep leaving from height $n$, a weight $b_{n}$ for every horizontal step at height $n$, and weight $1$ for all upsteps. For many orthogonal polynomial moment sequences, the weights $b_{n}$ are zero, which means the corresponding moments may be described by weighted Dyck paths; a \textsl{Dyck path} is just a Motzkin path with no horizontal steps. Drake and Kim \cite{drake.kim:k-distant} showed that the number of $2$-distant noncrossing matchings of $[2n]$---little \Sch numbers---is the same as the total weight of weighted Dyck paths of length $2n$ in which downsteps leaving from odd height have weight $1$, and downsteps leaving from even height have weight $2$. They proved this equality using equation (2) of Kim and Zeng \cite{kim.zeng:combinatorics} (or equation (1) of Vauchassade de Chaumont and Viennot \cite{chaumont.viennot:polynomes}), which in the present context is \begin{equation} s_{n} = \sum_{k \ge 0} \frac{1}{n} \binom{n}{k} \binom{n}{k+1} 2^{k}; \label{eq:little-sch-sum-of-narayana} \end{equation} in both works, the authors demonstrate that the sum above represents the generating function for the weighted Dyck paths described above. However, the sum also counts little \Sch paths, since $\binom{n}{k}\binom{n}{k+1}/n$ is a \textsl{Narayana number} (sequence \seqnum{A001263}), which counts Dyck paths of length $2n$ with $k+1$ peaks and $k$ ravines. A peak is an upstep immediately followed by a downstep, and a ravine is a downstep immediately followed by an upstep. Between two consecutive peaks, there must be exactly one ravine, so having $k+1$ peaks is equivalent to having $k$ ravines. Any ravine can clearly be ``filled in'' and replaced with a horizontal step, so a Dyck path with $k$ ravines corresponds to $2^{k}$ little \Sch paths, which explains equation~\eqref{eq:little-sch-sum-of-narayana}. On the other hand, any peak can be ``flattened'' into a horizontal step, so we also have \begin{equation} S_{n} = \sum_{k \ge 0} \frac{1}{n} \binom{n}{k} \binom{n}{k+1} 2^{k+1} \label{eq:big-sch-sum-of-narayana} \end{equation} because peaks can occur on the $x$-axis. This provides one explanation for why there are twice as many big \Sch paths as little ones. \subsection{Plan of the paper} \label{sec:plan-paper} The aim of this work is to demonstrate a bijection from weighted Dyck paths whose downsteps at even height have weight ~$2$ to little \Sch paths. That bijection will be a minor modification of a bijection from big \Sch paths to a similar class of Dyck paths; both bijections will in turn be consequences of more refined bijections between classes of little and big hybrid paths, which are described in \autoref{sec:descr-biject}. In \autoref{sec:hybrid-paths-matchings} we show the effect of those bijections on the corresponding matchings, and then find generating functions for little and big hybrid paths in \autoref{sec:enum-hybr-paths}. We finish by showing that our bijections are closely related to $231$-avoiding permutations in \autoref{sec:hybrid-paths-231}. \section{Description of the bijection} \label{sec:descr-biject} Instead of working with Dyck paths in which downsteps from even height have weight $2$, we will work with Dyck paths in which such downsteps may or may not be labeled ``special''; the two ideas are clearly equivalent. Such paths will be called \textsl{even-special Dyck paths} and abbreviated ``ESDPs''; \textsl{odd-special Dyck paths} (ODSPs) are defined similarly. We will first describe a bijection $E_{\infty}$ from odd-special Dyck paths to big \Sch paths---our desired bijection from even-special Dyck paths to little \Sch paths will follow from a minor modification of that bijection. The bijection $E_{\infty}$ will be a consequence of a more refined bijection $E$ between two classes of what we will call big hybrid paths. \textsl{Big hybrid paths} include odd-special Dyck paths and any path obtained by applying $E$ to a big hybrid path. To understand this recursive definition, we must define the map $E$. \begin{definition} \label{def:e-bijection} Given a hybrid path, the map $E$ does nothing to the path if the path contains no special steps. Otherwise, given a hybrid path with $k$ horizontal steps, $E$ yields a hybrid path with $k+1$ horizontal steps by the following procedure. Find the leftmost special step in the hybrid path. If that step is preceded by an upstep, \textsl{flatten} the upstep and special downstep by replacing them with a horizontal step. If the special step is preceded by a downstep $d$, find the upstep $u$ that matches $d$ and let $P$ be the (possibly empty) subpath between $u$ and $d$. Replace $u$ with a horizontal step, delete $d$, \textsl{slide} $P$ so that it follows the horizontal step, and make the original special step an ordinary downstep. \end{definition} \begin{figure} \centering \subfloat[When the special step is preceded by an upstep, $E$ and $e$ simply ``flatten'' the two steps.]{ \label{fig:e-bijection-flatten} % make the caption stuff in subfig see a wider box, so the caption % doesn't use ridiculously short lines \parbox{8.25cm}{\centering \inputtikz{e-bijection-flatten}} } \subfloat[When the special step is preceded by a downstep, $E$ and $e$ find the matching up step and ``slide'' $P$.]{ \label{fig:e-bijection-slide} \inputtikz{e-bijection-slide} } \caption{The action of bijections $E$ and $e$ on the leftmost special down step in a hybrid path.} \label{fig:e-bijection} \end{figure} \autoref{fig:e-bijection} demonstrates the flatten and slide operations. All the paths in \autoref{fig:E-forward-backward} are big hybrid paths. The map $E$ clearly preserves the total number of special and horizontal steps and, for paths with at least one special step, reduces the number of special steps by one. It is also a bijection: \begin{theorem} The map $E$ is a bijection from the set of odd-special Dyck paths of length $n$ with no special steps to the set of big \Sch paths of length $n$ with no horizontal steps. It is also a bijection from the set of big hybrid paths of length $n$ with $j$ special steps and $k$ horizontal steps to the set of big hybrid paths with $j-1$ special steps and $k+1$ horizontal steps. \label{thm:E-is-a-bijection} \end{theorem} We will show that $E$ is a bijection by describing a procedure for finding the horizontal step that was added last; the operation described in \autoref{def:e-bijection} and \autoref{fig:e-bijection} is obviously reversible if we know which horizontal step was added last. Before giving the proof, let's see why this identification is not as simple as it may sound. The problem is that sometimes $E$ ``moves forward'' and sometimes $E$ ``moves backward''. \autoref{fig:E-forward-backward} shows what we mean by this. A horizontal step may be created by $E$ to the left, to the right, or in the middle of the existing horizontal steps, so the left- or rightmost horizontal step need not be the last one added. \begin{figure}[h] \centering \subfloat[The horizontal steps added by $E$ move ``backwards'' when doing repeated slide operations.]{ \label{fig:E-slide-backward-ex} \inputtikz{E-slide-ex}} \subfloat[The horizontal steps added by $E$ move ``forwards'' when doing repeated flatten operations.]{ \label{fig:E-flatten-forward-ex} \inputtikz{E-flatten-ex}} \subfloat[Horizontal steps can also be added between existing horizontal steps.]{ \label{fig:E-slide-middle-ex} \inputtikz{E-slide-middle-ex}} \caption{The horizontal steps created by $E$ are not necessarily added left-to-right. The three paths on the far right look similar, but their horizontal steps were added in different orders.} \label{fig:E-forward-backward} \end{figure} One may think that, since horizontal steps from slides are always created at odd height and horizontal steps from flattenings are created at even height, it might be possible to use that information to identify the last-added step, but since slides change the height of parts of the path by one, a simple examination of odd and even heights will not suffice. \begin{proof}[Proof of \autoref{thm:E-is-a-bijection}] The first statement of the theorem is trivial, as it is saying that $E$ acts as the identity on the set of Dyck paths. For the second statement, we must show that it is possible to identify which horizontal step was added last. This can be done with the following procedure. Partition the path into subpaths that consist of either a sequence of non-horizontal steps, or a horizontal step, its matching step, and all steps in between. The only part of a path altered by $E$ when adding a horizontal step is between the horizontal step and its matching downstep, so if a horizontal step~$b$ is to the right of the downstep matching a horizontal step~$a$, then $b$ must have been added after ~$a$. (This is a special case of \nonthmref{thm:21-order-adding-sp-steps}.) This fact tells us that the last-added horizontal step must be in the rightmost such subpath that contains a horizontal step. Call that subpath the \textsl{first active subpath}. \autoref{fig:partition-by-hh} illustrates this partitioning process. \begin{figure}[h] \centering \inputtikz{partition-by-hh} \caption{The partitioning process to find the first active subpath, which is the rightmost subpath with a horizontal step.} \label{fig:partition-by-hh} \end{figure} If the first active subpath starts with a horizontal step on the $x$-axis, then, because horizontal steps on the $x$-axis can only be created with a flatten operation, the rightmost horizontal step in the subpath must be the last-added step. Otherwise, we may assume the first active subpath starts with a horizontal step at some positive height. If that step is at odd height, that step is the last-added horizontal step, because the slide operation of $E$ creates horizontal steps at odd height, and, as seen in \autoref{fig:E-slide-backward-ex}, as one moves forward along a sequence of downsteps, some of which are special steps, $E$ creates horizontal steps at the beginning of the first active subpath. If the step at the beginning of the first active subpath is at even height, we must partition the path again. Now partition the first active subpath into sequences of horizontal steps at the same height as the original horizontal step and subpaths that begin with an upstep and end at the downstep matching the upstep. Call these two kinds of sequences \textsl{valleys} and \textsl{hills}, respectively. Using the same reasoning as before, the last-added horizontal step must be in the rightmost hill or valley that contains a horizontal step. Call that hill or valley the \textsl{second active subpath}. In the subpath of \autoref{fig:hills-valleys}, the final hill is the second active subpath. \begin{figure}[h] \centering \inputtikz{partition-by-hills-valleys} \caption{Partitioning the first active subpath into hills and valleys. The second active subpath is the rightmost hill or valley with a horizontal step.} \label{fig:hills-valleys} \end{figure} If the second active subpath is a valley, the rightmost step in the valley is the most recently added horizontal step because steps in a valley must come from the flattening operation. If the second active subpath is a hill, we recursively use the procedure described here to identify the last-added step within that hill. Since the hill begins at even height, the path is of the same form as the hybrid paths we began with. Since the paths have finite length and the recursion step uses a shorter path than it started with, this procedure always finishes, and since the ``exit points'' always identify what must be the most recently added step, the procedure as a whole will identify the last-added horizontal step of a hybrid path. \end{proof} For example, with the second active subpath in \autoref{fig:hills-valleys}, we would recursively use the procedure on the final hill. The procedure in the proof above, given that hill (UUHHDd) as a single path would identify HHD as the first active subpath then, since the horizontal step is at even height, partition again and identify the valley HH as the second active subpath, and finally declare that single horizontal step as the most recently added horizontal step. In \autoref{fig:e-bijection-ex}, step $12$, starting at $(14, 2)$, is the last-added horizontal step. \subsection{Consequences of the bijection} \label{sec:consequences-of-E} If we start with an odd-special Dyck path, we can use $E$ to iteratively ``evolve'' the path into a big \Sch path. (In fact, we use $E$ to suggest the word ``evolve''.) Let $E_{\infty}$ be the resulting map from odd-special Dyck paths to big \Sch paths. Since $E$ is a bijection and preserves the total number of special steps and horizontal steps, we have the following corollary of \autoref{thm:E-is-a-bijection}. \begin{corollary} The map $E_{\infty}$ is a bijection from odd-special Dyck paths of length $n$ with $k$ special steps to big \Sch paths of length $n$ with $k$ horizontal steps. \label{thm:E-infinity-is-a-bijection} \end{corollary} The operation described in \autoref{def:e-bijection} and \autoref{fig:e-bijection} does not refer to the parity of the heights of the special steps, so we may use it with even-special Dyck paths. Define the map $e$ the same way as $E$, but starting with even-special Dyck paths. \textsl{Little hybrid paths} are defined analogously to big hybrid paths. By simply switching ``odd'' and ``even'' in the proof of \autoref{thm:E-is-a-bijection} and ignoring the possibility of sequences of horizontal steps on the $x$-axis, we see that $e$ is also a bijection: \begin{corollary} The map $e$ is a bijection from the set of even-special Dyck paths of length $n$ with no special steps to the set of little \Sch paths of length $n$ with no horizontal steps. It is also a bijection from the set of little hybrid paths of length $n$ with $j$ special steps and $k$ horizontal steps to the set of hybrid paths with $j-1$ special steps and $k+1$ horizontal steps. \label{thm:e-is-a-bijection} \end{corollary} By defining $e_{\infty}$ analogously to $E_{\infty}$, we accomplish our goal of showing bijectively that the little \Sch numbers enumerate even-special Dyck paths of length $n$: \begin{corollary} The map $e_{\infty}$ is a bijection from even-special Dyck paths of length $n$ with $k$ special steps to little \Sch paths of length $n$ with $k$ horizontal steps. \label{thm:e-infinity-is-a-bijection} \end{corollary} \autoref{fig:e-bijection-ex} shows an example of $e_{\infty}$. \begin{figure}[h] \centering \inputtikz{e-bijection-ex} \caption{An example of the bijection $e_{\infty}$.} \label{fig:e-bijection-ex} \end{figure} The connections between colored or labeled Dyck paths and the little \Sch numbers have also been studied by Asinowski and Mansour \cite[\S 4]{asinowski.mansour:dyck}; in their work, they colored ascents in Dyck paths with various kinds of paths. An \textsl{ascent} is a maximal sequence of up steps, and they colored ascents of length $k$ with Fibonacci paths of length $2k$, which they defined to be Dyck paths that consist only of pyramids (a pyramid is a Dyck path of the form $\text{U}^{n}\text{D}^{n}$). Asinowski and Mansour gave a bijection from the set of Dyck paths with ascents of length $k$ colored by Fibonacci paths ($\mathcal{D}^{\mathfrak{F}}(n)$, in their notation) to the set of little \Sch paths. This weighting of Dyck paths is different from the weighting of our even-special Dyck paths; for example, the path UUDUDD corresponds to four even-special Dyck paths but only two paths with ascents labeled by Fibonacci paths---one can label the initial UU ascent with UDUD or UUDD. We can also enumerate even- and odd-special Dyck paths by number of special steps. Using the reasoning behind equations \eqref{eq:little-sch-sum-of-narayana} and \eqref{eq:big-sch-sum-of-narayana}, which counted \Sch paths by changing peaks or ravines in Dyck paths into horizontal steps, the bijections above imply that the number of even-special Dyck paths of length $2n$ with $j$ special steps is, for positive $n$, \begin{equation} \sum_{k \ge 0} N(n,k) \binom{k}{j} = N(n, j)\,\twofone{j-n}{j-n+1}{j+2} = \frac{1}{n}\binom{n}{j}\binom{2n-j}{n+1}, \label{eq:esdps-with-j-sp} \end{equation} where $N(n, k)$ is again a Narayana number and the ${}_{2} F_{1}$ notation is a hypergeometric function evaluated at one, which we can sum with the Chu-Vandermonde identity. The above triangle of numbers is sequence \seqnum{A126216}. Similarly, the number of odd-special Dyck paths of length $2n$ with $j$ special steps is, for positive $n$, \begin{equation} \sum_{k \ge 0} N(n,k) \binom{k+1}{j} = N(n, j-1)\,\twofone{j-n}{j-n-1}{j} = \frac{1}{n-j+1}\binom{n}{j}\binom{2n-j}{n}; \label{eq:osdps-with-j-sp} \end{equation} the middle expression is not defined when $j=0$, but in that case, the sum on the left is just the sum of the Narayana numbers---a Catalan number---so the rightmost expression is correct for all nonnegative $j$. The triangle in equation \eqref{eq:osdps-with-j-sp} is sequence \seqnum{A060693}. \section{Hybrid paths as matchings} \label{sec:hybrid-paths-matchings} This work began with an investigation of certain matchings, and since little hybrid paths were developed to describe our bijection, it is fitting that we examine the connection between little hybrid paths and matchings. We already know that little \Sch paths correspond to $2$-distant noncrossing matchings, so first we will describe an interpretation of even-special Dyck paths. Using the bijection from \Sch paths to matchings, a Dyck path with no special steps corresponds to a noncrossing matching, so it is reasonable to interpret special steps in the path as special edges in the matching. For example, the path UUdUUUDDdD corresponds to the noncrossing matching $\{(1,10), \spthing{(2,3)}, \spthing{(4,9)}, (5,8), (6,7)\}$ in which the edges between $2$ and $3$ and between $4$ and $9$ are special. To interpret paths with both special steps and horizontal steps and understand the action of $e$ in terms of paths, we need to define nesting. An edge $(i_{1}, j_{1})$ in a matching \textsl{nests} the edge $(i_{2},j_{2})$ if $i_{1} < i_{2} < j_{2} < j_{1}$. An edge $a$ in a matching \textsl{immediately nests} edge $b$ if $a$ nests $b$, and any other edge that nests $b$ also nests $a$. Before describing the action of the flatten and slide operations on ``hybrid matchings'', we need one observation. \begin{lemma} Let $h$ be a double horizontal step in a little hybrid path. Let $d$ be the downstep matching $h$ and $u$ the upstep matching $d$. The step in the path corresponding to the rightmost (respectively, leftmost) vertex involved in the $1$-distant crossing at $h$ is either $d$ (resp., $u$) or the leftmost (resp., rightmost) horizontal step to the right (resp., left) of $h$ which is at the same height as $h$, whichever is closer to $h$. \label{thm:horiz-to-crossing-matching-steps} \end{lemma} \begin{proof} A key idea in this proof is that a sequence of steps in a hybrid path that begins with an upstep and ending with the matching downstep---what we called a hill in the proof of \autoref{thm:E-is-a-bijection}--- corresponds to a set of vertices in the matching that form a ``submatching''. Let $h$ be a double horizontal step in a little hybrid path, and partition the path as we did to find the second active subpath in the proof of \autoref{thm:E-is-a-bijection} (but ignore the height of $h$). The first step in $h$ corresponds to an opening half edge $x$. To what vertex will $x$ be connected? Any hill to the right of $h$ corresponds to a group of vertices that form a submatching, and hence $x$ will not be connected to any of them. If there is a double horizontal step between $h$ and $d$, then $x$ will be connected to the vertex corresponding to the second step of the leftmost such double horizontal step; otherwise, $x$ will be connected to the vertex corresponding to $d$. The proof for the ``respectively'' part of the statement is similar. \end{proof} For example, in \autoref{fig:2dnc-matching-little-sch}, the horizontal step at positions $4$ and $5$ corresponds to the $1$-distant crossing in the matching in the same position; step $14$ in the \Sch path is the downstep that matches the horizontal edge, so the right vertex of the edge incident to vertex $4$ is vertex $14$; and step $1$ in the path is the upstep that matches step $14$, so vertex $1$ is the left vertex of the edge incident to vertex $5$. Another example is UHHUDHHD; vertex $2$ in the corresponding matching (which is $\{(1, 3), (2, 7), (4, 5), (6, 8)\}$) connects to vertex $7$ because the second horizontal step is at the same height as the first, and is between the first horizontal step and its matching downstep. Now we can describe the corresponding action of the bijection $e$ on hybrid matchings. \begin{figure}[h] \centering \subfloat[The flatten operation when applied to a matching just ``swaps tails''.]{ \label{fig:e-bijection-matching-flatten} \inputtikz{e-bijection-matching-flatten}} \subfloat[The slide operation when applied to a matching. Note that the edge from $c$ to $b-1$ may actually be several edges, as in UUUHHDdD, where $b-1$ is $6$ and $c$ is $3$.]{ \label{fig:e-bijection-matching-slide} \inputtikz{e-bijection-matching-slide}} \caption{The effect of $e$ on matchings. This is the matchings version of \autoref{fig:e-bijection}.} \label{fig:e-bijection-matchings} \end{figure} \begin{theorem} The analogue of the flatten operation for hybrid paths works as follows on matchings: given a special edge connecting vertices $c$ and $c+1$, find the edge that immediately nests that special edge; say it connects $a$ and $b$. Then ``swap the tails'': replace the edges $(c,c+1)$ and $(a,b)$ with edges $(c,b)$ and $(a,c+1)$. \label{thm:e-matchings-flatten} \end{theorem} \begin{proof} The special downstep in the path (which is immediately preceded by an upstep, since we are doing a flatten operation) becomes a horizontal edge. So there will be $1$-distant crossing at vertices $c$ and $c+1$. We only need to find the other two vertices involved; because of the way matchings are constructed from paths and \nonthmref{thm:horiz-to-crossing-matching-steps}, those other two vertices are $a$ and $b$. \end{proof} To define the analogue of the slide operation, we need to define the \textsl{transitive left endpoint} of an edge. Given an edge $e$, the transitive left endpoint of that edge is simply the left endpoint of $e$---unless the edge is the right edge in a $1$-distant crossing; then the transitive left endpoint of $e$ is the transitive left endpoint of the left edge in the crossing. For example, the transitive left endpoint of the edge $(6,8)$ in the matching $\{(1,5), (2,3), (4,7), (6,8)\}$ is $1$. In little hybrid paths, the transitive left endpoint corresponds to finding the upstep that matches a downstep; because of \nonthmref{thm:horiz-to-crossing-matching-steps}, a matching upstep-downstep pair may not correspond to the left and right vertices of a single edge. \begin{theorem} The analogue of the slide operation for paths works as follows on matchings: given a special edge $(a,b)$, let $c$ be the transitive left vertex of the edge incident to vertex $b-1$. The slide operation on hybrid paths corresponds to replacing $(a,b)$ and $(c,b-1)$ with edges $(a,c+1)$ and $(c,b)$ and sliding all half edges incident to vertices from $c+1$ to $b-2$ to the right by one vertex. \label{thm:e-matchings-slide} \end{theorem} \begin{proof} Since we are doing a slide operation, the special step in the path must be preceded by a ordinary downstep, which means $b-1$ must be the right vertex of an ordinary edge nested by the special edge. The new $1$-distant crossing created by the slide operation will be at the upstep that matches the downstep at $b-1$, which as we saw above is the transitive left endpoint of the edge incident to $b-1$ in the matching. We create the new crossing at vertices $c$ and $c+1$; the slide operation on the path moves all steps from $c+1$ to $b-2$ to $c+2$ to $b-1$, so all half edges incident to vertices from $c+1$ to $b-2$ are moved to the right one vertex. \end{proof} \autoref{fig:e-bijection-matchings} demonstrates these two operations for matchings. \section{Enumeration of hybrid paths} \label{sec:enum-hybr-paths} Having defined and used hybrid paths it is natural to wonder just many of them there are. Let $L_{n}$ and $B_{n}$ be the number of little and big hybrid paths, respectively. All big \Sch paths and odd-special Dyck paths are big hybrid paths, and Dyck paths, which are counted by the Catalan number $C_{n}$, are both big \Sch paths and OSDPs, so $B_{n}$ is certainly at least $2 S_{n} - C_{n}$, but there are paths such as HHUd which are neither \Sch paths nor odd-special Dyck paths. \autoref{tab:hybrid-paths} shows the number of all hybrid paths, little and big, for some small values of $n$. \begin{table}[h] \centering \begin{tabular}{lrrrrrrrrrrrr} $n$: & 0 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22\\ \hline little: & 1 & 1 & 4 & 18 & 87 & 439 & 2278 & 12052 & 64669 & 350733 & 1918152 & 10560678\\ big: & 1 & 3 & 11 & 47 & 219 & 1075 & 5459 & 28383 & 150131 & 804515 & 4355163 & 23768079\\ \end{tabular} \caption{The number of little and big hybrid paths.} \label{tab:hybrid-paths} \end{table} One way to count hybrid paths is to begin with even- and odd-special Dyck paths with $j$ special steps, which are counted in equations \eqref{eq:esdps-with-j-sp} and \eqref{eq:osdps-with-j-sp}; repeatedly applying $e$ or $E$ to such a Dyck path will produce $j$ hybrid paths. Multiplying those equations by $j+1$ and summing over $j$ yields, for little hybrid paths, \begin{equation} L_{n} = C_{n}\,\threeftwo{-n}{-n+1}{2}{-2n}{1}{-1}, \label{eq:little-hyb-3f2} \end{equation} where $C_{n}$ is a Catalan number and the hypergeometric function is now evaluated at $-1$. Similarly, the number of big hybrid paths is \begin{equation} B_{n} = C_{n}\,\threeftwo{-n}{-n-1}{2}{-2n}{1}{-1}. \label{eq:big-hyb-3f2} \end{equation} Another way to enumerate these paths is to find their generating functions. Let $L(x)$ and $B(x)$ be the generating functions for little and big hybrid paths, respectively. We will use the following generating functions: $E(x)$ and $O(x)$ for even- and odd-special Dyck paths, and $s(x)$ and $S(x)$ for little and big \Sch paths. Of course, we already know that $E(x) = s(x)$, $O(x) = S(x)$, $S(x) = 2 s(x) - 1$, and \begin{displaymath} s(x) = \frac{2}{1 + x + \sqrt{x^2 - 6x + 1}}, \end{displaymath} but it will be helpful to use different names to keep different types of paths separate. In all the generating functions considered here, paths of length $2n$ are weighted by $x^{n}$. \begin{theorem} Let $R = \sqrt{x^{2} - 6x + 1}$. The ordinary generating function for little hybrid paths is \begin{equation} L(x) = \frac{R+1-x}{2} \cdot \frac{2(R+x)}{R (R+x+1)} \cdot \frac{2}{R+x+1} \label{eq:little-hybrid-gf-R} \end{equation} and the ordinary generating function for big hybrid paths is \begin{equation} B(x) = \left(\frac{R+1-x}{2} - 1 + x - \frac{R(R+x)}{2} + \frac{3}{2} - \frac{3x}{2} \right) \frac{2(R+x)}{R (R+x+1)} \cdot \frac{2}{R+x+1}. \label{eq:big-hybrid-gf-R} \end{equation} More explicitly, we have \begin{equation} L(x) = \frac{1}{8x}\left( 3x + 1 - \frac{3x^{2} - 8x + 1}{\sqrt{x^{2} -6x +1}}\right) \label{eq:little-hybrid-gf} \end{equation} and \begin{equation} B(x) = \frac{1}{2x}\left( 1 - \frac{2x^{2} - 7x + 1}{\sqrt{x^{2} -6x +1}}\right) - 1. \label{eq:big-hybrid-gf} \end{equation} \end{theorem} \begin{proof} We will decompose little and big hybrid paths to express $L$ and $B$ in terms of each other and then solve the system. A key idea is that raising a big hybrid path up one unit and sandwiching it between an upstep and downstep yields a valid little hybrid path, since all the step height parities have effectively been reversed. Doing the same thing to a little hybrid path yields a big hybrid path, although the resulting path will never have a horizontal step at height ~$1$. Every nonempty little hybrid path may be decomposed into an upstep, a big hybrid path $P$, a downstep, then a little hybrid path $Q$, as shown in \autoref{fig:little-hybrid-decomp}. Any pair $P$ and $Q$ is allowed, unless $P$ has a special step and $Q$ has a horizontal step. \begin{figure}[h] \centering \inputtikz{little-hybrid-decomp} \caption{A decomposition of a nonempty little hybrid path.} \label{fig:little-hybrid-decomp} \end{figure} Assume that $P$ has a special step, so that $Q$ has no horizontal step. Since $S(x)$ counts big hybrid paths with only upsteps, downsteps, and horizontal steps---in other words, with no special steps---the generating function for big hybrid paths with a special step is $B(x) - S(x)$; similar reasoning shows that the generating function for little hybrid paths with no horizontal steps is simply $E(x)$. Thus the generating function for little hybrid paths with a special step in their first components is $x (B(x) - S(x)) E(x)$. On the other hand, if $P$ doesn't have a special step, then it is a big \Sch path and $Q$ can be any little hybrid path. The generating function for little hybrid paths with no special step in their first components is therefore $x S(x) L(x)$. Every nonempty little hybrid path can be uniquely decomposed in this way and falls into exactly one of the above categories, so adding in the empty path we have \begin{displaymath} L(x) = 1 + x (B(x) - S(x)) E(x) + x S(x) L(x), \end{displaymath} or, solving for $L$, \begin{equation} L(x) = \frac{1 + x ( B(x) - S(x)) E(x)}{1 - x S(x)}. \label{eq:L-gf-in-terms-of-B} \end{equation} The decomposition for big hybrid paths is slightly more involved. Given a big hybrid path with an upstep, let $s$ be the first downstep to return to the $x$-axis and decompose the path as in \autoref{fig:big-hybrid-decomp}. In any such big hybrid path, either there is or is not a special step before ~$Q$. \begin{figure}[h] \centering \inputtikz{big-hybrid-decomp} \caption{A decomposition of a big hybrid path with an upstep. The path begins with a possibly empty sequence of horizontal steps. The step $s$ is the first downstep to return to the $x$-axis; it may or may not be a special step.} \label{fig:big-hybrid-decomp} \end{figure} Assume that there is a special step before $Q$, and that $s$ is special. In that case, $P$ can be any little hybrid path, because if $s$ is special, we know that no horizontal steps can appear in $P$ at height $1$---such a step has $s$ as its matching downstep and can only be created with a slide operation that would make $s$ an ordinary step. Since there are no horizontal steps at height $1$, $P$ can be any little hybrid path, and since there are special steps preceding $Q$, it cannot have any horizontal steps, and hence is an odd-special Dyck path. The generating function for the possibly empty sequence of horizontal steps at the beginning is $1/(1-x)$, so the generating function for paths of this type is $x L(x) O(x) / (1 - x)$. If a special step appears before $Q$ and $s$ is ordinary, then $P$ must have a special step and cannot have a horizontal step at height ~$1$. Assume there is such a horizontal step ~$h$. The step $h$ is at odd height and its matching step is $s$, so the only way $h$ could be created is by a slide operation that converts $s$ from a special to an ordinary step, but since we process special steps left to right, $s$ would be converted from special to ordinary only if there were no special steps in $P$, which is a contradiction. This means that $P$ can be any little hybrid path with a special step; the generating function for such paths is $L(x) - s(x)$. The subpath $Q$ can therefore be any odd-special Dyck path, so the generating function for all such big hybrid paths is $x (L(x) - s(x)) O(x) / (1-x)$. Finally, if there is no special step preceding $Q$, then $P$ can be any big \Sch path, and $Q$ can be any big hybrid path. The generating function for such big hybrid paths is $x S(x) B(x) / (1 -x)$. Every big hybrid path with an upstep falls into exactly one of the categories above, so, including paths that consist only of a sequence of horizontal steps on the axis, we have \begin{displaymath} B(x) = \frac{1}{1-x} + \frac{x L(x) O(x)}{1-x} + \frac{x (L(x) - s(x)) O(x)}{1-x} + \frac{x S(x) B(x)}{1 -x}, \end{displaymath} or, solving for $B$, \begin{equation} B(x) = \frac{1 + x L(x) O(x) + x (L(x) - s(x))}{1 - x - x S(x)}. \label{eq:B-gf-in-terms-of-L} \end{equation} Solving the system of equations \eqref{eq:L-gf-in-terms-of-B} and \eqref{eq:B-gf-in-terms-of-L} and using the fact that \begin{gather*} s(x) = E(x) = \frac{2}{1+x+R} = \frac{1+x-R}{4x} \quad \text{and}\\ S(x) = O(x) = \frac{4}{1+x+R} - 1 = \frac{1+x-R}{2x} - 1, \end{gather*} we obtain the desired expressions for $L(x)$ and $B(x)$. \end{proof} It may seem that the generating functions $L$ and $B$ were described in equations \eqref{eq:little-hybrid-gf-R} and \eqref{eq:big-hybrid-gf-R} in an unusual way, but the expressions show that $L$ and $B$ are in some sense built out of familiar generating functions for paths: \begin{displaymath} \frac{2(R+x)}{R (R+x+1)} = 1 + 2x + 7x^{2} + 30x^{3} + 141x^{4} + \cdots \end{displaymath} is the generating function for sequence \seqnum{A116363}, which counts dot products of rows of Pascal's and Catalan's triangle, and of course $2/(R+x+1)$ is the generating function for the little \Sch numbers. Also appearing in both $L$ and $B$ is \begin{displaymath} \frac{R+1-x}{2} = 1 - x - x S(x), \end{displaymath} a minor modification of the generating function for the big \Sch numbers. In $B$, we see that we have exactly $-x S(x)$; the remaining terms in $B$ are \begin{displaymath} -\frac{R(R+x)}{2} + \frac{3}{2} - \frac{3x}{2} \end{displaymath} which is $1 + x + x^{2} S(x)$. The expressions in \eqref{eq:little-hybrid-gf} and \eqref{eq:big-hybrid-gf} for $L(x)$ and $B(x)$ allow us to derive new expressions for the numbers of little and big hybrid paths. The expression $1/\sqrt{x^{2} - 6x + 1}$ is the generating function for the central Delannoy numbers (sequence \seqnum{A001850}). The central Delannoy number $D_{n}$ can be interpreted as the number of lattice paths from $(0,0)$ to $(n,0)$, not necessarily above the $x$-axis, consisting of upsteps, downsteps, and double horizontal steps; they can be expressed as \begin{displaymath} D_{n} = \sum_{k \ge 0} \binom{n}{k}^{2} 2^{k}. \end{displaymath} See Sulanke \cite{sulanke:objects} for basic facts about the central Delannoy numbers and a collection of objects enumerated by them. Using the generating function expressions, one may easily derive the number of little hybrid paths of length $2n$. Equation \eqref{eq:little-hybrid-gf} implies that \begin{equation} L_{n} = -\frac{1}{8}[x^{n+1}]\frac{3x^2 - 8x + 1}{\sqrt{x^2 - 6x + 1}} = -\frac{1}{8}(D_{n+1} - 8 D_{n} + 3 D_{n-1}), \label{eq:num-little-hybrids-via-delannoy} \end{equation} and similarly \eqref{eq:big-hybrid-gf} implies that \begin{equation} B_{n} = -\frac{1}{2} [x^{n+1}] \frac{2x^{2} - 7x + 1}{\sqrt{x^{2} - 6x + 1}} = -\frac{1}{2} (D_{n+1} - 7 D_{n} + 2 D_{n-1}). \label{eq:num-big-hybrids-via-delannoy} \end{equation} Both expressions above are valid for $n \ge 1$ and are, of course, equal to the expressions in \eqref{eq:little-hyb-3f2} and ~\eqref{eq:big-hyb-3f2}, respectively. My thanks to the anonymous referee for pointing out the relationship between the generating functions $L(x)$ and $B(x)$ and the central Delannoy numbers. \section{The bijections \texorpdfstring{$E$}{E} and \texorpdfstring{$e$}{e} and 231-avoiding permutations} \label{sec:hybrid-paths-231} While using the bijections $E$ or $e$, one can keep track of the order in which horizontal steps are added and thereby associate a permutation to an even- or odd-special Dyck path. For example, the paths in \autoref{fig:E-forward-backward} correspond to the permutations $321$, $123$, and $132$; the path in \autoref{fig:e-bijection-ex} corresponds to $12387465$. In this section we will see that every permutation so obtained must avoid the pattern ~$231$. This is very interesting, since $231$-avoiding permutations are counted by the Catalan numbers and hence are in bijection with Dyck paths; see Mansour et al.\ \cite[\S 3.1]{mansour.deng.ea:dyck}. A permutation $\pi = \pi_{1}\pi_{2}\cdots \pi_{n}$ written in one-line notation \textsl{contains} a pattern $\sigma$ (another permutation) if there is some subset of the $\pi_{i}$'s that are order-isomorphic to ~$\sigma$. A permutation \textsl{avoids} a pattern if it does not contain it. The permutation $12584367$ contains the pattern $231$ because the subset $583$ is order-isomorphic to $231$, and avoids the pattern $3124$. The notation $S_{n}(231)$ refers to the set of $231$-avoiding permutations of ~$[n]$. We start with a lemma that tells us exactly when the horizontal steps created by two special steps are added out of order---that is, when two special steps create the pattern ~$21$. Given a special step $s$, let $h(s)$ refer to the horizontal step created when $s$ is turned into an ordinary step. \begin{lemma} \label{thm:21-order-adding-sp-steps} Given two special steps $a$ and $b$ in a hybrid path with $a$ to the left of $b$, $h(b)$ is created to the left of $h(a)$ if and only if $b$ is preceded by a downstep $d$ and the upstep matching $d$ is to the left of ~$a$. \end{lemma} \begin{proof} We only need to examine three possibilities: $b$ is preceded by an upstep, $b$ is preceded by a downstep whose matching upstep is to the right of $a$, and $b$ is preceded by a downstep whose matching upstep is to the left of ~$a$. To work through those three cases, we need to use the fact that for any special step $s$, $h(s)$ is created to the left of $s$ and to the right of the downstep matching ~$s$. (When doing a flatten, ``to the left'' and ``to the right'' are weak inequalities, since the horizontal step will be created in the same position as those steps.) In the first case, if $b$ is preceded by an upstep, then $h(b)$ will clearly be to the left of $h(a)$, since $h(b)$ will be created at the position of $b$, which is to the right of ~$a$. If $b$ is preceded by a downstep whose matching upstep is to the right of $a$, let $u$ be that matching upstep. Since $h(b)$ will be created at $u$ and the following step, $h(b)$ is to the right of $a$ and hence to the right of ~$h(a)$. Finally, if $b$ is preceded by a downstep whose matching upstep is to the \emph{left} of $a$, let $u$ be that matching upstep. See \autoref{fig:e-bijection-slide}; $b$ would be the special step pictured in that figure, $u$ would be the upstep, and $a$ would be somewhere in the subpath $P$, and since the upstep matching $a$ is also in that subpath, $h(b)$ will be created to the left of ~$h(a)$. \end{proof} With that result, we can easily prove the following theorem. \begin{theorem} \label{thm:231-avoiding} The permutation corresponding to the order in which horizontal steps are added while transforming an even- or odd-special Dyck path into a small or large \Sch path avoids the pattern~$231$. \end{theorem} \begin{proof} Consider any three special steps $a$, $b$, and $c$ in a hybrid path, appearing in that order left to right. If these three steps cause the corresponding permutation to contain $231$, then we must have $h(b)$, $h(c)$, and $h(a)$ in that order. The bijections $E$ and $e$ process special steps left to right, so we first create $h(a)$, and then create $h(b)$ to the left of that. Now we must have $h(c)$ created to the right of $h(b)$, which means by \nonthmref{thm:21-order-adding-sp-steps} either $c$ is preceded by an upstep, or is preceded by a downstep whose matching upstep is to the right of $b$, but both of those possibilities cause $h(c)$ to be to the right of $h(a)$, which is a contradiction. \end{proof} The permutations produced are therefore a subset of $231$-avoiding permutations; next we will see that every such permutation can be obtained from some even- or odd-special Dyck path. \begin{theorem} \label{thm:hybrid-paths-all-231-avoiding-perms-possible} Every $231$-avoiding permutation can be obtained from some odd-special Dyck path. \end{theorem} \begin{proof} Given a $231$-avoiding permutation $\pi = \pi_{1}\cdots \pi_{n}$, we use the following recursive procedure to construct an odd-special Dyck path that, when using $E_{\infty}$, will create horizontal steps in the order specified by ~$\pi$. To begin with, the empty permutation corresponds to the empty path. Given a nonempty permutation $\pi$ of length $n$, if $\pi_{n} = n$, find the path corresponding to $\pi_{1}\cdots\pi_{n-1}$ and append the steps Ud to that path. (Recall that U refers to an upstep, and D and d refer to ordinary and special downsteps, respectively.) We will call this an \textsl{append} operation; it corresponds to the flatten operation. If a path $P$ corresponds to the permutation $\pi_{1}\pi_{2}\cdots \pi_{n-1}$, then the path obtained by appending Ud to $P$ will correspond to $\pi_{1}\pi_{2}\cdots \pi_{n-1} n$. If the permutation does not end with $n$, we will need the \textsl{lift} operation, which is defined as follows: given an odd-special Dyck path of the kind produced by this procedure, find an upstep leaving from the $x$-axis and let $Q$ be the subpath consisting of that upstep and everything following it. The lift operation, illustrated in \autoref{fig:lift}, replaces $Q$ with a path consisting of two upsteps, then $Q$, then an ordinary downstep and a special downstep. The lift operation corresponds to the slide operation of $E$ and ~$e$. \begin{figure}[h] \centering \inputtikz{lift} \caption{The lift operation. If the resulting path has $n$ special steps, in the corresponding permutation all numbers from $P$ will precede $n$, and all numbers from $Q$ will follow $n$.} \label{fig:lift} \end{figure} \newcommand{\corrto}{\leftrightarrow} For ease of description, define \textsl{good insertion} to be the operation of inserting $n$ into a $231$-avoiding permutation of $[n-1]$ anywhere except at the end so that the resulting permutation is also $231$-avoiding. We write $P \corrto \pi$ if a path $P$, constructed using the append and lift operations, corresponds to the permutation ~$\pi$. Assume $P \corrto \pi$, where $\pi \in S_{n}(231)$. Say that we obtain $\pi'$ by good insertion of $n+1$ after the $k$th entry of ~$\pi$. We need to show: \begin{enumerate} \item that we can do a lift operation following the $k$th special step of $P$ (that is, the $k$th special step ends on the $x$-axis), and \item the corresponding path $P'$ corresponds to $\pi'$. \end{enumerate} The path Ud corresponds to the permutation $1$, and both claims are true for that path-permutation pair. To prove the two claims in general, we need two propositions: \begin{proposition} If $\pi \in S_{n}(231)$, good insertion can be done after the $k$th entry of $\pi$ if and only if the first $k$ entries of $\pi$ form a permutation of ~$[k]$. \end{proposition} \begin{proposition} Assume that $P \corrto \pi$. The $k$th special step of $P$ ends on the $x$-axis if and only if the first $k$ entries of $\pi$ form a permutation of ~$[k]$. \end{proposition} The proof of the first is elementary and left to the reader. As for the second, let $s$ be the $k$th special step of $P$. Assume $s$ ends on the $x$-axis. Then by \nonthmref{thm:21-order-adding-sp-steps}, the horizontal step for every special step to the right of $s$ will be created to the right of $s$, which means the first $k$ entries of $\pi$ form a permutation of ~$[k]$. On the other hand, if $s$ does not end on the $x$-axis, then because of the definition of the lift operation, there must be a special step to the right of $s$ that is immediately preceded by a downstep $d$, with the upstep matching $d$ to the left of ~$s$. Therefore, by \nonthmref{thm:21-order-adding-sp-steps}, there will be a number bigger than $k$ among the first $k$ entries of $\pi$, so $\pi_{1}\cdots \pi_{k}$ will not form a permutation of ~$[k]$. The first claim above is now clear, since if $\pi'$ was obtained by good insertion into the $(k+1)$st position of $\pi$, then the first $k$ entries of $\pi$ form a permutation of $[k]$, which in turn means that the $k$th special step ends on the $x$-axis, and one can do a lift operation starting with following step. The second claim is also easy to see: say $\pi = \pi_{1}\cdots \pi_{n}$ and $\pi'$ is obtained by good insertion after ~$\pi_{k}$. If one lifts $P$ after the $k$th special step, the resulting path $P'$ will correspond to the permutation $\pi'$ because, following the lift operation, the special steps corresponding to $\pi_{1}\cdots\pi_{k}$ and to $\pi_{k+1}\cdots \pi_{n}$ will be turned into horizontal steps in the same order (they are either unchanged or simply raised by $2$ units), and the final step of $P'$ is a special downstep that will be turned into a horizontal step that follows every horizontal step created by the first $k$ special steps of $P'$ and precedes every horizontal step created by the $(k+1)$st to $n$th special steps. \end{proof} \autoref{fig:permutation-recursion} shows an example of this procedure. The permutation $21354$ is built from the permutation $1$ with the sequence ``good insert into position $1$, append, append, good insert into position $4$''; the path is built using the corresponding append and lift operations in the same order. \begin{figure}[h] \centering \inputtikz{permutation-recursion} \caption{An example of the recursive procedure to build an OSDP corresponding to a $231$-avoiding permutation. Here we see how the path for $21354$ is built up from the path Ud. Below each path is the corresponding permutation.} \label{fig:permutation-recursion} \end{figure} One can also obtain every $231$-avoiding permutation with even-special Dyck paths simply by taking a path produced by this procedure and sandwiching it between an upstep and an ordinary downstep. That produces an even-special Dyck path that clearly corresponds to the same permutation. We close with an interesting conjecture. The paths produced for $231$-avoiding permutations of $[n]$ are not all the same length; the lengths range from $2n$ for the path corresponding to $123\cdots n$ to $4n-2$ for the path corresponding to $n (n-1)\cdots 2 1$. An obvious question to ask is: how are the lengths distributed? In other words, find the coefficients of the polynomial \begin{displaymath} \sum_{\pi \in S_{n}(231)} q^{\pathlen(\pi)}, \end{displaymath} where $\pathlen(\pi)$ is the length of the path corresponding to $\pi$ using the construction above. We can also sum that expression over all $n$, since for a given length there can be only finitely many permutations that correspond to a path of that length, and ask what generating function we get. The lengths appear to have the Narayana distribution; see sequence \seqnum{A001263} and Sulanke \cite{sulanke:narayana}. The table below shows the polynomials for some small values of ~$n$. \begin{table}[h] \centering \begin{tabular}{ll|ll} $n$ & distribution of lengths & $n$ & distribution of lengths\\ \hline $1$ & $q^{2}$ & 4 & $q^{14} + 6q^{12} + 6q^{10} + q^{8}$ \\ $2$ & $q^{6} + q^{4}$ & 5 & $q^{18} + 10q^{16} + 20q^{14} + 10q^{12} + q^{10}$ \\ $3$ & $q^{10} + 3 q^{8} + q^{6}$ & 6 & $q^{22} + 15q^{20} + 50q^{18} + 50q^{16} + 15q^{14} + q^{12}$ \\ \end{tabular} \caption{The lengths of the OSDPs corresponding to $231$-avoiding permutations of $[n]$ appear to be Narayana-distributed.} \label{tab:lengths-narayana-dist} \end{table} \begin{conjecture} The lengths of the paths corresponding to $231$-avoiding permutations of $[n]$ using the above construction have the Narayana distribution; that is, \begin{equation} \sum_{\pi \in S_{n}(231)} q^{\pathlen(\pi)} = q^{2n} \sum_{k \ge 0} N(n, k) q^{2k}, \label{eq:conj-dist} \end{equation} where $N(n,k)$ is a Narayana number. We also have \begin{equation} \sum_{n \ge 0} \ \sum_{\pi \in S_{n}(231)} q^{\pathlen(\pi)} = \frac{1-q^{2}+q^{4}-\sqrt{1-2q^{2}-q^{4}-2q^{6}+q^{8}}}{2q^{4}}. \label{eq:conj-gf} \end{equation} \end{conjecture} The right-hand side of equation~\eqref{eq:conj-gf} is the generating function for generalized Catalan numbers described by Stein and Waterman \cite{stein.waterman:new} (see the $m=1$ column of Table 1), and by Vauchassade de Chaumont and Viennot \cite{chaumont.viennot:polynomes}. Those numbers are sequence \seqnum{A004148}, and count secondary structures of RNA molecules according to the number of bases. \section{Sage code} \label{sec:sage-code} \newcommand{\myurl}[1]{\href{http://#1}{\texttt{#1}}} Readers interested in programming code for working with the various paths, bijections, matchings, and permutations described here may find code for the Sage mathematics software system (see \myurl{sagemath.org}) at \myurl{arxiv.org/abs/1006.1959}. On that page, click ``Other formats'', then ``Download source'', and look for the file \texttt{code\_for\_dyck\_schroeder.sage} in the resulting archive. \begin{thebibliography}{10} \bibitem{asinowski.mansour:dyck} Andrei Asinowski and Toufik Mansour. \newblock Dyck paths with coloured ascents. \newblock {\em European J. Combinatorics} {\bf 29} (2008), 1262--1279. \bibitem{chaumont.viennot:polynomes} M.~Vauchassade~de Chaumont and G{\'e}rard Viennot. \newblock Polyn{\^o}mes orthogonaux et probl{\`e}mes d'{\'e}num{\'e}ration en biologie mol{\'e}culaire. \newblock {\em S{\'e}minaire Lotharingien de Combinatoire} {\bf 8} (1984), article B08l, 8 pp. \bibitem{chen.deng.ea:crossings} William Y.~C. Chen, Eva Y.~P. Deng, Rosena R.~X. Du, Richard~P. Stanley, and Catherine~H. Yan. \newblock Crossings and nestings of matchings and partitions. \newblock {\em Trans. Amer. Math. Soc.} {\bf 359} (2007), 1555--1575 (electronic). \bibitem{deutsch:bijective} Emeric Deutsch. \newblock A bijective proof of the equation linking the {S}chr{\"o}der numbers, large and small. \newblock {\em Discrete Math.} {\bf 241} (2001), 235--240. \bibitem{drake.kim:k-distant} Dan Drake and Jang~Soo Kim. \newblock $k$-distant crossings and nestings of matchings and partitions. \newblock {\em DMTCS Proceedings} {\bf AK} (2009), 349--360. \bibitem{kim.zeng:combinatorics} Dongsu Kim and Jiang Zeng. \newblock Combinatorics of generalized {T}chebycheff polynomials. \newblock {\em European J. Combinatorics} {\bf 24} (2003), 499--509. \bibitem{mansour.deng.ea:dyck} Toufik Mansour, Eva Y.~P. Deng, and Rosena R.~X. Du. \newblock Dyck paths and restricted permutations. \newblock {\em Discrete Appl. Math.} {\bf 154} (2006), 1593--1605. \bibitem{sloane:on-line} N.~J. A.~Sloane (ed.). \newblock The on-line encyclopedia of integer sequences, 2010. \bibitem{stein.waterman:new} P.~R. Stein and M.~S. Waterman. \newblock On some new sequences generalizing the {C}atalan and {M}otzkin numbers. \newblock {\em Discrete Math.} {\bf 26} (1979), 261--272. \bibitem{sulanke:narayana} Robert~A. Sulanke. \newblock The {N}arayana distribution. \newblock {\em J. Stat. Plan. Inference} {\bf 101} (2002), 311--326. \bibitem{sulanke:objects} Robert~A. Sulanke. \newblock Objects counted by the central {D}elannoy numbers. \newblock {\em J. Integer Sequences} {\bf 6} (2003), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Sulanke/delannoy.html}{Article 03.1.5}. \bibitem{viennot:combinatorial} G\'erard Viennot. \newblock A combinatorial theory for general orthogonal polynomials with extensions and applications. \newblock In {\em Orthogonal Polynomials and Applications (Bar-le-Duc, 1984)}, Vol.\ 1171 of {\em Lecture Notes in Mathematics}, Springer, 1985, pp.\ 139--157. \bibitem{viennot:theorie} G\'erard Viennot. \newblock Une th\'eorie combinatoire des p\^olynomes othogonaux generaux. \newblock Notes from a conference at the Universit\'e du Qu\'ebec \`a Montr\'eal, September 1983. \end{thebibliography} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% TeX-PDF-mode: t %%% End: \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A19; Secondary 05A15, 05A05. \noindent \emph{Keywords: } lattice paths, \Sch numbers, matchings, $231$-avoiding permutations. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A001003}, \seqnum{A001263}, \seqnum{A001850}, \seqnum{A004148}, \seqnum{A006318}, \seqnum{A060693}, \seqnum{A116363}, and \seqnum{A126216}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 15 2010; revised version received September 17 2010. Published in {\it Journal of Integer Sequences}, December 5 2010. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}