\documentclass[11pt]{amsart} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amssymb,latexsym,cite,longtable,url,array,booktabs} %\usepackage[linguistics]{forest} \usepackage{arydshln} \newcolumntype{L}{>{\raggedright\arraybackslash}p{8cm}} \newcolumntype{R}{>{\raggedright\arraybackslash}p{4.1cm}} \usepackage{longtable} \usepackage{pathlatex,color} \usepackage{tikz} \newcommand*\circled[1]{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {#1};}} \def\red{\textcolor{red} } \def\blue{\textcolor{blue} } \setlength{\unitlength}{1mm} \topmargin 0 pt \textheight 46\baselineskip \advance\textheight by \topskip \setlength{\parindent}{0pt} \setlength{\parskip}{3pt plus 2pt minus 1pt} \setlength{\textwidth}{155mm} \setlength{\oddsidemargin}{5.6mm} \setlength{\evensidemargin}{5.6mm} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{observation}[theorem]{Observation} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{fact}[theorem]{Fact} \newtheorem{example}[theorem]{Example} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{property}[theorem]{Property} \newtheorem{prop}[theorem]{Proposition} \newtheorem{problem}[theorem]{Problem} \newtheorem{notation}[theorem]{Notation} \def\T{\mathcal{T}} \def\P{\mathcal{P}_3} \newcommand{\I}{{\mathbf I}} \newcommand{\isim}{\stackrel{\I}{\sim}} \def\r{\ensuremath{\mathcal R}} \def\mbf#1{\mathchoice{\hbox{\boldmath $\displaystyle #1$}} {\hbox{\boldmath $\textstyle #1$}} {\hbox{\boldmath $\scriptstyle #1$}} {\hbox{\boldmath $\scriptscriptstyle #1$}}} \def\key{key\,} \begin{document} \title[]{Three classes of inversion sequences counted by large Schr\"oder numbers} \author{David Callan} \address{Department of Statistics, University of Wisconsin, Madison, WI 53706, USA} \email{callan@stat.wisc.edu} \author{Toufik Mansour} \address{Department of Mathematics, University of Haifa, 3498838 Haifa, Israel} \email{tmansour@univ.haifa.ac.il} \begin{abstract} In this paper, analytically and combinatorially, we reprove that the number of inversion sequences that avoid $\{100, 101, 201, 210\}$ (respectively $\{100, 110, 201, 210\}$) is given by the large Schr\"oder number, as shown by Martinez and Savage. Moreover, we show that the number of inversion sequences that avoid $\{101, 110, 201, 210\}$ is also given by the large Schr\"oder number. \end{abstract} \subjclass[2010]{05A05, 05A15} \keywords{Inversion sequences; Generating trees; Kernel method; Pattern avoidance; Schr\"order paths} \maketitle \section{Introduction} An {\em inversion sequence} of length $n$ is an integer sequence $e=e_0e_1\cdots e_n$ such that $0\leq e_i\leq i$ for each $0\leq i\leq n$. Let $\I_n$ denote the set of all the inversion sequences of length $n$. We say that an inversion sequence $e\in I_n$ contains the word $\tau=\tau_1\cdots\tau_k$ if there is a subsequence of length $k$ in $e$ that is order isomorphic to $\tau$; otherwise, we say that $e$ avoids $\tau$. Define $\I_n(\tau)$ to be the set of inversion sequences of length $n$ that avoid $\tau$. In this context, $\tau$ is called {\em pattern}. More generally, for any set $B$ of patterns, we define $\I_n(B)=\cap_{\tau\in B}\I_n(\tau)$. Two sets of patterns $B_1$ and $B_2$ are said to be {\em Wilf equivalent} if $|I_n(B_1)|=|I_n(B_2)|$, for all $n\geq 0$. The systematic study of pattern-avoidance for inversion sequences was initiated by Mansour and Shattuck \cite{ManS} for the patterns of length three with non-repeating letters, and by Corteel et al \cite{CMS} for repeating and non-repeating letters. In particular, \cite{ManS} gives an analytic and \cite{CMS} a bijective proof that $$\sum_{n\geq0}|\I_n(021)|x^n =Sch(x)=\frac{1-x-\sqrt{1-6x+x^2}}{2x}.$$ See also \cite{callan2021} for a bijective proof involving the little Schr\"oder numbers. Yan and Lin \cite{YanLin} completed the classification of the Wilf-equivalences for inversion sequences avoiding pairs of length-three patterns. Martinez and Savage \cite{MaSa} generalized and extended the notion of pattern-avoidance for the inversion sequences to triples of binary relations. In particular, they showed that \begin{align}\label{eqsch} \sum_{n\geq0}|\I_n(\{100, 101, 201, 210\})|x^n =\sum_{n\geq0}|\I_n(\{100, 110, 201, 210\})|x^n =Sch(x). \end{align} Hong and Li\cite{HLi} completed the Wilf classification for patterns of length four. More recently, the authors with Jelínek \cite{CJM} considered the classification of the Wilf-equivalences for inversion sequences avoiding triples of length-three patterns. The aim of this paper is to prove analytically and combinatorially the following result. \begin{theorem}\label{mth} Let $B_1=\{100, 101, 201, 210\}$, $B_2=\{100, 110, 201, 210\}$, and $B_3=\{101,110$, $201,210\}$. Then, for all $j=1,2,3$, \begin{align}\label{eqsch1} \sum_{n\geq0}|\I_n(B_j)|x^n =Sch(x). \end{align} \end{theorem} In particular, we reprove \eqref{eqsch} by two different proofs. \section{Analytical proofs} In this section, we present an analytical proof for \eqref{eqsch1}. To do that, we first use the algorithm presented in \cite{KMY} to guess and then to prove the rules of each generating tree (see \cite{W}) for all inversion sequences in $\cup_{n\geq0}\I_n$ that avoid $B_j$, where $j=1,2,3$. In each case, we translate the rules of the generating tree to a system of functional equations and then solve to obtain an explicit formula for the generating function $\sum_{n\geq0}|\I_n(B_j)|x^n$. In the next three subsections, we consider the enumeration problem of counting elements of $\I_n(B_j)$, where $j=1,2,3$. \subsection{Avoiding $B_3$} As we said, by using the algorithm of \cite{KMY}, we obtain the following result. \begin{lemma}\label{lemA1} The generating tree for $\cup_{n\geq0}\I_n(B_3)$ can be characterized as a generating tree $\mathcal{T}_3$ defined by a root $0$ and the following rules \begin{align*} &0^m\rightsquigarrow 0^{m+1},0^m1,\ldots,0^mm,\\ &0^mj\rightsquigarrow(0^{m+2-j})^{j+1},0^{m+1}(j+1),\ldots,0^{m+1}(m+1). \end{align*} \end{lemma} \begin{proof} Fix $0\in\I_0(B_3)$ to be the root of $\mathcal{T}$. Thus, it remains to show that the rules hold. By the definitions, the children of $0^m\in\I_m(B_3)$ are $0^{m+1},0^m1,\ldots,0^mm$. Thus, $0^m\rightsquigarrow 0^{m+1},0^m1,\ldots,0^mm$. Also, the children of $0^mj\in\I_{m+1}(B_3)$, $1\leq j\leq m$, are $0^mj0,0^mj1,\ldots,0^mjm$. Note that \begin{itemize} \item the subtree $\T(B_3;0^mji)$ of $\mathcal{T}$ with $0\leq i\leq j$ is isomorphic (in the sense of plane trees) to the subtree $\T(B_3;0^{m+2-j})$. To see that let $0^mji\pi'\in\I_n(B_3)$, then $\pi'$ does not contain any letter belong to the set $\{0,1,\ldots,i-1,i+1,\ldots,j\}$. Thus, $0^mji\pi'\in\I_n(B_3)$ if any only if $0^{m+2-j}\pi''\in I_{n+2-j}$, where $\pi''$ is the word that obtained from $\pi'$ after replacing the letter $k$ of $\pi'$ with $k-j$, where $k\geq j+1$. \item the subtree $\T(B_3;0^mji)$ of $\mathcal{T}$ with $j+1\leq i\leq m+1$ is isomorphic $\T(B_3;0^{m+1}i)$. This holds because $0^mji\pi'\in\I_n(B_3)$ if and only if $0^{m+1}i\pi'\in\I_n(B_3)$. \end{itemize} Thus, $0^mj\rightsquigarrow(0^{m+2-j})^{j+1},0^{m+1}(j+1),\ldots,0^{m+1}(m+1)$, which completes the proof. \end{proof} Define $A_m(x)$ (resp. $B_{m,j}(x)$) to be the generating functions for the number of nodes at level $n$ in the subtree of $\T_3$ with root $0^m$ (resp. $0^mj$) of $\T_3$, where the root of this subtree is the vertex $0^m$ (resp. $0^mj$) that stays at level $0$. Thus, Lemma \ref{lemA1} gives \begin{align*} A_m(x)&=x+xA_{m+1}(x)+x\sum_{j=1}^mB_{m,j}(x),\\ B_{m,j}(x)&=x+(j+1)xA_{m+2-j}(x)+x\sum_{i=j+1}^{m+1}B_{m+1,i}(x). \end{align*} Define $B_m(x;u)=\sum_{j=1}^mB_{m,j}(x)u^{j-1}$. Then, by multiplying the recurrence for $B_{m,j}(x)$ by $u^{j-1}$ and summing over $j=1,2,\ldots,m$, we obtain \begin{align*} A_m(x)&=x+xA_{m+1}(x)+xB_m(x;1),\\ B_m(x;u)&=\frac{x(1-u^m)}{1-u}+x\sum_{j=1}^m(j+1)A_{m+2-j}(x)u^{j-1}+\frac{x}{1-u}(B_{m+1}(x;1)-B_{m+1}(x;u)). \end{align*} Let $A(x;v)=\sum_{m\geq1}A_m(x)v^{m-1}$ and $B(x;v,u)=\sum_{m\geq1}B_m(x;u)v^{m-1}$. Then, by multiplying these two recurrences by $v^{m-1}$ and summing over $m\geq1$, we obtain \begin{align} A(x;v)&=\frac{x}{1-v}+\frac{x}{v}(A(x;v)-A(x;0))+xB(x;v,1),\label{eqA1}\\ B(x;v,u)&=\frac{x}{(1-v)(1-vu)}+\frac{x(2-vu)}{(1-vu)^2}(A(x;v)-A(x;0))\notag\\ &+\frac{x}{v(1-u)}(B(x;v,1)-B(x;v,u)).\label{eqA2} \end{align} In order to solve \eqref{eqA1}-\eqref{eqA2}, we {\bf assume} that the generating functions $A(x;v)$ and $B(x;v,u)$ satisfy two extra equations \begin{align} &\frac{A(x;v)}{B(x;v,1)}+\frac{1}{2}A(x;0)=1-v-\frac{1}{2}x,\label{eqA3}\\ &A(x;0)=\frac{1-x-\sqrt{1-6x+x^2}}{2}.\label{eqA4} \end{align} Note that the relation \eqref{eqA4} is guessed from the fact that we wish to prove $\sum_{n\geq0}|\I_n(B_2)|x^{n+1} =xSch(x)$. The relation \eqref{eqA3} is hard to guess directly from the problem, but here we used the first terms of these generating functions and we tested several relations such as $A(x;v)-B(x;v,1)$, $A(x;v)/B(x;v,v)$, and $A(x;v)/B(x;v,1)$. Since solution of the system \eqref{eqA1}-\eqref{eqA4} is a solution of the system \eqref{eqA1}-\eqref{eqA2}, we need only to solve the system \eqref{eqA1}-\eqref{eqA4}. By \eqref{eqA1}, \eqref{eqA3}, and \eqref{eqA4}, we obtain that \begin{align}\label{eqA5} A(x;v)=\frac{x((v^2+vx-2v+1)\sqrt{x^2-6x+1}+v^2x+vx^2-3v^2-5vx+4v+x-1)}{2(v-1)(v^2+vx-v+x)} \end{align} and $$B(x;v,1)=\frac{x((v+x-2)\sqrt{x^2-6x+1}+vx+x^2-3v-5x+2)}{2(1-v)(v^2+vx-v+x)}.$$ Now, by \eqref{eqA2}, we obtain \begin{align} B(x;v,u)&=\frac{x(uv^3+xuv^2-2uv^2+uv-2v^2-2xv+4v+x-2)\sqrt{x^2-6x+1}}{2(v^2+vx-v+x)(1-uv)^2(1-v)}\notag\\ &+\frac{xv(uv^2(x-3)+uv(x-4)(x-1)+u(x-1)+2v(2-x))}{2(v^2+vx-v+x)(1-uv)^2(1-v)}\notag\\ &+\frac{x(-2v(x^2-5x+3)+x^2-5x+2)}{2(v^2+vx-v+x)(1-uv)^2(1-v)}.\label{eqA6} \end{align} By using the expressions of $A(x;v)$ and $B(x;v,u)$, we see that \eqref{eqA1}-\eqref{eqA4} hold. Hence, we can state the following result. \begin{theorem}\label{thA} We have $$\sum_{n\geq0}|\I_n(B_3)|x^n =Sch(x).$$ Moreover, the generating functions $A(x;v)$ and $B(x;v,u)$ are given by \eqref{eqA5} and \eqref{eqA6}, respectively. \end{theorem} \subsection{Avoiding $B_2$} Again, by using the algorithm of \cite{KMY}, we obtain the following result. \begin{lemma}\label{lemB1} The generating tree for $\cup_{n\geq0}\I_n(B_2)$ can be characterized as a generating tree $\mathcal{T}_2$ defined by a root $0$ and the following rules \begin{align*} &0^m\rightsquigarrow 0^{m+1},0^m1,\ldots,0^mm,\\ &0^mj\rightsquigarrow(0^{m+2-j})^{j+1},0^{m+1}(j+1),\ldots,0^{m+1}(m+1). \end{align*} \end{lemma} By Lemma \ref{lemA1}, Theorem \ref{thA}, and Lemma \ref{lemB1}, we have the following result. \begin{theorem}\label{thB} We have $$\sum_{n\geq0}|\I_n(B_2)|x^n =Sch(x).$$ \end{theorem} \subsubsection{Avoiding $B_1$} \begin{lemma}\label{lemC1} The generating tree for $\cup_{n\geq0}\I_n(B_1)$ can be characterized as a generating tree $\mathcal{T}_1$ defined by a root $0$ and the following rules \begin{align*} &0^m\rightsquigarrow 0^{m+1},0^m1,\ldots,0^mm,\\ &0^mj\rightsquigarrow(0^{m+1-j})^j,0^{m+1}j,\ldots,0^{m+1}(m+1). \end{align*} \end{lemma} Define $A_m(x)$ (resp. $B_{m,j}(x)$) to be the generating functions for the number of nodes at level $n$ in the subtree of $\T_1$ with root $0^m$ (resp. $0^mj$) of $\T_1$, where the root of this subtree is the vertex $0^m$ (resp. $0^mj$) that stays at level $0$. Thus, Lemma \ref{lemC1} gives \begin{align*} A_m(x)&=x+xA_{m+1}(x)+x\sum_{j=1}^mB_{m,j}(x),\\ B_{m,j}(x)&=x+jxA_{m+1-j}(x)+x\sum_{i=j}^{m+1}B_{m+1,i}(x). \end{align*} Define $B_m(u)=\sum_{j=1}^mB_{m,j}u^{m-j}$. Then, by multiplying the recurrence for $B_{m,j}(x)$ by $u^{m-j}$ and summing over $j=1,2,\ldots,m$, we obtain \begin{align*} A_m(x)&=x+xA_{m+1}(x)+xB_m(x;1),\\ B_m(x;u)&=\frac{x(1-u^m)}{1-u}+x\sum_{j=1}^mjA_{m+1-j}(x)u^{m-j}+x\sum_{j=1}^m\sum_{i=j}^{m+1}B_{m+1,i}(x)u^{m-j}. \end{align*} Let $A(x;v)=\sum_{m\geq1}A_m(x)v^{m-1}$ and $B(x;v,u)=\sum_{m\geq1}B_m(x;u)v^{m-1}$. Then, by multiplying these two recurrences by $v^{m-1}$ and summing over $m\geq1$, we obtain \begin{align} A(x;v)&=\frac{x}{1-v}+\frac{x}{v}(A(x;v)-A(x;0))+xB(x;v,1),\label{eqC1}\\ B(x;v,u)&=\frac{x}{(1-v)(1-vu)}+\frac{x}{(1-v)^2}A(x;vu)\notag\\ &+\frac{x}{vu(1-u)}(B(x;v,u)-uB(x;vu,1))-\frac{x}{vu}B(x;v,0).\label{eqC2} \end{align} Again, in order to solve \eqref{eqC1}-\eqref{eqC2}, we {\bf assume} that the generating functions $A(x;v)$ and $B(x;v,u)$ satisfy \begin{align} &\frac{A(x;v)}{B(x;v,1)}+\frac{1}{2}A(x;0)=1-v-\frac{1}{2}x,\label{eqC3}\\ &A(x;0)=xSch(x)=\frac{1-x-\sqrt{1-6x+x^2}}{2},\label{eqC4}\\ &B(x;v,0)=-\frac{A(x;0)}{(1-v)^2}(v+1+A(x;0)),\label{eqC5} \end{align} By \eqref{eqC1}, \eqref{eqC3}, and \eqref{eqC4}, we obtain that \begin{align}\label{eqC6} A(x;v)=\frac{x((v^2+vx-2v+1)\sqrt{x^2-6x+1}++v^2x+vx^2-3v^2-5vx+4v+x-1)}{2(v-1)(v^2+vx-v+x)} \end{align} and $$B(x;v,1)=\frac{x((v+x-2)\sqrt{x^2-6x+1}+vx+x^2-3v-5x+2)}{2(1-v)(v^2+vx-v+x)}.$$ Now, by \eqref{eqC2}, \eqref{eqC5}, and \eqref{eqC6}, we obtain \begin{align} B(x;v,u)&=\frac{x(u^2v^3-2u^2v^2+xuv^2-2uv^2-2xuv+4uv+v+x-2)\sqrt{1-6x+x^2}}{2(v-1)^2(1-uv)(u^2v^2+xuv-uv+x)}\notag\\ &+\frac{x((x-3)u^2v^3+2(2-x)u^2v^2+(x-4)(x-1)uv^2)}{2(v-1)^2(1-uv)(u^2v^2+uvx-uv+x)}\notag\\ &+\frac{x(-2x^2uv+10xuv-6uv+vx+x^2-v-5x+2)}{2(v-1)^2(1-uv)(u^2v^2+uvx-uv+x)}.\label{eqC7} \end{align} By using the expressions for $A(x;v)$ and $B(x;v,u)$, we see that \eqref{eqC1}-\eqref{eqC5} all hold. Hence, we can state the following result. \begin{theorem}\label{thC} We have $$\sum_{n\geq0}|\I_n(B_1)|x^n =Sch(x).$$ Moreover, the generating functions $A(x;v)$ and $B(x;v,u)$ are given by \eqref{eqC6} and \eqref{eqC7}, respectively. \end{theorem} \section{Combinatorial proofs} In this section, we present combinatorial proofs of Theorems \ref{thA}, \ref{thB}, and \ref{thC}. First, let us recall $UDF$ and Schr\"oder paths. A $UDF$ path is is a lattice path of upsteps $U= (1,1)$, downsteps $D=(1,-1)$ and flatsteps $F=(2,0)$. The horizontal line through the initial point is \emph{ground level} and heights are measured relative to ground level. A \emph{Schr\"{o}der path}\footnote{See \url{http://oeis.org/A006318}} is a $UDF$ path that ends at ground level and never dips below ground level. Its size is measured as the number of $U$s plus the number of $F$s. We use the term \emph{weak-fall} step to mean an $F$ or a $D$. Since $\#\, U$s = $\#\,D$s in a Schr\"{o}der path, the size of a Schr\"{o}der path is the number of weak-fall steps it contains. Let $\r_n$ denote the set of Schr\"{o}der paths of size $n$. An \emph{elevated} Schr\"{o}der path is one that starts $U$, ends $D$, and has no vertex at ground level other than the endpoints. The \emph{elevation} of a Schr\"{o}der path $P$ is $U.P.D$, where dots denote concatenation. An \emph{ascent} in a path is a maximal run of contiguous upsteps and similarly for a \emph{descent}. The terminal descent of a Schr\"{o}der path is the run of $D$s that terminates the path; it is of length 0 if the path ends with a flatstep. \subsection{Bijection $\mbf{\phi}$ from $\mbf{\I_n(B_1)}$ to $\mbf{\r_n}$.} Recall that $B_1=\{100,101,201,210\}$. The set $\I_n(B_1)$ can be characterized as the set of inversion sequences $e_0e_1 \dots e_n$ such that for each $i\ge 2$, if $e_i< e_{i-1}$ then $e_j>e_{i-1}$ for all $j\ge i+1$. In particular, for an avoider $e_0e_1 \dots e_n$ with $n\ge 1,$ we have $\max(e_i)_{i=0}^n=e_n$ if $e_n\ge e_{n-1}$, and $=e_{n-1}$ otherwise. It will be convenient to say a vertex in a Schr\"{o}der path is a \emph{\key} vertex if it is a valley vertex---the vertex separating a contiguous $DU$---or the terminal vertex of a flatstep $F$ (regardless of the next step). Define $\phi(0)=\epsilon$, the empty path. Now, suppose given $e=e_0e_1\dots e_n \in \I_n(B_1)$ with $n\ge 1$. By induction, set $P=\phi(e_0\dots e_{n-1}) \in \r_{n-1}$ and set $i=n-e_n$. Also, set $Q=P.D$. Note that $Q$ contains $n$ weak-fall steps and ends at height $-1$. Define $S=\phi(e)$ as follows. If $i=n$, set $S=U.Q$, thus forming the elevation of $P$. If $0\le i \le n-1$, locate the $i$-th weak-fall step in $Q$ measuring from the end of the path, and insert a $U$ immediately before this weak-fall step to obtain an intermediate Schr\"{o}der path $R\in \r_n$. In case $i=0$, this is interpreted to mean that $U$ is inserted at the end of Q, thereby introducing a \key vertex at height $-1$. In the path $R$, if the step immediately preceding the inserted $U$ is a $D$ such that the valley vertex formed by this $DU$ is at odd height, delete this $D$ and change the inserted $U$ to an $F$ to obtain $S$. Otherwise, set $S=R$. For example, with $n=4$ and $e=00102$, we have $P=\phi(0010)=UUDUDD\ \textrm{(induction)},\ i=2$, and $P,Q,R,S$ are shown in Figure 1 below, where a $DU$ in $R$ is changed to an $F$ in $S$. \Einheit=0.4cm \[ \SPfad(-17,0),111111\endSPfad \Pfad(-17,0),334344\endPfad \SPfad(-9,0),1111111\endSPfad \Pfad(-9,0),33434\endPfad \blue{\Pfad(-4,1),44\endPfad} \DuennPunkt(-17,0) \DuennPunkt(-16,1) \DuennPunkt(-15,2) \DuennPunkt(-14,1) \DuennPunkt(-13,2) \DuennPunkt(-12,1) \DuennPunkt(-11,0) \DuennPunkt(-9,0) \DuennPunkt(-8,1) \DuennPunkt(-7,2) \DuennPunkt(-6,1) \DuennPunkt(-5,2) \NormalPunkt(-4,1) \DuennPunkt(-3,0) \DuennPunkt(-2,-1) \SPfad(0,0),11111111\endSPfad \Pfad(0,0),334343\endPfad \blue{\Pfad(6,2),44\endPfad} \SPfad(10,0),1111111\endSPfad \Pfad(10,0),3343144\endPfad \Label\u{ \textrm{$P$}}(-14,-1) \Label\u{ \textrm{$Q,\ i=2$}}(-6,-1) \Label\u{ \textrm{$R$}}(4,-1) \Label\u{ \textrm{$S=\phi(00102)$}}(13.5,-1) \DuennPunkt(0,0) \DuennPunkt(1,1) \DuennPunkt(2,2) \DuennPunkt(3,1) \DuennPunkt(4,2) \NormalPunkt(5,1) \NormalPunkt(6,2) \DuennPunkt(7,1) \DuennPunkt(8,0) \DuennPunkt(10,0) \DuennPunkt(11,1) \DuennPunkt(12,2) \DuennPunkt(13,1) \DuennPunkt(14,2) \DuennPunkt(15,2) \DuennPunkt(16,1) \DuennPunkt(17,0) \Label\u{\textrm{Figure 1: The path $\phi(00102)$}}(0,-2.5) \] \vspace*{3mm} \noindent As another example, $e=01131$ yields $P=FUDUD,\ i=3$, and $Q,S$ are shown in Figure 2 below, where a $DU$ at ground level in $Q$ is raised to odd height in $R=S$. \Einheit=0.5cm \[ \SPfad(-8,0),111111\endSPfad \Pfad(-8,0),13\endPfad \blue{\Pfad(-6,1),4\endPfad} \Pfad(-5,0),3\endPfad \blue{\Pfad(-4,1),44\endPfad} \SPfad(1,0),1111111\endSPfad \Pfad(1,0),133\endPfad \Pfad(5,1),3\endPfad \blue{\Pfad(4,2),4\endPfad} \blue{\Pfad(6,2),44\endPfad} \DuennPunkt(-8,0) \DuennPunkt(-7,0) \NormalPunkt(-6,1) \DuennPunkt(-5,0) \DuennPunkt(-4,1) \DuennPunkt(-3,0) \DuennPunkt(-2,-1) \Label\u{\textrm{$Q,\ i=3$}}(-5,-1) \Label\u{\textrm{$R=S=\phi(01131)$}}(4.5,-1) \DuennPunkt(1,0) \DuennPunkt(2,0) \NormalPunkt(3,1) \NormalPunkt(4,2) \DuennPunkt(5,1) \DuennPunkt(6,2) \DuennPunkt(7,1) \DuennPunkt(8,0) \Label\u{\textrm{Figure 2: The path $\phi(01131)$}}(0,-2.5) \] We have $\phi(00)=UD,\,\phi(01)=F$ and the action of $\phi$ on avoiders for $n=2$ is shown in Figure 3 below. \Einheit=0.4cm \[ \SPfad(-15,0),1111\endSPfad \Pfad(-15,0),3344\endPfad \SPfad(-9,0),1111\endSPfad \Pfad(-9,0),3434\endPfad \DuennPunkt(-15,0) \DuennPunkt(-14,1) \DuennPunkt(-13,2) \DuennPunkt(-12,1) \DuennPunkt(-11,0) \DuennPunkt(-9,0) \DuennPunkt(-8,1) \DuennPunkt(-7,0) \DuennPunkt(-6,1) \DuennPunkt(-5,0) \SPfad(-3,0),11\endSPfad \Pfad(-3,0),341\endPfad \DuennPunkt(-3,0) \DuennPunkt(-2,1) \DuennPunkt(-1,0) \DuennPunkt(0,0) \SPfad(2,0),111\endSPfad \Pfad(2,0),314\endPfad \SPfad(8,0),11\endSPfad \Pfad(7,0),134\endPfad \Label\u{\phi(000)}(-13,-.5) \Label\u{\phi(001)}(-7,-.5) \Label\u{\phi(002)}(-1.5,-.5) \Label\u{\phi(010)}(3.5,-.5) \Label\u{\phi(011)}(8.5,-.5) \Label\u{\phi(012)}(13,-.5) \DuennPunkt(2,0) \DuennPunkt(3,1) \DuennPunkt(4,1) \DuennPunkt(5,0) \DuennPunkt(7,0) \DuennPunkt(8,0) \DuennPunkt(9,1) \DuennPunkt(10,0) \Pfad(12,0),11\endPfad \DuennPunkt(12,0) \DuennPunkt(13,0) \DuennPunkt(14,0) \Label\u{\textrm{Figure 3: The paths for $\I_2(B_1)$}}(0,-2.5) \] \medskip For purposes of inverting $\phi$, note that whenever $\phi$ introduces a new \key vertex in $S$ that was not present in $P$, it is at even height. To reverse the map, it is only necessary to determine where the inserted $U/F$ appears in $S$ for then we can retrieve $i$ by counting the weak-fall steps after this $U/F$, we can retrieve $P$ by deleting the last step of $S$ and deleting the inserted $U$ or, in case the inserted $U$ became an $F$, changing this $F$ to a $D$. Then, by induction, we get the first $n$ terms of the inverse avoider as $e_0 \dots e_{n-1} = \phi^{-1}(P)$, and $e_n=n-i$. Here is the procedure to identify the location of the inserted $U/F$. \begin{itemize} \vspace*{-1mm} \item If $S$ has no \key vertices at even height (so $S$ must be an elevated path for else there is a valley vertex or $F$ step at ground level, thus at even height), then a $U$ was inserted at the end of the run of (0 or more) upsteps at the start of $Q$ to get $R=S=\phi(e)$. Delete the first and last steps of $S$ to get $P$ and set $i=n$. \item If $S$ has at least one \key vertex at even height, locate the last such vertex $V$. If $V$ is immediately followed by a $U$, the ascent started by this $U$ is where a $U$ was inserted, and $P$ and $i$ can be recovered. Otherwise, $V$ terminates an $F$ step that either ends the path or is immediately followed by a $D$ (it can't be followed by another $F$ for than $V$ would not be the last \key vertex at even height and it is not followed by $U$ by assumption) and this $F$ step replaced a $DU$ in $R$ to get $S$. So change the $F$ to $D$ and delete the last step to get $P$, and count weak-fall steps after $V$ to get $i$. (If the path $S$ ends with a flatstep $F$, the net effect is to delete $F$, and $i=0$.) \end{itemize} To explain why this reversal procedure works, we begin with a useful lemma. \begin{lemma} \label{init} In an avoider $e = e_0e_1 \dots e_n \in \I_n(B_1)$,\\ $($i$\,)$ the number of consecutive $U$s that start $\phi(e)$ %$($which may be 0$\,)$ is the number of noninitial 0s in $e$, and \\ $($ii$\,)$ the number of consecutive $D$s that terminate $\phi(e)$ %$($which may be 0$\,)$ is $n-\max\{e_i\}$. \begin{proof} We prove both parts by simultaneous induction on $n$. The base cases are clear. (i) Suppose first that $e_0\dots e_{n-1}$ is weakly increasing so that all its $0$\,s occur at the start. By induction, the initial ascent length of $P=\phi(e_0\dots e_{n-1})$ is the number of initial 0s in $e_1\dots e_{n-1}$. If $e_n=0$, then $P$ is elevated to get $\phi(e)$ and the conclusion holds. If $e_n\ne 0$, then $ia$. Hence, $i=n-e_na$, then $\max\{e_i\}_{i=0}^n = e_n$ and $i=n-e_n < n-a$. Since $U$ is inserted just before the $i$th-from-end step on the terminal descent of $n-a$ $D$s in $Q$, we see that $\phi(e)$ ends with precisely $i=n-e_n=n-\max\{e_i\}_{i=0}^n$ $D$s, as required. \end{proof} \end{lemma} The pyramid paths $U^n D^n,\ n\ge 0$, are the only Schr\"{o}der paths with no \key vertices at all and they correspond under $\phi$ to the all-zeros avoiders $0^{n+1}$. Otherwise, the last (rightmost) \key vertex in a Schr\"{o}der path is the very last vertex if the path ends $F$ and the first vertex of the last ascent if the path ends $D$. For $n\ge 2$, consider an avoider $e$ and the construction for $\phi$ described above. Set $a=\max(e_j)_{j=0}^{n-1}$\ $(=\max(e_{n-2},e_{n-1})\,)$. By Lemma \ref{init}, $P$ ends with $n-1-a$ downsteps and so $Q$ ends with $n-a$ downsteps. If $e_n\ge e_{n-1}$, then certainly $e_n \ge a$ and so $i=n-e_n\le n-a$. Hence, the construction will insert $U$ at one of the vertices \emph{on the terminal descent} of $Q$ (since $Q$ ends $D$, there are at least two such vertices). If $e_n=e_{n-1}$, then $i=n-a$, so $U$ is inserted at the top vertex of the terminal descent (Figure 4a), no new \key vertex is introduced and no \key vertex of $P$ is disturbed. If $e_n>e_{n-1}$, then $in-a$ and the $U$ must be inserted at a vertex strictly before the last \key vertex of $P$ and all \key vertices after the inserted $U$ are raised 1 unit (example in Figure 2 above). Next, for an avoider $e=e_0e_1\dots e_n \in \I_n(B_1)$, consider the paths $P_k,Q_k,$ $R_k,S_k,$ with $P_k=\phi(e_0\dots e_k)$ used in the recursive construction of $\phi(e)$ described above as $k$ increases from 1 to $n-1$. As long as $e_k\ge e_{k-1}$, all \key vertices are at even level and everything is fine. At the first descent (if there is one) $e_ke_{k-1}$, and so a new last \key vertex is introduced, not disturbing its predecessor \key vertex at odd height, and this last \key vertex is at even height. As long as the terms of $e$ continue to weakly increase, existing \key vertices are undisturbed and any new \key vertex is at even height, the last \key vertex serving to recover the inserted $U$. At the next descent, say $e_{k+m}k+m-e_{k+m}$. Thus, if a \key vertex reaches odd height due to the insertion of a $U$, it remains henceforth at that height, and the procedure for inverting $\phi$ works. A consequence of the preceding analysis is that $\phi$ takes the number of descents in an avoider $e$ to the number of runs of \key vertices at odd height in the corresponding Schr\"{o}der path. (The \key vertices occur in runs of one height parity followed by a run of the other height parity.) \subsection{Bijection from $\mbf{\I_n(B_1)}$ to $\mbf{\I_n(B_2)}$.} Recall that $B_1=\{100,101,201,210\}$ and $B_2=\{100,110,201,210\}$. The $B_2$-avoiders can be characterized as the inversion sequences $e_0\dots e_n$ that satisfy for $i\ge 1$ (i) $e_i\ge \max\mskip2mu$(descent tops in $e_0\dots e_{i-1}$), and (ii) $e_i\ge \max\mskip2mu$(repeated entries in $e_0\dots e_{i-1}$). To define the bijection, given $e_0\dots e_n \in \I_n(B_1)$, split the sequence into segments after each descent bottom and place each segment in a box. Each segment is weakly increasing except for a descent bottom in the last position (the last segment may or may not end with a descent), and all entries in each noninitial box exceed all entries in the preceding box. Within each box, place a circle around the descent bottom (if there is one) and around the second occurrence of each repeated entry that is greater than the descent bottom. Then within each box, rotate the circled entries to the right, and erase circles and boxes. An example is shown below. \[ \begin{array}{l} \framebox{0\,1\,1\,2\,\circled{2}\,2\,2\,3\,\circled{3}\,4\,\circled{1}}\,\framebox{6\,8\,\circled{8}\,8\,\circled{5}}\, \framebox{10\, \circled{9}}\, \framebox{11\,\,11\,\,13\vphantom{\circled{2}}}\ \rightarrow \\[2mm] \framebox{0\,1\,1\,2\,\circled{1}\,2\,2\,3\,\circled{2}\,4\,\circled{3}}\,\framebox{6\,8\,\circled{5}\,8\,\circled{8}}\, \framebox{10\, \circled{9}}\, \framebox{11\,\,11\,\,13\vphantom{\circled{2}}} \ = \\[2mm] \ 0\mskip4mu 1\mskip4mu 1\mskip4mu 2\mskip6mu 1\mskip6mu 2\mskip4mu 2\mskip4mu 3\mskip9mu 2\mskip8mu 4\mskip8mu 3\mskip21mu 6\mskip4mu 8\mskip8mu 5\mskip8mu 8\mskip10mu 8\mskip20mu 10\mskip16mu 9\mskip19mu 11\,\,11\,\,13 \end{array} \] To describe the inverse map, we use the following Lemma \begin{lemma} For $e=e_0\dots e_n \in \I_n(B_2)$, if $bab$ is an instance of a 101 pattern in $e$, then $($i$\,)$ $a$ is immediately preceded by $b$ in $e$, $($ii$\,)$ $a$ occurs only once as part of a 101 pattern and such $a$'s increase left to right. \end{lemma} \begin{proof} (i) Suppose, for a contradiction, that $bcab$ appears in $e$ with $b>a$ (so $bab$ is a 101) and $c\ne b$. If $c>b$, then $cab$ is a forbidden 201; if $ae_j$ for some $ie_j$ would imply $bae_j$ is a 201. In $\psi(e)$, the entry $e_k$ becomes $b$ and then $e_ie_j b$ is a 210 in $\psi(e)$. \qed %--------------------------------------------------------------- \begin{thebibliography}{99} \bibitem{CJM} D. Callan, V. Jelínek, and T. Mansour, Inversion sequences avoiding a triple of patterns of 3 letters, preprint. \bibitem{callan2021} D. Callan, Some bijections for lattice paths, preprint, arXiv:2112.05241, Dec 2021. \bibitem{CMS} S. Corteel, M.A. Martinez, C.D. Savage, and M. Weselcouch, Patterns in inversion sequences I, {\em Discrete Math. Theor. Comput. Sci.} 18(2) (2016). \bibitem{HLi} L. Hong and R. Li, Length-four pattern avoidance in inversion sequences, https://arxiv.org/abs/2112.15081. \bibitem{KMY} I. Kotsireas, T. Mansour, and G. Yıldırım, An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences, {\em J. Symb. Comput.} 120 (2024), Article 102231. \bibitem{ManS} T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, {\em Pure Math. Appl.} 25(2) (2015), 157--176. \bibitem{MaSa} M.A. Martinez and C.D. Savage, Patterns in inversion sequences II: inversion sequences avoiding triples of relations, {\em J. Integer Seq.} 21 (2018), Article 18.2.2. \bibitem{YanLin} C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, {\it Discrete Math. Theor. Comput. Sci.} 22(1) (2020-2021), Paper No. 23. \bibitem{W} J. West, Generating trees and forbidden subsequences, {\em Discrete Math.} 157 (1996), 363--374. \end{thebibliography} \end{document}