%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{27}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%Sergi and Juan's packages and macros:
\usepackage{amssymb,amsmath,amsthm,latexsym}
\usepackage{multicol}
\usepackage{verbatim,color}
\usepackage[raggedright]{titlesec} %This wraps titles so they don't go out of bounds

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prob}[theorem]{Problem}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\newcommand\bI{\mathbf{I}}
\newcommand\dist{\operatorname{dist}}
\DeclareMathOperator{\Em}{Em}
\newcommand\ul{\underline}
\newcommand{\Inv}{\mathcal{I}}
\newcommand\Tstrut{\rule{0pt}{2.6ex}}
\newcommand\Bstrut{\rule[-0.9ex]{0pt}{0pt}}
\newcommand{\seqnum}[1]{#1}
%%%%%%%%%%%%%%%%%%%%%%%%


%% define your title in the usual way
\title{Inversion sequences avoiding consecutive patterns}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Juan S. Auli\thanks{\href{mailto:juan.s.auli.gr@dartmouth.edu}{juan.s.auli.gr@dartmouth.edu}.}\addressmark{1}
  \and Sergi Elizalde\thanks{\href{mailto:sergi.elizalde@dartmouth.edu}{sergi.elizalde@dartmouth.edu}. Partially supported by Simons Foundation grant \#280575.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Dartmouth College, Hanover, NH, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
Inversion sequences are integer sequences $e_1e_2\dots e_n$ such that $0\leq e_i<i$ for each $i$.
The study of classical patterns in inversion sequences was initiated by Corteel--Martinez--Savage--Weselcouch and Mansour--Shattuck.
Here we focus on consecutive patterns in inversion sequences, namely patterns whose entries are required to occur in adjacent positions.
We enumerate inversion sequences that avoid small consecutive patterns. We also study the notion of Wilf equivalence in this setting, as well as generalizations that consider the positions of the occurrences, and classify patterns of length up to 4 into equivalence classes.

Finally, in analogy to the work of Martinez--Savage in the classical case, we consider  consecutive patterns of relations among 3 adjacent entries.
Our setting allows us to give a simple bijective proof of a result of Baxter--Shattuck and Kasraoui about vincular permutation patterns, and to prove a conjecture of Martinez--Savage about certain unimodal inversion sequences.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{inversion sequence, pattern avoidance, consecutive pattern, Wilf equivalence}


\addbibresource{fpsac}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle


\section{Introduction}\label{sec:intro}


A common encoding of permutations is by their inversion sequences. Specifically, denoting by $S_n$ the set of permutations of $[n]=\{1,2,\ldots,n\}$, and by $\bI_n$ the set of inversion sequences of length $n$ ---that is, integer sequences $e=e_{1}e_{2}\dots e_{n}$ with $0\leq e_{i}<i$ for each $i$--- one can define a bijection $\Theta:S_{n}\rightarrow\bI_{n}$ that assigns to each $\pi\in S_n$ its inversion sequence
\begin{equation}\label{eq:theta_bijection}
\Theta(\pi)=e=e_{1}e_{2}\dots e_{n}, \quad\textnormal{ where }\quad
e_{j}=|\{i:i<j\textnormal{ and }\pi_{i}>\pi_{j}\}|.
\end{equation}
Clearly, $e_1+\cdots+e_n$ is the number of inversions of $\pi$, namely, pairs $(i,j)$ with $i<j$ and $\pi_i>\pi_j$.

In analogy to patterns in permutations, a research area that has received a lot of attention in the last few decades, one can study patterns in inversion sequences. In this context,
a {\em pattern} is a word $p=p_{1}p_{2}\dots p_{r}$ with $p_{i}\in\{0,1,\ldots,r-1\}$ for each $i$, where any value $j>0$ can appear in $p$ only if $j-1$ appears as well.
Given a word $w=w_1w_2\dots w_k$ over the integers, define its {\em reduction} to be the word obtained by
replacing all the occurrences of the $i$th smallest entry of $w$ with $i-1$ for all $i$. Then, an inversion sequence $e$ {\em contains} the
classical pattern $p=p_{1}p_{2}\dots p_{r}$ if there exists
a subsequence
$e_{i_{1}}e_{i_{2}}\dots e_{i_{r}}$ of $e$ (where $i_1<\cdots<i_r$) with reduction $p$.
Otherwise, we say that $e$ {\em avoids}~$p$. For instance, the inversion sequence $e=00014224$ avoids the pattern $210$, but it contains the pattern $101$ because $e_{5}e_{6}e_{8}=424$ has reduction $101$.

The study of classical patterns in inversion sequences was started by Corteel, Martinez, Savage, and Weselcouch~\cite{MartinezSavageI}, and Mansour and Shattuck~\cite{MansourShattuck}. Their work connected classical patterns in inversion sequences to other combinatorial structures, which inspired more research in the area~\cite{Beaton, 
KimLin,%  Lin, 
MartinezSavageII, Yan}.
Motivated by this work and by the growing interest in consecutive patterns in permutations~\cite{ElizaldeNoy}, we
initiate an analogous systematic study of consecutive patterns in inversion sequences. 
In this extended abstract, most results are presented without a proof; for more details, we refer the reader to the full papers~\cite{AuliElizalde,AuliElizaldeII}.
In the definition below, the entries of a consecutive pattern are underlined to distinguish it from a classical pattern.

\begin{definition} An inversion sequence $e$ {\em contains} the consecutive pattern
$p=\underline{p_{1}p_{2}\dots p_{r}}$ if there is a consecutive subsequence
$e_{i}e_{i+1}\dots e_{i+r-1}$ of $e$ whose reduction is $p$; this subsequence is called an {\em occurrence} of $p$ in position $i$.
Otherwise, we say that $e$ {\em avoids} $p$.  Define
\[
\Em(p,e)=\{i:e_{i}e_{i+1}\dots e_{i+r-1} \textnormal{ is an occurrence of } p\}.
\]
Denote by $\bI_n(p)$ the set of inversion sequences of length $n$ that avoid $p$.
\end{definition}

\begin{example}\label{exa:contain_avoid_consec}
The inversion sequence $e=0021100300\in\bI_{10}$ avoids  $\underline{120}$, but it contains $\underline{010}$, since $e_7e_8e_9=030$ is an occurrence of $\underline{010}$. It also contains three occurrences of $p=\underline{100}$, in positions $\Em(p,e)=\{3,5,8\}$.
\end{example}


It is sometimes useful to represent an inversion sequence $e$ as an underdiagonal lattice path consisting of unit horizontal and vertical steps. Each entry $e_{i}$ of $e$ is represented by a horizontal step: a segment between the points $(i-1,e_{i})$ and $(i,e_{i})$. The vertical steps are then inserted to make the path connected (see \cref{fig:path_represent} (a)(b)).

We are also interested in the following equivalence relations, defined in analogy to those for consecutive patterns in permutation~\cite{DwyerElizalde}. Henceforth, unless otherwise stated,
patterns will refer to consecutive patterns in inversion sequences, and
equivalence of patterns will refer to the equivalences in \cref{def:Wilf}.

\begin{definition}\label{def:Wilf} Let $p$ and $p'$ be consecutive patterns. We say that $p$ and $p'$ are
\begin{itemize}
\item
{\em Wilf equivalent\/}, denoted by $p\sim p'$, if
$|\bI_{n}(p)|=|\bI_{n}(p')|$,
for all $n$;
\item
{\em strongly Wilf equivalent\/}, denoted by $p\stackrel{s}{\sim}p'$,
if for each $n$ and $m$, the number of
inversion sequences in
$\bI_{n}$ containing $m$ occurrences of $p$ is the same as for $p'$;
\item {\em super-strongly Wilf equivalent}, denoted  by
$p\stackrel{ss}{\sim}p'$, if the above condition holds
for any set of prescribed positions for the $m$ occurrences; that is,
\[
|\{e\in\bI_{n}:\Em(p,e)=T\}|=|\{e\in\bI_{n}:\Em(p',e)=T\}|.
\]
for all $n$ and all $T\subseteq [n]$.
\end{itemize}
\end{definition}

Clearly, $p\stackrel{ss}{\sim}p'$ implies $p\stackrel{s}{\sim}p'$, which in turn implies $p\sim p'$.
An equivalence of any one of the these three types will be called a {\em generalized Wilf equivalence}.

\section{Consecutive patterns of length 3}\label{sec:conseclength3}

For any consecutive pattern $p$ of length 3, we are able to give recurrences to compute the numbers $|\bI_{n}(p)|$. Most of our recurrences
use the refinement $\bI_{n,k}(p)=\{e\in\bI_{n}(p):e_{n}=k\}$. A list of these recurrences is given in \cref{tab1}.


\begin{table}[htb]
\resizebox{\columnwidth}{!}{
 \begin{tabular}{ c@{\hskip 0.2in}c@{\hskip 0.2in}p{11cm} }
 \hline
 Pattern $p$ & in the OEIS~\cite{OEIS} & Recurrence for $|\bI_{n,k}(p)|$
 \Tstrut\Bstrut\\
 \hline
 $\underline{012}$ & A049774 & $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-\sum_{l= 1}^{k-1}\sum_{j= 0}^{l-1}\sum_{i\geq j}|\bI_{n-3,i}(p)|$ \Tstrut\\
 $\underline{021}$ & A071075 & $
|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
(n-2-k)\sum_{j= 0}^{k-1}|\bI_{n-2,j}(p)|$
  \Tstrut\\
 $\underline{102}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 \sum_{j\geq1}j|\bI_{n-2,j}(p)|$ \Tstrut\\
 $\underline{120}$ & A200404 & $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-\sum_{j>k}(n-2-j)|\bI_{n-2,j}(p)|$  \Tstrut\\
 $\underline{201}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-k
 \sum_{j>k}|\bI_{n-2,j}(p)|$ \Tstrut\\
 $\underline{210}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 \sum_{l=k+1}^{n-4}\sum_{j=l+1}^{n-3}\sum_{i\leq j}|\bI_{n-3,i}(p)|$ \Tstrut\\
 $\underline{000}$ & A052169 \Tstrut & $|\bI_{n}(p)|=\frac{(n+1)!-d_{n+1}}{n}$,
 where $d_{n}=$ \# of derangements of [n]\Tstrut\\
 $\underline{001}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 \sum_{j<k}|\bI_{n-2,j}(p)|$ \Tstrut\\
 $\underline{010}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 (n-2-k)|\bI_{n-2,k}(p)|$ \Tstrut\\
 $\underline{011}$ & New\Tstrut &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 \sum_{j<k}|\bI_{n-2,j}(p)|$ if $k\neq n-1$, and
 $|\bI_{n,n-1}(p)|=|\bI_{n-1}(p)|$ \\
 $\underline{100} \stackrel{ss}{\sim} \underline{110}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 \sum_{j>k}|\bI_{n-2,j}(p)|$ \Tstrut\\
 $\underline{101}$ & New &
 $|\bI_{n,k}(p)|=|\bI_{n-1}(p)|-
 k|\bI_{n-2,k}(p)|$ \Tstrut\Bstrut\\
 \hline
 \end{tabular}
}
\caption{Enumerative results for avoidance of consecutive patterns of length 3.}\label{tab1}
\end{table}

Even though we do not include the proofs of the results in \cref{tab1} in this extended abstract, we will mention some consequences and generalizations.
Next is a recurrence for the number of inversion sequences avoiding the consecutive pattern consisting of $r$ zeros. We denote this pattern by $\underline{0}^{r}$.

\begin{proposition}\label{prop_general_0s}
Let $n\geq r\geq 2$. The sequence $|\bI_{n}(\underline{0}^{r})|$
satisfies the recurrence
\[
|\bI_{n}(\underline{0}^{r})|=\sum_{j=1}^{r-1}(n-j)|\bI_{n-j}(\underline{0}^{r})|,
\]
with initial conditions $|\bI_{n}(\underline{0}^{r})|=n!$, for $1\leq n<r$.
\end{proposition}

Denoting by $d_n$ be the number of derangements (i.e., permutations with no fixed points) of length $n$, it follows from the above recurrence that
\[
|\bI_{n}(\underline{000})|=\frac{(n+1)!-d_{n+1}}{n}.
\]
It would be interesting to find a direct combinatorial proof of this fact.

The recurrences in \cref{tab1} show that the only two patterns of length 3 that are Wilf equivalent are $\underline{100}$ and $\underline{110}$. It turns out that the following stronger result holds.

\begin{proposition}\label{prop:110ss100} The patterns $\underline{110}$ and $\underline{100}$ are super-strongly Wilf equivalent.
\end{proposition}

To prove this equivalence, first we construct a bijection
$$\{e\in\bI_{n}:\Em(\underline{110},e)\supseteq S\}\to\{e\in\bI_{n}:\Em(\underline{100},e)\supseteq S\}$$
for any $S\subseteq [n]$, by replacing occurrences of $\underline{110}$ in positions $S$ with occurrences of $\underline{100}$. Then, using the Principle of Inclusion-Exclusion, we conclude that $\underline{110}\stackrel{ss}{\sim}\underline{100}$.



\subsection{From patterns in inversion sequences to patterns in permutations}

In this subsection we discuss some correspondences between consecutive patterns of length 3 in inversion
sequences and permutation patterns. We denote by $S_n(\sigma)$ the set of permutations in $S_n$ that avoid the pattern $\sigma$.
We underline the entries of $\sigma$ that are required to be adjacent in an occurrence. Patterns where some entries are underlined are called {\em vincular} (or {\em generalized}) permutation patterns, and were introduced by Babson and Steingr\'{\i}msson~\cite{Babson}.

\begin{proposition}\label{gen_prop_012_permut}\label{prop:pat_vincular} Let $\pi\in S_{n}$, and let $e=\Theta(\pi)$ be its corresponding inversion sequence given by \eqref{eq:theta_bijection}. Then 
\begin{enumerate} %,leftmargin=1.5cm, itemsep=1pt]
\item[(a)] $\pi$ avoids $\underline{(r+1)r\ldots 1}$ if and only if $e$ avoids $\underline{01\ldots r}$;
\item[(b)] $\pi$ avoids $3\underline{214}$ if and only if $e$ avoids $\underline{120}$;
\item[(c)] $\pi$ avoids  $2\underline{413}$ if and only if $e$ avoids $\underline{021}$.
\end{enumerate}
\end{proposition}

Permutations avoiding $\underline{143}2$ were studied by
Baxter and Pudwell~\cite{BaxterPudwell}. The sequence $|S_{n}(\underline{143}2)|$ appears as A200404 in~\cite{OEIS}, but no
enumerative results seem to be known. Using the reverse-complement operation, it follows from \cref{prop:pat_vincular} (b) that $|\bI_{n}(\underline{120})|=|S_{n}(\underline{143}2)|$, so these numbers can be computed using the recurrence in \cref{tab1}.

\cref{prop:pat_vincular} (c) implies that $|\bI_{n}(\underline{021})|=|S_{n}(\underline{132}4)|$. The exponential generating function for permutations avoiding $\underline{132}4$ can be deduced by combining \cite[Proposition 3.1]{ElizaldeII} and \cite[Theorem 4.1]{ElizaldeNoy}, from where we get
\begin{displaymath}\sum_{n\ge0} |\bI_{n}(\underline{021})| \frac{z^n}{n!}=\exp\left(\int_{0}^{z} \frac{dt}{1-\int_0^t e^{-u^2/2} du}\right) .\end{displaymath}


\section{Consecutive patterns of length 4}\label{sec:conseclength4}

For consecutive patterns of length 4 in inversion sequences, the classification into Wilf equivalence classes becomes quite interesting. Note that, unlike in the case of permutations, there are no equivalences resulting from trivial symmetries.
There are a total of 75 consecutive  patterns of length 4, which fall into 55 Wilf equivalence classes. Strikingly, this is also the number of  strong and super-strong Wilf equivalence classes; in other words, all the equivalences among consecutive patterns of length 4 are super-strong equivalences.

\begin{theorem}\label{Equiv4} A complete list of the generalized Wilf equivalences
between consecutive patterns of length $4$ is as follows: 
\begin{multicols}{2}
 \begin{enumerate}[label=(\roman*),itemsep=0pt,leftmargin=1.5cm]
  \item $\underline{0102}\stackrel{ss}{\sim}\underline{0112}$.
  \item $\underline{0021}\stackrel{ss}{\sim}\underline{0121}$.
  \item $\underline{1002}\stackrel{ss}{\sim}\underline{1012}\stackrel{ss}{\sim}\underline{1102}$.
    \item $\underline{0100}\stackrel{ss}{\sim}\underline{0110}$.
      \item $\underline{2013}\stackrel{ss}{\sim}\underline{2103}$.
  \item $\underline{1200}\stackrel{ss}{\sim}\underline{1210} \stackrel{ss}{\sim}\underline{1220}$.
  \item $\underline{0211}\stackrel{ss}{\sim}\underline{0221}$.
  \item $\underline{1000}\stackrel{ss}{\sim}\underline{1110}$.
  \item $\underline{1001}\stackrel{ss}{\sim}\underline{1011}\stackrel{ss}{\sim}\underline{1101}$.
  \item $\underline{2100}\stackrel{ss}{\sim}\underline{2210}$.
  \item $\underline{2001}\stackrel{ss}{\sim}\underline{2011}\stackrel{ss}{\sim}\underline{2101}\stackrel{ss}{\sim}\underline{2201}$.
  \item $\underline{2012}\stackrel{ss}{\sim}\underline{2102}$.
  \item $\underline{2010}\stackrel{ss}{\sim}\underline{2110}\stackrel{ss}{\sim}\underline{2120}$.
 \item $\underline{3012}\stackrel{ss}{\sim}\underline{3102}$.
 \end{enumerate}
 \end{multicols}
\end{theorem}

This leads us to speculate the following analogue to Nakamura's conjecture for consecutive patterns in permutations {\cite[Conjecture5.6]{Nakamura}}, which remains open.

\begin{conjecture}\label{ConjNakamura} Two consecutive patterns in inversion sequences are strongly Wilf equivalent if and only if they are Wilf equivalent.
\end{conjecture}

It is in fact possible that a stronger version of \cref{ConjNakamura} holds, namely that all three types of generalized Wilf equivalence for consecutive patterns in inversion sequences (see \cref{def:Wilf}) coincide.
Our results show that this is the case for patterns of length at most~4. On the other hand, we will see in \cref{cor:Wilf-strongWilf} some evidence in the other direction, when we consider patterns of relations.

Regarding enumeration, the only consecutive pattern $p$ of length 4 for which the sequence $|\bI_{n}(p)|$ appears in the OEIS~\cite{OEIS} is $p=\underline{0123}$, since $|\bI_{n}(\underline{0123})|=|S_{n}(\underline{1234})|$, by \cref{gen_prop_012_permut} (a).

The equivalences in \cref{Equiv4} are proved using a variety of methods. Next we summarize three of the techniques that we use.

\subsection{Equivalences proved via bijections}\label{subsec:equiv4_biject}

Equivalences (ii)--(vii), (ix), (xi), (xii) and (xiv) in \cref{Equiv4} are proved bijectively. In fact, in these cases we can show that not only $p\stackrel{ss}{\sim} p'$, but also
\begin{multline}\label{eq:symss}
|\{e\in\bI_{n}:\Em(p,e)=S,\,\Em(p',e)=T\}|=|\{e\in\bI_{n}:\Em(p,e)=T,\,\Em(p',e)=S\}|,
\end{multline}
for all $n$ and all $S,T\subseteq [n]$. In other words, the joint distribution of the positions of the occurrences of $p$ and $p'$ is symmetric.

\eqref{eq:symss} is proved by exhibiting a bijection from $\bI_{n}$ to itself that changes all occurrences of $p$ into occurrences of $p'$, and vice versa. Such a bijection can be constructed when the patterns satisfy certain conditions.

\begin{definition}
Two consecutive patterns $p$ and $p'$ are {\it mutually non-overlapping\/} if it is impossible
for an occurrence of $p$ and an occurrence of $p'$ in an inversion sequence to overlap in more than one entry; equivalently, if for all $1<i<r$, the reductions of $p_{1}\ldots p_{i}$ and $p'_{r-i+1}\ldots p_{r}$ do not coincide, and neither do the reductions of $p'_{1}\ldots p'_{i}$ and $p_{r-i+1}\ldots p_{r}$.
We say that $p$ is {\it non-overlapping\/} if it is mutually non-overlapping with itself.
\end{definition}

\begin{example} The patterns $\underline{110}$ and $\underline{010}$ are non-overlapping and mutually non-overlap\-ping.
However, the patterns $\underline{110}$ and $\underline{100}$ are mutually overlapping. Indeed, the inversion sequence $0002211\in\bI_{7}$ has occurrences of $\underline{110}$ and $\underline{100}$ overlapping in two entries.
The pattern $\underline{1100}$ is overlapping. 
\end{example}

\begin{definition}\label{def:changeable} Let $p=\underline{p_{1}p_{2}\ldots p_{r}}$ and $p'=\underline{p'_{1}p'_{2}\ldots p'_{r}}$ be two consecutive patterns such that $p_{1}=p'_{1}$, $p_{r}=p'_{r}$, and $\max_i\{p_i\}=\max_i\{p'_i\}$.
We say that $p$ is {\em changeable} for $p'$ if, for all $1\leq i\leq r$,
\[
p'_{i}\leq \max(  \{p_j : 1\le j\le i\} \cup \{p_j - j + i : i<j\leq r\} ).
\]
If $p$ is changeable for $p'$ and $p'$ is changeable for $p$, then we say that $p$ and $p'$ are {\em interchangeable}.
\end{definition}

\begin{example}\label{exa:change_patterns_with_def}  Consider the consecutive patterns $p=\underline{01230}$ and $p'=\underline{03210}$. Note that
\[
p'_{2}=3>1= \max(  \{p_j : 1\le j\le 2\} \cup \{p_j - j + 2 : 2<j\leq 5\} ).
\]
Hence, $\underline{01230}$ is not changeable for $\underline{03210}$.

On the other hand, the patterns $p=\underline{0021}$ and $p'=\underline{0121}$ are interchangeable. Indeed, in this case
$p'_{2}=1= \max(  \{p_j : 1\le j\le 2\} \cup \{p_j - j + 2 : 2<j\leq 4\} )$ and $p'_{i}=p_{i}$ for $i\neq 2$, so $p$ is changeable for $p'$. Similarly, $p'$ is changeable for $p$ because $p_{i}\leq p'_{i}$, for all~$i$.
\end{example}

\begin{theorem}\label{thm:general_extend_110_100_biject} Let $p$ and $p'$ be non-overlapping, mutually non-overlapping, and interchangeable consecutive patterns. Then $p$ and $p'$ satisfy \eqref{eq:symss}. In particular, $p\stackrel{ss}{\sim} p'$.
\end{theorem}

For each of the equivalences (ii)--(vii), (ix), (xi), (xii) and (xiv) in \cref{Equiv4}, it can be easily verified that the patterns are non-overlapping, mutually non-overlapping, and interchangeable. Thus, these equivalences follow from \cref{thm:general_extend_110_100_biject}.

\subsection{Equivalences proved via inclusion-exclusion}\label{subsec:equiv4_non_over_inc_exc}

Some equivalences in \cref{Equiv4} follow from the next result, which has weaker hypotheses than \cref{thm:general_extend_110_100_biject}. It relaxes the condition  of $p$ and $p'$ being mutually non-overlapping, at the expense of not proving \eqref{eq:symss} and not producing a direct bijection changing all the occurrences of $p$ into occurrences of $p'$.

\begin{theorem}\label{thm:general_extend_110_100_sergi} Let $p$ and $p'$ be non-overlapping and interchangeable consecutive patterns. Then $p\stackrel{ss}{\sim} p'$.
\end{theorem}

Equivalences (viii) and (x) in \cref{Equiv4} follow.
The proof of \cref{thm:general_extend_110_100_sergi} generalizes the ideas behind the proof of \cref{prop:110ss100}.


\subsection{Equivalences between overlapping patterns}\label{subsec:equiv4_over_inc_exc}

The equivalences proved so far have relied on the patterns being non-overlapping. For some specific overlapping patterns, the proof of \cref{thm:general_extend_110_100_sergi} can be adapted to show their equivalence. The proof of (i) and (xiii) in \cref{Equiv4} relies on a decomposition of inversion sequences into blocks of overlapping occurrences, together with the bijections hinted in \cref{fig:Scheme_0102_0112}, and an inclusion-exclusion argument.

\begin{figure}[htb]
\centering
\includegraphics[width=0.9\textwidth]{Scheme_0102_0112}
\caption{Schematic diagram of the bijections behind the proof of $\underline{0102}\stackrel{ss}{\sim}\underline{0112}$.}
	\label{fig:Scheme_0102_0112}
\end{figure}


The equivalences $\underline{0102}\stackrel{ss}{\sim}\underline{0112}$ and $\underline{2010}\stackrel{ss}{\sim}\underline{2110}\stackrel{ss}{\sim}\underline{2120}$ can be generalized as follows.

\begin{theorem}  For every $r\ge1$ and $s\geq 2$, we have
 \begin{align*}
 {\underline{0^{r}\,1\,0^{r}\,2\,0^{r}\ldots (s-1)\,0^{r}\,s}} &\stackrel{ss}{\sim} {\underline{0^{r}\,1\,1^{r}\,2\,2^{r}\ldots (s-1)\,(s-1)^{r}\,s}},\\
 {\underline{s\,0^{r}\,(s-1)\,0^{r}\ldots 0^{r}\,10^{r}}} &\stackrel{ss}{\sim}{\underline{s\,(s-1)^{r}\,s\,(s-2)^{r}\,s\ldots s\,1^{r}s\,0^{r}}}\\
 &\stackrel{ss}{\sim}{\underline{s\,(s-1)^{r}\,(s-1)\,(s-2)^{r}\,(s-2)\ldots 1^{r}1\,0^{r}}}.
 \end{align*}
\end{theorem}


\section{Patterns of relations}

Extending the systematic study of
Corteel et al.\ \cite{MartinezSavageI} for classical patterns in inversion sequences,
Martinez and Savage~\cite{MartinezSavageII} reframe the notion of a
pattern of length 3 to instead consider a triple of binary relations between the entries of the occurrence.
In this section we define a consecutive analogue of this notion.


\begin{definition}
Let $R_{1},R_2\in\{\leq,\geq,<,>,=,\neq\}$. An inversion sequence $e$ {\em contains} the {\em consecutive pattern
of relations} $(\underline{R_{1},R_{2}})$ if there is an $i$ such that $e_{i}R_{1}e_{i+1}$ and $e_{i+1}R_{2}e_{i+2}$;
in this case, $e_{i}e_{i+1}e_{i+2}$ is called an {\em occurrence} of $(\underline{R_{1},R_{2}})$ in position $i$.
Otherwise, we say that $e$ {\em avoids} $(\underline{R_{1},R_{2}})$. Denote by $\bI_{n}(\underline{R_{1},R_{2}})$ the set of inversion sequences of length $n$ that avoid $(\underline{R_{1},R_{2}})$.
\end{definition}

\begin{example}
The inversion sequence $e=002241250$ contains $(\underline{>,<})$ because $e_{5}e_{6}e_{7}=412$ is an occurrence of this pattern. However, $e$ avoids $(\underline{=,>})$, and so $e\in\bI_{9}(\underline{=,>})$.
\end{example}

It is important to note that an occurrence of $(\underline{R_{1},R_{2}})$ is also an occurrence of some consecutive pattern of length 3, and so avoidance of
$(\underline{R_{1},R_{2}})$ is equivalent to avoidance of a set of consecutive patterns. Specifically, we can write $\bI_{n}(\underline{R_{1},R_{2}})=\bigcap_p\bI_{n}(p)$, where $p$ ranges over the consecutive patterns $p=\underline{p_1p_2p_3}$ satisfying $p_1R_1p_2$ and $p_2R_2p_3$. One advantage of studying the sets $\bI_{n}(\underline{R_{1},R_{2}})$ is that they often exhibit more structure than the sets $\bI_{n}(p)$,
provide connections to other combinatorial objects, and yield simpler enumeration sequences.

In this section we provide formulas for $|\bI_{n}(\underline{R_{1},R_{2}})|$, and we study the analogues for consecutive patterns of relations of
the notions of equivalence in \cref{def:Wilf}.

The 36 consecutive patterns of relations $(\underline{R_{1},R_{2}})$ with $R_{1},R_2\in{\{\leq,\geq,<,>,=,\neq\}}$ fall into
30 Wilf equivalence classes, and into 31 strong Wilf equivalence classes, which are also super-strong equivalence classes.
The next result provides this classification.

\begin{theorem}\label{EquivIneq}  A complete list of the generalized
Wilf equivalences between consecutive patterns of relations $(\underline{R_{1},R_{2}})$ in inversion sequences
is as follows:
\begin{multicols}{2}
  \begin{enumerate}[label=(\roman*),itemsep=0pt,leftmargin=1.5cm]
 \item$(\underline{\geq,<})\stackrel{ss}{\sim}(\underline{<,\geq})
 \sim(\underline{\neq,\geq}).$
 \item $(\underline{\geq,\geq})\stackrel{ss}{\sim}(\underline{<,<})$.
 \item $(\underline{\geq,=})\stackrel{ss}{\sim}(\underline{=,\geq})$.
 \item $(\underline{\geq,>})
 \stackrel{ss}{\sim}(\underline{>,\geq})$.
 \item $(\underline{>,=})\stackrel{ss}{\sim}(\underline{=,>})$.
 \end{enumerate}
\end{multicols}
\end{theorem}

Note that the patterns $(\underline{\geq,<})$ and $(\underline{\neq,\geq})$ (similarly, $(\underline{<,\geq})$ and $(\underline{\neq,\geq})$) are Wilf equivalent but not strongly Wilf equivalent.

\begin{corollary}\label{cor:Wilf-strongWilf}
Wilf equivalence and strong Wilf equivalence classes of consecutive patterns of relations in inversion sequences do not coincide in general.
\end{corollary}

This result is surprising for two reasons. First, Wilf equivalence and strong Wilf equivalence classes of single consecutive patterns are conjectured to coincide, both in the setting of permutations (see \cite[Conjecture 5.6]{Nakamura}) and in the setting of inversion sequences (see \cref{ConjNakamura}). \cref{cor:Wilf-strongWilf} shows that the analogous statement for consecutive patterns of relations does not hold.
Second, when considering consecutive patterns of relations in the setting of permutations, by
defining $\pi_i\pi_{i+1}\pi_{i+2}$  to be an occurrence of $(\underline{R_{1},R_{2}})$ in $\pi\in S_n$ if $\pi_{i}R_{1}\pi_{i+1}$ and $\pi_{i+1}R_{2}\pi_{i+2}$,
Wilf equivalence and strong Wilf equivalence classes of such patterns in permutations coincide. In fact, all such equivalences are obtained from trivial symmetries, unlike in the case of inversion sequences.

As a consequence of \cref{EquivIneq} (iv), we deduce the following result about permutation patterns, originally conjectured by
Baxter and Pudwell {\cite[Conjecture17]{BaxterPudwell}},
and later proved by
Baxter and Shattuck {\cite[Corollary11]{BaxterShattuck}} and by Kasraoui \cite[Corollary1.9(a)]{Kasraoui}.

\begin{corollary}\label{BaxterandPudwell}
The vincular permutation patterns $\underline{124}3$ and $\underline{421}3$
are Wilf equivalent, that is,  $|S_n(\underline{124}3)|=|S_n(\underline{421}3)|$ for all~$n$.
\end{corollary}

Inversion sequences avoiding consecutive patterns of relations provide the right setting to prove this result. Our proof, which is simpler than the previously known ones, is a sequence of bijections $S_n(\underline{124}3)\to S_{n}(2\underline{134})\to \bI_{n}(\underline{>,\geq}) \stackrel{\Phi}{\to} \bI_{n}(\underline{\geq,>}) \to S_{n}(3\underline{124}) \to S_{n}(\underline{421}3)$, where the key step is the bijection $\Phi$.


Regarding enumeration, we show that, for many patterns $(\underline{R_1,R_2})$, the sequence $|\bI_{n}(\underline{R_{1},R_{2}})|$ matches an existing sequence in the OEIS~\cite{OEIS} enumerating other combinatorial objects. These results are summarized in \cref{tab3}. Our proofs are bijective in most cases.

\begin{table}[h]
\centering
\resizebox{.95\columnwidth}{!}{
 \begin{tabular}{c@{\hskip 0.3cm}c@{\hskip 0.5cm}p{8cm} }
 \hline
 Pattern $(\underline{R_{1},R_{2}})$ & OEIS~\cite{OEIS} & Description
 \Tstrut\Bstrut\\
 \hline
 $(\underline{\leq,\neq})$ & \seqnum{A040000} & $2$ \ (for $n>1$)  \Tstrut\\
 $(\underline{\leq,\geq})$ & \seqnum{A000027} & $n$  \Tstrut\\
  $(\underline{\geq,\neq})$ & \seqnum{A000124} \Tstrut & $\binom{n}{2}+1$ \\
 $(\underline{\geq,\leq})$ & \seqnum{A000045} & $F_{n+1}$  \ (Fibonacci) \Tstrut\\
 $(\underline{\neq,\leq})$ & \seqnum{A000071} \Tstrut & $F_{n+2}-1$ \\
 $(\underline{\geq,<})\stackrel{ss}{\sim}(\underline{<,\geq})
 \sim(\underline{\neq,\geq})$ & \seqnum{A000079} & $2^{n-1}$ \Tstrut\\
 $(\underline{\neq,\neq})$ & \seqnum{A000085} & Number of involutions of $[n]$ \Tstrut\\
  $(\underline{\leq,>})$ & \seqnum{A000108} & $C_{n}$ \ (Catalan) \Tstrut\\
    $(\underline{>,\leq})$ & \seqnum{A071356} & Underdiagonal paths of from the origin to $x=n$ with steps $(0,1)$, $(1,0)$, $(1,2)$\\
 $(\underline{=,\neq})$ & \seqnum{A003422} & $0!+1!+2!+\cdots+(n-1)!$ \Tstrut\\
 $(\underline{\geq,\geq})\stackrel{ss}{\sim}(\underline{<,<})$ & \seqnum{A049774} &
 $|S_{n}(\underline{321})|$ \Tstrut\\
  $(\underline{\neq,=})$ & \seqnum{A000522} \Tstrut & $\sum_{i=0}^{n-1}(n-1)!/i!$ \\
  $(\underline{\geq,>})\stackrel{ss}{\sim}(\underline{>,\geq})$ & \seqnum{A200403} &
  $|S_{n}(\underline{124}3)|$ \Tstrut\\
  $(\underline{=,=})$ & \seqnum{A052169} & $\frac{(n+1)!-d_{n+1}}{n}$  \Tstrut\Bstrut\\
 \hline
 \end{tabular}
}
 \caption{Consecutive patterns of relations $(\underline{R_{1},R_{2}})$ for which
 $|\bI_{n}(\underline{R_{1},R_{2}})|$ appears in~\cite{OEIS} and has an existing alternative combinatorial
 interpretation.}\label{tab3}
\end{table}

Let us sketch how some of the formulas in \cref{tab3} were obtained. Using the fact that
$$
\bI_{n}(\underline{\geq,\leq})=\{e\in\bI_{n}: e_{1}< e_{2}<\cdots < e_{j}\geq e_{j+1}>e_{j+2}>\cdots >e_{n} \text{ for some }1\leq j\leq n\},
$$
we construct a bijection from this set to the set of compositions of $n$ with parts $1$ and $2$, which has cardinality $F_{n+1}$.
To enumerate $\bI_{n}(\underline{\neq,\neq})$, we describe a bijection to the set of involutions of $[n]$.
On the other hand, the set $\bI_{n}(\underline{\leq,>})$ consists precisely of weakly increasing inversion sequences, which are in bijection with Dyck paths.

The enumeration of $\bI_{n}(\underline{>,\leq})$ is more complicated, and it relies on a bijection $\varphi$ to a certain set
$\mathcal{R}_{n}$ of lattice paths defined as follows.

\begin{definition}
A {\em marked Dyck path} $P$ is an underdiagonal lattice path from $(0,0)$ to some point in the diagonal, with horizontal steps $E=(1,0)$ and two possible kinds of vertical steps $(0,1)$, denoted by $N$ and $N^*$. Denoting by
$E(P)$, $N(P)$ and $N^*(P)$, the number of $E$, $N$ and $N^*$ steps in $P$, respectively, the size of $P$ is defined as $N^{*}(P)+E(P)=N(P)+2N^*(P)$.
If a marked Dyck path $P$ has no $N^{*}$ step in the last run of vertical steps, then we say that $P$ has an {\em unmarked tail}. Let $\mathcal{R}_{n}$ be the set of paths of size $n$ with an unmarked tail.
\end{definition}

To define $\varphi$, we use the fact that
$$\bI_{n}(\underline{>,\leq})=\{e\in\bI_{n}: e_{1}\leq e_{2}\leq\cdots\leq e_{j}>e_{j+1}>\cdots >e_{n}\text{ for some }1\leq j\leq n\}.$$
Given $e\in\bI_{n}(\underline{>,\leq})$, let $P$ be the corresponding underdiagonal lattice path from $(0,0)$ to the line $x=n$, using steps $N=(0,1)$, $S=(0,-1)$ and $E=(1,0)$, having $n$ steps $E$ at heights given by $e_1,\ldots,e_n$.
We construct $\varphi(e)\in\mathcal{R}_{n}$ as follows; see \cref{fig:carla_conj_proof1} (b)(c) for an example.
\begin{enumerate}[label=\arabic*)]
\item For every $E$ step in the descending portion of $P$ (i.e., to the right of the line $x=j$), which corresponds to an entry $e_i$ with $i>j$, mark the $N$ step in the ascending portion of $P$ going from height $e_i$ to height $e_i+1$, turning it into an $N^{*}$ step.
\item Erase the descending portion of $P$, and instead append $j-e_j$ $N$ steps. Let $\varphi(e)\in \mathcal{R}_n$ be the resulting path from the origin to $(j,j)$.
\end{enumerate}

\begin{figure}[htb]
\centering
\begin{tabular}{c@{\qquad}c@{\qquad}c}
\includegraphics[scale=0.48]{Example_inv_seq_path}
&
\includegraphics[scale=0.48]{carla_conj1}
&
\includegraphics[scale=0.48]{carla_conj2}
\\
(a) & (b) & (c)
\end{tabular}
\caption{(a) The inversion sequence $e=002031\in\bI_{6}$ as an underdiagonal lattice path. (b)
The inversion sequence $e=011344421\in\bI_{9}(\underline{>,\leq})$. (c) Its corresponding marked Dyck path ${\varphi(e)=ENEEN^{*}N^{*}ENEEENNN}\in\mathcal{R}_{9}$.}\label{fig:path_represent}\label{fig:carla_conj_proof1}
\end{figure}



Then we use standard generating function techniques to enumerate paths in $\mathcal{R}_n$.
As a byproduct of these bijections, we obtain a proof of the following result involving non-consecutive triples of relations, which refines a
conjecture of Martinez and Savage {\cite[Section 2.19]{MartinezSavageII}}. Alternative proofs of their conjecture using different methods have been obtained independently by Cao, Jin, and Lin~\cite[Theorem 5.1]{CaoJinLin} and by Hossain.

\begin{theorem}\label{carlaConjecture}
For $e\in\bI_n$, let $\dist(e)=|\{e_{1},e_{2},\ldots,e_{n}\}|$ be the number of distinct entries of $e$.
Then
\[
\sum_{n\geq 0}\sum_{e\in\bI_{n}(\underline{>,\leq})}z^{n}t^{\dist(e)}=\frac{1+z(3-t)-\sqrt{1-z(2+2t-z+6zt-zt^{2})}}{4z}.
\]
In particular, the distribution of the statistic $\dist$ on $\bI_{n}(\underline{>,\leq})$ is symmetric.
\end{theorem}


\printbibliography

\end{document}
