\documentclass{ruthesis}
\special{papersize=8.5in,11in} %***for A4-default configurations on servers


\usepackage{hyperref}
\usepackage{fancyvrb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{tablefootnote}
\usepackage{hyperref}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{amssymb,latexsym,url,graphicx}
\usepackage{tikz,color,lscape}

\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{thm}[prop]{Theorem}
\newtheorem{obs}[prop]{Observation}


\theoremstyle{definition}
\newtheorem{defn}[prop]{Definition}
\newtheorem{cor}[prop]{Corollary}

\theoremstyle{definition}
\newtheorem{eg}[prop]{Example}
\newtheorem{conds}{Conditions}
\def \tss {\textsuperscript} \def \s {\sigma} \def \Av {\text{Av}} \def \rar {\rightarrow} \def \es {\emptyset} \def \ds {\displaystyle}
\def \sse {\subseteq} \def \td {\text{-}} \def \down {\text{down}} \def \up {\text{up}} \def \a {\alpha} \def \t {\tau} \def \r {\rho}

\begin{document}\sloppy
\phd
\title{Flexible Schemes and Beyond: Experimental Enumeration of Pattern Avoidance Classes}
\author{Yonah Biers-Ariel}
\program{Mathematics}
\director{Doron Zeilberger}
\approvals{4} % CHANGE THIS IF YOU HAVE EXTRA COMMITTEE MEMBERS
\submissionyear{2020} %CHANGE TO APPLICABLE YEAR...
\submissionmonth{May} % ... AND MONTH

\abstract{
This thesis demonstrates several applications of experimental methods to the enumeration of pattern-avoiding permutations. First, we introduce flexible schemes -- a new extension of enumeration schemes. We show how a computer can find flexible schemes and use them to count permutations. We establish sufficient conditions for the existence of finite flexible schemes, and in particular show that they exist whenever finite enumeration schemes or regular insertion encodings do. Next, we combine enumeration schemes with structural arguments to give a new algorithm for counting 1342-avoiding permutations. We find a recurrence for the number of permutations avoiding four dashed patterns, and finally generalize Claude Lenormand's ``raboter" sequence. We have implemented all the algorithms described here in Maple and provide links to the Maple code in each section.
 } 
\beforepreface
 
\acknowledgements{
This thesis would not have been possible without the support, first and foremost, of my advisor Doron Zeilberger. He is responsible for my introduction to the wide world of experimental math, and most of the problems appearing here were originally his suggestions. His enthusiasm and encouragement have made my PhD a truly rewarding experience.
 
I would also like to thank Vince Vatter for suggesting the problem of uniting enumeration schemes and the insertion encoding. The first section of this dissertation would not exist without the papers he pointed me to and the techniques I found in them. I am also grateful to him as well as to Bhargav Narayanan and Swastik Kopparty for their service on my dissertation committee.

The experimental mathematician is only as powerful as the computers they use. In writing this thesis, I made frequent use of the Amarel computing cluster, and so I am grateful to Rutgers' Office of Advanced Research Computing for creating and maintaining this important resource.

No one can spend all their time researching, and I'd further like to thank all my fellow graduate students who made my time at Rutgers so much fun. There are too many people in this category to list them all, but I'd especially like to thank Keith Frankston, Justin Semonsen, Abigail Raz, and Matthew Russell. 

Finally, I'd like to thank my wife, Michelle Flores, who moved to New Jersey so that I could pursue this opportunity and who feeds me cookies when I get angry trying to debug my code.
}

\afterpreface

%\maketitle
%\newpage
%\tableofcontents
%\newpage
\chapter{Introduction}
What an exciting time to be a combinatorialist! Nearly a century of advances in computation has made mathematical experimentation easier than ever. It has inspired new questions and given new tools to answer them. It has even caused us to rethink what an answer is \cite{Wilf}. However, while our computers are able assistants, they have not yet outgrown the need for their fleshy, fallible masters. There is still a great deal for us humans to do in collaboration with them.

This collaboration, which we refer to as experimental math, takes many forms. Its most common and fundamental form happens when mathematicians computationally generate many, many objects and then make conjectures about the objects' properties based on this huge supply of data. Once we know what to prove, proving it is often not so difficult. The most obvious instance of this sort of experimental math in this thesis is in Chapter \ref{Callan}, but in a looser sense every result here was conceived of through experimentation.

This collaboration can also be reversed, with a human supplying the conjecture and the start of a proof, and the computer finishing it. Often these proofs involve a human showing that a minimal counterexample must have a specific form, and the computer showing that no objects of that form are counterexamples. This sort of experimental math famously proved the four color theorem \cite{4color1}\cite{4color2}.

A more specialized kind of experimental math occurs when a computer is responsible both for conjecturing and proving its own theorems. A human explains to a computer what sort of object would constitute an answer, and then sets the computer to work. This sort of experimental math can be as simple as interpolating a degree-$d$ polynomial through $d+1$ points, but can be applied to much more difficult problems as well. Zeilberger's algorithm for finding hypergeometric sum identities \cite{A=B} is a classic example of this. Chapters \ref{auto_enum} and \ref{raboter} of this thesis are concerned with this sort of experimental math, and contain additional examples of it. 

While experimental math is a powerful methodology with many deep results, this thesis focuses mainly on its applications to pattern avoidance. The modern study of pattern avoidance began in \textit{The Art of Computer Programming} where Knuth asked which permutations can be sorted using only a single stack, and how many of them are there \cite{Knuth}? The field has grown tremendously since then (see \cite{VSurvey} for a detailed survey), but our focus is on Knuth's classic question: given some class of permutations, how many are there?

More is known about this question than we could possibly describe in this introduction, but we will cover a few highlights. The answer to Knuth's original question is that the stack-sortable permutations are precisely those that avoid the pattern 231, and they are counted by the Catalan numbers \cite{Knuth}. In fact, Knuth showed that for any pattern $\s$ of length 3, the number of length-$n$ permtuations avoiding $\s$ is the $n\tss{th}$ Catalan number. Of the seven symmetry classes of length 4 patterns, six have known enumeration sequences \cite{Gessel}\cite{West_Vex}\cite{Bona}, while the 1324-avoiding permutations are so far unenumerated. Wikipedia is an excellent reference for the enumeration sequences and (when known) generating functions of individual classes \cite{wiki2x4}. 

Not only do we have enumeration sequences for many permutation classes, we have some asymptotic knowledge of how every class grows. Letting $\Av(\s;n)$ be the number of length-$n$ permutations avoiding $\s$, we know that $\lim_{n \rar \infty} |\Av(\s;n)|^{1/n} = c_\s$ \cite{Marcus} and that $c_\s$ is generally exponentially large in the pattern length \cite{Fox}.

The first part of this thesis is concerned with experimental strategies for enumerating pattern avoiding permutations. We introduce a few existing strategies including enumeration schemes and the insertion encoding, and then develop a new method with the power of both of these. Additionally, we provide the (to our knowledge) first experimental conditions to establish the nonexistence of an enumeration scheme.

The second part of this thesis looks at two individual permutation classes. The first class consists of the permutations avoiding the pattern 1342 which were famously enumerated by B\'ona \cite{Bona} using a bijection with a certain class of labeled trees. Here, we prove a recurrence which we can justify directly in terms of the permutation class' avoidance properties. This recurrence uses elements both from enumeration schemes and from the structure paradigm for automatic enumeration. Next, we consider the permutations avoiding the dashed patterns $1-32-4, 1-42-3, 2-31-4, 2-41-3$ for which we prove a recurrence conjectured by Callan \cite{oeis}. Finally, we leave the world of pattern avoidance to generalize Claude Lenormand's ``Raboter" sequence.

The material in Section \ref{Callan} has been previously published in the Journal of Integer Sequences \cite{my_jis}. We also intend to publish the material in Section \ref{auto_enum}. All other material appears only in this thesis. 

\chapter{Automatic Avoidance Class Enumeration}\label{auto_enum}
\section{Background}\label{background}
In the last twenty years, an increasing amount of research has focused on the experimental enumeration of permutation classes. Rather than the traditional approach of considering a single avoidance class (or family of avoidance classes), these algorithms seek to input any set of patterns and then (hopefully) return some certificate which gives a polynomial-time algorithm to generate the enumeration sequence of the permutations which avoid these patterns. By polynomial-time, we mean that the time to find the $n\tss{th}$ term of the sequence is a polynomial in $n$; what Wilf calls a \textit{p-solution} \cite{Wilf}.

The first of these were enumeration schemes, developed by Zeilberger \cite{ZSchemes} and expanded by Vatter \cite{VSchemes}. The idea is to separate permutations into groups by their prefixes and then attempt to reduce these classes to simpler groups by deleting prefix elements. Of course, we can ask about much more than just classical patterns in permutations. The dashed patterns created by Babson and Steingr\'imsson \cite{Babson} can be counted by schemes of Baxter and Pudwell \cite{Baxter}, and the pattern-avoiding words introduced by Burstein \cite{Burstein} can be counted by schemes of Pudwell \cite{Pudwell} and Shar and Zeilberger \cite{Shar}.

This thesis is concerned with both classical and dashed patterns, but only in permutations. Vatter's enumeration schemes are described in greater detail in Section \ref{schemes}; Baxter and Pudwell's schemes, while not described explicitly, provide some of the key ideas of Section \ref{vin}.

The other enumeration algorithm which we are interested in is the insertion encoding developed by Albert, Linton, and Ru\v{s}kuc \cite{Ins}. The strategy here is to consider a finite automaton which moves between states, each state specifying which elements are already included in the permutation and where new elements will be inserted. It is described in greater detail in section \ref{insenc}.

Both of these algorithms, along with the new enumeration scheme that we propose in this paper, follow the paradigm of building a permutation element by element and finding rules to reduce partially-completed permutations to simpler ones. Another paradigm began with Albert and Atkinson \cite{Albert} and has been developed further by, among others, Bean, Gudmundsson, and Ulfarsson \cite{struct}. The general idea is to decompose pattern-avoiding permutations into component structures which can more easily be counted. While we don't describe this algorithm in detail, and it isn't needed for our original work in Section \ref{flexible}, it is a powerful strategy, and is able to enumerate all classes of pattern-avoiding permutations with a regular insertion encoding, all classes where the number of elements of length $n$ is polynomial in $n$, and all classes avoiding at least six patterns of length four.

The object of this section is to answer a question posed by Vatter \cite{VSchemes}: Is there an automatic enumeration algorithm that applies to all permutation classes with finite enumeration schemes and all classes with regular insertion encodings? Here we provide an algorithm to produce what we will call flexible schemes. Finite flexible schemes exist for every class with a finite enumeration scheme or a regular insertion encoding (and many classes with neither). Like traditional schemes, flexible schemes do not provide generating functions -- indeed, they exist for avoidance classes which are believed not to have any D-finite generating function \cite{no_gf} -- but they do provide polynomial-time enumeration of their permutation classes. 

We begin by presenting two existing strategies for the automatic enumeration of pattern-avoiding permutations: traditional enumeration schemes and the insertion encoding. In Section \ref{flexible}, we describe how flexible schemes differ from traditional ones, and present an automatic way to find them. In Section \ref{conditions} we show that a finite flexible scheme exists whenever either a finite traditional scheme or regular insertion encoding does. In Section \ref{results}, we present some of the successes we have had on specific avoidance classes, and in Section \ref{vin} we adapt flexible schemes to count permutations avoiding vincular patterns.

\subsection{Definitions}
In general, we use standard definitions for permutation patterns and related objects. A \emph{permutation} is some reordering of the numbers in $[n] = \{1,2,\dots,n\}$. Permutations are written as a string of ordered values (like 24513), and the length-0 permutation is written as $\es$. A string $s$ of $k$ distinct elements of $[n]$ can be turned into a permutation by taking its \emph{reduction}, the unique permutation of length $k$ whose elements occur in the same order as $s$.

A permutation $\s = \s_1\s_2 \dots \s_n$ \emph{contains} a pattern $p = p_1p_2 \dots p_k$ if there exists a sequence $i_1, i_2, \dots, i_k$ such that $\s_{i_1}\s_{i_2}\dots \s_{i_k}$ reduces to $p$. In this case, we call $\s_{i_1}\s_{i_2}\dots \s_{i_k}$ an \emph{occurrence} of $p$ in $\s$; if there is no occurrence of $p$ in $\s$, then $\s$ \emph{avoids} $p$. The following example illustrates these definitions.

\begin{eg}
The permutation 24513 contains the pattern 132 because 253 reduces to 132 (and hence is an occurrence of 132). However, 24513 avoids 321 because it does not contain three elements in decreasing order.
\end{eg}

When discussing Zeilberger's enumeration schemes, we need to categorize permutations by their prefixes. A \emph{prefix} of a permutation is the reduction of one of the permutation's initial segments. When we turn to Vatter's enumeration schemes and then the new ones introduced in this thesis, we will instead categorize permutations by their downfixes. A \emph{downfix} of a permutation consists of the permutation's elements which lie below a particular value kept in their proper order.

\begin{eg}
The permutation 24513 has six prefixes: $\es, 1, 12, 123, 2341,$ and $24513$. It also has six downfixes: $\es, 1, 21, 213, 2413,$ and $24513$.
\end{eg}

When discussing Vatter's enumerations schemes, we will also need to categorize permutations by their \emph{gap vectors}. A permutation $\s_1\s_2\dots \s_n$ with downfix $\s_{i_1}\s_{i_2} \dots \s_{i_l}$ has corresponding gap vector $[i_1 - 1, i_2 - i_1 -1, \dots, i_l-i_{l-1}-1, n - i_l]$. We are particularly interested in gap vectors whose components are larger than those of some other vector, and so we say a gap vector $\mathbf{g} = [g_1,g_2, \dots, g_{l+1}]$ \emph{satisfies} a gap condition $\mathbf{h} = [h_1,h_2,\dots, h_{l+1}]$ if $g_i \ge h_i$ for all $1 \le i \le l+1$. When $\mathbf{g}$ satisfies $\mathbf{h}$, we write $\mathbf{g} \succeq\mathbf{h}$.

\begin{eg}
Consider the permutation 24513 and its downfix 21. It has corresponding gap vector $[0,2,1]$ which satisfies $[0,1,1]$ and $[0,2,0]$, but not $[1,1,1]$. Notice if a permutation has length $n$ and its downfix has length $l$, then the corresponding gap vector must have length $l+1$, and its elements must sum to $n-l$.
\end{eg}

We will often want to talk about the set of permutations avoiding some set of patterns $B$ with downfix $\pi$ and corresponding gap vector $\mathbf{g}$. We call this set $Z(B, \pi, \mathbf{g})$. When this set is nonempty, we say that $\mathbf{g}$ is \emph{viable} for $B$ and $\pi$ and when it is empty we say that $\mathbf{g}$ is \emph{nonviable} for $B$ and $\pi$.

Sometimes, we also want to talk about the set of permutations with downfix $\pi$ and corresponding gap vector $\mathbf{g}$ without worrying about what patterns they avoid. We call this set $Y(\pi, \mathbf{g})$.

\begin{eg}
The gap vector $[2,1,0]$ is viable for pattern set $\{123\}$ and downfix 12 because 
\[Z(\{123\}, 12, [2,1,0]) = \{35142, 43152, 45132, 53142, 54132\}.\]
On the other hand, the gap vector $[0,0,1]$ is nonviable. When we don't worry about avoiding 123, we find that 
\[Y(12, [2,1,0]) = \{34152, 35142, 43152, 45132, 53142, 54132\}.\]
\end{eg}

The key operation at the heart of enumeration schemes is that of deleting a downfix element to yield a simpler permutation. When a permutation with downfix $\pi$ and gap vector $\mathbf{g}$ has the $i\tss{th}$ element of its downfix deleted, it yields a permutation with downfix $d_i(\pi)$ and gap vector $d_i(\mathbf{g})$. Precisely, we define $d_i(\pi_1\pi_2 \dots \pi_k)$ to be the reduction of $\pi_1\dots \pi_{i-1} \pi_{i+1}\dots \pi_k$, and $d_i([g_1,g_2,\dots,g_{k+1}])$ $= [g_1, \dots, g_{i-1}, g_i + g_{i+1}, g_{i+2}, \dots, g_{k+1}]$. 

We also need to consider the \emph{refinements} of $\pi$, that is all the permutations formed by inserting the element $|\pi| +1$ somewhere in $\pi$. When we refine $\pi$, we also need to change $[g_1,g_2,\dots g_{k+1}]$ by deleting 1 from $g_i$ (representing the element which is now in the downfix), inserting a new element $g'$ between $g_i$ and $g_{i+1}$, and splitting the mass of $g_i$ between it and $g'$ (representing the elements that were between the $\pi_i$ and $\pi_{i+1}$, but are now between $\pi_{i+1}$ and $\pi_{i+2}$). Precisely, we let 
\[f_i(\pi_1\pi_2\dots \pi_k) = \pi_1\dots \pi_i (k+1) \pi_{i+1} \dots \pi_k, \text{ and}\] 
\[f_{i,j}([g_1,g_2,\dots, g_{k+1}]) = [g_1,\dots, g_{i-1}, j, g_i - j -1, g_{i+1}, \dots, g_{k+1}].\]

\begin{eg}
Let $\pi = 24513$ and $\mathbf{g} = [1,2,1,2,1,2]$. Then $d_1(\pi) = 3412$ and $d_1(\mathbf{g}) = [3,1,2,1,2]$. Similarly, $f_2(\pi) = 264513$ and $f_{2,1}(\mathbf{g}) = [1,1,0,1,2,1,2]$. 
\end{eg}

\subsection{Enumeration Schemes} \label{schemes}
The history and basic idea of enumeration schemes have already been discussed; here we illustrate the schemes with an extended example due to Vatter in \cite{VSchemes}. 
\begin{eg}
Suppose we want an algorithm to enumerate the permutations which avoid the two patterns 1342 and 1432. We begin by considering all permutations with the downfix 1 (i.e. all permutations). Our goal is to find elements of the downfix such that if an occurrence of a forbidden pattern uses the element, then there is a different occurrence of a forbidden pattern which does not use the element. When we find such an element, we can delete it, secure in the knowledge that the resulting permutation contains a forbidden pattern if and only if the original one did. These elements are called \emph{reversely deletable} (in \cite{ZSchemes}) or \emph{ES-reducible} (in \cite{VSchemes}). We follow the more recent source and call them ES-reducible. When a downfix has an ES-reducible element, we will also call the downfix itself ES-reducible. When a downfix is not ES-reducible, we say that it is \emph{ES-irreducible}.

One can easily find permutations with the downfix 1 which contain either the pattern 1342 or 1432 but which contain neither pattern when the 1 is removed (for example, 1342 itself is such a permutation). Therefore, we consider the \emph{refinements} of 1, that is all the length-2 permutations for which 1 is a downfix. These refinements are 12 and 21. Looking at 21, we see that the second element is ES-reducible; if any permutation uses the 1 in an occurrence of 1342 or 1432, the pattern could just as easily be formed using the 2 instead. Turning to 12, though, we find that neither element is ES-reducible; indeed we can form forbidden subpatterns which use both of them.

We are saved, though, by considering gap vectors. If a permutation has at least two elements between the 1 and the 2 (i.e. if its gap vector corresponding to 12 satisfies $[0,2,0]$) , then either a 1342 or 1432 pattern must occur. On, the other hand, if it has fewer than two elements between the 1 and the 2 (i.e. if the gap vector fails to satisfy $[0,2,0]$), then 2 is ES-reducible. Therefore, we either replace 12 with a shorter downfix, or else we can ignore it entirely.

In Section \ref{details}, we explain precisely how a computer could record these rules, and how it would use them to generate terms of the permutation class' enumeration sequence.
\end{eg}

\subsection{Insertion Encoding} \label{insenc}
The insertion encoding encodes a process in which a permutation is built up by inserting its elements from smallest to largest, but only in designated slots. These slots, indicated by $\diamond$, are the only places in which a new element can be added, and they must end up containing an element. Each permutation is constructed by a unique sequence of insertions. The following example shows how 24513 is constructed.
\begin{eg}
\[ \diamond\]
\[\diamond 1 \diamond\]
\[2\diamond 1 \diamond \]
\[2\diamond 13\]
\[24\diamond 13\]
\[24513\]
\end{eg}

Albert et al. in \cite{Ins} describe this sequence by recording at each step which slot an element is inserted into, numbering them beginning with 1 on the left. They also record where in its slot each new element is added. An $m$ represents inserting an element in the middle of a slot (leaving $\diamond$s on both sides), an $r$ represents inserting it on the right of a slot (leaving a $\diamond$ on its left), an $l$ represents inserting it on the left of a slot (leaving a $\diamond$ on the right), and an $f$ represents filling the slot (leaving no $\diamond$ at all). So, 24513 is recorded as $m_1l_1f_2l_1f_1$. 

When the strings that represent valid permutations in the avoidance class form a regular language, we say the insertion encoding is regular, and the avoidance class can be efficiently enumerated. The authors were able to precisely characterize classes with regular insertion encodings: they are the classes which contain only finitely many \emph{vertical alternations}, i.e. permutations where each odd element is greater than each even element or vice-versa. Later, Vatter showed in \cite{VIns} that the these classes could also be characterized as those for which any sufficiently long partial permutation has an insertion encoding reducible element, i.e. an element which can be removed without affecting the set of insertion sequences that could finish the permutation.

\section{Flexible Schemes} \label{flexible}
 \subsection{Motivation}
 In this section, we introduce a new idea to extend traditional enumeration schemes and enable them to count many more avoidance classes. It is motivated by the following question: What if there is a downfix and gap condition which do not guarantee that all permutations with that downfix and satisfying that condition contain a forbidden pattern, but which do allow some element of the downfix to be deleted?
  
If a downfix has such an element for every possible gap vector, then we always are able to reduce it to a simpler downfix. Of course, this is not very useful if it is hard to tell, for a given gap vector, which element is the reducible one. However, if a downfix contains such an element for every possible gap vector, and if we can determine which element that is by comparing the gap vector to finitely many gap conditions, then we can efficiently reduce the downfix. Because we allow the element being deleted to change based on the gap vector, we call such a downfix \emph{Flexible Scheme reducible} (or FS-reducible). 
   
The following example shows how this lets us count the avoidance class $\Av(1423,2314)$.
\begin{eg}\label{1423_2314}
Note that a (moderately) quick calculation with Vatter's Maple package \texttt{WILFPLUS} reveals that 3214 and 4321 are both irreducible using traditional schemes. In fact, $k\dots21$ is ES-irreducible for all $k$ (this can be proven using the main theorem of Section \ref{necc}), and no finite scheme exists.

However, 321 is FS-reducible, and thus so are its refinements 3214 and 4321. Suppose that $\mathbf{g}$ is a gap vector satisfying the condition [0,1,0,0], i.e. $\mathbf{g}$ has length 4 and $g_2 \ge 1$. It is not true that any permutation with prefix 321 and gap vector $\mathbf{g}$ must contain a forbidden pattern; for instance, $\mathbf{g} = [0,1,0,0]$ yields the permutation 3421. It is true, however, that as long as this gap condition is satisfied, the third element of the downfix is deleteable, i.e. $|Z(\{1423, 2314\}, 321, [g_1, g_2, g_3, g_4])| = |Z(\{1342, 3124\}, d_3(321), d_3([g_1, g_2, g_3,g_4]))|$.

To see this, suppose that a permutation $\s$ has downfix 321 and gap vector $[g_1, g_2, g_3, g_4]$ (thus, $\s_{g_1+1} = 3, \s_{g_1+g_2 +2} =2,$ and $\s_{g_1+g_2+g_3+3} = 3$). By way of contradiction, suppose that $g_2 \ge 1$, but the 1 in $\s$ is not FS-reducible. In other words $\s$ contains either a 1423 or 2314 pattern when the 1 is present, but contains no forbidden pattern when it is removed. Suppose that the 1 participates in a 1423 pattern. When the 1 is removed, either the 2 or 3 can fill in for it in the 1423 pattern, so a forbidden pattern still occurs.

The more difficult case is if 1 participates in a 2314 pattern. Obviously, 1 serves as the 1 in this pattern. We consider three subcases based on which element of $\s$ serves as the 2. First, suppose that 2 serves as the 2. To complete the pattern, we find $\s_i, \s_j$ with $3 < \s_i < \s_j$ such that $ g_1+g_2+2 < i < g_1+g_2+g_3 + 3 < j$. Choose $k$ such that $g_1 + 1 < k < g_1+g_2 +2$ (we know this is possible since $g_2 \ge 1$). If $\s_k < \s_j$, then $3\s_k 2\s_j$ form a 2314 pattern, while if $\s_k > \s_j$, then $3\s_k \s_i \s_j$ for a 1423 pattern.

In the second case, some $\s_l$ with $l \le g_1+1$ serves as the 2. As before, complete the pattern, this time by finding $\s_i, \s_j$ such that  $l < i < g_1+g_2 + g_3 + 3 < j$. If $i < g_1+g_2+2$ (in other words, if $\s_i$ occurs before 2) then $\s_l\s_i2\s_j$ is a 2314 pattern. Otherwise, $ g_1+g_2+2 < i$, and we are back in case 1. 

In the third case, some $\s_l$ with $g_1+1 < l < g_1+g_2+g_3+3$ serves as the 2. Complete the pattern by finding $\s_i, \s_j$ with $l < \s_i < g_1+g_2+g_3+3 < \s_j$, and note that $3\s_i 1\s_j$ is also a 2314 pattern and so we are back in case 2.

We have now dealt with the difficult case when $g_2 \ge 1$, and we are left with the easier case when $g_2 = 0$. Let $\s$ be a permutation with a 321 downfix and gap vector $[g_1,0,g_3,g_4]$. Since $2$ and $3$ are consecutive both in terms of their position in $\s$ and their values, but neither 1423 nor 2314 contain decreasing elements which are consecutive in both senses, it follows that no occurrence of a forbidden pattern uses both $2$ and $3$. Further, 3 can be replaced in any forbidden pattern with 2 (or vice-versa) and so 3 is deletable.

\end{eg}

As the previous example shows, verifying one of these reducibility rules by hand is largely a matter of making simple arguments for many tedious special cases. We will see in Section \ref{find_scheme} how a computer can do all this work for us.

\subsection{Counting with Schemes} \label{details}

In this section, we describe flexible schemes from the perspective of a computer, beginning with the data structure in which they are stored and then showing that a scheme allows for polynomial-time enumeration of a permutation class.

A scheme is a collection of \textit{replacement rules} which allow any sufficiently long permutation downfix to be replaced by a shorter one. As much as possible, we model these rules after Zeilberger's \textit{VZ-triples} defined in \cite{VZSchemes}.
 
A replacement rule is a pair $[\pi, \mathbf{H}]$, where $\pi$ is a downfix and $\mathbf{H} = \big[[\mathbf{h_1}, r_1],\dots,[\mathbf{h_k},r_k]\big]$ is a list of pairs. In each pair, $\mathbf{h_k}$ is a gap condition and $r_k$ is either 0 (if every gap vector satisfying $\mathbf{h_k}$ is nonviable for $\pi$) or a positive integer $i$ (if the $i\tss{th}$ downfix element is deletable whenever $\mathbf{h_k}$ is satisfied). If $\mathbf{H}$ is an empty list, then $\pi$ is not FS-reducible, otherwise the final $\mathbf{h_k}$ should be the list of all zeros so that every possible gap vector satisfies some $\mathbf{h_k}$.

In order for a scheme to be complete, it should have replacement rules for downfixes of every length up to $d$ (called the \textit{depth} of the downfix), and none of the rules for length $d$ downfixes should have empty $\mathbf{H}$, i.e. every downfix of length $d$ should be FS-reducible. It's worth noting that it's not strictly necessary to have a replacement rule for every downfix; if some downfix $\pi$ has a downfix of its own that already has a replacement rule, we can use that to reduce $\pi$, and we don't need a rule specifically for $\pi$. On the other hand, in this scenario we definitely can find a replacement rule for $\pi$, and so we might as well.

\begin{eg}
Suppose we are trying to avoid the pattern 123. We obtain the scheme 
\[\bigg\{\Big[\big[\big],\big[\big]\Big],\Big[[1],\big[\big]\Big],\Big[[1,2],\big[[[0,0,1],0],[[0,0,0],2]\big]\Big],\Big[[2,1],\big[[[0,0,0],2]\big]\Big]\bigg\}\]
 of depth is 2.

This scheme is interpreted as follows. If a permutation has the empty downfix, we do not know how to reduce it, and so we consider its refinement 1. But, we also don't know how to reduce 1, so we next consider both refinements of 1: 12 and 21.  If a permutation has the downfix 12, we check to see if it satisfies the gap condition [0,0,1], i.e. if it has at least one element following the 2. If so, the permutation cannot possibly avoid 123 (this is indicated by the $0$ following the gap condition). If not, we check to see if it satisfies the gap condition [0,0,0]; since every permutation always does, we find that the second element of the downfix is FS-reducible. Finally, if a permutation has the downfix 21, we check to see if it satisfies the gap condition [0,0,0]; again it must, and so the second element of the downfix is FS-reducible.
\end{eg}

We call the algorithm which follows these rules \texttt{FindTerm}. This algorithm inputs a scheme $S$, a downfix $\pi$, and a gap vector $\mathbf{g}$, and it outputs the number of elements in $Y(\pi, \mathbf{g})$ which are in the permutation class that $S$ describes. Pseudocode for \texttt{FindTerm} is given in Algorithm \ref{FT}.

\begin{algorithm}
\caption{\texttt{FindTerm}\label{FT}}
	\SetKwFunction{Find}{Find}
	\SetKwFunction{FindFirst}{FindFirst}
	\SetKwFunction{Break}{break}
	\SetKwFunction{Len}{length}
	\SetKwFunction{Return}{return}
	
	\Find $r \in S$ such that $r[1] = \pi$\\
	$\mathbf{H}:=r[2]$ \\
	\If{$\mathbf{H} = []$}{
		\If{ $\mathbf{g} = [0,0,\dots, 0]$}{
			\Return(1)
		}
		$output := 0$ \\
		\For{$i := 1$ \KwTo \Len$(\mathbf{g})+1$}{
			\For{$j := 0$ \KwTo $\mathbf{g}[i]-1$}{
				$output\text{ += }(\texttt{FindTerm}(S, f_i(\pi), f_{i,j}(\mathbf{g})))$
			}
		}
		\Return($output$)
	}
	\FindFirst $\mathbf{h} \in \mathbf{H}$ such that $\mathbf{h}[1] \preceq \mathbf{g}$\\
	$i := \mathbf{h}[2]$\\
	\If{i = 0}{
		\Return(0)
	}
	\Else{
		\Return$(\texttt{FindTerm}(S, d_i(\pi), d_i(\mathbf{g})))$
	}
\end{algorithm}

Given a scheme $S$ for a permutation class, we find the number of permutations of length $n$ which avoid it as $\texttt{FindTerm}(S, [], [n])$. We claim that the runtime is polynomial in $n$.

\begin{prop} Let $S$ be a scheme with depth $d$. Then, $\texttt{FindTerm}(S,[],[n])$ runs in $O(n^{d+2})$ time. 
\end{prop}

\begin{proof}
Note that in every recursive call, $\mathbf{g}$ has no more than $d+1$ elements, each of which is in $[0,n-1]$. Similarly, $\pi$ has no more than $d$ elements. Based on these (extremely rough) bounds, we conclude that we need to call \texttt{FindTerm} recursively at most $d!n^{d+1}$ times. Within each call, if $\mathbf{H} = []$, we loop first over all $i \in [1, \texttt{length}(\mathbf{g})+1]$ ($\le d+2$ values), and then over all $j \in \mathbf{g}[i]$ ($\le n$ values). On the other hand, if $\mathbf{H} \neq []$, we need to look through some fixed number of possible $\mathbf{h}$s (making $\le n$ comparisons each time) to find the first one with $\mathbf{h}[1] \preceq \mathbf{g}$, and then make a single recursive call.
\end{proof}

Notice that this will not run in polynomial time if $S$ is not finite. In particular, suppose that $S$ contains just one downfix of length $m$ for each positive integer $m$. Then, we can enumerate the permutations of length $n$ in the class described by $S$ by using the partial scheme of consisting of the $n$ downfixes with length $\le n$. While there are very few downfixes, each one comes with many gap vectors; in particular there are $\ds O\big((\frac{n}{2})^\frac{n}{2}\big)$ gap vectors corresponding to the downfix of length $\frac{n}{2}$, and so we must call $\texttt{FindTerm}$ recursively exponentially many times.

\subsection{Automatic Scheme Discovery} \label{find_scheme}

Of course, a scheme is only useful if we can find it in the first place. Given some downfix $\pi$, the idea is to test every possible gap condition $\mathbf{h}$ to see if it either guarantees a forbidden pattern or has some element $r$ which is FS-reducible for all gap vectors satisfying $\mathbf{h}$. Once we find such an $\mathbf{h}$, we know how to reduce $\pi$ whenever its gap vector satisfies $\mathbf{h}$, so for future $\mathbf{h'}$, we only need to find $r$ which is FS-reducible for all gap vectors satisfying $\mathbf{h'}$ and failing to satisfy $\mathbf{h}$ (or have $\mathbf{h'}$ guarantee a forbidden pattern). The following proposition, based on Proposition 6.2 from \cite{VSchemes}, lets a computer verify that $r$ is FS-reducible for all gap vectors satisfying $\mathbf{h}$ and not satisfying $\mathbf{h_1},\mathbf{h_2},\dots, \mathbf{h_k}$ by checking only a finite number of gap vectors. Note that $||B||_\infty$ is the length of the largest element of $B$ and $||\mathbf{g}||_1$ is the sum of the elements of $\mathbf{g}$.

\begin{prop}\label{check} Let $B$ be a set of forbidden patterns, $\pi$ be a downfix, and $\mathbf{h}, \mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$ be gap conditions. Suppose that 
 \[|Z(B; \pi; \mathbf{g})| = |Z(B;d_r(\pi) ; d_r(\mathbf{g}))|\]
 for all $\mathbf{g}$ with $||\mathbf{g}||_1 \le ||B||_\infty -1 + ||\mathbf{h}||_1$ which satisfy $\mathbf{h}$ but fail to satisfy any of $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$. Then the equality holds for all $\mathbf{g}$ which satisfy $\mathbf{h}$ but fail to satisfy any of $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$.
 \end{prop}
 \begin{proof}
Choose some $\mathbf{g}$ satisfying $\mathbf{h}$ and no other $\mathbf{h_i}$. It is clear that $|Z(B; \pi; \mathbf{g})| \le |Z(B;d_r(\pi) ; d_r(\mathbf{g}))|$ always holds since each permutation in $Z(B; \pi; \mathbf{g})$ can have the downfix element $r$ removed to yield a distinct permutation in $Z(B;d_r(\pi) ; d_r(\mathbf{g}))$.
 
To see that $ \ge$ also holds, fix $\mathbf{g}$ satsifying $\mathbf{h}$ but not $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$. Our strategy is to show that if there is any $\s \not\in Z(B;\pi;\mathbf{g})$ such that removing the downfix element $r$ gives a permutation in $Z(B;d_r(\pi);d_r(\mathbf{g}))$, then there is such a $\s$ corresponding to a small gap vector.

Consider a permutation $\s\in Y(\pi, \mathbf{g})$ but not in $Z(B; \pi; \mathbf{g})$; that is a permutation with downfix $\pi$ and corresponding gap vector $\mathbf{g}$ which contains a pattern of $B$. Suppose further that removing the $r$ in the downfix of $\s$ eliminates the forbidden pattern so that the resulting permutation is in $Z(B;d_r(\pi) ; d_r(\mathbf{g}))$. Choose an occurrence of a pattern $b \in B$ in $\s$, and suppose it uses the elements $\s_{i_1},\s_{i_2},\dots,\s_{i_k}$ (where $k \le ||B||_\infty$). Form $\s'$ by removing from $\s$ all the elements which do not participate in this pattern; since at least one element from the pattern ($r$) came from the downfix, we have at most $||B||_\infty-1$ elements not in the downfix.
 
Up until this point, the proof has been identical to the proof of Proposition 6.2 in \cite{VSchemes}, but now we need to ensure that $\s'$ has a gap vector $\mathbf{g'} \succeq \mathbf{h}$. This can be done by replacing the elements of $\s$ which ensured that $\mathbf{g} \succeq \mathbf{h}$; in the worst case we have removed all the elements of $\s$ which lay in gaps with positive minimum sizes, and so we need to replace $||\mathbf{h}||_1$ elements. Altogether, $\s'$ has $\le ||B||_\infty -1 + ||\mathbf{h}||_1$ elements following its prefix.

To complete the proof, we note that by construction $\s'$ has gap vector $\mathbf{g'}$ satisfying $||\mathbf{g'}||_1 \le ||B||_\infty -1 + ||\mathbf{h}||_1$. Also by construction, $\mathbf{g'}$ satisfies $\mathbf{h}$, and since $\mathbf{g'} \preceq \mathbf{g}$, it also fails to satisfy any of $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$. Finally, when the $r$ in the downfix is removed, $\s'$ ceases to contain any pattern of $B$.
 \end{proof}

There are two ways to possible good outcomes when considering a potential gap condition: some downfix element is deletable for all gap vectors satisfying the gap condition or all gap vectors satisfying the gap condition are nonviable. Proposition \ref{check} shows how to check for the first good outcome, and checking for the second is even easier. Since $\mathbf{h}$ is a gap vector satisfying itself, it must be nonviable if all gap vectors satisfying it are nonviable. Conversely, if some other gap vector is viable, then there exists $\s \in Z(B,\pi,\mathbf{g})$ for $\mathbf{g} \succeq \mathbf{h}$, and removing elements from $\s$ will give $\s' \in Z(B,\pi,\mathbf{h})$. Therefore, it is enough to check if $Z(B,\pi,\mathbf{h})$ is empty.

We can now precisely describe how to determine if a downfix has a reduction rule. Algorithm \ref{HRR} inputs a set $B$ of forbidden patterns, a downfix $\pi$, and a maximum $l_1$ norm for gap conditions $l$. Let $\text{Comp}(i,m)$ be the set of nonnegative, length-$m$ vectors whose components sum to $i$. 

\begin{algorithm}[h!]
\caption{\texttt{HasReductionRule}\label{HRR}}
	\SetKwFunction{Comp}{Comp}
	\SetKwFunction{Return}{return}
	\SetKwFunction{Len}{length}
	\SetKwFunction{Append}{append}
	\SetKwFunction{Goto}{go to}
	
	$k :=$ \Len$(\pi)$\\
	$gap\_restricts := \bigcup_{i=0}^l$ \Comp$(i,k+1)$\\
	$used\_gap\_restricts := \{\}$\\
	$partial\_reduction := []$\\
	\For {$\mathbf{h} \in gap\_restricts \backslash used\_gap\_restricts$}{\label{alg:for}
		\If
		{$Z(B, \pi, \mathbf{h}) = \es$}
		{
			\Append $\big[\mathbf{h}, 0\big]$ to $partial\_reduction$\\
			$used\_gap\_restricts := used\_gap\_restricts \cup \{\mathbf{h}\}$\\
			\Goto{\ref{alg:for}}
		}
		\Else{
			\For {$i:=1$ \KwTo $k$}{
				\If {$|Z(B,\pi,\mathbf{g})| = |Z(B,d_i(\pi), d_i(\mathbf{g})|$ for all $\mathbf{g} \in \{x: ||x||_1 \le ||B||_\infty + ||h||_1 -1, x \succeq \mathbf{h}, x \not\succeq \mathbf{h'} \text{ for all } \mathbf{h'} \in used\_gap\_restricts$}{
			\Append $\big[\mathbf{h}, i]$ to $partial\_reduction$\\
			$used\_gap\_restricts := used\_gap\_restricts \cup \{\mathbf{h}\}$\\
			\Goto{\ref{alg:for}}
				}
			}
		}
	}
	\If{$[0,0,\dots,0] \in used\_gap\_restricts$}{
		\Return($partial\_reduction$)
	}
	\Else{
		\Return($[\pi, []]$)
	}
\end{algorithm}
There is a subtlety here in that the order in which we choose $\mathbf{h} \in gap\_restricts$ matters. It may be that there is a way to reduce $\pi$ whenever its gap vector satisfies $\mathbf{h_1}$ and doesn't satisfy $\mathbf{h_2}$, but not when it satisfies $\mathbf{h_1}$ and $\mathbf{h_2}$. Therefore, we could miss a reduction rule if we consider $\mathbf{h_1}$ before $\mathbf{h_2}$. As a result, after every new addition to the reduction rule Algorithm \ref{HRR} is building, we have to start over and consider every potential $\mathbf{h}$ again to be sure that we find every possible reduction rule.

Now that we have an algorithm to see if a particular downfix is FS-reducible, we can describe the overall algorithm \texttt{HasScheme}. This algorithm inputs a set of forbidden subpatterns $B$, a maximum depth $M$ and a maximum $l_1$ norm for gap conditions $l$. This is a recursive algorithm, and so it also inputs three sets $partial\_scheme$, $downfixes\_reduced$ and $downfixes\_needed$ to keep track of the rules found so far, the downfixes which have reduction rules, and the downfixes that need reduction rules respectively. In the initial function call, $partial\_scheme := \es$, $downfixes\_reduced := \es$, and $downfixes\_needed := \{[]\}$. Pseudocode is given in Algorithm \ref{HS}.

\begin{algorithm}
\caption{\texttt{HasScheme}\label{HS}}
	\SetKwFunction{Return}{return}
	\SetKwFunction{HRR}{HasReductionRule}
	\SetKwFunction{HS}{HasScheme}
	\SetKwFunction{Append}{append}
	\SetKwFunction{Len}{length}



	$k :=$ \Len($\pi$)\\
	\If{$downfixes\_needed = \es$}{
		\Return($partial\_scheme$)\\
		}
	\For{$\pi \in downfixes\_needed$}{
		$new\_rule :=$ \HRR$(B,\pi, l)$\\
		\If{$new\_rule[2] \neq []$}{
			$partial\_scheme := partial\_scheme \cup \{new\_rule\}$\\
			$downfixes\_reduced := downfixes\_reduced \cup \{\pi\}$\\
			\If{$new\_rule[2] > 0$}{
				$downfixes\_needed := downfixes\_needed \cup \{d_{new\_rule[2]}(\pi)\}$\\
			}
			}
		\ElseIf{k = M}{
				\Return(FAIL)
			}
		\Else{
			$partial\_scheme := partial\_scheme \cup \{new\_rule\}$\\
			$downfixes\_reduced := downfixes\_reduced \cup \{\pi\}$\\
			$downfixes\_needed := downfixes\_needed \cup \{f_i(\pi): 0\le i \le k\}$
			}
		}
	$downfixes\_needed := downfixes\_needed \backslash downfixes\_reduced$\\
	\Return(\HS($B, M, l, partial\_scheme, downfixes\_reduced, downfixes\_needed$))
	
	
\end{algorithm}
 
We conclude this section with a caveat regarding the performance of flexible schemes. In the next section we will show that flexible schemes provide polynomial-time enumeration for any permutation class with a finite traditional scheme or a regular insertion encoding, and many other classes besides. However, there is no free lunch. Compared with regular insertion encodings, enumeration is much slower because flexible schemes simply do not recognize the underlying C-finite structure of the enumeration sequences they produce. As a result, instead of enumeration in linear time, we have to settle for enumeration in $O(n^{d+2})$ time. Compared to traditional schemes, meanwhile, flexible schemes may require much longer gap conditions, and so may be more difficult to build. With traditional schemes, we need only consider gap conditions of size $\le ||B||_\infty -1$, and so it is reasonable to simply try all possible gap conditions. Here, we may need much longer gap conditions, and so we must impose an artificial limit on the ones we will consider. In practice, though, this seems to be only a minor disadvantage (see Section \ref{results}).
 
\subsection{Sufficient Conditions for Flexible Schemes}\label{conditions}
For some automatic enumeration algorithms, we know precisely when they will succeed. As noted earlier, permutation classes have regular insertion encodings if and only if they contain finitely many vertical alternations. Enumeration schemes have proven more difficult to analyze, however. For all but a handful of special cases, we can only conclude that a finite enumeration scheme exists when we find one, and we can only conjecture that one does not exist when we do a lot of work and still fail to find one. In this section, we prove that finite flexible schemes exist whenever a finite traditional scheme or regular insertion encoding does.
 
First, we show that every downfix which is ES-reducible is also FS-reducible. As defined in \cite{VSchemes}, a downfix is ES-reducible if and only if there exists $r$ such that for all $\mathbf{g}$ either $|Z(B, \pi, \mathbf{g})| = 0$ or $|Z(B, \pi, \mathbf{g})| = |Z(B, d_r(\pi), d_r(\mathbf{g}))|$.

A downfix is FS-reducible, meanwhile, if and only if there exists a finite list of gap-conditions $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$ with $\mathbf{h_k}=[0,0,\dots,0]$ and a corresponding list of integers $r_1, r_2, \dots r_k$ (where each integer is in $\{0,1,\dots, |\pi|\}$) such that for all $\mathbf{g}$, if $i$ is chosen minimally so that $\mathbf{g} \succeq \mathbf{h_i}$, then
\[|Z(B,\pi, \mathbf{g})| = 
\begin{cases}
0 &\text{ if } r_i =0
\\
|Z(B,d_{r_i}(\pi), d_{r_i}(\mathbf{g}))| &\text{ otherwise}
\end{cases}
\]

We claim that if a downfix is ES-reducible, then that downfix is also FS-reducible. As noted in \cite{VSchemes}, the set $\{\mathbf{g}: |Z(B, \pi, \mathbf{g})| \neq 0\}$ is a lower order ideal in the lattice $\mathbf{N}^{|\pi|+1}$ and has a finite basis $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$ such that $|Z(B, \pi, \mathbf{g})| = 0$ if and only if $\mathbf{g} \succeq\mathbf{h_i}$ for some $i$. Therefore, we can simply use these $\mathbf{h}$s along with $\mathbf{h_{k+1}} = [0,0,\dots,0]$ and $(r_i)_{i=1}^{k+1}$ where $r_i = 0$ for $i \le k$ and $r_{k+1} = r$ to fulfill the conditions for FS-reducibility.

Next, we show that a regular insertion encoding also guarantees a finite flexible scheme.

\begin{thm}\label{insenc_suff}
Let $B$ be a set of forbidden patterns, and suppose the class of permutations avoiding $B$ has a regular insertion encoding. Then, that class also has a finite flexible scheme.\end{thm}
\begin{proof}
Recall that the permutation classes with regular insertion encodings are exactly those with finitely many vertical alternations. For such a class, we can find $k$ such that no vertical alternation in the class is longer than $2k$, and so, for every downfix $\pi$, any gap vector $\mathbf{g}$ with $k+1$ positive entries is nonviable (because every $\s \in Y(\pi, \mathbf{g})$ contains as a subsequence a vertical alternation of length $2k+1$). 

Fix some sufficiently long $\pi$; our strategy is as follows. Our first gap conditions are the ones with $k+1$ 1s and all other entries 0. As noted earlier, any vector satisfying one of these conditions is nonviable, and so we now only need to consider gap vectors with at most $k$ positive entries. We next show that every gap condition $\mathbf{h}$ consisting of $k$ 1 entries and $(\text{length}(\mathbf{h}) - k)$ 0 entries has an element $r$ which is FS-reducible for every $\mathbf{g}$ satisfying $\mathbf{h}$. Then, for every gap condition $\mathbf{h'}$ consisting of $(k-1)$ 1 entries and $(\text{length}(\mathbf{h}) - k +1)$ 0 entries, we find an $r$ which is FS-reducible for every $\mathbf{g}$ satisfying $\mathbf{h'}$ and not satisfying any of the earlier $\mathbf{h}$ with $k$ 1 entries. We continue in this way until we have found an $r$ which is FS-reducible for every $\mathbf{g}$ satisfying $[0,0,\dots,0]$ but not satisfying any $\mathbf{h}$ which contains a 1. Every $\mathbf{g}$ with $j$ positive entries satisfies an $\mathbf{h}$ with $j$ 1 entries but not any $\mathbf{h}$ with more than $j$ 1 entries, and so this will show that $\pi$ is FS-reducible.

Let $\pi$ be a downfix and $\mathbf{h}$ be a gap condition with $k$ ones. Consider some element $i$ of $\pi$, and suppose it is not FS-reducible. Then, there exists some $\s$ with downfix $\pi$ and gap vector $\mathbf{g} \succeq \mathbf{h}$ which contains a pattern of $B$, but which does not contain such a pattern when $i$ is removed. Furthermore, by Proposition \ref{check} we can assume that $||\mathbf{g}||_1 \le ||B||_\infty - 1 + k$. Following Vatter in \cite{VIns}, we say that $\s$ witnesses $i$. Note that $i$ is present in every occurrence in $\s$ of every pattern of $B$, and so $\s$ can witness at most $||B||_\infty$ elements $i$.

Now, we just need to show that only finitely many $\s$s can witness elements. Since $\mathbf{g} \succeq \mathbf{h}$ but has no more than $k$ positive entries, all entries of $\mathbf{g}$ are 0 except for the $k$ which $\mathbf{h}$ forced to be positive. Thus, there are finitely many possible $\mathbf{g}$s which can provide witnesses (the precise number is the number of ordered integer partitions of numbers less than or equal to $||B||_\infty -1 +k$ into $k$ parts). For some fixed $\mathbf{g}$ there are $||\mathbf{g}||_1!$ possible permutations $\s$ with downfix $\pi$ and gap vector $\mathbf{g}$. Therefore, only a fixed number of downfix elements can be witnessed, and this number is independent of the length of $\pi$. So, we can take $\pi$ large enough, and there will be a downfix element which is not witnessed and hence is FS-reducible.

At this point, we have shown that for all sufficiently long $\pi$ and gap conditions $\mathbf{h}$ with $k$ ones, there exists an element $r$ which is FS-reducible for every viable $\mathbf{g} \succeq \mathbf{h}$. The proof is essentially the same for any $j < k$, but we will write it out anyway for the sake of completeness. 

Let $\pi$ be a downfix and $\mathbf{h}$ be a gap condition with $j$ ones for some $0 \le j < k$. Consider some element $i$ of $\pi$, and suppose it is not FS-reducible. Then, there exists some $\s$ which contains a pattern of $B$, but which does not contain such a pattern when $i$ is removed. This $\s$ has downfix $\pi$ and gap vector $\mathbf{g}$ satisfying $\mathbf{h}$ but not satisfying $\mathbf{h'}$ for any $\mathbf{h'}$ with more than $j$ positive entries. Again Proposition \ref{check} lets us assume that $||\mathbf{g}||_1 \le ||B||_\infty - 1 + j$. Also as before, $\s$ can witness at most $||B||_\infty$ elements $i$.

We know that all entries of $\mathbf{g}$ are 0 except for the $j$ which $\mathbf{h}$ forced to be positive (otherwise, $\mathbf{g}$ would satisfy some other $\mathbf{h'}$ with more 1s). Again, this means that only finitely many $\mathbf{g}$s can provide witnesses, and each $\mathbf{g}$ provides at most $||\mathbf{g}||_1!$ witnesses. Thus, if $\pi$ is large enough, there is a downfix element which is FS-reducible. As noted at the end of the second paragraph of this proof, that is enough to show that $\pi$ is FS-reducible. Since this is true for all sufficiently large $\pi$, a finite flexible scheme exists.
\end{proof}

While Theorem \ref{insenc_suff} shows that a finite scheme does exist, it could, in principle, be extremely deep and thus practically impossible to find. In our experiments recorded in Section \ref{results}, though, we considered 48 permutation classes with a regular insertion encoding and found finite flexible schemes for all but 3 of them. 

\subsection{Maple Implementation}
The algorithms described in this section have been implemented in the Maple package Flexible Scheme, available at the author's \href{https://sites.math.rutgers.edu/~yb165/Flexible\_Scheme.mpl}{website}. To use the package, download and save this text file. Then, open a Maple worksheet and run the command \texttt{read `Flexible\_Scheme.mpl`;}. To display the two main functions (\texttt{HasScheme} and \texttt{FindTerm}), call the help function by running the command \texttt{Help();}, and then to learn more about a function, say \texttt{HasScheme}, call help again with \texttt{HasScheme} as its argument.

The function \texttt{HasScheme} takes four arguments. The first is the set of forbidden subpatterns that define the permutation class it is trying to find a scheme for. The second is the maximum depth it will search, if it cannot reduce the downfixes at this depth, then it will give up. The third argument is the maximum gap size, that is the largest $l_1$ norm we allow putative gap restrictions to have. The final argument is a boolean called quick\_fail which, when set to true, will cause \texttt{HasScheme} to look for irreducible downfix in a depth-first manner. If no scheme of sufficiently small depth exists, this strategy provides a substantial speed-up in proving that no such scheme exists. If a scheme is found, \texttt{HasScheme} returns it, and if no scheme is found, \texttt{HasScheme} returns the reduction rules that it was able to find along with the downfixes it was unable to reduce.

The second function \texttt{SeqS} takes two arguments. The first is a scheme describing a permutation class, and the second is an integer $n$. The function returns the $n\tss{th}$ term of the enumeration sequence of the permutation class.

\section{Empirical Results}\label{results}
We tried to find regular insertion encodings, traditional schemes, and flexible schemes for several different permutation classes. In particular we looked at the avoidance classes of pattern sets $B$ where $B$ consisted of either a single pattern of length 3, 4, or 5, a pair of patterns of length 3, a pair of patterns of length 4, or a pattern of length 4 and another of length 5. 

For each of these possible pattern lengths, Table \ref{ER} shows how many classes have regular insertion encodings, how many have finite traditional schemes, how many have finite flexible schemes, and how many of those with finite flexible schemes did not have either a regular insertion encoding or a finite traditional scheme. For finding regular insertion encodings, we used Vatter's package \texttt{InsEnc} from \cite{VIns}, for finding traditional schemes we used both Zeilberger's package \texttt{VATTER} from \cite{VZSchemes} and Vatter's package \texttt{WILFPLUS} from \cite{VSchemes}, and for finding flexible schemes we used our own \texttt{Flexible\_Scheme}. 

While we can safely conclude that we found regular insertion encodings whenever they exist, the same is not true of schemes. When finding traditional schemes using \texttt{WILFPLUS}, we only considered downfixes of length $\le 8$; it is conceivable that finite schemes exist, but simply require longer downfixes, and so we did not find them. When finding traditional schemes using \texttt{VATTER} and flexible schemes using \texttt{Flexible\_Scheme}, we only considered downfixes of length $\le 8$ and gap conditions with $l_1$ norm $\le 2$. In addition, if we could not determine whether an avoidance class had a finite scheme after 36 hours of computation, we recorded it as not having a scheme.

Because of these constraints, it is conceivable that either \texttt{InsEnc} or \texttt{WILFPLUS} could have found a regular insertion encoding or a finite scheme for some class that \texttt{Flexible\_Scheme} failed to find one for. In practice, this happened for three of the avoidance classes we considered (all of which were avoiding a length 4 and length 5 pattern). 

\begin{table}[h]\caption{Empirical Results}\label{ER}
\begin{center}
\begin{tabular}{| c | c | c | c | c | c |}
\hline
Pat length\tablefootnote{$[n], [m]$ refers to classes avoiding one pattern of length $n$ and one of length $m$, $[n]$ refers to patterns avoiding one pattern of length $n$} & Sym Classes\tablefootnote{Every permutation class has up to 8 symmetries given by inverting, reversing, and complementing its patterns. Every class has the same enumeration sequence as its symmetries, so we really only care about the number of symmetry classes which can be enumerated, not the total number of permutation classes} & Ins. Enc. & ES & FS & New with FS \\ 
\hline
[3] & 2 & 0 & 2 & 2 & 0 \\
\hline
[4] & 7 & 0 & 2 & 2& 0\\
\hline
[5] & 23 & 0 & 2 & 2 & 0\\
\hline
[3], [3] & 5 & 5&5 &5 &0 \\
\hline
[4], [4] & 56 & 13 & 33 & 44 & 9 \\
\hline
[4], [5] & 434 & 30 & 112 & 173 & 59  \\
\hline
\end{tabular}
\end{center}
\end{table}


The permutation classes avoiding two length four permutations have been particularly well studied by previous authors. Generating functions are known for all but three of them, and these are conjectured not to have any D-finite generating functions in \cite{no_gf}. Two of these (avoiding \{4321, 4231\} and \{4312, 4123\}) have finite traditional schemes, and the remaining one (avoiding \{4231, 4123\}) has a finite flexible scheme. As indicated in Table \ref{ER}, 12 of the 56 symmetry classes lack finite flexible schemes as far as we can tell. These are the classes avoiding $\{1234, 3412\}$, $\{1324, 2143\}$, $\{1324, 3412\}$, $\{1324, 2341\}$, $\{1324, 4231\}$, $\{1324, 2413\}$, $\{1324, 2431\}$, $\{1342, 1423\}$, $\{1342, 2413\}$, $\{1432,2413\}$, $\{2143, 2413\},$ and $\{2413, 3142\}$. The interested reader can find links to the enumeration sequences and generating functions of all of these avoidance classes at \cite{wiki2x4}.

\section{Necessary Conditions for Schemes}\label{necc}
We next consider when we can safely give up on finding a traditional enumeration scheme (unfortunately the results do not yet extend to flexible schemes). While a few pattern avoidance classes have been proven to lack finite enumeration schemes (for example $\{1234, 4231\}$ and $\{2413, 3142\}$ in \cite{VSchemes}), there is in general no way to tell if a class has a finite scheme without simply trying to find one and eventually giving up. Here, we show that if $12\dots k$ is ES-irreducible for sufficiently large $k$ ($k=4$ is sufficient in some cases of interest), then no finite traditional scheme exits.

Before proving our result, we need to introduce a new (but standard) definition: an \emph{interval} of a permutation $\pi$ is a set of indices $I$ such that both $I$ and $\{\pi_i : i \in I\}$ are contiguous. An \emph{increasing interval}, then, is simply an interval where $\pi_i < \pi_j \iff i < j$ for all $i,j \in I$. Sometimes, we will abuse this definition by referring to the subpermutation of $\pi$ whose elements have indices in $I$ as an interval as well.

\begin{eg}
Consider the permutation 51243. Its intervals are $\es, \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{2,3\}, \{2,3,4,5\}$ and $\{1,2,3,4,5\}$. Its increasing intervals are $\es, \{1\}, \{2\}, \{3\}, \{4\}, \{5\},$ and $\{2,3\}$.
\end{eg} 

Note that a downfix $\pi$ is ES-irreducible for a set of patterns $B$ if and only if for each $i \in \pi$ there exists $\mathbf{g_i}$ satisfying the following conditions:
\begin{conds}\label{irred}~\\
\begin{enumerate}
\item $Z(B, \pi, \mathbf{g_i}) \neq \es$.
\item There exists $\s \in Y(\pi, \mathbf{g_i}) \backslash Z(B, \pi, \mathbf{g_i})$ such that every occurrence in $\s$ of a pattern in $B$ involves the element $i$. \end{enumerate}
\end{conds}
By Proposition 6.2 in \cite{VSchemes}, we can further assume that $||\mathbf{g_i}||_1 \le ||B||_\infty -1$. 

The idea behind the following two proofs is simple: if the longest increasing interval in a pattern has length $l$, then any occurrence of that pattern can use at most $l$ elements from any increasing interval in a permutation. Therefore, if that permutation has an increasing interval with more than $l$ elements, one of them can be ignored. Conditions \ref{irred} essentially require us to find two permutations for a given downfix element and gap vector; one to witness that the gap vector is viable, and one to witness that the element is not deletable. If we have these two permutations for each element of the downfix $12\dots k-1$, and they have sufficiently long increasing intervals, we can turn them into witnesses for each element of the downfix $12\dots k$ by extending their increasing intervals by a single element.

Before giving an actual theorem, we motivate it with the following example:
\begin{eg}
Consider the pattern set $B=\{3241, 4132\})$, and note that 1234 is ES-irreducible for the set of patterns (this can be checked using WILFPLUS, for instance). To show that 12345 is also ES-irreducible, we need to show that Conditions \ref{irred} hold for each of the five elements; in this example we will show that they hold for 1. Notice that, because 1234 is ES-irreducible, there exists a $\mathbf{g_1'}$ satisfying Conditions \ref{irred} for the 1 in 1234, for instance $[1,1,0,0,0]$ will do the job, since $516234 \in Z(B, 1234, [1,1,0,0,0])$, and $615234 \in Y(1234,[1,1,0,0,0])\backslash Z(B, 1234, [1,1,0,0,0])$ has three 4132 patterns all using the 1 and no 3241 patterns.

Now, we'll show that $\mathbf{g_1} = [1,1,0,0,0,0]$ satsifies Conditions \ref{irred} for the 1 in 12345. Take 516234, increase all elements larger than 1 by 1, and insert a 2 between the new 7 and 3 to get 6172345, and note that this permutation is in $Z(B, 12345, [1,1,0,0,0,0])$. Similarly, take 615234, increase all elements larger than 1 by 1 and insert a 2 between the new 6 and 3 to get 7162345, and note that this permutation is in $Y(12345,[1,1,0,0,0,0]) \backslash Z(B, 12345, [1,1,0,0,0,0])$, and the four 4132 patterns all use the 1 (and there are still no 3241 patterns).
\end{eg}


%\begin{lemma}\label{still_irred} Let $B$ be a set of patterns, and suppose the longest increasing interval of a pattern in $B$ has length $l$. Then, two related statements hold:
%\begin{enumerate}
%\item Let $\g'$ satisfy Conditions \ref{irred} for an element $i-1$ of the downfix $\pi' = 12\dots k-1$, and let $\s'$ be the permutation promised by the second of Conditions \ref{irred}. If $\s'$ has at least $l$ consecutive downfix elements at any point before $i-1$, (i.e. $\g'$ has $l-1$ consecutive 0s sometime before its $i-1\tss{th}$ element), then create $\s$ by adding an additional element to this run (and $\g$ by adding an additional 0 to the run of $l-1$ 0s). This pair fulfills Conditions \ref{irred} for the element $i$ of $\pi = 12\dots k$.
%\item Let $\g'$ satisfy Conditions \ref{irred} for an element $i$ of the downfix $\pi' = 12\dots k-1$, and let $\s'$ be the permutation promised by the second of Conditions $\ref{irred}. If $\s'$ has at least $l$ consecutive downfix elements at any point after $i$, (i.e. $\g'$ has $l-1$ consecutive 0s sometime after its $i+1\tss{th}$ element), then create $\s$ by adding an additional element to this run (and $\g$ by adding an additional 0 to the run of $l-1$ 0s). This pair fulfills Conditions \ref{irred} for the element $i$ of $\pi = 12\dots k$.
%\end{enumerate}
%\end{lemma}
%\begin{proof}
%We begin with the first statement. 

\begin{lemma}\label{still_irred} Let $B$ be a set of patterns. Suppose that the longest increasing interval of a pattern in $B$ has length $l$. Then, two related statements hold:
\begin{enumerate}
\item Suppose that $\mathbf{g'}$ satisfies Conditions \ref{irred} for an element $i-1$ of the downfix $\pi' = 12 \dots k-1$. Suppose further that $g'_j, g'_{j+1}, \dots g'_{j+l-2}$ are all 0 for some $j \ge 2$ where $i > j+l-1$. Form $\mathbf{g}$ by inserting a 0 into $\mathbf{g'}$ immediately before entry $g'_j$. Then $\mathbf{g}$ satisfies Conditions \ref{irred} for the element $i$ of $\pi = 12\dots k$.
\item Suppose that $\mathbf{g'}$ satisfies Conditions \ref{irred} for an element $i$ of the downfix $\pi' = 12 \dots k-1$. Suppose further that $g'_j, g'_{j+1}, \dots g'_{j+l-2}$ are all 0 for some $j > i+1$ where $j+l-1 \le k$. Form $\mathbf{g}$ by inserting a 0 into $\mathbf{g'}$ immediately before entry $g'_j$. Then $\mathbf{g}$ satisfies Conditions \ref{irred} for the element $i$ of $\pi = 12\dots k$.
\end{enumerate}
\end{lemma}
\begin{proof}
We begin with the first statement. There is a bijection $F$ between permutations $\s' \in Y(\pi', \mathbf{g'})$ and permutations $\s \in Y(\pi, \mathbf{g})$ given by inserting a copy of the element $j-1$ immediately before the existing $j-1 \in \s'$ and then increasing all elements of $\s'$ greater than or equal to $j-1$ (except for the new copy) by one. Choose $\s' \in Z(B, \pi', \mathbf{g'})$, let $a = \sum_{p=1}^{j-1} g'_p$, and note that $\big\{a + j-1, a +  j,\dots, a + j+l-2\big\}$ is an increasing interval of $\s'$. Let $\s = F(\s')$ (now $I = \big\{a + j-1,a +  j,\dots, a + j+l-1\big\}$ is an increasing interval of $\s$), and suppose by way of contradiction that $\s \not\in Z(B, \pi, \mathbf{g})$. There must be an occurrence of a pattern of $B$ in $\s$ which uses $j$, but $j$ is in $I$ which has length $l+1$, and this pattern can use at most $l$ elements in $I$. Since it doesn't matter which $l$ elements are used, the pattern can just as well be formed with the $l$ elements of the increasing interval that aren't $j$. Thus, this pattern already existed in $\s'$ and $\s' \not \in Z(B, \pi', \mathbf{g'})$. This contradicts our choice of $\s'$, so we conclude that $\s \in Z(B, \pi, \mathbf{g})$.

Next, we verify that $\mathbf{g}$ satisfies the second of Conditions \ref{irred} for $i$. Let $\s' \in Y(\pi', \mathbf{g'}) \backslash Z(B, \pi', \mathbf{g'})$ be the permutation promised by the second condition, and set $\s = F(\s')$. We immediately have that $\s \in Y(\pi, \mathbf{g}) \backslash Z(B, \pi, \mathbf{g})$. Consider some occurrence $p_1$ in $\s$ of a pattern in $B$. Again, let $I$ be the increasing interval of length $l+1$ beginning with $j-1$. As noted in the preceding paragraph, this occurrence $p_1$ contains $\le l$ elements of $I$, and, so we can find an occurrence $p_2$ of the same pattern using all the same elements of $\s$ outside of $I$, but not using $j-1$. This occurrence $p_2$ corresponds to an occurrence $p_3$ of the same pattern in $\s'$ which must have used $i-1$ (because $\s'$ satisfies Conditions \ref{irred} for $i-1$). When we turn $\s'$ into $\s$, we increase all elements at least as large as $j-1$ by 1; since $i -1 \ge j-1$ it is increased to $i$. Therefore, $p_2$ used $i$, and so did $p_1$ since $i$ lies outside $I$ and $p_1$ and $p_2$ use all the same elements except for the ones with indices in $I$. Thus, $\s$ satisfies Conditions \ref{irred} for $i$. 

The proof of the second statement is essentially the same, except now $I$ falls after $i$. 
\end{proof}

\begin{prop} Let $B$ be a set of patterns whose longest increasing interval has length $l$. Suppose that $\big\lfloor k/2\big\rfloor -1 \ge (l-1)(||B||_\infty-1)+l$, and $\pi'=12\dots (k-1)$ is ES-irreducible for $B$. Then $\pi = 12\dots k$ is also ES-irreducible for $B$.
\end{prop}
\begin{proof}
We claim that $\pi$ is ES-irreducible for $B$, so we will find $\mathbf{g}$ satisfying Conditions \ref{irred} for every $i \in \pi$. Choose such an $i \in \pi$, and suppose $i \ge \lfloor k/2 \rfloor +1$. Let $\pi' = 12\dots k-1$; by our hypothesis, $\pi'$ is ES-irreducible for $B$, and so there exists $\mathbf{g'}$ which satisfies Conditions \ref{irred} for $i-1$. Now, $\pi'$ has at least $\lfloor k/2 \rfloor -1$ elements less than $i-1$, which by assumption is at least $(l-1)(||B||_\infty-1)+l$. Since $||\mathbf{g'}||_1 \le ||B||_\infty -1$, even if all the positive entries in $\mathbf{g'}$ are placed before $i-1$, we can find at least $l$ entries of $\pi'$ occurring before $i-1$ such that the $l-1$ $g'_j$ corresponding to the gaps between them are all 0. Thus the conditions of Lemma \ref{still_irred} part 1 are satisfied, and if we form $\s$ as per the lemma, we find that $\s$ satisfies Conditions \ref{irred} for $i$.

Now suppose that $i \le \lfloor k/2 \rfloor$. Then, $\pi'$ has at least $\lfloor k/2 \rfloor - 1$ elements greater than $i$, so we can find at least $l$ entries of $\pi$ occurring after $i$ such that the $l-1$ $g'_j$ corresponding to the gaps between them are all 0. Thus the conditions of Lemma \ref{still_irred} part 2 are satisfied, and if we form $\s$ as per the lemma, we find that $\s$ satsifies Conditions \ref{irred} for $i$.
\end{proof}

This result shows that as long as $12\dots k$ is irreducible for $k$ large enough (when $l=1, k=4$ will do), then $B$ has no finite traditional scheme. A similar argument shows that the same is true if $k\dots 21$ is irreducible (and thus that $\{1423, 2314\}$ from Example \ref{1423_2314} has no such scheme). While we have not been able to prove the corresponding result for flexible schemes, we suspect that it is also true.

\section{Flexible Schemes For Covincular Patterns}\label{vin}

The purpose of this section is to extend the work of Baxter and Pudwell \cite{Baxter} on enumeration schemes for vincular patterns to flexible schemes. A vincular, or dashed, pattern is much like a classical pattern, except in an occurrence of a vincular pattern some of the permutation elements participating in the pattern may be required to occur consecutively in the permutation. In Section \ref{Callan} we talk more about vincular patterns, but in this section we are actually interested in a related object: what Bean et al. \cite{Bean_covincular} call \textit{covincular patterns}.

The reason for this is that the previous authors count with prefix schemes and we count with downfix schemes, and so we are essentially counting the inverses of the permutations that they count. The inverse of a vincular pattern is not another vincular pattern, but rather a covincular patterns. This is a pair $\t=(\s, X)$ where $\s$ is the underlying permutation which must be avoided and $X$ indicates which elements in an occurrence of $\s$ must be consecutive values (rather than having consecutive indices like a vincular pattern). Similarly, a \textit{spaced permutation} is a pair $\r = (\pi, Y)$ where $\pi$ is the underlying permutation and $Y$ indicates which elements of $\pi$ should not be treated as occurring consecutively. If $X = \es$, then $\t$ is just an ordinary pattern, and if $Y = \es$, then $\r$ is an ordinary permutation.

Containment of covincular patterns is slightly more complicated than classical containment. Let $\pi = \pi_1\pi_2\dots \pi_n$ and $\s = \s_1\s_2 \dots \s_k$ be permutations. For $\pi$ to contain the covincular pattern $(\s,X)$, we first must find a classical occurrence of $\s$ in $\pi$, i.e. we need $i_1 < i_2 < \dots < i_k$ such that $\pi_{i_1}\pi_{i_2}\dots\pi_{i_k}$ has the same relative order as $\s$ (ignoring dots). This occurrence must have the further property that for all $\s_l, \s_m$ with $\s_l + 1 = \s_m$, if $\s_l \in X$, then $\pi_{i_m}$ is one larger than $\pi_{i_l}$ and $\pi_{i_l} \notin Y$. 

Finding a downfix of a spaced permutation is done more or less how one would expect. A downfix of $(\pi, Y)$ is a pair $(\pi', Y')$ where $\pi'$ is the subpermutation of $\pi$ consisting of elements $\le l$ for some integer $l$, and $Y'$ is the subset of $Y$ whose elements are no greater than (the same integer) $l$.

We define $S(B, \pi, \mathbf{g})$ similarly to how we defined $Z(B, \pi, \mathbf{g})$. Just like $Z(B, \pi, \mathbf{g})$, it is the set of permutations with downfix $\pi$ and corresponding gap vector $\mathbf{g}$, the only difference is that both $\pi$ and the elements of $S(B,\pi,\mathbf{g})$ are spaced permutations. 

\begin{eg} 
\begin{align*}
S(\{(123,\{2\})\}, (21,\{1\}), [0,1,1]) &=
\\
&\big\{(2413, \{1\}), (2413, \{1,3\}), (2413, \{1,4\}), 
\\
&(2413, \{1,3,4\}), (2314, \{1,3\}), (2314, \{1,3,4\})\big\}
\end{align*}
Notice that $(2314, \{1,3\})$ avoids $(123, \{2\})$ because, although 234 is an occurrence of 123 and are all consecutive values, we pretend that there is some placeholder value between 3 and 4 (since $3\in \{1,3\}$). Since the 2 and 3 in any occurrence of $(123, \{2\})$ can't have any values between them, this is not a valid occurrence.
\end{eg}

As with classical pattern avoidance, the key operation here will be deleting a downfix element to get a smaller permutation. Unlike with classical pattern avoidance, though, when we delete a downfix element, we need to add a placeholder element to $Y$ to mark where the element used to be, while retaining all previous placeholders as well. Let $d_r((\pi,Y)) = \t' = (\pi',Y')$. We define $\pi' = d_r(\pi)$ (we abuse notation by treating $d_r$ as a function both on classical and spaced permutations), and $Y' = \{y: y \in Y, y <r\} \cup \{y-1 : y \in Y, y \ge r\} \cup \{r-1\}$. (Notice that if $r=1$, then we add the element 0 to $Y'$ which has no effect on whether a permutation contains $\t'$; this makes sense since $1$ can't prevent a pattern by separating two pattern elements, and so we don't actually need to add a placeholder when deleting it.) Since gap vectors are the same for spaced permutations as for classical ones, we do not need to redefine $d_r(\mathbf{g})$. Lemma \ref{no_pat} shows that we cannot create a new pattern when we delete a permutation element in this way.

\begin{lemma}\label{no_pat} Suppose $(\pi, Y)$ is a permutation which does not contain the pattern $(\s, X)$. Then, $d_r((\pi, Y))$ does not contain $(\s, X)$ either. 
\end{lemma}
\begin{proof}
Let $(\pi',Y') = d_r((\pi,Y))$. Suppose $(\pi', Y')$ contains $(\s, X)$, and suppose this occurrence uses the elements $\pi'_{i_1}, \pi'_{i_2}, \dots, \pi'_{i_k}$. These elements correspond to the elements $\pi_{j_1}, \pi_{j_2}, \dots, \pi_{j_k}$ of $\pi$ (note that $\pi_{j_x} \neq r$ for all $x$), and these elements form a (classical) occurrence of $\s$. Since $(\pi, Y)$ doesn't contain $(\s, X)$, we can find $\pi_{j_l}, \pi_{j_m}$ corresponding to $\s_l,\s_m$ such that $\s_{l}+1 = \s_m$, $\s_l \in X$ and either $\pi_{j_l} +1 < \pi_{j_m}$ or $\pi_{j_l} \in Y$.

First, suppose $\pi_{j_l} + 1 < \pi_{j_m}$. Either $\pi'_{j_l} + 1 < \pi'_{j_m}$, in which case we didn't actually have an occurrence of $(\s,X)$ in $(\pi', Y)$, or $\pi_{j_l} = r-1$ and $\pi_{j_m} = r+1$. In this case, $Y'$ contains $\pi_{j_l} = r-1$, and so again we didn't actually have an occurrence of $(\s, X)$. Next, suppose that $\pi_{j_l} \in Y$. If $r < \pi_{j_l}$, then $\pi_{j_l} - 1 = \pi'_{j_l} \in Y'$, and if $r > \pi_{j_l}$, then $\pi'_{j_l} = \pi_{j_l} \in Y$ and so again we didn't actually have an occurrence of $(\s, X)$. 
\end{proof} 

We can now proceed much as we did in Section \ref{find_scheme}. As before, we need to know two things: when we can delete downfix elements, and when every permutation with a particular downfix and gap vector contains a forbidden pattern.

\subsection{Deleting Downfix Elements}\label{delete}

 There is a simple bijection $F_r$ between $S(\es, \r, \mathbf{g})$ and $S(\es,d_r(\r), d_r(\mathbf{g}))$ given by deleting the $r$ in the permutation's downfix, and adding an appropriate place holder. Let $f_r$ be the restriction of $F_r$ to $S(B, \r, \mathbf{g})$; in the classical case, it was obvious that $f_r$ was an injection into $S(B, d_r(\r), d_r(\mathbf{g}))$; in the covincular case, this is a consequence of Lemma \ref{no_pat}. Sometimes, $f_r$ is not just an injection, but is a bijection; we would like some analogue of Proposition \ref{check} which tells us when that is the case. Luckily, this proposition is easily adapted to our new situation.

\begin{prop}\label{vin_check}
Let $B$ be a set of forbidden patterns, $\r=(\pi,Y)$ be a downfix, and $\mathbf{h}, \mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$ be gap conditions. Suppose that 
\[|S(B, \r, \mathbf{g})| = |S(B,d_r(\r), d_r(\mathbf{g}))|\]
for all $\mathbf{g}$ with $||\mathbf{g}||_1 \le ||B||_\infty -1 + ||\mathbf{h}||_1$ which satisfy $\mathbf{h}$ but fail to satisfy any of $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$. Then the equality holds for all $\mathbf{g}$ which satisfy $\mathbf{h}$ but fail to satisfy any of $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$.
\end{prop}

\begin{proof} 
Choose some $\mathbf{g}$ satisfying $\mathbf{h}$ and no other $\mathbf{h_i}$. The observation in the previous paragraph is enough to show that $|S(B,\r, \mathbf{g})| \le |S(B,d_r(\r), d_r(\mathbf{g})|$, so we just need to show the reverse inequality. 

Suppose that there is some spaced permutation $(\s,X) \in S(\es,\r,\mathbf{g})$, but which isn't in $S(B,\r,\mathbf{g})$ because it contains some pattern of $B$. Suppose further that when the $r$ in the downfix is deleted (and $r-1$ added to $X$), it ceases to contain any pattern of $B$. Choose some occurrence of a pattern $b \in B$ in $(\s, X)$, and suppose that it uses the elements $\s_{i_1}, \s_{i_2}, \dots, \s_{i_k}$ (where $k \le ||B||_\infty$). Form $\s'$ by iteratively finding non-downfix elements $s$ which do not participate in this occurrence and which are not necessary to ensure that $\s'$ has a gap vector satisfying $\mathbf{h}$, and then deleting these elements by replacing $(\s,X)$ with $d_s((\s,X))$. Since there are $\le ||B||_\infty -1$ elements other than $r$ participating in the forbidden occurrence and $\le ||h||_1$ elements needed to have a gap vector satisfy $\mathbf{h}$, we can delete all by $||B||_\infty-1+||h||_1$ non-downfix elements in this way. Reduce the resulting permutation.

At this point, we have a permutation $(\s', X') \in S(\es, \r, \mathbf{g})\backslash S(B, \r, \mathbf{g})$ with $||g||_1 \le ||B||_\infty -1 + ||h||_1$ where $\mathbf{g}$ satisfies $\mathbf{h}$ and no other $\mathbf{h_i}$. All that remains is to show that $d_r((\s',X')) \in S(B, d_r(\r), d_r(\mathbf{g}))$. To do this, notice that we can form $d_r((\s', X'))$ by first finding $d_r((\s, X))$, which we assumed has no forbidden pattern, and deleting all the $s$'s that we deleted from $(\s, X)$ in the previous paragraph. By Lemma \ref{no_pat} these deletions cannot create any forbidden pattern, and so $d_r((\s',X')) \in S(B,d_r(\r), d_r(\mathbf{g}))$ as required.
\end{proof}

Strictly speaking, $|S(B, \r, \mathbf{g})| = |S(B,d_r(\r), d_r(\mathbf{g}))|$ is not exactly the equality we want. This is an equality between sets of spaced permutations where placeholders can occur anywhere, but we actually want an equality between sets of spaced permutations where placeholders can only occur in the downfix. Precisely, the equality we want is $|R(B, \r, \mathbf{g})| = |R(B,d_r(\r), d_r(\mathbf{g}))|$ where $R(B, \r, \mathbf{g})$ is the set of spaced patterns $(\s,X)$ with downfix $\r=(\pi,Y)$ and corresponding gap vector $\mathbf{g}$ such that $X=Y$. Fortunately, the equality we have is stronger than the one we actually want.

\begin{cor}\label{real_vin_check}
Under the same hypotheses as Proposition \ref{vin_check}, we also have that
\[|R(B,\r,\mathbf{g})| = |R(B,d_r(\r), d_r(\mathbf{g}))|\]
for all $\mathbf{g}$ which satisfy $\mathbf{h}$ but fail to satisfy any of $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$.
\end{cor}
\begin{proof}
Let $\r = (\pi, Y)$, and by way of contradiction, suppose there is some $(\s', X') \in R(B,d_r(\r), d_r(\mathbf{g}))$ whose preimage $(\s, Y)$ under $F_r$ is not in $R(B, \r,\mathbf{g})$. It follows that either $(\s, X) \not\in R(\es, \r, \mathbf{g})$ or $(\s, X) \not\in S(B, \r, \mathbf{g})$. That $(\s, X) \in R(\es, \r, \mathbf{g})$ is clear simply from the definition of $R$, and that $(\s, X) \in S(B, \r, \mathbf{g})$ follows from Proposition \ref{vin_check}. Therefore, $(\s, X) \in R(\es, \r, \mathbf{g}) \cap S(B, \r, \mathbf{g}) = R(B, \r, \mathbf{g})$ and we have obtained a contradiction.
\end{proof}

Notice that while the conclusion of Proposition \ref{vin_check} implies that of Corollary \ref{real_vin_check}, the converse is not true. This opens up the possibility that we could verify Proposition \ref{vin_check} for just some subset of permutations in $S(B,\r,\mathbf{g})$ and find a condition which is true more often and which still implies Corollary \ref{real_vin_check}.

Specifically, we would like to find a subset 
\[S'_r\big(B, \r, \mathbf{h},(\mathbf{h_i})_{i=1}^k\big) \subseteq \bigcup_{||\mathbf{g}||_1 \le ||B||_\infty + ||\mathbf{h}||_1 - 1} S(B, \r, \mathbf{g})\]
 which contains exactly those spaced permutations resulting from taking a permutation in $R(B, \r, \mathbf{g})$ (for any $\mathbf{g}$) and performing the deletions described in the proof of Proposition \ref{vin_check} to check if $r$ is deletable for permutations with gap vectors satisfying $\mathbf{h}$ and not any $\mathbf{h_i}$. Our next step is to build such an $S'_r$, based on the containment scenarios of Baxter and Pudwell \cite{Baxter}. While we do not prove that this $S'_r$ is minimal, it is much smaller than $S$. 

We define $S'_r\big(B, (\pi,Y), \mathbf{h}, (\mathbf{h_i})_{i=1}^m \big)$ to be the set of spaced permutations $(\s, X)$ satisfying the following conditions:
\begin{enumerate}
\item $(\pi, Y)$ is a downfix of $(\s, X)$.
\item $(\s, X)$ contains an occurrence of a pattern $(\mu, Z) \in B$. Let this occurrence be $\s_{i_1}\s_{i_2}\dots\s_{i_k}$, it must be that $r = \s_{i_l}$ for some $l$. 
\item The gap vector corresponding to $(\s, X)$ (i.e. $\mathbf{g}$ such that $(\s, X) \in S(\es, (\pi,Y), \mathbf{g})$) satisfies $\mathbf{h}$ but not $\mathbf{h_i}$ for any $i$.
\item $X$ contains all elements except possibly those in $\{1,2,\dots,|\pi|-1\}$ and $\{\s_{i_l}: \mu_l \in Z\}$. In other words, $X$ contains all elements except the ones that would violate conditions 1 or 2.
\item $(\s, X)$ is minimal. 
\end{enumerate}

Note that $S'_r$ is actually missing some of the spaced permutations resulting from taking a permutation in $R(B, \r, \mathbf{g})$ and performing the deletions described in the proof of Proposition \ref{vin_check}. In particular, condition 4 demands that $X$ contain every element that it can hold without violating conditions 1 or 2, but some resulting permutations may have a smaller (or even empty) $X$. It is enough, though, to check the spaced permutations with maximal $X$; we want to know if there is a spaced permutation such that deleting $r$ erases all occurrences of a forbidden pattern, and if that's true of a spaced permutation with more adjacent elements, it is certainly true of a spaced permutation with fewer adjacent elements.

The following is an example of $S_r'$:
\begin{eg}
\begin{align*}
S_2'(\{(123, \{1\})\}, 21, [1,0,0]) = \big\{&(52341, \{3,4\}), (52314, \{3,4\}), 
\\
&(42351, \{3,4\}), (42315, \{3,4\}),
\\
&(52134, \{3,4\}), (42135, \{3,4\})\big\}.
\end{align*}
This set is built as follows. The downfix element 2 must participate in a forbidden subpattern, and the only role it can fill in such a pattern is the smallest element. Therefore, it must be followed by a 3 and then some larger element, and these elements can occur either before or after the 1 in the downfix. This gives us three options: $2341, 2314,$ and $2134$. However, these have gap vectors $[0,2,0], [0,1,1],$ and $[0,0,2]$, none of which satisfy $[1,0,0]$, so we need to add an extra element before the 2. This element can't be between the 2 and 3, but can either be larger than the 3 and smaller than the 4 or larger than the 4. This gives us the six permutations $42351, 52341, 42315, 52314, 42135,$ and $52134$. To find $Y$ for each permutation, we note that $1 \not\in Y$ because it and 2 are both in the downfix and $2 \notin y$ because it serves as the 1 in a $(123, \{1\})$ pattern, but both 3 and 4 can be in $Y$.
\end{eg}

\subsection{Guaranteeing Forbidden Patterns}
We now can tell when some downfix element $r$ can be deleted from every permutation in $R(B, \r, \mathbf{g})$ with $\mathbf{g}$ satisfying $\mathbf{h}$ but not $\mathbf{h_1}, \mathbf{h_2}, \dots, \mathbf{h_k}$. Our next task is to determine when $R(B, \r, \mathbf{g}) = \es$ for every $\mathbf{g}$ satisfying $\mathbf{h}$. Just like how we defined $R(B, \r, \mathbf{g})$ to be all $(\s, X) \in S(B, (\pi, Y), \mathbf{g})$ where $X = Y$ (i.e. contains as few elements as possible), we can define $T(B, \r, \mathbf{g})$ to be all $(\s, X) \in S(B, (\pi, Y), \mathbf{g})$ where $X = Y \cup \{|\pi|, |\pi|+1, \dots, |\pi| + ||\mathbf{g}||_1 -1\}$ (i.e. contains as many elements as possible).

\begin{prop}\label{non_viable}
Suppose that $T(B, \r, \mathbf{h}) = \es$. Then, $R(B, \r, \mathbf{g}) = \es$ for all $\mathbf{g} \succeq \mathbf{h}$.
\end{prop}
\begin{proof}
We prove the contrapositive. Choose some $(\s, X) \in R(B, (\pi, Y), \mathbf{g})$ where $\mathbf{g} \succeq \mathbf{h}$. Form $(\s', X')$ by deleting non-downfix elements from $\s$ until the only non-downfix elements left are those forced to be present by $\mathbf{h}$. As in the proof of Proposition \ref{vin_check}, put a placeholder element in $X'$ for each deletion. The resulting permutation avoids all the patterns in $B$ by Lemma \ref{no_pat}. Add more elements to $X'$ until $X' = Y \cup \{|\pi|, |\pi|+1, \dots, |\pi| + ||\mathbf{g}||_1 -1\}$; adding more elements to $X'$ can't cause to contain a pattern that it didn't already, and so $(\s', X') \in T(B, \r, \mathbf{h})$.
\end{proof}

Much like Theorem 4 in \cite{Baxter}, Proposition \ref{non_viable} gives only a sufficient condition for $R(B, \r, \mathbf{g}) = \es$. Example \ref{not_necc} illustrates the non-necessity of the condition.

\begin{eg}\label{not_necc}
We will show that $R(\{(312, \{2\})\}, (12, \es), \mathbf{g}) = \es$ for all $\mathbf{g} \succeq [1,0,0]$ even though $(312, \{2\}) \in T(B, \r, [1,0,0])$. It is clear that $(312, \{2\}) \in T(B, \r, [1,0,0])$ since the 2 in the permutation can't serve as the 2 in the pattern since there is a placeholder element between it and the 3.

However, it still holds that $R(\{(312, \{2\})\}, (12, \es), \mathbf{g}) = \es$ for all $\mathbf{g} \succeq [1,0,0]$. Choose some $ (\s, X) \in R(\es, (12, \es), \mathbf{g})$ (note that $X = \es$). Because $\mathbf{g} \succeq [1,0,0]$, there is at least one element of $\s$ greater than 2 preceding the 1. Let $\s_{i_1}$ be the smallest such element. This choice forces $\s_{i_1} -1$ to occur after the 1, and so $\s_{i_1} 1 (\s_{i_1}-1)$ forms a (312, \{2\}) pattern.
\end{eg}

\subsection{Finding a Scheme}
Now that we can determine when a downfix element is deletable and when all permutations with a certain downfix and gap vector are non-viable, we are ready to define the covincular versions of \texttt{FindTerm}, \texttt{HasReductionRule}, and \texttt{HasScheme}. We do so in much the same way that we did for classical patterns. In fact, both \texttt{FindTerm} and \texttt{HasScheme} do not even need to be rewritten. The pseudocode provided in Algorithms \ref{FT} and \ref{HS} works just as well in the covincular case; all that is necessary is to remember that $\pi$ is now a spaced permutation and $d_r(\pi)$ and $f_i(\pi)$ are slightly different when $\pi$ is a spaced permutation. Further, \texttt{HasReductionRule} needs only slight modification; specifically $Z(B, \pi, \mathbf{h})$ in Algorithm \ref{HRR} needs to be replaced with $T(B, \pi, \mathbf{h})$ and $Z(B, \pi, \mathbf{g})$ and $Z(B, d_r(\pi), d_r(\mathbf{g}))$ need to be replaced with $S(B, \pi, \mathbf{g})$ and $S(B, d_r(\pi), d_r(\mathbf{g}))$ respectively.

All these functions are implemented in the Maple package \texttt{Flexible\_Covincular\_Scheme}, available on the author's \href{https://sites.math.rutgers.edu/~yb165/Flexible_Covincular_Scheme.mpl}{website}. As with \texttt{Flexible\_Scheme}, the main two functions are \texttt{HasScheme} which attempts to find a enumeration scheme for a set of forbidden patterns and \texttt{SeqS} which uses a scheme to generate as many terms of the enumeration sequence as the user requests. 

Our method of building schemes is a bit different than that of Baxter and Pudwell \cite{Baxter}. There, the authors don't add placeholders to downfixes when deleting elements, but instead check whether deleting an element can introduce a new pattern (we just check whether deleting an element can eliminate a pattern). Our primary reason for this difference is that we wanted our framework to be as analogous as possible to our framework for finding schemes for classical pattern avoidance. Both frameworks have advantages in terms of which sets of forbidden patterns they can find schemes for; in fact we found some pattern sets which could be enumerated using existing vincular schemes but not using flexible ones. 

\subsection{Empirical Results}
We tried to find schemes for enumerating the permutations avoiding covincular permutations of length 4 as well as pairs of covincular permutations of length 4. In both cases, we compared the successes of our new flexible schemes (FS) with existing enumeration schemes (ES). We allowed both types of schemes to have depth up to 5, and use gap restrictions with $l_1$ norm up to 2. As Table \ref{vin_empirical} shows, we found that both types of schemes managed to enumerate the same permutation classes avoiding a single pattern of length 4. For pairs of length-4 patterns, flexible schemes were able to enumerate significantly more classes than existing schemes, but there were a handful of classes that flexible schemes couldn't enumerate even though previous ones could. As in Section \ref{results}, we record a permutation class as not having a scheme if we couldn't find on after 36 hours of computation.


\begin{table}[h]\caption{Empirical Results}\label{vin_empirical}\addtolength{\tabcolsep}{-1.5pt}

\begin{tabular}{| c | c | c | c | c | c |}
\hline
Pat length & Sym Classes & ES Only & FS Only& Both ES and FS & Neither ES nor FS \\ 
\hline
[4] & 56 & 0 & 0 & 35 & 21 \\
\hline
[4],[4] & 4776 & 9 & 269 & 1649& 2849\\
\hline
\end{tabular}
\end{table}


\section{Future Work}
There are a number of potential avenues for future research. As noted in the introduction, traditional schemes have been extended beyond pattern avoidance in permutations to pattern avoidance in words \cite{Pudwell}. We believe that flexible schemes can also be extended to cover this case just as Section \ref{vin} extends them to covincular pattern avoidance. 

Another tempting possibility is to unite flexible schemes (or traditional schemes for that matter) with the structure paradigm exemplified by the \texttt{TileScope} algorithm \cite{struct}. In Section \ref{1342}, we do this in a special case by attempting to find a scheme for the permutations that avoid 1423 and then, once we find an ES-irreducible downfix, finding its structural properties to complete the enumeration. Unfortunately, Section \ref{1342} does this in an ad hoc way which only works for the specific class under consideration. It would be very interesting to build a general algorithm for many different permutation classes.

Finally, this section only partially answers Vatter's original question \cite{VSchemes} which was to build a framework capable of enumerating any permutation class with a finite enumeration scheme, a regular insertion encoding, or finitely many simple permutations. While we have made partial progress to an answer the whole question remains open.

\chapter{Permutations avoiding 1423 (and Equivalently 1342)}\label{1342}
The permutations avoiding 1342 have the generating function $\ds \frac{32x}{1+20x-8x^2-(1-8z)^{3/2}}$ and are also given by the formula 
\[|\Av(\{1342\};n)| =  \frac{(7n^2 -3n -2)}{2} \cdot (-1)^{n-1} + 3\sum_{i=2}^n 2^{i+1} \cdot \frac{(2i-4)!}{i!(i-2)!}\cdot \binom{n-i+2}{2} \cdot (-1)^{n-i}.\]
These results were originally found by B\'ona \cite{Bona} through a bijection between $\Av(\{1342\})$ and a certain class of labelled trees. Later, the generating function was rederived by Bloom and Elizalde through a bijection from the permutations in $\Av(\{3124\})$ to specific board minimal rook placements, and from there to certain Dyck paths \cite{Bloom}. In this section, we derive a fast recurrence to count the 1342-avoiding permutations in the style of enumeration schemes.

Like Bloom and Elizalde, we find it more convenient to actually count a different class of permutations. In our case, we will enumerate permutations avoiding 1423, but counting one class is equivalent to counting the other since 1423 and 1342 are inverses.

We will find it convenient to talk about permutations with particular downfixes and \textit{index vectors} (rather than gap vectors like in Section \ref{auto_enum}). An index vector gives the index of each downfix element in the permutation. We define $A(B, \pi, \mathbf{i}, n)$ to be the set of permutations of length $n$ avoiding the patterns in $B$ with downfix $\pi$ and corresponding index vector $\mathbf{i}$. For example, $A(\{123\}, 21, [1,3],4) = \{2413\}$. 

Note that we could equivalently express this set as $Z(\{123\}, 21, [0,1,1])$, and, in fact, it is simple to translate any set of permutations defined using an index vector to one defined using a gap vector. The arguments which we will be making, however, are much more natural when expressed using index vectors, and so we choose that convention.

\section{Structure of 1423 Avoiders}

We are trying to find $|A(\{1423\}, \es, [], n)|$, and we begin with the standard enumeration scheme trick of separating the permutations into classes by where their 1 element occurs. Algebraically,
\begin{equation}\label{first_refine}
|A(\{1423\},\es, [],n)| = \sum_{i=1}^{n} |A(\{1423\}, 1, [i],n)|.
\end{equation}
Next, we separate them further by where their 2 element occurs, and find:
\[|A(\{1423,1,[i],n)| = \sum_{j=i+1}^{n} |A(\{1423\}, 12, [i,j],n)| + \sum_{j=0}^{i-1} |A(\{1423\}, 21, [j, i],n)|.\]
The second element of the downfix 21 is ES-reducible, and so we can actually write
\begin{equation}\label{es-redu}
|A(\{1423,1,[i],n)| = \sum_{j=i+1}^{n} |A(\{1423\}, 12, [i,j],n)| + \sum_{j=0}^{i-1} |A(\{1423\},1,[j], n-1)|
\end{equation}

Now it gets tricky, though. Not only is 12 not ES-reducible, there appears to be no finite traditional (or flexible) scheme for 1423. Luckily, we still know a great deal about the structure of a permutation with a 12 prefix, as shown in the following observation.

\begin{obs}\label{obvious} If $\pi$ avoids 1423 and has a 12 downfix, then all the elements in $\pi$ occurring between the 1 and 2 are smaller than all the elements occurring after the 2.
\end{obs}
 
In fact, much more is true. 

\begin{lemma}\label{split_nice} 
For all $\pi \in A(\{1423\},12,[i,j],n)$ there exists $k \le i$ such that $\{\pi_k, \pi_{k+1}, \dots, \pi_j\} = \{1,2,\dots, j-k+1\}$; that is the $j-k+1$ elements between $\pi_k$ and $\pi_j$ are smaller than all other elements of $\pi$.
\end{lemma}
\begin{proof}
We proceed by induction on $i$. If $i=j-1$, then the lemma is trivial. Otherwise the open interval $(i,j)$ is nonempty. Let $\pi_{k_1}$ be the first (left-most) element in $\pi$ which is less than an element whose index is in $(i,j)$ and let $\pi_{j_1} = \max\{\pi_l: l \in (i,j)\}$. If $k_1=i$, then the lemma follows from Observation \ref{obvious}, so assume $k_1 < i$. Form $\pi'$ by taking the subpermutation of $\pi$ consisting of $\pi_{k_1},\pi_{j_1}$, and all $\pi_l > \pi_{j_1}$, and then reducing this subpermutation. Note that $\pi'$ is a permutation avoiding 1423 which has a 12 downfix (provided by $k_1$ and $j_1$); let $i'$ and $j'$ be the indices of the 1 and 2 elements respectively. Note also that $i' < i$, and so the induction hypothesis promises an index $k' \le i' < i$ such that the elements of $\pi'$ between $\pi_{k'}$ and $\pi_{j'}$ are smaller than all other elements of $\pi'$.

Let $k$ be the index of the element from $\pi$ which was reduced to $\pi_{k'}$. We claim that, in $\pi$, every element between $\pi_k$ and $\pi_j$ is smaller than all other elements of $\pi$. Suppose this is not the case, then there exist $x \in [k,j], y \not\in [k,j]$ with $\pi_x > \pi_y$. If $y > j$, then $\pi_y > \pi_{j_1}$ by Observation \ref{obvious}, and if $y < k$ then $\pi_y > \pi_{j_1}$ by the choice of $k_1$ (since $k \le k_1$). Once we have $\pi_y > \pi_{j_1}$, we get that $\pi_x > \pi_{j_1}$, and so $\pi'$ contains elements $\pi'_{y'}$ and $\pi'_{x'}$ corresponding to both $\pi_y$ and $\pi_x$ respectively with $\pi'_{x'} > \pi'_{y'}$. But, $x' \in [k',j']$ and $y \not\in [k',j']$ which contradicts the last sentence of the previous paragraph. Thus, the lemma holds.
\end{proof}

Lemma \ref{split_nice} suggests dividing a permutation $\pi$ with a 12 downfix into two pieces: $\pi_{\down}$ consisting of the elements with indices in $[k,j]$ and $\pi_{\up}$ consisting of all the others (reduced so that it is also a permutation). The following lemma establishes conditions on $\pi_{\down}$ and $\pi_{\up}$ that guarantee that $\pi$ will avoid 1423. 

\begin{lemma}\label{down_up}
Let $\pi_\down$ and $\pi_\up$ be defined as in the previous paragraph, and let $\pi_{\up'}$ be the reduced subpermutation of $\pi$ consisting of all the elements with indices not in $[k+1,j]$ (so $\pi_{\up'}$ has one more element than $\pi_\up$).  Then, $\pi$ avoids 1423 if and only if $\pi_\down$ and $\pi_{\up'}$ both avoid 1423.
\end{lemma}

\begin{proof}
The only if direction is easy; $\pi_\down$ and $\pi_\up$ are both subpermutations of $\pi$, and so if either contains 1423, $\pi$ does as well.

To show the if direction, suppose that $\pi$ contains 1423 and write this occurrence as $\pi_{i_1}\pi_{i_2}\pi_{i_3}\pi_{i_4}$. We claim that either $\pi_{i_1}\pi_{i_2}\pi_{i_3}\pi_{i_4} \in \pi_\down, \pi_{i_1}\pi_{i_2}\pi_{i_3}\pi_{i_4} \in \pi_\up$, or $\pi_{i_2}\pi_{i_3}\pi_{i_4} \in \pi_\up$ and $i_2 > k$. (Note that the element of $\pi_{\up'}$ corresponding to the $k$ in $\pi$ is the smallest element of $\pi_{\up'}$ and so can replace $\pi_{i_1}$ as the 1 in the 1423 occurrence.)

Suppose that $\pi_{i_1}\pi_{i_2}\pi_{i_3}\pi_{i_4} \not\in \pi_\down$ and $\pi_{i_1}\pi_{i_2}\pi_{i_3}\pi_{i_4} \not\in \pi_\up$, it follows that $\pi_{i_1} \in \pi_\down$ and $\pi_{i_2} \in \pi_\up$. Since $\pi_{i_1}\pi_{i_2}\pi_{i_3}\pi_{i_4}$ is an occurrence of 1423, we can conclude that $i_2, i_3, i_4 > j$, so $pi_{i_2}\pi_{i_3}\pi_{i_4} \in \pi_\up$, and, since $j > k$, ${i_2}> k$. Thus, $\pi_{\up'}$ contains 1423. 
\end{proof}

\section{Recurrences for 1423 Avoiders}

Combining Lemmas \ref{split_nice} and \ref{down_up} suggests we compute the number of permutations with a 12 downfix by finding the number of possible $\pi_\down$ and multiplying by the number of possible $\pi_\up$, which would give the (incorrect) recurrence
\begin{equation}\label{wrong}
|A(\{1423\},12,[i,j],n)| = \sum_{k=1}^{i} |A(\{1423\},1,[i-k+1], j-k)| \cdot |A(\{1423\},1,[k],n-j+k)|
\end{equation}
A few elements of this recurrence require explanation. The first term represents all possible $\pi_\down$; these are 1423-avoiding permutations with 12 downfixes where the 2 is the final element of the permutation. These permutations have $j-k+1$ elements, but since we know that the last element must be a 2, we can just ignore it and treat it as a length $j-k$ permutation. For the second term, we need to count all $\pi_\up$ which avoid 1423 even when they are turned into $\pi_{\up'}$, i.e. even when a 1 is inserted in the $k\tss{th}$ position. Even though the $\pi_\up$ only have length $n-j+k-1$, and no restrictions on where their first element can be, we actually count the permutations of length $n-j+k$ with a 1 in their $k\tss{th}$ position.

Unfortunately, Equation \ref{wrong} is incorrect because the right-hand side counts permutations once for every $k$ such that the permutation can be separated into $\pi_\down$ and $\pi_\up$ with $\pi_\down$ containing all the elements at most $j-k+1$ and $\pi_\up$ containing all other elements. This leads to a lot of double-counting!

To fix this, we will count permutations only once, corresponding to the maximal $k$ that allows them to be appropriately broken up. If we separate $\pi$ into $\pi_\down$ and $\pi_\up$ and find that $\pi_\down$ can be broken into two parts where the second part has at least $j-i+1$ elements and all elements in the first part are larger than all elements in the last part, that would imply that we could have taken just that second part as $\pi_\down$ and included the first part in $\pi_\up$. In this decomposition $\pi_\down$ starts later in the permutation, so $k$ is larger.

When a permutation can be broken up in this way we say it is decomposable. Precisely, we say that a suffix whose elements are all smaller than all the other elements of the permutation is a \textit{small suffix}, and a permutation with a proper small suffix of length $\ge p$ is $p$-\textit{decomposable}. Similarly, a permutation which is not $p$-decomposable is $p$-\textit{indecomposable}. This is definition is reminiscent of but not exactly the same as B\'ona's definition of decomposable in \cite{Bona}.

Now, we can define $A(\{1423\},12, [i,j], n, p)$ to be the subset of $A(\{1423\},12,[i,j],n)$ consisting of $p$-indecomposable permutations. Similarly, $A(\{1423\},1,[i],n,p)$ is the subset of $A(\{1423\},1,[i],n)$ consisting of $p$-indecomposable permutations.

This leads us to the final and correct system of recurrences.

\begin{thm}
The following system of recurrences holds:
\[|A(\{1423\},\es,[],n)| = \sum_{i=1}^n |A(\{1423\},1,[i],n,n)|\]
\begin{align*}
|A(\{1423\},1,[i],n,p)| & =  
\begin{cases} \ds\sum_{j=n-p}^{i-1} |A(\{1423\},1,[j],n-1,p)| &\text{ if } p \ge 2 \text{ or } (p=1, n \neq i)
\\
0 &\text{ otherwise }
\end{cases}
\\
&+ 
\begin{cases} \ds\sum_{j=1}^{n-p-1} |A(\{1423\},1,[j],n-1,n-j)|  &\text{ if } p \ge 2 \text{ or } (p=1, n \neq i)
\\
0 &\text{ otherwise }
\end{cases}
\\& + \sum_{j=i+1}^n |A(\{1423\},12,[i,j],n,p-1)| 
\end{align*}
\begin{align*} 
|A(\{1423\},12,[i,j],n,p)| &= \sum_{k=1}^{n-p-1} |A(\{1423\},1,[i-k+1],j-k,j-i-1)| 
\\ &\hspace{1cm} \cdot |A(\{1423\}, 1, [k], n-j+k, n-j+1)|
\\
& + \sum_{k=n-p}^i |A(\{1423\},1,[i-k+1],j-k,j-i-1)|
\\ & \hspace{1cm}\cdot |A(\{1423\}, 1, [k], n-j+k, p-j+k)|.
\end{align*}
\end{thm}
\begin{proof}
The first equation is almost identical to the Equation \ref{first_refine}. Note that $A(\{1423\},1,[i],n) = A(\{1423\},1,[i],n,n)$ because a length-$n$ permutation has no proper suffix of length $n$.

The second equation is closely related to Equation \ref{es-redu}. The first sum in Equation \ref{es-redu} is exactly the same as the final term in this new equation, except we have to ensure that the $p$-indecomposibility which the left-hand side requires is also respected by the left-hand side. The second sum in Equation \ref{es-redu} gives rise to the first two sums in this new equation. These two are indexed by the second downfix element being added to a permutation in $A(\{1423\},1,[i],n,p)$.  If $p=0$ or $p=1$ and $n = i$, then $|A(\{1423\},1,[i],n,p)| = 0$ since there is a (possibly empty) proper small suffix of every permutation in $A(\{1423\},1,[i],n)$. Otherwise, any such proper small suffix would have to include the new downfix element. Note that (just like in Equation \ref{es-redu}) we drop the old downfix element since it is ES-reducible.

Now, there are two cases based on how close to the end of the permutation the new downfix element occurs. If it occurs far away from the end of the permutation (specifically by element $n-p-1$) then any proper small suffix which is long enough to include this new element (i.e. has length $\ge n-j$) already has length $p$. On the other hand, any proper suffix which doesn't include this new element is not small. Therefore, permutations obey the left-hand side's $p$-indecomposibility condition if and only if they lack a proper small suffix of length $\ge n-j$. 

The other case is when $j$ is close to the end of the permutation (i.e. $\ge n-p$). Any small suffix which is long enough to cause a permutation counted by the left-hand side to be $p$-decomposable is already long enough to include $j$, and so we just need to check for proper suffixes of length $\ge p-1$ ($p$ is not necessary because we're ignoring the 1 in the downfix which, when added back in, would add one to the small suffix's length.)

We're now ready to consider the third equation. This equation is based on Equation \ref{wrong}. Recall that this equation describes breaking a permutation $\pi$ into $\pi_\down$ and $\pi_\up$ where $\pi_\down$ includes all the elements with indices between $k$ (the index of the right-hand side sum) and $j$, while $\pi_\up$ includes all other elements. To count all possible $\pi_\down$, we see that they are length $j-k$ permutations (we know that the last element of $\pi_\down$ is 2, and so we ignore it) avoiding 1423 where the 1 occurs in position $i-k+1$. As noted earlier, to ensure that $k$ is chosen maximally, we also insist that no $\pi_\down$ have a small suffix of length $\ge j-i-1$. 

To count all possible $\pi_\up$, though, we need two cases based on the value of $k$. If $k$ is small (i.e. $\le n-p-1$), then any small suffix long enough to reach the point where $\pi_\down$ starts (as any small suffix of length $\ge 1$ must) will give a small suffix of length $\ge p$. Therefore, we just need to ensure that $\pi_\up$ has no small suffix of length $n-j+1$. On the other hand, if $k$ is large, then merely reaching $\pi_\down$ is not enough to give a small suffix of length-$p$. To do so, $\pi_\up$ must have a small suffix long enough that it's length, when added to the length of $\pi_\down$, gives a small suffix of length $p$. So, we need to ensure that $\pi_\up$ has no small suffix of length $p-j+k$ to prevent this from happening. Once we have the number of possible $\pi_\down$ and $\pi_\up$ for each $k$, we multiply them and sum over all $k$ to find the number of possible $\pi$.
\end{proof}
With these recurrences in hand, we only need the initial conditions
\[|A(\{1423\},1,[i],1,p)| = \begin{cases} 1 & \text{ if } p > 0
\\
0 & \text{ if } p = 0
\end{cases}
\]
to have a fast algorithm to compute the number of length-$n$ permutations which avoid 1423 (and equivalently 1342).

\section{Maple Implementaion}
 An implementation of this recurrence is available on the author's website \href{https://sites.math.rutgers.edu/~yb165/1423Avoid.mpl}{here}. This package has three functions: \texttt{a(n)}, \texttt{b(i,n,p)}, and \texttt{c(i,j,n,p)} which calcuate $|A(\{1423\},\es,n)|, |A(\{1423\},1,[i],n,p)|,$ and $|A(\{1423\},12,[i,j],n,p)|$ respectively. Users can see all these functions by calling the \texttt{Help()} function or can call this function with either \texttt{a}, \texttt{b}, or \texttt{c} as an argument to see descriptions of these functions.
 
\chapter{A New Quantity Counted by OEIS Sequence A006012}\label{Callan}
In this section, we prove a conjecture of Callan in \cite{oeis} that OEIS sequence A006012 counts a certain kind of permutation. Call this sequence $(a_n)_{n=1}^\infty$; then $a_n$ is defined by $a_1=1$, $a_2=2$, and $a_n=4a_{n-1}-2a_{n-2}$ (the actual sequence in the OEIS is offset by one, so $a_0=1$, $a_1=2$, and the recursion is the same). The conjecture states that $a_n$ is equal to the number of permutations of length $n$ for which no subsequence $abcd$ has the following two properties: $b$ and $c$ occur consecutively and $\max\{a,c\} < \min\{b,d\}$. As noted in the introduction, this work was originally published in the \textit{Journal of Integer Sequences} \cite{my_jis}.

We can rewrite this conjecture in the language of pattern avoidance, in particular, using the dashed notation for vincular pattern avoidance introduced by Babson and Steingr\'imsson \cite{Babson}. They define a dashed pattern to be a permutation $\pi_1...\pi_k$, some of whose elements may be separated by dashes. A subsequence of a permutation is an occurrence of a pattern if (i) all the elements have the same relative order as the elements of the pattern, and (ii) if there is no dash between the $i\tss{th}$ and $i+1\tss{th}$ elements of the pattern, then the $i\tss{th}$ and $i+1\tss{th}$ element of the subsequence occur consecutively in the permutation. Just like in ordinary pattern avoidance, a permutation avoids a pattern if it does not contain any occurrence of the pattern, and a permutation avoids a set of patterns if it does not contain any occurrence of any of them. As in the previous section, $\Av(B)$ is the set of permutations avoiding all the patterns in a set $B$, and $\Av(B;n)$ is the set of length $n$ permutations in $\Av(B)$. The following two examples should help clarify these definitions.

\begin{eg} The permutation 251346 contains the subsequence 5146 which is an occurrence of the pattern 3-1-24 because the elements of the subsequence occur in the same relative order as 3124, and the 4 and 6 are consecutive in the original permutation (the 5 and 1 are also consecutive - that is allowed but not necessary). 
\end{eg}

\begin{eg} The permutation 251346 avoids 32-1-4 (i.e. $251346 \in \text{Av}(\{32\td1\td4\};6) \sse \text{Av}(\{32\td1\td4\})$). 
\end{eg}

We are now ready to rewrite the conjecture using this notation. To express it and the theorems in the next section concisely, we let $A= \{1\text{-}32{\text{-}}4,\allowbreak 1{\text{-}}42{\text{-}}3,\allowbreak 2{\text{-}}31{\text{-}}4,\allowbreak 2{\text{-}}41{\text{-}}3\}$ and $B=\{1{\text{-}}3{\text{-}}2{\text{-}}4,\allowbreak 1{\text{-}}4{\text{-}}2{\text{-}}3,\allowbreak 2{\text{-}}3{\text{-}}1{\text{-}}4,\allowbreak 2{\text{-}}4{\text{-}}1{\text{-}}3\}$.

\begin{prop}\label{conjecture} A subsequence of a permutation $abcd$ has the properties that $b$ and $c$ occur consecutively in the permutation and $\max\{a,c\} < \min\{b,d\}$ if and only if that subsequence is an occurrence of a pattern in $A$.
\end{prop}
\begin{proof}
Let $abcd$ be a subsequence with the two indicated properties. Suppose that $a<c$ and $b <d$. Because $\max\{a,c\} < \min\{b,d\}$, it follows that $a<c<b<d$, and so $abcd$ is an occurrence of $1\text{-}3\text{-}2\text{-}4$. Also, because $b$ and $c$ occur consecutively, we can remove the middle dash and say that $abcd$ is an occurrence of $1\text{-}32\text{-}4$. If $a>c$ or $b>d$, we can apply the same argument as long as we switch $1\text{-}32\text{-}4$ with another appropriately chosen member of $A$. 

Conversely, suppose that $abcd$ is an occurrence of a pattern in $A$. In every pattern in $A$, the first and third elements are 1 and 2, while the second and fourth are 3 and 4. Therefore, we have $\max\{a,c\} < \min\{b,d\}$. Further, since there is no dash between the second and third elements of any pattern in $A$, it must be that $b$ and $c$ occur consecutively.
\end{proof}
Using Proposition \ref{conjecture}, we rewrite the conjecture as
\begin{equation}\label{main}
a_n = |\Av(A;n)|.
\end{equation}

We will prove two theorems. The first is that Av$(A)$ and Av$(B)$ are the same set. In particular, this theorem establishes that $|\Av(A;n)|=|\Av(B;n)|$ for $n \ge 1$. The second theorem is that $a_n=|\Av(B;n)|$ for $n \ge 1$, so together these two theorems prove that Equation \ref{main} holds.

\begin{thm} The equality $\Av(A)=\Av(B)$ holds.
\end{thm}

\begin{proof}
It is immediately clear that any permutation containing an occurrence of an element of $A$ must contain an occurrence of an element of $B$, so we only need to show that the converse is also true. Let $\pi$ be a permutation. As established by Proposition \ref{conjecture}, subpermutation $\pi_a\pi_b\pi_c\pi_d$ of $\pi$ is an occurrence of a pattern in $A$ if and only if $c=b+1$ and $\max\{\pi_a,\pi_c\} < \min\{\pi_b,\pi_d\}$. Similarly, a subpermutation $\pi_a\pi_b\pi_c\pi_d$ of $\pi$ is an occurrence of a pattern in $B$ if and only if $\max\{\pi_a,\pi_c\} < \min\{\pi_b,\pi_d\}$.

Choose any element of $B$, and suppose that $\pi$ contains an occurrence of this element. Find $a <b<c<d$ such that $\max\{\pi_a,\pi_c\} < \min\{\pi_b, \pi_d\}$. Let $e$ be the largest index less than $c$ such that $\pi_e > \max\{\pi_a, \pi_c\}$, i.e., $e= \max\{i : i <c, \pi_i > \max\{\pi_a, \pi_c\}\}$. Because $b$ is an element of $\{i : i <c, \pi_i > \max\{\pi_a, \pi_c\}\}$, it follows that $e$ exists and $a < b \le e < e+1\le c< d$. Now, we claim that $\pi_a\pi_e\pi_{e+1}\pi_d$ is an occurrence of a pattern in $A$. Obviously, $e +1 =e+1$, and so it remains to check that $\max\{\pi_a,\pi_{e+1}\} < \min\{\pi_e, \pi_d\}$. Because $\max\{\pi_a,\pi_c\} < \min\{\pi_b, \pi_d\}$, we conclude that $\pi_a < \pi_d$, and by the choice of $e$, we also have $\pi_a < \pi_e$. Now, either $e+1 = c$, in which case $\pi_{e+1}=\pi_c$, or else $\pi_{e+1} < \max\{\pi_a, \pi_c\}$ because otherwise we would have chosen $e+1$ as the $\max\{i : i <c, \pi_i > \max\{\pi_a, \pi_c\}\}$ instead of $e$. It follows that $\pi_{e+1} \le \max\{\pi_a,\pi_c\} < \pi_d, \pi_e$ for the same reasons as $\pi_a$. Therefore, $\max\{\pi_a,\pi_{e+1}\} < \min\{\pi_e, \pi_d\}$ and $\pi_a\pi_e\pi_{e+1}\pi_d$ is an occurrence of a pattern in $A$. We conclude that the permutations avoiding the patterns of $A$ are the same as the permutations avoiding the patterns of $B$.
\end{proof}

Armed with this theorem, we now need only show that $\big(|\Av(B;n)|\big)_{n \ge 1}$ satisfies the same recurrence as $(a_n)_{n \ge 1}$. Our strategy will be as follows: given $\Av(B;n-1)$, define four maps which, when all of them are applied to all the permutations of $\Av(B;n-1)$, will generate all of the permutations of $\Av(B;n)$. Then we will count how many permutations of $\Av(B;n)$ are double-counted in this way, and find that there are two for every element of $\Av(B;n-2)$, thereby establishing the recurrence.

Note that, for a permutation to avoid all the patterns of $A$, it must be the case that either 1 and 2 occur consecutively (not necessarily in that order) or either 1 or 2 is the last element of the permutation. This observation motivates the following definitions of the four maps $f_\text{before}, f_\text{after}, f_\text{end}$, and $f_\text{bump}$. Let $f_\text{before}$ be the function that inputs a permutation and outputs that permutation with all elements increased by 1 and a 1 inserted immediately before the new 2. Let $f_\text{after}$ be the function that also inputs a permutation and outputs that permutation with all the elements increased by 1 and a 1 inserted immediately after the new 2. Similarly, let $f_\text{end}$ be the function that inputs a permutation, increases all its elements by 1 and puts a 1 at the end of it, and let $f_\text{bump}$ be the function that inputs a permutation, increases all its elements by 1, replaces the new 2 with a 1 and puts a 2 at the end. The following example gives a concrete illustration of the four functions.

\begin{eg} Let $\pi= 31542$. Then $f_\text{before}(\pi) = 412653, \allowbreak f_\text{after}(\pi) = 421653, \allowbreak f_\text{end}(\pi) = 426531, \allowbreak \text{ and } f_\text{bump}(\pi) = 416532$. Note that $\pi \in \Av(B)$, and so are all its images.
\end{eg}

Suppose $n \ge 2$. The following two lemmas will together establish that

\begin{align}\label{lemmas}\small
\begin{split}
&f_\text{before}(\Av(B;n-1)) \cup f_\text{after}(\Av(B;n-1)) \cup f_\text{end}(\Av(B;n-1)) \cup f_\text{bump}(\Av(B;n-1)) 
\\
&= \Av(B;n).
\end{split}
\end{align}

\begin{lemma}
The functions $f_\text{before}, f_\text{after}, f_\text{end}$, and $f_\text{bump}$ all map elements of $\Av(B;n-1)$ to elements of $\Av(B;n)$.
\end{lemma}
\begin{proof}
Choose some $\sigma \in \Av(B;n-1)$, and consider each function in turn. If $f_\text{before}(\sigma)$ or $f_\text{after}(\sigma)$ contains an occurrence $\tau$ of a pattern in $B$, then this occurrence must use the element 1 or else $\tau$ would already be an offending pattern in $\sigma$. But then replacing 1 by 2 would again give an offending pattern in $\sigma$. Thus, no such occurrence is possible in either $f_\text{before}(\sigma)$ or $f_\text{after}(\sigma)$. In addition, if $f_\text{end}(\sigma)$ or $f_\text{bump}(\sigma)$ contains an occurrence of a pattern in $B$, then this occurrence cannot use the last element because that element is either a 1 or a 2, and patterns in $B$ only end with $3$ or $4$. So, this occurrence would already be an occurrence of the pattern in $\sigma$, and therefore cannot exist.
\end{proof}

\begin{lemma}
Every permutation in $\Av(B;n)$ is the image of a permutation in $\Av(B;n-1)$ under at least one of the functions $f_\text{before}, f_\text{after}, f_\text{end}$, or $f_\text{bump}$.
\end{lemma}
\begin{proof}
Choose some $\pi \in \Av(B;n)$. As previously noted, either 1 and 2 occur consecutively in $\pi$, or else either 1 or 2 is the final element of $\pi$. Let $\pi'$ be $\pi$ with the 1 removed and each element decreased by 1. We have introduced no new patterns, and so $\pi' \in \Av(B;n-1)$. Suppose that 1 occurs immediately before 2 in $\pi$, then $f_\text{before}(\pi') =\pi$. If the 1 occurs immediately after 2 in $\pi$, then $f_\text{after}(\pi')= \pi$. If the 1 occurs at the end of $\pi$, then $f_\text{end}(\pi')=\pi$. If the 2 occurs at the end of $\pi$, then we need to define $\pi''$, which is $\pi$ with the 1 removed, the 2 moved the position where the 1 used to be, and each element decreased by 1. Again, we have introduced no new patterns, and so $\pi'' \in \Av(B;n-1)$, and $f_\text{bump}(\pi'')=\pi$.
\end{proof}

Now that we have established Equation \ref{lemmas}, we can prove the main result.

\begin{thm}
The sequence $\big(|\Av(B;n)|\big)_{n \ge 1}$ satisfies the same recurrence as $(a_n)_{n \ge 1}$.
\end{thm}
\begin{proof} Since $\Av_{1}(B) = \{1\}$ and $\Av_{2}(B) = \{12, 21\}$, the initial conditions hold. If the four functions $f_\text{before}, f_\text{after}, f_\text{end}$, and $f_\text{bump}$ all had disjoint ranges, we could conclude from Equation \ref{lemmas} that $|\Av(B;n)|= 4\cdot |\Av(B;n-1)|$. Unfortunately, some permutations are counted in the range of multiple functions. Each $f$ outputs a certain kind of permutation: $f_\text{before}$ outputs permutations where 1 immediately precedes 2, $f_\text{after}$ outputs permutations where 2 immediately precedes 1, $f_\text{end}$ outputs permutations where 1 occurs at the end, and $f_\text{bump}$ outputs permutations where 2 occurs at the end. A permutation in $\Av(B;n)$ that fulfills two of these criteria will be hit twice, hence double-counted. Such permutations must be counted once by either $f_\text{before}$ or $f_\text{after}$ and again by either $f_\text{end}$ or $f_\text{bump}$ because no permutation can be hit by both $f_\text{before}$ and $f_\text{after}$ or both $f_\text{end}$ and $f_\text{bump}$. Thus, the final two elements of such permutations are 1 and 2 (not necessarily in that order). Let $g : \Av(B;n) \rightarrow \Av(B;n-2)  $ be defined as the function that takes a permutation, removes from it the elements 1 and 2, and reduces all other elements by 2. If we restrict $g$ to those permutations that end in either 12 or 21, $g$ becomes a 2-to-1 map from the double-counted permutations of $\Av(B;n)$ to the permutations of $\Av(B;n-2)$, and so the number of double-counted permutations is twice $|\Av(B;n-2)|$. It follows that $|\Av(B;n)|=4\cdot |\Av(B;n-1)|-2\cdot |\Av(B;n-2)|$ for $n \ge 3$. 
\end{proof}

\chapter{A Generalization of the ``Raboter" Operation}\label{raboter}
In a 2018 talk at Rutgers' Experimental Math Seminar, Neil Sloane described Claude Lenormand's ``raboter" operation for the base two representation of a number \cite{sloane_talk}. From this representation, one reduces by one the length of each run of consecutive 1s and 0s. Denote this operation by $r(n)$; so, for example, $r(12) = 2$ because 12 is represented in binary as 1100, and reducing the length of each run by one yields 10. 

Sloane also defined $L(k)=\sum_{n=2^k}^{2^{k+1}-1}r(n)$ and conjectured that $L(k) = 2\cdot 3^{k-1} - 2^{k-1}$, a fact which was quickly proven by Doron Zeilberger \cite{drz_raboter} and Chai Wah Wu \cite{oeis}.

In Section \ref{bases}, we generalize this theorem to bases other than 2. Let $r(b,n)$ be the the number whose base-$b$ representation is generated by taking the base-$b$ representation of $n$ and shortening each run of consecutive identical elements by one. Further, let $L(b,n) = \sum_{n=b^k}^{b^{k+1}-1} r(b,n)$. We will prove that 
\[L(b,k) = \frac{b(b-1)}{2b-1} (2b-1)^k - \frac{b-1}{2} b^k.\]

In Section \ref{powers}, we raise $r(b,n)$ to various powers. Define $L(p,b,k) = \sum_{n=b^k}^{b^{k+1}-1} r(b,n)^p$; we develop an algorithm in Maple to rigorously compute $L(p,b,k)$ as an expression in terms of $k$ for any fixed $p,b$. In addition, for any fixed $p$, we can conjecture an expression for $L(p,b,k)$ in terms of $b$ and $k$.

\section{More General Bases}\label{bases}
Following the example of Zeilberger, we find a recurrence satisfied by $L(b,k)$ and then find a closed form expression satisfying the same recurrence.
\begin{thm} $\ds L(b,k) = (2b-1)\cdot L(b,k-1) + b^{k-1}\frac{(b-1)^2}{2} $ for $k \ge 2$.
\end{thm}
\begin{proof} 
The $b^{k+1} - b^{k} = b^{k}(b-1)$ numbers which contribute to $L(b,k)$ are exactly those numbers whose base-$b$ representations use $k+1$ digits, so each can be written as $Ab_1b_2$ where $A \in \{1,\dots,b-1\} \times \{0,\dots,b-1\}^{k-2}$ and $b_1, b_2 \in \{0,\dots,b-1\}$. If $b_1 \neq b_2$, then $b_2$ is a run of just one element, so the raboter operation eliminates it and $r(b,Ab_1b_2) = r(b,Ab_1)$. Numbers with representations $Ab_1$ are exactly those which were counted in the calculation of $L(b,k-1)$, and each is counted $b-1$ times here, once for each $b_2 \neq b_1$. 

If $b_2 = b_1$, then the base-$b$ representation of $r(b,Ab_1b_2)$ is the representation of $r(b,Ab_1)$ with $b_2$ appended to the end, and so $r(b,Ab_1b_2) = b\cdot r(b,Ab_1) + b_2$. Thus,
\begin{align*}
L(b,k) &= \sum_A\Big( \sum_{b_1} r(b,Ab_1b_1) + \sum_{b_2 \neq b_1} r(b,Ab_1b_2)\Big)
\\
&= \sum_A \Big(\sum_{b_1} \big(b\cdot r(b,Ab_1) +b_1\big) + \sum_{b_2 \neq b_1} r(b,Ab_1)\Big)
\\
&= \sum_A \sum_{b_1} (2b-1)r(b,Ab_1) + \sum_A \sum_{b_1} b_1
\\
&= (2b-1)L(b,k-1) + (b-1)b^{k-2}\frac{b(b-1)}{2}
\\
&= (2b-1)L(b,k-1) + b^{k-1}\frac{(b-1)^2}{2}.
\end{align*}
\end{proof}
Together with initial condition $L(b,1) = \frac{b(b-1)}{2}$, this determines the sequence $(L(b,k))_{k=1}^\infty$. Finding an explicit formula for $L(b,k)$ is now just a matter of finding a formula which obeys this same recurrence. 
\begin{cor}$ L(b,k) = \frac{b(b-1)}{2b-1} (2b-1)^k - \frac{b-1}{2} b^k$.
\end{cor}
\begin{proof}
With some help from Doron Zeilberger's Maple package Cfinite, we conjecture that the formula for $L(b,k)$ has the form $\a_1 (2b-1)^k + \a_2 b^k$, so we solve the system of equations 
\begin{align*}
&\a_1(2b-1) + \a_2 b =  \frac{b(b-1)}{2}
\\
&\a_1(2b-1)^2 +\a_2 b^2 = (2b-1) \frac{b(b-1)}{2} +b\frac{(b-1)^2}{2}
\end{align*}
for $\a_1,\a_2$ and find $\a_1 = \frac{b(b-1)}{2b-1}$ and $\a_2 = -\frac{b}{2} + \frac{1}{2}$.
Let $L'(b,k) = \ds \frac{b(b-1)}{2b-1} (2b-1)^k - \frac{b-1}{2} b^k$. Proving that $L(b,k) = L'(b,k)$ is simply a matter of verifying that $L'(b,1) =  \frac{b(b-1)}{2}$ and $\ds L'(b,k) =(2b-1)\cdot L'(b,k-1) + b^{k-1}\frac{(b-1)^2}{2} $ for $k \ge 2$, which can easily be done using Maple or any other computer algebra system.
\end{proof}

\section{Higher Moments}\label{powers}
With a formula for $L(b,k)$ found, we consider the following additional generalization:
\[L(p,b,k) = \sum_{n=2^k}^{2^{k+1}-1} r(b,n)^p;\]
that is the sum of $r(b,n)^p$ taken over all numbers $n$ whose base-$b$ representation has $k+1$-digits. 
The trick in this case is to work inductively beginning with the (solved) $p=1$ case, and along the way compute $L(l,p,b,k)$ which we define to be the sum of $r(b,n)^p$ taken over all numbers $n$ whose base-$b$ representation has $k+1$-digits, the last of which is $l$.

In order to compute $L(l,p,b,k)$, we use the following recurrence:
\begin{thm}
$L(l,p,b,k) = (b^p-1)\cdot L(l,p,b,k-1)+ L(p,b,k-1) + \sum_{i=1}^p l^i b^{p-i} \binom{p}{i} L(l,p-i,b,k-1).$
\end{thm}
\begin{proof} The numbers with length-$(k+1)$ base-$b$ representations ending in $l$ are exactly those which can be written as $Ab_1b_2$ with $A\in \{1,\dots,b-1\} \times \{0,\dots,b-1\}^{k-2}, b_1 \in \{0,\dots,b-1\},$ and $b_2 = l$. Therefore,
\begin{align*} L(l,p,b,k) &= \sum_A \Big(\sum_{b_1 \neq l} r(b,Ab_1 l)^p + r(b,All)^p\Big)\\
&= \sum_A \Big(\sum_{b_1 \neq l} r(b,Ab_1)^p + (b\cdot r(b,Al)+l)^p\Big)\\
&= L(p,b,k-1) - L(l,p,b,k-1) + \sum_A \sum_{i=0}^p \binom{p}{i} b^{p-i} r(b,Al)^{p-i} l^{i} \\
&= L(p,b,k-1) - L(l,p,b,k-1) + b^pL(l,p,b,k-1) \\
&\hspace{1cm}+ \sum_{i=1}^p \binom{p}{i} b^{p-i} L(l,p-i,b,k-1)^{p-i} l^{i}\\
&= (b^p-1)\cdot L(l,p,b,k-1)+ L(p,b,k-1) + \sum_{i=1}^p l^i b^{p-i} \binom{p}{i} L(l,p-i,b,k-1).
\end{align*}
\end{proof}
We find a similar recurrence for $L(p,b,k)$.
\begin{thm}
$L(p,b,k) = (b^p+b-1)L(p,b,k-1) + \sum_{l=0}^{b-1} \sum_{i=1}^p b^{p-i} l^i \binom{p}{i}L(l,p-i,b,k-1)$.
\end{thm}
\begin{proof}
Again, note that the numbers counted by $L(p,b,k)$ are those which can be written as $Ab_1b_2$ with $A\in \{1,\dots,b-1\} \times \{0,\dots,b-1\}^{k-2},$ and $b_1,b_2 \in \{0,\dots,b-1\}.$ Therefore, the following equations hold:
\begin{align*} 
L(p,b,k) &= \sum_A \Big(\sum_{b_1 \neq b_2} r(b,Ab_1b_2)^p + \sum_{b_1} r(b,Ab_1b_1)^p\Big) \\
&=\sum_A (b-1)\sum_{b_1} r(b,Ab_1)^p + \sum_A\sum_{b_1} (br(Ab_1)+b_1)^p\\
&=(b-1)L(p,b,k-1) + \sum_A\sum_{b_1}\sum_{i=0}^p \binom{p}{i} b^{p-i}r(Ab_1)^{p-i} b_1^i \\
&= (b-1)L(p,b,k-1) + \sum_A\sum_{b_1} b^{p}r(Ab_1)^{p} + \sum_{b_1}\sum_{i=1}^p \sum_A \binom{p}{i} b^{p-i}r(Ab_1)^{p-i} b_1^i\\
&=(b^p + b-1)L(p,b,k-1) + \sum_{b_1}\sum_{i=1}^p b_1^i b^{p-i}\binom{p}{i} L(b_1,p-i,b,k-1).
\end{align*}
Change the name of $b_1$ to $l$ to maintain consistent notation, and we have derived the claimed equation.
\end{proof}
\section{Maple Implementation}
The Maple package \texttt{raboter.txt} available \href{http://sites.math.rutgers.edu/~yb165/raboter.txt}{here} contains functions to implement this recurrence. The most important are \texttt{SumPowers(b,k,p)} which finds an expression in terms of $k$ for $L(p,b,k)$ (for fixed $b$ and $p$) and \texttt{GuessGeneralForm(b,n,p)} which conjectures an expression in terms of $k$ and $b$ for $L(p,b,k)$ (for fixed $p$).

For example, this package proves that
\[L(2,2,k) = \frac{2}{3}5^k - \frac{1}{6}2^k-\frac{2}{3}3^k\]
and conjectures that
\begin{align*}L(2,b,k) &= \Big(\frac{1}{6}b^2-\frac{1}{6}b-\frac{1}{3}\Big)(b-1)^k+\Big(-\frac{1}{6}b^2+\frac{1}{3}b -\frac{1}{6}\Big) b^k 
\\
&- \frac{b(b-1)}{2b-1} (2b-1)^k + \frac{2b^3+3b^2-3b-2}{6(b^2+b-1)} (b^2+b-1)^k.
\end{align*}


\bibliography{Thesis_Bib}
\bibliographystyle{abbrv}


\end{document}