\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{claim}[theorem]{Claim} \newtheorem*{theorem*}{Theorem} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Counting the Nontrivial Equivalence Classes\\ \vskip .1in of $S_n$ Under $\{1234,3412\}$-Pattern-Replacement } \vskip 1cm \large Quinn Perian\\ Stanford Online High School\\ Academy Hall Floor 2 8853\\ 415 Broadway\\ Redwood City, CA 94063\\ USA\\ \href{mailto:quinn.perian@outlook.com}{\tt quinn.perian@outlook.com}\\ \ \\ Bella Xu\\ William P. Clements High School\\ 4200 Elkins Drive\\ Sugar Land, TX 77479\\ USA\\ \href{mailto:bxu107@gmail.com}{\tt bxu107@gmail.com}\\ \ \\ Alexander Lu Zhang\\ Lower Merion High School\\ 315 E Montgomery Ave\\ Ardmore, PA 19003\\ USA\\ \href{mailto:azhang896@gmail.com}{\tt azhang896@gmail.com} \end{center} \vskip .2 in \begin{abstract} We study the $\{1234, 3412\}$-pattern-replacement equivalence relation on the set $S_n$ of permutations of length $n$, which is conceptually similar to the Knuth relation. In particular, we enumerate and characterize the nontrivial equivalence classes, or equivalence classes with size greater than 1, in $S_n$ for $n \geq 7$ under the $\{1234, 3412\}$-equivalence. This proves a conjecture by Ma, who found three equivalence relations of interest in studying the number of nontrivial equivalence classes of $S_n$ under pattern-replacement equivalence relations with patterns of length $4$, enumerated the nontrivial classes under two of these relations, and left the aforementioned conjecture regarding enumeration under the third as an open problem. \end{abstract} \section{Introduction} A permutation $\pi \in S_n$ is said to \emph{contain a pattern} $\sigma \in S_c$, $c \le n$, if there is a $c$-letter subsequence $\pi_{i_1}, \pi_{i_2}, \ldots, \pi_{i_c}$ of $\pi$ that is \emph{order-isomorphic} with $\sigma$ (i.e., for indices $j, k \in [c]$, $\pi_{i_j} < \pi_{i_k}$ if and only if $\sigma_j < \sigma_k$). In the past thirty years, the topic of permutation patterns has risen to the forefront of combinatorics (see Kitaev~\cite{kitaev2011patterns} for a survey) and has even spawned its own annual conference~\cite{conf}. The focus of this paper is \emph{permutation pattern-replacement equivalences}. Given a set of patterns $P \subseteq S_c$ and a permutation $\pi \in S_n$, one can perform a \emph{$P$-pattern-replacement} on $\pi$ by taking a subsequence $\pi_{i_1}, \ldots, \pi_{i_c}$ of $\pi$ that forms a pattern $\sigma \in P$ and rearranging the relative order of the letters $\pi_{i_1}, \ldots, \pi_{i_c}$ so that they form a different pattern in $P$. We say that two permutations $\alpha, \beta \in S_n$ are \emph{$P$-replacement equivalent} if $\alpha$ can be reached from $\beta$ by a series of $P$-pattern-replacements. This defines an equivalence relation on $S_n$, which is known as the $P$-replacement equivalence~\cite{kuszmaul2013counting, kuszmaulzhou20, S12, LPRW, PRW, Kn, NS, ma, fazel2014equivalence}. The study of permutation pattern-replacement equivalences is closely related to the study of permutation pattern avoidance~\cite{kitaev2011patterns,SS,claesson2001generalized, lewis2011pattern, marcus2004excluded, albert2006stanley, bona2007new, bona2005limit}, which seeks to count the number of singleton equivalence classes (i.e., the number of permutations containing no patterns in $P$). The dual problem of counting the number of non-singleton (i.e., \emph{nontrivial}) equivalence classes has recently received a large amount of attention in the literature~\cite{kuszmaul2013counting, kuszmaulzhou20, S12, LPRW, PRW, Kn, NS, ma, fazel2014equivalence}. Other variations of pattern-replacement equivalence, beyond the variant defined above that we study in this paper, have also been investigated in the past. For instance, pattern-replacement equivalences where the letters forming a pattern are required to be consecutive in value, adjacent in the permutation, or both have been examined in previous papers~\cite{ma, kuszmaulzhou20}. Other variants include equivalence relations in which there exist multiple disjoint sets of patterns, such that a pattern in any set can be rearranged to form other patterns in the same set~\cite{kuszmaul2018fast,kuszmaulzhou20}. Most of the research so far on permutation pattern-replacement equivalences has worked to systematically understand the equivalence classes for all pattern-replacement equivalence relations involving patterns of length three~\cite{kuszmaul2013counting, kuszmaulzhou20, S12, LPRW, PRW, Kn, NS}. Many interesting number sequences have arisen (e.g., the Catalan numbers, Motzkin numbers, tribonacci numbers, central binomial coefficients, and many more complicated number sequences). Recently, Ma~\cite{ma} initiated the systematic study of pattern-replacement equivalences with patterns of length four. Because the number of pattern-replacement sets $P \subseteq S_4$ is very large, Ma took a computational approach to identify which of the pattern-replacement sets were most interesting to study. In particular, Ma computed the number of nontrivial equivalence classes under $P$-equivalence for all sets $P \in S_4^2$ and then matched the resulting number sequences with the \textit{On-Line Encyclopedia of Integer Sequences} (OEIS)~\cite{sloane2003online} in order to identify pattern-replacement sets $P$ for which the number of nontrivial equivalence classes is described by a natural formula. Ma identified three formulae of particular interest and was able to enumerate the nontrivial equivalence classes for the equivalence relations corresponding to two of them. Enumerating the equivalence classes for the third equivalence relation, namely the $\{1234, 3412\}$-equivalence, has remained an open question. In this paper, we resolve the aforementioned open problem by proving the following theorem: \begin{theorem}[Conjectured by Ma~\cite{ma}] For $n \geq 7$, the number of nontrivial equivalence classes of $S_n$ under the $\{1234,3412\}$-equivalence is $\frac{n^3+6n^2-55n+54}{6}$ (given by sequence \seqnum{A330395}). \label{thm:nontrivial} \end{theorem} Recall that we define two permutations $\alpha, \beta \in S_n$ to be equivalent under the $\{1234, 3412\}$-equivalence if $\alpha$ can be reached from $\beta$ by performing a series of $1234 \rightarrow 3412$ and $3412 \rightarrow 1234$ pattern-replacements. A $1234 \rightarrow 3412$ pattern-replacement in a permutation $\pi$ simply takes an increasing 4-letter subsequence $\pi_{i_1}, \pi_{i_2}, \pi_{i_3}, \pi_{i_3}$ (where $i_1 < i_2 < i_3 < i_4$), and places each of $\pi_{i_3}, \pi_{i_4}, \pi_{i_1}, \pi_{i_2}$ in positions $i_1, i_2, i_3, i_4$ of the permutation. For example, in the permutation $\pi = 7162435$, the subsequence $1, 2, 3, 5$ forms a $1234$ pattern, and we can perform a $1234 \rightarrow 3412$ pattern replacement to obtain the new permutation $\pi' = 7365412$. Similarly, a $3412 \rightarrow 1234$ pattern-replacement takes any four-letter subsequence that forms a $3412$ pattern, and rearranges the letters in that subsequence to instead be in increasing order, thereby forming a $1234$ pattern. Theorem~\ref{thm:nontrivial} counts the number of \emph{nontrivial} equivalence classes in $S_n$ under the $\{1234, 3412\}$-equivalence. These are the equivalence classes of size greater than one, or alternatively, the equivalence classes consisting of non-$\{1234, 3412\}$-avoiding permutations. In the remainder of the paper, we prove Theorem~\ref{thm:nontrivial}. \subsection{Formal definitions} \begin{definition}[Standardization of a permutation] Given a word $\rho$ of length $n$ consisting of $n$ distinct letters in $\mathbb{N}$, the \textit{standardization} of $\rho$ is the permutation in $S_n$ obtained by replacing the $i$th smallest letter in $\rho$ with $i$ for each $i \in \{1, 2, \ldots, n\}$. \end{definition} \begin{definition}[Sub-standardization of a permutation] Given a permutation $\pi \in S_n$, and a subword $\rho$ of $\pi$, the standardization of $\rho$ is known as a \textit{sub-standardization} of $\pi$. If removing the letter $a$ from $\pi$ gives $\rho$, then the standardization of $\rho$ is also called the sub-standardization of $\pi$ formed by removing $a$, denoted by $\pi_{-(a)}$. In general, the standardization of the permutation formed by removing distinct letters $a_1, a_1, \ldots, a_n$ from $\pi$ is denoted by $\pi_{-(a_1, \ldots, a_n)}$. \end{definition} \begin{definition}[Pattern formation] Given a pattern $p \in S_c$ and a permutation $\pi \in S_n$, we say that $\pi$ contains pattern $p$ if $p$ is a sub-standardization of $\pi$. If a subword $\rho$ of $\pi$ has standardization $p$, then we say that $\rho$ \textit{forms} pattern $p$. \end{definition} \begin{definition}[Pattern-replacement] Given two patterns $p, q \in S_c$ and a permutation $\pi \in S_n$, a $p \rightarrow q$ \textit{pattern-replacement} can be performed by taking any subword $\rho$ of $\pi$ that forms pattern $p$, and rearranging the letters in $\rho$ to instead form pattern $q$. \end{definition} \begin{definition}[Pattern-replacement equivalences] Given a set of patterns $P \subseteq S_c$, we say that two permutations $p, q \in S_n$ are \textit{equivalent} under $P$-equivalence if $p$ can be reached from $q$ by a sequence of pattern-replacements using patterns in $P$. Maximal collections of $P$-equivalent permutations are known as \textit{equivalence classes}, and an equivalence class is said to be \textit{nontrivial} if it contains more than one permutation. \end{definition} \subsection{Paper outline} To prove Theorem \ref{thm:nontrivial}, we use three lemmas in order to characterize the equivalence classes under the $\{1234, 3412\}$-equivalence. To begin, we use the principle of inclusion-exclusion to establish a recurrence relation that allows us to express the equivalence classes in $S_n$ in terms of the equivalence classes in $S_{n - 1}$ and $S_{n-2}$ (Section~\ref{sec:recursion}). This reduces the proof of Theorem~\ref{thm:nontrivial} to proving that the number of equivalence classes of a certain form is $n + 1$. We then characterize $n - 1$ of these classes that have a natural combinatorial structure, consisting of all permutations one transposition away from one of $n-1$ different representative permutations (Section~\ref{sec:small}). Finally, we show that the remaining permutations fall into exactly two classes depending on the parity of the number of inversions they contain (Section~\ref{sec:parity}); here, we use a proof structure that exploits the \emph{stooge-sort technique} of Kuszmaul \cite{kuszmaul2013counting}. The authors have checked, by computer, the veracity of each of these intermediate steps for the first few values of $n$. Combining these steps, we prove Theorem~\ref{thm:nontrivial}. \section{Reducing to permutations neither beginning with \texorpdfstring{$n$}{} nor ending with 1}\label{sec:recursion} In this section, we reduce the proof of Theorem~\ref{thm:nontrivial} to counting the number of nontrivial equivalence classes that contain no permutations with $n$ in the first position or $1$ in the last position. \begin{lemma}\label{lem:reduce with recursion} Theorem~\ref{thm:nontrivial} can be reduced to proving that there are exactly $n+1$ nontrivial equivalence classes of $S_n$ where no permutation begins with $n$ or ends with $1$. \end{lemma} \begin{proof} Let $A_n$ be the total number of nontrivial equivalence classes of $S_n$ under the $\{1234,3412\}$-equivalence. Let $B_n$ be the number of nontrivial equivalence classes of $S_n$ under the $\{1234,3412\}$-equivalence that do not contain any permutation beginning with $n$ or ending with $1$. Then we have the following recurrence relation. \begin{claim} For $n \ge 3$, \begin{equation}\label{eq:1} A_n - B_n = 2A_{n-1}-A_{n-2}. \end{equation} \label{clm:recurrence} \end{claim} \begin{proof} Since the largest element is never first and the smallest element is never last in the patterns $1234$ and $3412$, no pattern-replacements under the $\{1234,3412\}$-equivalence can move a leading $n$ or an ending $1$. Therefore, appending $n$ to the front (resp., $1$ to the end) of all permutations of an equivalence class in $S_{n - 1}$ results in an equivalence class in $S_n$. Call this the \emph{lifting observation}. We can count the number of equivalence classes where all permutations have either $n$ in the first position or $1$ in the last position (or both) in two different ways. The left side of \eqref{eq:1} represents this number with complementary counting, where all equivalence classes not satisfying the requisite are subtracted from the total number of equivalences classes. On the right side of \eqref{eq:1}, we count the same number of equivalence classes using the principle of inclusion-exclusion. By the lifting observation, we can append an $n$ to the front of all permutations in $S_{n-1}$ or append a $1$ to the back of all permutations in $S_{n-1}$ to form all possible equivalence classes where all permutations have either $n$ in the first position or $1$ in the last position (or both). (This contributes $2A_{n - 1}$ to \eqref{eq:1}.) The repeats, which are formed by appending both an $n$ to the front and a $1$ to the back of all permutations in $S_{n-2}$, are then subtracted off. (This removes $A_{n - 2}$.) Since the two sides of \eqref{eq:1} count the same quantity, we must have equality. \end{proof} Using the recursion given in the preceding claim, we now analyze the value that $B_n$ must take in order for $A_n$ to satisfy the formula stated in Theorem~\ref{thm:nontrivial}. \begin{claim} Showing that $B_n = n+1$ suffices to prove that $A_n = \frac{n^3+6n^2-55n+54}{6}$ for all $n \ge 7$. \end{claim} \begin{proof} Suppose $B_n = n + 1$ for all $n \ge 7$. We use this to prove that $A_n = \frac{n^3+6n^2-55n+54}{6}$ for all $n \ge 7$. The base cases of $n=7,8$ for $A_n = \frac{n^3+6n^2-55n+54}{6}$ have been checked by computer~\cite{ma}. Assume by induction that our formula for $A_n$ holds for $n = k-1$ and $n = k-2$ for some integer $k \ge 9$. Then by Claim~\ref{clm:recurrence}, \begin{align*} A_k &= B_k + 2A_{k-1} - A_{k-2} \\ &= k+1 + 2\cdot\frac{(k-1)^3+6(k-1)^2-55(k-1)+54}{6} \\ & \phantom{foobargoobar} - \frac{(k-2)^3+6(k-2)^2-55(k-2)+54}{6} \\ &= k+1 + 2\cdot\frac{k^3+3k^2-64k+114}{6} - \frac{k^3-67k+180}{6} \\ &= \frac{k^3+6k^2-55k+54}{6}, \end{align*} which is our formula for $A_k$. By induction, $A_n = \frac{n^3+6n^2-55n+54}{6}$ holds for all $n \ge 7$. \end{proof} This completes the proof of the lemma. \end{proof} \section{Characterizing the \texorpdfstring{$n-1$}{} small classes}\label{sec:small} In this section, we characterize $n-1$ of the nontrivial equivalence classes of $S_n$ that contain no permutation beginning with $n$ or ending with $1$. Each of these classes is associated with a ``leader permutation'' that is one transposition away from each permutation in the class. Below we define the notion of a leader permutation and what we mean when we call two permutations ``adjacent.'' The equivalence classes then correspond to the sets of permutations that are adjacent to each leader permutation. \begin{definition}[Leader permutation] Define a \textit{leader permutation} of length $n$ to be a permutation of the form $a_1a_2 \cdots a_n$ such that for some integer $k \in [2,n]$, $a_i = k-i$ for all $1\leq i < k$ and $a_{i} = n+k-i$ for all $k \leq i \leq n$. \end{definition} Two equivalent definitions are that a permutation is a leader permutation if it is the plus-composition of two nonempty, decreasing patterns~\cite{albert2005simple}, and that a permutation is a leader permutation if it is a member of the geometric grid class of $\begin{pmatrix} 0 & -1\\ -1 & 0 \end{pmatrix}$ with at least one letter on each of the two lines corresponding to the $-1$'s~\cite{albert2013geometric}. \begin{example} The $7$ leader permutations of length $8$ are $18765432$, $21876543$, $32187654$, $43218765$, $54321876$, $65432187$, and $76543218$. \end{example} \begin{definition}[Adjacent permutations] We define two permutations $\pi,\rho\in S_n$ to be \textit{adjacent} if neither $\pi$ nor $\rho$ begins with $n$ or end with $1$ and if $\pi$ is a transposition of $\rho$ such that the positive difference between the two letters in the transposition is neither $1$ nor $n-1$. \end{definition} We now provide our characterization of the equivalence classes associated with the leader permutations in $S_n$. \begin{proposition} For any leader permutation $\pi$, the set of permutations adjacent to $\pi$ is an equivalence class. Moreover, there are $n-1$ of these classes. \label{prop:adjacentclasses} \end{proposition} To prove Proposition~\ref{prop:adjacentclasses}, we begin by proving that the equivalence classes are disjoint. \begin{lemma}\label{lem: disjoint adj to leader} For distinct leader permutations $\pi, \psi$, the set of permutations adjacent to $\pi$ is disjoint from the set of permutations adjacent to $\psi$. \label{lem:adjacent1} \end{lemma} \begin{proof} Assume for the sake of contradiction that the two sets share a common element. This would imply that it is possible to reach $\pi$ from $\psi$ in two or fewer transpositions. Since any leader permutation is a derangement of any other leader permutation, the permutations $\pi$ and $\psi$ differ in all $n \geq 7$ positions. However, since each transposition can only switch the positions of two letters, it is impossible for two or fewer transpositions to get $\pi$ from $\psi$, a contradiction. \end{proof} Next we prove that \begin{lemma} If we have a permutation adjacent to some leader permutation $\pi$ and we apply a $\{1234, 3412 \}$-pattern-replacement to it, the resulting permutation is also adjacent to $\pi$. \label{lem:adjacent2} \end{lemma} \begin{proof} Note that $\pi$ consists of a decreasing set of consecutive letters followed by another decreasing set of consecutive letters that are all larger than those of the first set; let $X$ and $Y$ denote these two sets, respectively. Figure~\ref{fig:leader} shows this for $\pi = 32187654$, for which $X$ consists of $321$ and $Y$ consists of $87654$. \begin{figure}[H] \centering \includegraphics[height=0.25\textwidth]{leader.eps} \caption{The leader permutation $32187654$. $X$ is in gray on left and $Y$ is on right.}\label{fig:leader} \end{figure} Consider a permutation $a_1a_2 \cdots a_n$ such that if a transposition is applied to two letters $a_i$ and $a_j$, $i \neq j$, the resulting permutation is equal to a leader permutation $\pi$. We claim that any $\{1234, 3412\}$-pattern-replacement applied to $a_1a_2 \cdots a_n$ must use both $a_i$ and $a_j$ and result in a permutation adjacent to $\pi$. To show that a $\{1234, 3412\}$-pattern-replacement applied to $a_1a_2 \cdots a_n$ must use both $a_i$ and $a_j$, first note that any three-letter subsequence of $\pi$ must correspond to one of the patterns $321$, $213$, or $132$ depending on how many letters are from each of $X$ and $Y$. Figure~\ref{fig:subpatterns} shows three examples of such three-letter subsequences in the leader permutation 54321876; each corresponds to a different pattern. \begin{figure}[H] \centering \includegraphics[height=0.25\textwidth]{subpatterns.eps} \caption{The subsequences $532$, $417$, and $487$ of $54321876$.}\label{fig:subpatterns} \end{figure} However, neither $1234$ nor $3412$ contains any of $321$, $213$, or $132$ as a subpattern, which means $\pi$ does not contain any three-letter subpattern of $1234$ or $3412$. As a consequence, any $1234$ or $3412$ pattern in $a_1a_2 \cdots a_n$ must contain both $a_i$ and $a_j$. Furthermore, the pattern in $a_1a_2 \cdots a_n$ must contain exactly one letter between $a_i$ and $a_j$. To see this, note that in $\pi$, any four-letter subsequence corresponds to one of the patterns $4321$, $3214$, $2143$, or $1432$ depending on how many letters are from each of $X$ and $Y$. The only transpositions of two letters that could result in $1234$ are swapping the $1$ and $3$ in $3214$ and swapping the $2$ and $4$ in $1432$, and the only transpositions that could result in $3412$ are swapping the $2$ and $4$ in $3214$ and swapping the $1$ and $3$ in $1432$. In any case, there is exactly one letter between the swapped letters $a_i$ and $a_j$. Since a $\{1234,3412\}$-pattern-replacement swaps the first and third letters and swaps the second and fourth letters, $a_i$ and $a_j$ are swapped back to their original order in $\pi$, and a new transposition is applied. The new permutation is adjacent to $\pi$. This completes the proof of the claim. \end{proof} Finally, we show that any two permutations adjacent to the same leader permutation are always equivalent. \begin{lemma} For any permutations $\tau$ and $\sigma$ that are both adjacent to a leader permutation $\pi$, $\tau$ can be reached from $\sigma$ by a sequence of $\{1234,3412\}$-pattern-replacements. \label{lem:adjacent3} \end{lemma} \begin{proof} We prove this using induction on $n$. Our base cases of $n=7$ and 8 can be checked by computer. Assume as an inductive hypothesis that the result holds for $n - 1 \ge 8$. Consider two permutations $\tau$ and $\sigma$ of length $n$ that are adjacent to some leader permutation $\pi$. Pick one of their common letters $a$ that is (1) not $1$ or $n$; (2) not part of either transposition from the leader permutation; (3) not adjacent in position to both letters in the transposition from $\pi$ to $\tau$; and (4) not adjacent in position to both letters in the transposition from $\pi$ to $\sigma$. Such an $a$ is guaranteed to exist because $n \geq 9$ and the four aforementioned conditions on $a$ restrict at most $8$ letters in total. Now, consider the sub-standardizations $\tau \prime$, $\sigma \prime$, and $\pi \prime$ respectively formed by removing $a$ from $\tau$, $\sigma$, and $\pi$. Note that $\pi \prime$ is a leader permutation of length $n-1$ (because $a \neq 1$ and $a \neq n$). In addition, $\tau \prime$ and $\sigma \prime$ are both adjacent to $\pi \prime$. Thus, by our inductive hypothesis, $\pi \prime$ can be reached from $\tau \prime$ by a sequence of pattern-replacements. By looking at the letters in $\tau$ corresponding to those of $\tau\prime$, we see that $\pi$ can be reached from $\tau$ by a sequence of pattern-replacements. This completes the proof by induction. \end{proof} Combined, Lemmas~\ref{lem:adjacent1},~\ref{lem:adjacent2},~and~\ref{lem:adjacent3} complete the proof of Proposition~\ref{prop:adjacentclasses}. \section{Showing that there are two remaining classes}\label{sec:parity} We now proceed to show that there are only two nontrivial classes remaining to be analyzed. To do this, we find two representative permutations, one from each class. First, we show that these representative permutations cannot be in the same equivalence class because they differ in parity, which implies that there are at least two remaining equivalence classes. Then, we show that every permutation that we have yet to analyze is equivalent to one of these two representative permutations, hence showing that there are at most, and thus exactly, two remaining nontrivial equivalence classes. To show the second part, we use induction on the size of the permutation. We begin by applying the inductive hypothesis to all but one of the letters of the permutation to transform them to be order-isomorphic to a representative permutation (of length $n - 1$). After applying this transformation, we return to considering all $n$ letters of the transformed permutation. We then select a different letter in the transformed permutation (specifically, we pick a letter that is already in the ``final'' position that we want it to be in), and we apply the inductive hypothesis to the $n-1$ letters of the permutation excluding that letter in order to transform them to be order-isomorphic to a representative permutation (of length $n - 1$). If done correctly, this construction causes the entire final permutation to form a representative permutation of length $n$, completing the proof. We begin with some preliminary definitions. \begin{definition}[Primary permutation] We call a permutation in $S_n$ \textit{primary} if it is not adjacent to a leader permutation and does not start with $n$ or end with 1. \end{definition} \begin{definition}[Primary class] We define a \textit{primary class} to be a nontrivial equivalence class of primary permutations in $S_n$. \end{definition} \begin{lemma}\label{lem: parity invariance} All of the permutations in each equivalence class have the same parity. \end{lemma} \begin{proof} Each $1234 \leftrightarrow 3412$ pattern-replacement consists of two transpositions. Since parity is invariant under both transpositions, the lemma follows. \end{proof} In the remainder of the section, we work to be able apply induction. To do so, we examine a sub-standardization of an arbitrary primary permutation formed by excluding one letter. The goal is to find conditions on the letter removed such that the sub-standardization is also primary, hence allowing us to apply the inductive hypothesis to the sub-standardization. There are two possible problems with this approach: either the sub-standardization is adjacent to a leader permutation, or the sub-standardization could start with its largest letter or end in $1$. The latter is easily dealt with, and we put it off to Case $2$ of Lemma~\ref{lem: 2 primary classes}. The former, however, can be dealt with using an intuitive claim that we prove in Lemma~\ref{lem:creating-primary-permutations}. We show in Lemma~\ref{lem:creating-primary-permutations} that, if removing a certain letter results in a permutation adjacent to a leader permutation, we can instead choose a different letter, with some constraints, to yield a permutation that is not adjacent to a leader permutation. We start by defining and proving some basic results about semi-leader permutations. \begin{definition} We define a \emph{semi-leader permutation} to be a permutation that is either a leader permutation or the decreasing permutation. \end{definition} Two equivalent definitions are that a permutation is a leader permutation if it is the plus-composition of two (possibly empty) decreasing patterns \cite{albert2005simple}, and that a permutation is a leader permutation if it is a member of the geometric grid class of $\begin{pmatrix} 0 & -1\\ -1 & 0 \end{pmatrix}$~\cite{albert2013geometric}. In the following lemmas, we say that a transposition of a sub-standardization swaps the same physical letters as it did in the original permutation. \begin{lemma}\label{lem:leader-minus-one} For any permutation $\rho\in S_k$ with $k\geq 5$, distinct letters $a, b$ in $\rho$, and transposition $\tau$ not operating on $a$ or $b$ such that $\tau \cdot \rho_{-(a)}$ is a leader permutation, $\tau \cdot \rho_{-(a, b)}$ is the unique semi-leader permutation adjacent to $\rho_{-(a, b)}$. \end{lemma} \begin{proof} To begin, note that the standardization of any semi-leader permutation with one letter removed is always a semi-leader permutation. We first show that $\tau \cdot \rho_{-(a, b)}$ is a semi-leader permutation (note that $\tau$ does not involve $a$ or $b$). In particular, $\tau \cdot \rho_{-(a)}$ is a leader permutation, and thus removing $b$ to get $\tau \cdot \rho_{-(a, b)}$ results in a semi-leader permutation. Moreover, $\tau \cdot \rho_{-(a, b)}$ is the unique semi-leader permutation adjacent to $\rho_{-(a, b)}$. In particular, any other such semi-leader permutation $x$ would differ from $\tau \cdot \rho_{-(a, b)}$ in at most $4$ positions and would therefore have to agree with $\tau \cdot \rho_{-(a, b)}$ in at least one position. Whenever two semi-leader permutations of the same length agree in at least one position, they must be the same permutation, meaning that $x$ would actually equal $\tau \cdot \rho_{-(a, b)}$. \end{proof} \begin{lemma}[Creating primary permutations]\label{lem:creating-primary-permutations} Let $\rho\in S_k$ with $k\geq 5$ be a primary permutation. Suppose there exists a letter $a$ in $\rho$ such that removing $a$ results in a sub-standardization $\rho_{-(a)}$ that is leader-permutation-adjacent. Let $\tau_1$ be the transposition taking $\rho_{-(a)}$ to a leader permutation, and suppose $b$ is some letter in both $\rho$ and $\rho_{-(a)}$ that is not operated on by $\tau_1$ and such that $a \not\equiv b \pm \modd{1} {k}$. Also, suppose that if $\tau_1$ operates on two letters with only one letter of $\rho_{-(a)}$ between them, then $b$ is not that letter. Then the sub-standardization $\rho_{-(b)}$ obtained by removing $b$ from $\rho$ is not adjacent to any leader permutation. \end{lemma} \begin{proof} Suppose, for the sake of contradiction, that $\tau_2\cdot \rho_{- (b)}$ is a leader permutation for some transposition $\tau_2$. If $\tau_2$ operates only on elements of $\rho_{-(a, b)}$ (i.e., $\tau_2$ does not involve $a$), we can conclude that $\tau_2=\tau_1$ by Lemma~\ref{lem:leader-minus-one}. In particular, $\tau_2 \cdot \rho_{-(a, b)}$ is a semi-leader permutation because $\tau_2 \cdot \rho_{-(b)}$ is a leader permutation. Thus $\tau_1 \cdot \rho_{-(a, b)} = \tau_2 \cdot \rho_{-(a, b)}$, so $\tau_1=\tau_2$. However, if $\tau_1=\tau_2$ then $\tau_1$ takes both $\rho_{-(b)}$ and $\rho_{-(a)}$ to leader permutations. We claim that this then implies that $\rho$ is also a leader permutation, a contradiction. This is because when we add $b$ to $\rho_{-(b)}$ to get $\rho$, $b$ is not adjacent to $a$ (recall that $a \not\equiv b \pm \modd{1} {k}$), so the letters that $b$ is adjacent to in $\rho_{-(a)}$ remain adjacent to $b$ in $\rho$ (although their values may be shifted by $1$), ensuring that $\rho$ is a leader permutation. It remains to consider the case in which $\tau_2$ operates on $a$. In this case, we define $\tau_2 \cdot \rho_{-(a, b)}$ to be the standardization of $\tau_2 \cdot \rho_{-(b)}$ with $a$ removed. Now, $\tau_2$ moves only one letter in $\rho_{-(a, b)}$ and results in a semi-leader permutation (as $\tau_2 \cdot \rho_{-(a, b)}$ is contained in $\tau_2 \cdot \rho_{-(b)}$, which is a semi-leader permutation). Thus, there are two semi-leader permutations $x = \tau_1 \cdot \rho_{-(a, b)}$ and $y = \tau_2 \cdot \rho_{-(a, b)}$, each of length $k - 2$, such that we can get from $x$ to $y$ by swapping two letters (applying the inverse of $\tau_1$, which is itself) and then moving one letter (the end result of $\tau_2$ after removing $b$). We place each letter of the permutation on a circle in clockwise order starting with the first letter. Observe that, up to rotation, all semi-leader permutations are equivalent in such a circular formation, implying that on the circle $x$ and $y$ are equivalent up to rotation. Let $\tau_1$ swap letters $j,k$. An example of a semi-leader permutation placed on a circle with $\tau_1$ applied is shown in Figure~\ref{fig:circle-argument}. Note that, because $\tau_1$ does not swap adjacent letters, neither $j$ nor $k$ are adjacent to any of the same letters as they were before $\tau_1$. However, moving one letter can remove at most three adjacencies ($2$ containing the moved letter and $1$ for the letters it moved between), so one of the four new adjacencies with $j$ or $k$ remains. Hence, after performing transposition $\tau_1$ and moving one letter, the circle is not the same up to rotation, a contradiction. \begin{figure}[H] \centering \includegraphics[height=0.45\textwidth]{circle-argument.eps} \caption{Example of a semi-leader permutation of length $8$ placed on a circle, where $\tau_1$ swaps $3$ and $6$ and creates four new adjacencies involving $3$ or $6$, namely $(4,6)$, $(6,2)$, $(3,5)$, and $(7,3)$.}\label{fig:circle-argument} \end{figure} \end{proof} We now proceed with a definition and then show that $2$ is both a lower and upper bound on the number of primary classes in the following two lemmas, respectively. \begin{definition} Define $\Pi_n=123\cdots n$ and $\Psi_n =123\cdots (n-3)(n-2)n(n-1)$. \end{definition} \begin{lemma}\label{lem: at least 2 primary classes} There are at least two \textbf{primary classes} in $S_n$ for $n\geq 7$. \end{lemma} \begin{proof} Let $n \ge 7$. First of all, note that the permutations $\Pi_n$ and $\Psi_n$ are both primary permutations. In particular, for $n\geq 7$, no transposition takes $\Pi$ or $\Psi$ to a leader permutation because for any transposition $\tau$, both $\tau \cdot \Pi$ and $\tau \cdot \Psi$ contain $123$ patterns. Further, the parity of the number of inversions is even in $\Pi$ and odd for $\Psi$, so they are in two distinct primary classes by Lemma~\ref{lem: parity invariance}. This proves that $2$ is a lower bound on the number of primary classes. \end{proof} \begin{lemma}\label{lem: 2 primary classes} There are exactly two \textbf{primary classes} in $S_n$ for $n\geq 7$. \end{lemma} \begin{proof} Let $n \ge 7$. We have, by Lemma~\ref{lem: at least 2 primary classes}, that $2$ is a lower bound on the number of primary classes. To proceed, we use induction to show $2$ is an upper bound on the number of primary classes. The base cases of $n=7,8,9,10$ are verifiable by computer. For the inductive step, we assume that Lemma~\ref{lem: 2 primary classes} holds for an $n=k-1$ with $k-1\geq 9$ and prove that Lemma~\ref{lem: 2 primary classes} holds for $n=k$. To do so, we show that any primary permutation in $S_k$ is equivalent to one of $\Pi_k$ and $\Psi_k$. Let $\rho\in S_k$ be an arbitrary primary permutation; we show that $\rho$ is equivalent to either $\Pi_k$ or $\Psi_k$ depending on the parity of the number of inversions $\rho$ contains. Because primary classes are nontrivial, we can find some $1234$ or $3412$ pattern in $\rho$. Take an arbitrary such pattern $q$. Since $k\geq 10$, we can now find some letter $a$ inside of $\rho$ such that $a\neq 1$, $a \neq k$, $a$ is neither the first nor last letter in $\rho$, and $q$ does not contain $a$. Now, we consider the sub-standardization $\rho\prime\in S_{k-1}$ of $\rho$ that excludes $a$. Because $a$ was not in $q$, $\rho\prime$ still contains $q$ and thus is part of a nontrivial class, and because $a$ was neither $n$ nor the first letter in $\rho$, $\rho\prime$ does not start with $n$. Similarly, $\rho\prime$ does not end with $1$. We proceed by cases based on whether $\rho\prime$ is adjacent to a leader permutation. \bigskip \noindent \textbf{Case 1:} $\mathbf{\rho\prime}$ \textbf{is a primary permutation.} In this case, by the inductive hypothesis, $\rho\prime$ is equivalent to either $\Pi_{k-1}$ or $\Psi_{k-1}$. Hence, in $\rho$, we can use the equivalence relation to reorder the elements excluding $a$ to form $\Pi_{k-1}$ or $\Psi_{k-1}$. Call this new permutation after the reordering $\rho_1$. Now, observe that because $a$ was not the first letter in $\rho$ but both $\Pi_{k-1}$ and $\Psi_{k-1}$ begin with $1$, $1$ is the first letter in $\rho_1$. Moreover, the second letter in $\rho_1$ is either $2$ or $a$, neither of which equals $n$. Consider the sub-standardization $\rho_1\prime$ created by excluding the $1$ in $\rho_1$. Note that $\rho_1\prime$ neither starts with $n$ nor ends with $1$. Additionally, we attain a $1234\cdots(k-4)$ pattern in $\rho_1\prime$ by ignoring the $a$ and the final two letters of $\rho_1\prime$. Such a pattern clearly must contain a $1234$ pattern and can never occur in a permutation adjacent to a leader permutation because $k-4\geq5$, so $\rho_1\prime$ is primary. Since $\rho_1\prime$ is primary, by our inductive hypothesis it is equivalent to either $\Psi_{k-1}$ or $\Pi_{k-1}$. In either case rearranging the sub-permutation of $\rho_1$ that $\rho_1\prime$ corresponds to yields that $\rho_1$, and hence $\rho$, must be equivalent to either $\Psi_k$ or $\Pi_k$, as desired. \bigskip \noindent\textbf{Case 2:} $\mathbf{\rho\prime}$ \textbf{is not primary.} In this case, consider some letter $b$ in $\rho$ such that \begin{enumerate} \item if the second letter of $\rho$ is $k$, $b$ is not the first letter in $\rho$ \item if the second to last letter of $\rho$ is $1$, $b$ is not the last letter in $\rho$ \item if the last letter in $\rho$ is $2$, $b\neq 1$ \item if the first letter in $\rho$ is $k-1$, $b\neq k$. \end{enumerate} Next we show that, as long as $k \ge 11$, it is possible to select $b$ satisfying conditions (1), (2), (3), and (4) as well as the conditions of Lemma~\ref{lem:creating-primary-permutations} (which we reiterate shortly). Let $\tau$ be the transposition taking $\rho'$ to a leader permutation. Note that these conditions imply that the sub-standardization $\rho^\star\in S_{k-1}$ attained by removing $b$ from $\rho$ neither ends in $1$ nor starts with $k$. Further, note that if the if-conditions for $(2)$ and $(3)$ both take effect, this would force $\rho$ to end with $12$, and either the $1$ or the $2$ would be operated on by $\tau$ as no leader permutation ends with $12$. Similarly, if the if-conditions for $(1)$ and $(4)$ both take effect, $\rho$ would start with $(k-1)k$, and either $(k-1)$ or $k$ would be operated on by $\tau$. Also, it is easy to see that both letters operated by $\tau$ must be a part of any $1234$ or $3412$ pattern in $\rho'$, because the 3-letter subsequences of these patterns do not appear in leader permutations. Hence, we if we take $b$ satisfying (1), (2), (3), and (4) and we require $b$ to satisfy the conditions of Lemma~\ref{lem:creating-primary-permutations} (meaning that $b$ is not contained in the pattern $q$; $b$ is not operated on by $\tau$; $b \neq a$; $b\not\equiv a\pm \modd{1} {k}$; and if $\tau$ swaps two letters separated by only one letter, $b$ is not that letter) then in total we exclude at most $10$ elements from the possible choices (in particular, (1), (2), (3), and (4) exclude at most two elements not already excluded as part of $\tau$). This means that as long as $k\geq 11$, we can find such a $b$ in $\rho$. Then, by Lemma~\ref{lem:creating-primary-permutations}, the permutation pattern formed by removing $b$ from $\rho$ must be a primary permutation, so this case reduces to Case $1$. These two cases complete the induction, establishing that the number of primary classes is exactly 2. \end{proof} \section{Putting the proof together} We now finish proving Theorem~\ref{thm:nontrivial} by combining the lemmas proven in the previous sections. \begin{theorem*}[Theorem~\ref{thm:nontrivial} restated] For $n \ge 7$, the number of nontrivial equivalence classes of $S_n$ under the $\{1234,3412\}$-equivalence is $\frac{n^3+6n^2-55n+54}{6}$. \end{theorem*} \begin{proof} First of all, by Lemma~\ref{lem:reduce with recursion}, we see that it is sufficient to show that there are exactly $n+1$ classes of permutations in $S_n$ not beginning with $n$ or ending with $1$. Every such permutation is in exactly one of two categories, the set of permutations adjacent to leader permutations and primary permutations. By Proposition~\ref{prop:adjacentclasses} there are $n-1$ classes of permutations adjacent to a leader permutation, and by Lemma~\ref{lem: 2 primary classes} there are exactly two primary classes. Thus, in total we find that permutations not beginning in $n$ or ending in $1$ fit into $n-1+2=n+1$ classes, as desired. By Lemma~\ref{lem:reduce with recursion}, this completes the proof. \end{proof} \section{Acknowledgments} The authors would like to thank Canada/USA Mathcamp for providing the opportunity to conduct this research. The authors would also like to thank William Kuszmaul for his mentorship on the project and for suggesting the research problem. \begin{thebibliography}{99} \bibitem{albert2013geometric} M.~Albert, M.~Atkinson, M.~Bouvel, N.~Ru{\v{s}}kuc, and V.~Vatter, Geometric grid classes of permutations, {\em Trans. Amer. Math. Soc.} {\bf 365} (2013), 5859--5881. \bibitem{albert2005simple} M.~H. Albert and M.~D. Atkinson, Simple permutations and pattern restricted permutations, {\em Discrete Math.} {\bf 300} (2005), 1--15. \bibitem{albert2006stanley} M.~H. Albert, M.~Elder, A.~Rechnitzer, P.~Westcott, and M.~Zabrocki, On the {Stanley--Wilf} limit of 4231-avoiding permutations and a conjecture of {Arratia}, {\em Adv. in Appl. Math.} {\bf 36} (2006), 96--105. \bibitem{bona2005limit} M.~B{\'o}na, The limit of a {Stanley--Wilf} sequence is not always rational, and layered patterns beat monotone patterns, {\em J. Combin. Theory Ser. A} {\bf 110} (2005), 223--235. \bibitem{bona2007new} M.~B{\'o}na, New records in {Stanley--Wilf} limits, {\em European J. Combin.} {\bf 28} (2007), 75--85. \bibitem{claesson2001generalized} A.~Claesson, Generalized pattern avoidance, {\em European J. Combin.} {\bf 22} (2001), 961--971. \bibitem{fazel2014equivalence} V.~Fazel-Rezai, {Equivalence classes of permutations modulo replacements between 123 and two-integer patterns}, {\em Electron. J. Combin.} {\bf 21} (2014), \href{https://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p47}{Article P2.47}. \bibitem{conf} {The international conference on permutation patterns}, 2020. \newblock Available at \url{https://permutationpatterns.com}. \bibitem{kitaev2011patterns} S.~Kitaev, {\em Patterns in Permutations and Words}, Springer Science \& Business Media, 2011. \bibitem{Kn} D.~Knuth, Permutations, matrices, and generalized {Young} tableaux, {\em Pacific J. Math.} {\bf 34} (1970), 709--727. \bibitem{kuszmaul2013counting} W.~Kuszmaul, {Counting permutations modulo pattern-replacement equivalences for three-letter patterns}, {\em Electron. J. Combin.} {\bf 20} (2013), \href{https://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p10}{Article P10}. \bibitem{kuszmaul2018fast} W.~Kuszmaul, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, {\em Math. Comp.} {\bf 87} (2018), 987--1011. \bibitem{kuszmaulzhou20} W.~Kuszmaul and Z.~Zhou, New results on families of pattern-replacement equivalences, {\em Discrete Math.} {\bf 343} (2020), 111878. \bibitem{lewis2011pattern} J.~B. Lewis, {Pattern avoidance for alternating permutations and Young tableaux}, {\em J. Combin. Theory Ser. A} {\bf 118} (2011), 1436--1450. \bibitem{LPRW} S.~Linton, J.~Propp, T.~Roby, and J.~West, Equivalence classes of permutations under various relations generated by constrained transpositions, {\em J. Integer Sequences} {\bf 15} (2012), \href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html}{Article 12.9.1}. \bibitem{ma} M.~Ma, {New results on pattern-replacement equivalences: generalizing a classical theorem and revising a recent conjecture, preprint}, 2020. \newblock Available at \url{https://arxiv.org/abs/2009.04546}. \bibitem{marcus2004excluded} A.~Marcus and G.~Tardos, Excluded permutation matrices and the {Stanley--Wilf} conjecture, {\em J. Combin. Theory Ser. A} {\bf 107} (2004), 153--160. \bibitem{NS} J.-C. Novelli and A.~Schilling, The forgotten monoid, {\em RIMS K\^oky\^uroku Bessatsu} {\bf 8} (2008), 71--83. \bibitem{PRW} A. Pierrot, D. Rossin, and J. West, Adjacent transformations in permutations, in \emph{FPSAC 2011, Discrete Math. Theor. Comput. Sci. Proc.}, 2011, pp. 765--776. \bibitem{SS} R.~Simion and F.~W. Schmidt, Restricted permutations, {\em European J. Combin.} {\bf 6} (1985), 383--406. \bibitem{sloane2003online} N.~J.~A. Sloane et~al., {The on-line encyclopedia of integer sequences}, 2020. \newblock Available at \url{https://oeis.org}. \bibitem{S12} R.~P. Stanley, An equivalence relation on the symmetric group and multiplicity-free flag h-vectors, {\em J. Comb.} {\bf 3} (2012), 277--298. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2020 {\it Mathematics Subject Classification}: Primary 05A05; Secondary 05A15. \noindent \emph{Keywords:} permutation, permutation pattern, equivalence class, integer sequence, pattern-replacement, transposition. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A330395}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 29 2020; revised versions received September 18 2020; October 16 2020. Published in {\it Journal of Integer Sequences}, October 17 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}