\documentclass[12pt]{article}
\usepackage{e-jc}


\usepackage{amsthm,amsmath,amssymb}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


%%%%
%%%% The next few commands set up the theorem type environments.
%%%% Here they are set up to be numbered section.number, but this can
%%%% be changed.
%%%%

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}


\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


%%%
%%% The following, if uncommented, numbers equations within sections.
%%% 

\numberwithin{equation}{section}


\begin{document}

\title{Pattern Popularity in $132$-avoiding Permutations}

\author{Kate Rudolph\thanks{Supported by NSF grant DMS-1062709 and NSA grant H98230-11-1-0224}\\
\small Department of Mathematics\\[-0.8ex]
\small Massachusetts Institute of Technology\\[-0.8ex]
\small Cambridge, MA, U.S.A.\\
\small\tt k8r@mit.edu}

\date{\dateline{Aug 13, 2012}{Nov 27, 2012}\\
\small Mathematics Subject Classifications: 05A05, 05A15, 05A19}
\maketitle
\begin{abstract}
The popularity of a pattern $p$ is the total number of copies of $p$ within all permutations of a set. We address popularity in the set of $132$-avoidng permutations. B\'{o}na showed that in this set, all other non-monotone length-$3$ patterns are equipopular, and proved equipopularity relations between some length-$k$ patterns of a specific form. We prove equipopularity relations between general length-$k$ patterns, based on the structure of their corresponding binary plane trees. Our result explains all equipopularity relations for patterns of length up to $7$, and we conjecture that it provides a complete classification of equipopularity in $132$-avoiding permutations.
\end{abstract}

\section{Introduction}

Let $\sigma=\sigma_1\ldots\sigma_n$ be a permutation of the numbers $1, \ldots ,n$, and $p=p_1\ldots p_k$ be a permutation of $1,\ldots, k$, with $k\le n$. The permutation $\sigma$ \emph{contains} the pattern $p$ if some subsequence of $\sigma$ is order-isomorphic to $p$; that is, if there is some sequence of indices $1\le i_1< \cdots <i_k\le n$ such that $\sigma_{i_s}<\sigma_{i_t}$ if and only if $p_s<p_t$. A permutation may contain multiple copies of a pattern: for example, the permutation $51243$ contains two copies of the pattern $123$, one at indices $2, 3$ and $4$, and another at indices $2$, $3$, and $5$. If $\sigma$ contains no copies of a pattern $p$, we say that $\sigma$ \emph{avoids} $p$. The set of all $\sigma\in S_n$ which avoid $p$ is denoted $S_n(p)$. 

Let $f(\sigma, p)$ be the number of copies of $p$ occurring in $\sigma$. 

\begin{definition} The \emph{popularity} $P_S(p)$ of a pattern $p$ in a set $S$ of permutations is given by:
$$P_S(p)=\sum_{\sigma\in S} f(\sigma, p).$$
\end{definition}

\begin{example}
If we take $S=S_n$, the set of all permutations of $1,\ldots n$, then any two patterns of the same length are equally popular. By linearity of expectation, for all patterns $p$ of length $k$, $P_{S_n}(p)=\frac{n!}{k!}\binom{n}{k}$. 
\end{example}

A notion related to popularity was defined by B\'{o}na, Sagan, and Vatter in \cite{bsv}. They define the \emph{frequecny} $S_{n,q}(c)$ to be the number of permutations of length $n$ which contain exactly $c$ copies of the pattern $q$. The popularity of $q$ in $S_n$ is related to the frequency by $P_{S_n}(q)=\sum_{c\ge 0} c*S_{n,q}(c)$. That is, the popularity is the total number of occurrences of the pattern $q$, counting multiplicity. Frequency is not studied in this paper, but we mention it to clarify the new term popularity. 

While our example of popularity was easy, it becomes more difficult to compute the popularity of patterns when $S=S_n(p)$ for some pattern $p$.  This problem was first proposed, in slightly different terms, by Joshua Cooper \cite{Cooper}, who asks: given two permutations $p$ and $r$, what is the expected number of copies of $p$ in a permutation chosen at random from $S_n(r)$? Instead of considering expectation, in this paper we will examine the equivalent question of how many copies of $p$ exist in all permutations in $S_n(r)$, which is exactly the popularity.

The focus of this paper is the popularity of patterns in $S_n(132)$, the set of length-$n$ $132$-avoiding permutations. For convenience, we will write $P_{S_n(132)}(p)$ as $A_n(p)$. 

Permutations of length $n$ avoiding $132$ are counted by the Catalan numbers. The popularity of any pattern $p$ containing $132$ in $S_n(132)$ will be zero, because if $\sigma\in S_n(132)$ contains $p$, then $\sigma$ contains $132$, a contradiction. Thus, we will look only at the popularity of patterns which are themselves permutations in $S_n(132)$.

B\'{o}na \cite{Bona1} showed that for all patterns $p$ of length $k$ and for all $n$, we have $$A_n(12\cdots k)\le A_n(p)\le A_n(k\cdots 21);$$ that is, the strictly increasing pattern is the least popular and the strictly decreasing pattern is the most popular among all patterns of length $k$.

If $A_n(p)=A_n(q)$ for all $n$, we say that $p$ and $q$ are \emph{equipopular}. This is an equivalence relation, so we can divide patterns of length $k$ into equivalence classes using equipopularity. B\'{o}na \cite{Bona2} showed that for length-$3$ patterns, there are three equivalence classes: $123$ and $321$ comprise the least-popular and most-popular classes, respectively, while $213, 312,$ and $231$ are all equipopular. 

In \cite{Bona2}, B\'{o}na also proved that patterns of a certain specific form are equipopular. Adopting the notation in Definition \ref{def:plusminus}, B\'{o}na's theorem states

\begin{theorem}[B\'{o}na]
Let $q$ and $t$ be any non-empty patterns that end in their largest entry, and let $i_u$ denote the increasing pattern $12\ldots u$. Then for all positive integers $n$, we have $$A_n((q\ominus t)\oplus i_u)=A_n((q\oplus i_u)\ominus t).$$
\end{theorem}

This theorem provides an exponential number of pairs of patterns which are equipopular, but at least one pattern in the pair must end in its largest element in order for the theorem to apply.  Thus if a pattern $p$ is not equipopular to any pattern $q$ ending in its largest element, then B\'{o}na's theorem of \cite{Bona2} can not apply to $p$. 

This paper extends B\'{o}na's results and proves that more general classes of patterns are equipopular. Our results completely explain all experimentally observed equipopularity classes in patterns of length at most $7$. The main theorem uses a bijection from $132$-avoiding permutations to another combinatorial object called binary plane trees, and states that when two binary plane trees have the same spine structure (see Definition \ref{def:spines}), their corresponding patterns are equipopular. Thus the result applies to all patterns of all lengths $k$. We have experimentally computed the popularities for all patterns with $k\le 7$, and there are no additional equipopularity relations besides those predicted by our theorem. We conjecture that our theorem also provides a full classification of the equipopularity classes for all $k$.

For example, the patterns $43251$, $43521$, $53214$, $53241$, and $54213$ are all equipopular by the main theorem of this paper. Calculations of their popularities $A_n(p)$ for the first few values of $n$ show that no other length-$5$ patterns are equivalent to these five. Since none of them ends in its largest element, they cannot be proved equivalent by B\'{o}na's theorem of \cite{Bona2}. In general, the main result of this paper explains all observed equipopularity results in our numerical evidence, a problem left open by B\'{o}na in \cite{Bona2}.

In Section \ref{gf}, we use the method of generating functions outlined by B\'{o}na in \cite{Bona1} to prove general results about extending equipopular patterns, which will be used in the proof of the main theorem in Section \ref{proof}. In Section \ref{bij} we describe a bijection from $132$-avoiding permutations to binary plane trees, and define the notation which allows us to precisely state the main theorem. Section \ref{proof} contains the proof of the main theorem.

%In Section 2, I classify length-4 patterns similarly. The $14$ length-$4$ patterns which do not contain a $132$ pattern break down into $5$ equivalence classes, of sizes $1$, $6$, $2$, $4$, and $1$. 

%In Section 3, I define a set $\beta_k$ of length $k$ patterns and proved that every element in the set is equipopular. I conjecture that $\beta_k$ comprises the ``second-least popular'' equivalence class, in the same sense that $123\cdots k$ is the least popular, for all $n$. 

% Finally in Section \ref{conclusion} I discuss my conjecture that the main theorem is a full classification of all length-$k$ patterns into equipopularity classes. 


\section{Arguments Using Generating Functions}
\label{gf}
In this section we will show that, given equipopular patterns, we can build longer patterns from them which are also equipopular. We will do this by manipulating the generating functions for the popularity. The theorems proved here will be used in the proof of the main theorem. 

B\'{o}na \cite{Bona1} lays out a procedure for breaking down the possible cases of the occurence of a pattern $p$ in a $132$-avoiding permutation $\sigma$ of length $n$. 

In any $132$-avoiding permutation $\sigma$, all the entries to the left of the entry $n$ must be greater than all the entries to the right of $n$, otherwise there would be an occurrence of the pattern $132$. We say that the pattern $p$ has a \emph{cut} at index $i$ if all entries of $p$ before and at index $i$ are greater than all entries after index $i$. The pattern $p$ can occur in $\sigma$ in several ways, enumerated by B\'{o}na \cite{Bona1}: 
\begin{enumerate}
\item $p$ occurs entirely to the left of $n$
\item $p$ occurs entirely to the right of $n$
\item the largest element $k$ in $p$ can be represented by the $n$ in $\sigma$, with the rest of the pattern $p$ split between the left and right sides of $\sigma$
\item for each cut in $p$, we can split $p$ between the left and right blocks of $\sigma$ at that cut. 
\end{enumerate}
If $p$ ends in its largest element, the fourth case cannot occur as there are no such indices $i$.

Let $c_n$ be the $n$th Catalan number, and $C(x)=\sum_{n\ge 0} c_nx^n$ be the generating function for the Catalan numbers. 

We will show that given two equipopular patterns $p$ and $q$, it is possible to construct more equipopular patterns of a longer length. This will require notation for combining two patterns to make another. We define two operations for combining patterns.

\begin{definition}
Given two patterns $p$ and $q$, of lengths $k$ and $m$ respectively, we let $p\oplus q$ be the pattern of length $k+m$ consisting of $p$ followed by $q$ shifted up by $k$: 
$$(p\oplus q)_i=
\begin{cases}
p_i & \text{if } i \le k \\
q_{i-k}+k & \text{if } i > k.
\end{cases}$$
Similarly, $p\ominus q$ is the pattern of length $k+m$ containing $p$ shifted up by $m$, followed by $q$:
$$(p\ominus q)_i=
\begin{cases}
p_i+m & \text{if } i \le k \\
q_i & \text{if } i > k.
\end{cases}$$
\label{def:plusminus}
\end{definition}

\begin{example}
If $p=3421$ and $q=123$, then $p\oplus q = 3421567$ and $p\ominus q=6754123$. 
\end{example}

\begin{theorem}
$132$-avoiding patterns $p$ and $q$ are equipopular if and only if $p\oplus 1$ and $q\oplus 1$ are equipopular.
\label{plus1}
\end{theorem}

We note that if a pattern $p$ avoids $132$, then so must $p\oplus 1$, because the additional $1$ at the end cannot introduce an occurrence of $132$.

\begin{proof}
The idea of this proof is to relate the generating function for the popularity of $p$ to that of $p\oplus 1$. 

 Let $a_n=A_n(p)$ and $b_n=A_n(q)$. Let $A(x)=\sum_{n\ge 0} a_nx^n$ be the generating function for $a_n$ and $B(x)=\sum_{n\ge 0} b_nx^n$ be the generating function for $b_n$. Let $a'_n=A_n(p\oplus 1)$ and $b'_n=A_n(q\oplus 1)$. 

We will proceed by counting the number of ways $p\oplus 1$ can occur in a permutation whose entry $n$ is at index $i$, and then we will sum over all $i$. 

Since $p\oplus 1$ ends in its largest element, there are no cuts, so we only need to consider the first three cases. %above to count the number of ways $a'_n$ that $p\oplus 1$ can occur as a pattern in a length $n$ $132$-avoiding permutation.
\begin{enumerate}
\item there are $a'_{i-1}$ ways for $p\oplus 1$ to occur to the left of the $n$, and for each of those there could be any $132$-avoiding permutation on the right of the $n$, for $c_{n-i}$ possibilites in each case ($a'_{i-1}c_{n-i}$ possibilities).
\item there are $a'_{n-i}$ ways for $p\oplus 1$ to occur on the right of the $n$ and for each of those, $c_{i-1}$ ways to fill the elements on the left side of the $n$ ($a'_{n-i}c_{i-1}$ possibilities).
\item if the largest element of $p\oplus 1$ coincides with $n$, an instance of $p$ must occur to the left of $n$ and any $132$-avoiding permutation may fall to the right ($a_{i-1}c_{n-1}$ possibilities).
\end{enumerate}  
Summing over all possible positions of $i$ we get 
$$a'_n=\sum_{i=1}^na'_{i-1}c_{n-i}+\sum_{i=1}^na'_{n-i}c_{i-1}+\sum_{i=1}^na_{i-1}c_{n-i}$$

Converting to a generating function by taking $A'(x)=\sum_{n\ge 0} a'_nx^n$, we find 

$$A'(x)=2xA'(x)C(x)+xA(x)C(x)$$ which is equivalent to $$A'(x)=\frac{xA(x)C(x)}{1-2xC(x)}.$$

The same argument shows that $$B'(x)=\sum_{n\ge 0} b'_nx^n=\frac{xB(x)C(x)}{1-2xC(x)}.$$

Thus $A(x)=B(x)$ if and only if $A'(x)=B'(x)$, so $p$ and $q$ are equipopular if and only if $p\oplus 1$ and $q\oplus 1$ are equipopular.
\end{proof}

If we let $I_j$ be the pattern $123\ldots j$, then repeated application of Theorem \ref{plus1} gives the following corollary. 
\begin{corollary}
$132$-avoiding patterns $p$ and $q$ are equipopular if and only if $p\oplus I_j$ and $q\oplus I_j$ are equipopular for any positive integer $j$. 
\end{corollary}

If $p$ and $q$ are equipopular, $p\ominus 1$ and $q\ominus 1$ need not be equipopular. For example, although $231$ and $213$ are equipopular \cite{Bona2}, we have $231\ominus 1=3421$ and $213\ominus 1=3241$. A little computation shows $A_5(3241)=15$ and $A_5(3421)=16$, so $3421$ and $3241$ are not equipopular. However, when $p$ and $q$ both end in their largest element, we have the following result: 

\begin{theorem}
$132$-avoiding patterns $p$ and $q$ are equipopular if and only if  $(p~\oplus~1~)~\ominus~1$ and $(q\oplus1)\ominus1$ are equipopular.
\label{scaffold}
\end{theorem}

\begin{proof}
We will find a relation between the generating function for $p$ and that for $(p\oplus 1)\ominus 1$. As before, let $a_n=A_n(p)$, $b_n=A_n(q)$, $a'_n=A_n(p\oplus 1)$ and $b'_n=A_n(q\oplus 1)$. Also, let $a^*_n=A_n((p\oplus 1)\ominus 1)$ and let $b^*_n=A_n((q\oplus 1)\ominus 1)$. Let $A(x)$, $B(x)$, $A'(x)$, $B'(x)$, $A^*(x)$, and $B^*(x)$ be the generating functions for $a_n$, $b_n$, $a'_n$, $b'_n$, $a^*_n$, and $b^*_n$, respectively. From the proof of Theorem \ref{plus1}, we know

$$A'(x)=\frac{xA(x)C(x)}{1-2xC(x)} \qquad\text{and}\qquad B'(x)=\frac{xB(x)C(x)}{1-2xC(x)}.$$


Now, we will use the cases outlined at the beginning of this section to count the number of ways $(p\oplus 1)\ominus 1$ can occur in a length-$n$ $132$-avoiding permutation whose entry $n$ is at index $i$. Later we will sum over all $i$. The four cases, in the same order as before, are:
\begin{enumerate}
\item the $(p\oplus 1)\ominus 1$ pattern occurs entirely to the left of index $i$ and the right of index $i$ is occupied by any $132$-avoiding permutation ($a^*_{i-1}c_{n-i}$).
\item the $(p\oplus 1)\ominus 1$ pattern occurs entirely to the right of index $i$ and the left of index $i$ is occupied by any $132$-avoiding permutation ($a^*_{n-i}c_{i-1}$).
\item the largest element in the $(p\oplus 1)\ominus 1$, which is the second to last element in the pattern, coincides with the $n$ in $\sigma$ at index $i$. A $p$ pattern occurs to the left. On the right of the $n$ is any $132$-avoiding permutation, but we must also choose which of the $n-i$ elements to the right will be included to form the last element of our $(p\oplus 1)\ominus 1$ pattern. ($a_{i-1}c_{n-1}(n-i)$).
\item There is only one cut: the $(p\oplus 1)$ pattern occurs on the left side of the $n$ and the last element of the $(p\oplus 1)\ominus 1)$ pattern occurs somewhere on the right side of the $n$ ($a'_{i-1}c_{n-i}(n-i)$).
\end{enumerate}

Summing over all $i$, we find that $$a^*_n=\sum_{i=1}^na^*_{i-1}c_{n-i}+ \sum_{i=1}^na^*_{n-i}c_{i-1}+ \sum_{i=1}^na_{i-1}c_{n-i}(n-i)+ \sum_{i=1}^na'_{i-1}c_{n-i}(n-i)$$

Let $Z(x)=\sum_{n\ge 0} nc_nx^n$. Then we find 

$$A^*(x)=2xA^*(x)C(x)+xA(x)Z(x)+xA'(x)Z(x),$$ or equivalently $$A^*(x)=\frac{xZ(x)(A(x)+A'(x))}{1-2xC(x)}=\frac{xZ(x)\left(A(x)+A(x)\frac{xC(x)}{1-2xC(x)}\right)}{1-2xC(x)}.$$
The same argument shows that $$B^*(x)=\frac{xZ(x)(B(x)+B'(x))}{1-2xC(x)}=\frac{xZ(x)\left(B(x)+B(x)\frac{xC(x)}{1-2xC(x)}\right)}{1-2xC(x)}.$$

Thus $A^*(x)=B^*(x)$ if and only if $A(x)=B(x)$, so $p$ and $q$ are equipopular if and only if $(p\oplus 1)\ominus 1$ and $(q\oplus 1)\ominus 1$ are equipopular.

%If $p$ and $q$ are equipopular, then $A(x)=B(x)$ and $A'(x)=B'(x)$ by Theorem \ref{plus1}. Thus $A(x)+A'(x)=B(x)+B'(x)$ and $$A^*(x)= \frac{xZ(x)}{1-2xC(x)}(A(x)+A'(x))=\frac{xZ(x)}{1-2xC(x)}(B(x)+B'(x))=B^*(x)$$ and so $(p\oplus 1)\ominus 1$ and $(q\oplus 1)\ominus 1$ are equipopular.

%Conversely, suppose $(p\oplus 1)\ominus 1$ and $(q\oplus 1)\ominus 1$ are equipopular. Then $A^*(x)=B^*(x)$ so $$\frac{xZ(x)(B(x)+B'(x))}{1-2xC(x)}=\frac{xZ(x)(A(x)+A'(x))}{1-2xC(x)}$$ or $A(x)+A'(x)=B(x)+B'(x)$. We know $A'(x)=\frac{xA(x)C(x)}{1-2xC(x)}$ and $B'(x)=\frac{B(x)C(x)}{1-2xC(x)}$ by the previous theorem, so we have $$A(x)+A(x)\frac{xC(x)}{1-2xC(x)}=B(x)+B(x)\frac{C(x)}{1-2xC(x)}.$$ Factoring yields  $$A(x)(1+ \frac{xC(x)}{1-2xC(x)})=B(x)(1+ \frac{xC(x)}{1-2xC(x)})$$ and $A(x)=B(x)$, meaning $p$ and $q$ are equipopular as desired.

\end{proof}


%\section{Bijection from 132-Avoiding Permutations to Non-Crossing Partitions}
\section{Bijection to Binary Plane Trees}
\label{bij}


%Another sort of combinatorial object that can be counted by the catalan numbers is non-crossing partitions.
%
%\begin{definition} A \emph{non-crossing partition} of $n$ is a partition of the numbers $1, 2\ldots n$, such that for any $a$ and $b$ belonging to one part, and $x$ and $y$ belonging to a different part, they are not arranged such that $a<x<b<y$. Equivalently, if the numbers $1,2,\ldots n$ are viewed as points on a line, with elements of the same part connected by arcs above the line, in a non-crossing partition none of the arcs may cross each other.
%\end{definition}
%
%Multiple bijections exist between $132$-avoiding permutations and non-crossing partitions. Here we will define one such bijection, $f$, which will be useful in classifying $132$-avoiding permutations by popularity. 
%
%Given a $132$-avoiding permutation $p$, of length $n$, we compute $f(p)$ by:
%
%We define the ``greedy falling sequence'' of some subsequence of $p$ to be the sequence whose first element is the largest element of $p$, and thereafter each element is the largest element of $p$ to the right of the previous element. For example if the subsequence of $p$ were $456312$, the greedy falling sequence would be $6,3,2$. The ``greedy falling index set'' is just the indices of the greedy falling sequence, or in our example, $\{3,4,6\}$. 
%
%To compute $f(p)$, first we take the greedy falling index set of the entire pattern $p$, and make it a part of our partition. Suppose this part has $m$ elements, $i_1, i_2,\ldots i_m$. Then it splits the remaining elements into $m+1$ (possibly empty) subsequences: the elements before index $i_1$, the elements between indices $i_1$ and $i_2$, etc. Recursively apply $f$ to each of these subsequences, adding the resulting parts to the output partition. 
%
%For example, to compute $f(456312)$, first we'd create the part $\{3,4,6\}$ from the greedy falling index set. Now we have $i_1=3$, $i_2=4$, $i_3=6$, and the remaining elements are split into two subsequences: $45$, and $1$. (The subsequence between $i_1$ and $i_2$ is empty, as is the subsequence after $i_3$.) Computing $f(45)$ we have the greedy falling index set $\{2\}$, and the recursing on the remaining subsequence $4$ we get the greedy falling index set $\{1\}$. Computing $f(1)$, we keep in mind that $1$ was at index $5$, so its greedy falling index set is $\{5\}$. Thus $f(456312)$ is the partition $\{\{1\},\{2\},\{3,4,6\},\{5\}$.
%
%
%%Then, let $j$ be the index of the largest element in $p$. We look at the subsequence of $p$ consisting of elements after index $j$ which are not already in a part of the partition, take the greedy falling index set of this subsequence, and add it as a part to the partition. We repeat this process until every index after $j$ has been added to some part. Then, we recursively apply $f$ to the subsequence of $p$ consisting of elements before index $j$, until all indices have been added to the partition.
%
%The resulting partition must be non-crossing, by construction. Once the first part has been created, none of the recursively generated parts can contain indices which would cross the existing part.
%
%It would be possible to compute $f(p)$ for any permutation $p$, not just $132$-avoiding permutations; however, this would map multiple patterns $p$ to the same non-crossing partition. To show that $f$ is a bijection, we define a function $g$ from non-crossing partitions to $132$-avoiding permutations, which we'll prove is the inverse of $f$.
%
%To compute the function $g$ on a partition $\pi$ of size $n$, determine $k$, the smallest elment in the same part as the element $n$. Then let $\pi_a$ be the restriction of $\pi$ to $1,2\ldots (k-1)$ and $\pi_b$ be the restriction of $\pi$ to $k+1, k+2,\cdots n$. Then $g(\pi)$ is equal to $(g(\pi_a) \oplus 1 )\ominus g(\pi_b)$. (Here $g$ of the empty partition is the empty sequence).
%
%To see that $g$ is the inverse of $f$, suppose $f(p)=\pi$. We'll show that $g(\pi)=p$. Suppose the largest element of $p$ is at index $i$. Then in $\pi$, $i$ will be in the same part as $n$ because the initially greedy falling index set must include $n$. No index less than $i$ can be in the same part as $n$ because the element at that index in $p$ would have to be greater than the element at $i$, a contradiction. So $i$ is the least element in a group with $n$. So in the computation of $g(\pi)$, we find $k=i$ and thus the largest element is placed at index $i$ as desired. By construction of $g$, all the elements on the left of index $i$ are greater than all the elements on the right of index $i$, so $p$ is $132$-avoiding. Recursively applying this argument to the left and right sides yields that $g(\pi)$ is exactly $p$, so $g$ is the inverse of $f$ and this map is indeed a bijection. 
%
%\begin{definition}
%The \emph{shape} of a partition is the sequence of part sizes, sorted in descending order.
%\end{definition}
%\begin{example}
%Suppose we have the partition $\{\{1\},\{2\},\{3,4,6\},\{5\}$. It has parts of size $1$, $1$, $3$, and $1$, so it's shape is $3,1,1,1$.
%\end{example}
%
%
%Now we can state the main result of this paper:
%
%\begin{theorem}
%If $p$ and $q$ are $132$-avoiding patterns, and the corresponding partitions $f(p)$ and $f(q)$ have the same shape, then $p$ and $q$ are equipopular.
%\end{theorem}
%
%\subsection{Binary Plane Trees}

In order to prove the main theorem, we introduce a set of objects, binary plane trees, which like $132$-avoiding permutations can be counted by the Catalan numbers. 

\begin{definition}
A \emph{binary plane tree} is a rooted, unlabeled tree in which each node has at most two children, and every child is designated as either the left or the right child of its parent, even if it is the only child. 
\end{definition}
There is a well-known bijection, described in \cite{Bona2}, between $132$-avoiding permutations and binary plane trees. For a $132$-avoiding permutation $p$, we construct its associated binary plane tree $T(p)$ recursively. If $p$ is the empty sequence, $T(p)$ is the empty tree. Then suppose $p$ is of length $n$. The root node of $T(p)$ represents the entry $n$ of $p$. If $p_1$ is the subsequence of $p$ before the $n$ entry, and $p_2$ is the subsequence of $p$ after the $n$ entry, then in $T(p)$ the left subtree of the root is $T(p_1)$ and the right subtree is $T(p_2)$.

We can recover the $132$-avoiding permutation $p$ corresponding to a tree by labeling each of the nodes by the entry it must represent. (Although binary plane trees are unlabeled, the labeling we give them is uniquely determined by the shape of the tree, so it does not affect the combinatorial definition of binary plane trees.) We know the root node must represent the element $n$. Suppose the right subtree has $i$ nodes, and thus the left subtree has $n-i-1$ nodes. Since every element to the left of $n$ in $p$ is greater than every element to the right of $n$ (because otherwise there would be an instance of the pattern $132$) we know that the left subtree of the root must represent the values $i+1,\ldots,n-1$ and the right subtree must represent the values $1,2,\ldots,i$. Recursively applying this rule allows us to construct a unique labeling of the nodes on the tree. The permutation it represents can be recovered by an in-order reading of the nodes: for each node we encouter, perform the in-order reading of its left child, then read the value of the node itself, then perform the in-order reading of its right child. 

\begin{figure}
\begin{tikzpicture}[scale=1,
	inf/.style={circle, draw=black, fill=black, inner sep = 0pt, minimum size = 2mm}]
	
%\node at (-5, 1.5) {5647231};
%	\node[cross out] {Cross out};
	\node (7) at (0, 3) [inf] {};
	\node (6) at (-1, 2) [inf] {};
	\node (5) at (-1.5, 1) [inf] {};
	\node (4) at (-.5, 1) [inf] {};
	\node (3) at (1, 2) [inf] {};
	\node (2) at (.5, 1) [inf] {};
	\node (1) at (1, 0) [inf] {};


	\node [left] at (0, 3)  {7};
	\node [left] at (-1, 2)  {6};
	\node [left] at (-1.5, 1)  {5};
	\node [left] at (-.5, 1)  {4};
	\node [left] at (1, 2)  {3};
	\node [left] at (.5, 1)  {2};
	\node [left] at (1, 0) {1};

	\draw     (5) -- (6);
	\draw			(6) -- (7);
	\draw			(7) -- (3);
	\draw			(3) -- (2);
	\draw			(2) -- (1);
	\draw			(6) -- (4);
\end{tikzpicture}
\caption{An example of the binary plane tree $T(5647213)$. The tree is labeled to illustrate the bijection, although in general binary plane trees are unlabeled.}
\label{bijectionillustration}
\end{figure}

%The definition of $T(p)$ has a sort of parallelism with the recursive structure of the definition of $g$ above, and in fact we find $f(p)$, the partition corresponding to $p$, in the structure of $T(p)$. 

\begin{definition}
The \emph{spines} of a tree $T(p)$ are the connected components of $T(p)$ when all edges connecting left children to their parents are deleted. The \emph{length} of a spine is the number of nodes in the spine. The \emph{spine structure} of $T(p)$ is the sequence of the lengths of spines in $T(p)$, sorted in descending order.
\label{def:spines}
\end{definition}



\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=.8,
	inf/.style={circle, draw=black, fill=black, inner sep = 0pt, minimum size = 2mm}]

	\draw [red, line width=3mm, opacity=30, line cap=round] (-0.1, 3.1) -- (2.1, 0.9);
	\draw [red, line width=3mm, opacity=30, line cap=round] (-1.1,2.1) -- (-.9,1.9);
	\draw [red, line width=3mm, opacity=30, line cap=round] (.45, 1.1) -- (.55, .9);
	\draw [red, line width=3mm, opacity=30, line cap=round] (-2.05, 1.1) -- (-1.45, -0.1);

	\node (7) at (0, 3) [inf] {};
	\node (6) at (-1, 2) [inf] {};
	\node (5) at (-2, 1) [inf] {};
	\node (4) at (-1.5, 0) [inf] {};
	\node (3) at (1, 2) [inf] {};
	\node (2) at (.5, 1) [inf] {};
	\node (1) at (2, 1) [inf] {};

	\draw (4) -- (5) ;
	\draw (5) -- (6) ;
	\draw (6) -- (7) ;
	\draw (3) -- (2) ;
	\draw (7) -- (3) ;
	\draw (3) -- (1) ;
	
	\node (7a) at (-6, 3) [inf] {};
	\node (6a) at (-7, 2) [inf] {};
	\node (5a) at (-8, 1) [inf] {};
	\node (4a) at (-7.5, 0) [inf] {};
	\node (3a) at (-5, 2) [inf] {};
	\node (2a) at (-5.5, 1) [inf] {};
	\node (1a) at (-4, 1) [inf] {};

	\draw (4a) -- (5a) ;
	\draw (5a) -- (6a) ;
	\draw (6a) -- (7a) ;
	\draw (3a) -- (2a) ;
	\draw (7a) -- (3a) ;
	\draw (3a) -- (1a) ;
	

\end{tikzpicture}
\end{center}
\caption{An example of a binary plane tree with spine structure $\{3,2,1,1\}$. On the right the spines are highlighted. }
\label{figspine}
\end{figure}


An example of the spine structure is given in Figure \ref{figspine}. Note that the spine structure of a tree $T(p)$ with $n$ nodes is just a partition of $n$. Now we can precisely state the main theorem of this paper.

\begin{theorem}
For $132$-avoiding patterns $p$ and $q$, if the spine structures of $T(p)$ and $T(q)$ are the same, then $p$ and $q$ are equipopular.
\end{theorem}


%Another set of objects which are counted by the Catalan numbers and are thus in bijection with binary plane trees and $132$-avoiding permutations are the non-crossing partitions:
%
%\begin{definition} A \emph{non-crossing partition} of $n$ is a partition of the numbers $1, 2\ldots n$, such that for any $a$ and $b$ belonging to one part, and $x$ and $y$ belonging to a different part, they are not arranged such that $a<x<b<y$. 
%\end{definition}
%
%It may be useful to view this problem in terms of non-crossing partitions in some cases, although they will not be used in the proof of the main theorem. However, we will show a bijection from binary plane trees to non-crossing partitions because it may be much easier to count the number of non-crossing partitions with certain block sizes than the number of binary plane trees with certain spine structure.
%
%We can construct a labeled partition $\pi(p)$ from $T(p)$ by labeling each node of the tree with its index in the in-order reading, and then placing all the labels on the same spine into the same part of $\pi(p)$. 
%
%\begin{prop}
%For a $132$-avoiding permutation $p$, $\pi(p)$ will be a non-crossing partition:
%\end{prop}
%
%\begin{proof}
%Suppose that the partition $\pi$ constructed from $T(p)$ were not non-crossing, so there exist indices $a<x<b<y$ such that the nodes at positions $a$ and $b$ are on the same spine, and the nodes at positions $x$ and $y$ are both on a different spine. For convenience, we will call the nodes by their index in the in-order reading. So $b$ is in the right subtree of $a$ and $y$ is in the right subtree of $x$. %Since $x$ comes before $b$, either $x$ is in the left subtree of $b$ or there is a lowest node $r$ such that $x$ is in the left subtree of $r$ and $b$ is in the right subtree of $r$. In the first case, if $x$ is in the left subtree of $b$, then since $y$ is in the right subtree of $x$ then $y$ is also in the left subtree of $b$ so $y$ comes before $b$, a contradiction. So we must be in the second case. 
%
%Now, since $a$ comes before $x$, either $a$ is in the left subtree of $x$, $x$ is in the right subtree of $a$, or there is a lowest node $s$ such that $a$ is in the left subtree of $s$ and $x$ is in the right subtree of $s$. In the first case, if $a$ is in the left subtree of $x$, then since $b$ is in the right subtree of $a$, we have $b$ is also in the left subtree of $x$ so $b$ comes before $x$, a contradiction. 
%
%In the second case, we must consider several subcases: either $x$ is in the left subtree of $b$, $b$ is in the right subtree of $x$, or there is a lowest node $p$ such that $x$ is in the left subtree of $p$ and $b$ is in the right subtree of $p$. In the first subcase, since $y$ is in the right subtree of $x$, which is in the left subtree of $b$, $y$ is in the left subtree of $b$ so $y$ is before $b$, a contradiction. In the second subcase, $x$ is in the right subtree of $a$ and $b$ is in the right subtree of $x$. Thus $x$ is on the path from $a$ to $b$. But $a$ and $b$ are on the same spine, so $x$ must also be on that same spine, contradicting the assumption that $x$ and $y$ are on a different spine than $a$ and $b$. Finally in the third subcase, since $y$ is in the right subtree of $x$, which is in the left subtree of $p$, then $y$ is in the left subtree of $p$ and $b$ is in the right subtree of $p$. So $y$ comes before $b$, a contradiction.
%
%In the third case we have $a$ in the left subtree of $s$, $x$ in the right subtree of $s$, and $b$ in the right subtree of $a$. Since $a$ is in the left subtree of $s$, so is $b$. But $x$ is in the right subtree of $s$, so $x$ comes after $b$, a contradiction. 
%
%Thus the labeled partition $\pi(p)$ is non-crossing. \end{proof}
%
%It can be verified that this construction of a non-crossing partition out of a binary plane tree is a bijection, as both classes of objects are counted by the Catalan numbers. However, since the view of binary plane trees as non-crossing partitions is not central to the proof of the main theorem, we won't prove that this is a bijection.


%The spines of a tree $T(p)$ effectively partition its nodes into the connected components. This partition is exactly $f(p)$ when the nodes are considered by their index in the in-order reading:

%\begin{prop}
%Given a permutation $p$ of length $n$, if $\{i_1,i_2,\ldots i_m\}$ (listed with the elements in increasing order) is one of the parts in the partition $f(p)$, then the node with index $i_j$ in the in-order reading of $T(p)$ is the right child of the node with index $i_{j-1}$ in the in-order reading, for $2\le j\le m$
%\end{prop}
%
%
%\begin{proof}
%We'll first proceed by assuming $\{i_1,i_2,\ldots i_m\}$ is the first part of the partition created, and then we'll handle the recursion. If $\{i_1,i_2,\ldots i_m\}$ is the first part created during evaluation of $f$, then $i_1$ is the index of $n$ in $p$, which corresponds to the node of $T(p)$. By the definition of a greedy falling index set, $i_2$ is the index of the greatest element of $p$ occurring after $i_1$. The greatest element ocurring after the element $n$ must occur as the root of the right subtree of $n$, or in other words as the right child of $n$. Thus the node at index $i_2$ is the right child of the node at index $i_1$, as desired. 
%
%Now, in general, suppose that the node at index $i_j$ is the right child of the node with index $i_{j-1}$ for all $2\le j\le k$. We'll show that the node at index $i_{k+1}$ is the right child of the node at index $i_k$. By the inductive hypothesis each node at index $i_j$ is the right child of a right child, etc. and thus is not a left descendant of any node. Let the node at index $i_k$ be $r$ and the node at index $i_{k+1}$ be $s$. Because the partition is the first greedy falling index set of $p$, we know $i_{k+1}$ is the index of the greatest element in $p$ occurring after index $i_{k}$. Thus the $s$ must occur after the node $r$ in the in order reading. By the definition of the greedy falling sequence, $p_{i_k}>p_{i_{k+1}}$ so the label of $r$ is greater than the label of $s$. Thus the nodes $r$ and $s$ form a $21$ pattern in $T(p)$. We can see from the structure of the tree that this can only occur if $s$ is a right descendant of $r$ or there is some node $q$ such that $r$ is a left descendant of $q$ and $s$ is a right descendant of $q$. However, as we stade before, the node at index $i_k$, namely $r$, is not a left descendant of any node, thus we must have that $s$ is a right descendant of $r$. We also know that $p_{i_{k+1}}$ is the greatest element of $p$ to the right of $p_{i_k}$, so $s$ must be the root of the right subtree of $r$, or the right child of $r$, as desired. So our induction is complete.
%
%Now we must consider the case where $\{i_1,i_2,\ldots i_m\}$ is generated by the function $f$ at some level of recursion. We've shown as a base case the first level of recursion. Suppose that the proposition is true for all parts of $f(p)$ generated at $r-1$ or fewer levels of recursion. We'll examine some part $\{i_1,i_2,\ldots i_m\}$ that was generated at the $r$th level by finding the greedy falling sequence of the subsequence of $p$ between indices $i_a$ and $i_b$, where $i_a$ and $i_b$ were consecutive elements in a part of the partition generated on a previouos level. So, by the inductive hypothesis, the node with index $i_b$ in $T(p)$ is the right child of the node with index $i_a$. The subseqeunce of $p$ we from which $\{i_1,i_2,\ldots i_m\}$ was derived is contains only elements after index $i_a$ but before index $i_b$, so in the in-order reading of $T(p)$ they must be read after the node with index $i_a$, but before the node with index $i_b$. Since $i_b$'s node is the right child of $i_a$'s node, the only place these nodes can appear is in the left subchild of the node with index $i_b$. So, take that subtree in isolation as its own tree. The proof above for the first level of recursion holds, so the proposition is true at the $r$th level of recursion. Thus, by induction it is true in general. 
%\end{proof}
%
%The converse is also true: 
%\begin{prop}
%Let $p$ be some $132$-avoiding pattern of length $n$. If $b$ is the right child of $a$ in $T(p)$, then the index of $b$ and the index of $a$ are in the same part in $f(p)$.
%\end{prop}
%
%\begin{proof}
%Suppose for the sake of contradiction that $b$ is the right child of $a$ but $a$ and $b$ belong to different parts in $f(p)$. Let $a$ belong to $\{a_1,a_2, \ldots a_u\}$ and $b$ belong to $\{b_1,b_2,\ldots b_v\}$. By the previous proposition, we know that the node at index $a_{i}$ is the right child of the node at index $a_{i-1}$ for all $2\le i\le u$. Thus if the node $a$ corresponds to index $a_i$ for any $i<u$, then the right child of $a$, $b$, would be at index $a_{i+1}$ for $i+1\le u$. Thus $b$ would be in the same part as $a$, contradicting our assumption that $a$ and $b$ are in different parts. So $a$ is at index $a_u$. Similarly, we know that the node at index $b_j$ is the right child of the node at index $b_{j-1}$ for all $2\le j\le v$. So if $b$ is at index $b_j$ for some $2\le j\le v$, then $b$'s parent, $a$ will be at some index $b_{j-1}$ with $1\le j-1\le v-1$, and thus $a$ will be in the same part as $b$, another contradiction. So $b$ is at index $b_1$. 
%
%Now, the part $\{b_1,b_2,\ldots b_v\}$ must have been generated at some level of recursion in the execution of $f(p)$, and thus it is equal to the greedy falling index set of some subsequence of $p$. It cannot have been generated at the first level of recursion, because if it were, $b_1$ would be the index of the largest element of $p$. Thus the node at index $b_1$, $b$, would have the label $n$, and it would be the root. $b$ is not the root node of $T(p)$, since it has a parent, the part it corresponds to cannot have been generated at the first level. So $\{b_1,b_2,\ldots b_v\}$ is the greedy falling index set of the subsequence of $p$ between $i_f$ and $i_l$, where $i_f$ and $i_l$ are adjacent elements of some part generated at a previous level of recursion. Since $i_f$ and $i_l$ are adjacent elements of the same part, we know the node in $T(p)$ at index $i_l$ is the right child of the node at index $i_f$. All the nodes representing the subsequence of $p$ between $i_f$ and $i_l$ must fall between these nodes in the in-order reading of $T(p)$, so the only place for them to go is in the left child of $i_l$. Now, $b_1$ is the index of the largest element in this subsequence, so it must be the index of the root of the subtree containing the subsequence. But $b_1$ is the index of $b$, so $b$ must be the root of the left subtree of $i_l$, or the left child of $i_l$. But $b$ was a right child: the right child of $a$. This is a contradiction, so our assumption was false, and if $b$ is the right child of $a$ then the indices of $b$ and $a$ are in the same part. 
%\end{proof}
%
%Thus we've shown that for every pattern $p$, the spines in $T(p)$ are exactly the length of a corresponding part in $f(p)$, and no longer. 
%
%\begin{cor}
%$T(p)$ and $T(q)$ have the same spine structure if and only if $f(p)$ and $f(q)$ have the same shape.
%\label{spineshape}
%\end{cor}
%
%Thus we can phrase our theorem equivalently in terms of trees: for $132$-avoiding patterns $p$ and $q$, if the spine structures of $T(p)$ and $T(q)$ are the same, then $p$ and $q$ are equipopular.

\section{Proof of Main Theorem}
\label{proof}

Several of the ideas in this proof are borrowed from \cite{Bona1}: he introduces the idea of looking for subtrees in binary plane trees as equivalent to looking for patterns in permutations, and the idea of switching some subtrees. 

To begin the proof, we first notice that switching two left subtrees in a binary plane tree does not affect its spine structure. If our theorem is true the patterns represented by the trees before and after the switch should have the same popularity. This motivates our left-subtree-switching lemma.

\begin{lemma}[Left-Subtree-Switching Lemma] 
Given a $132$-avoiding pattern $p$ of length $k$, and two nodes $a$ and $b$ of $T(p)$ such that neither is in the left subtree of the other, let $T(q)$ be the tree obtained by switching the left subtrees of $a$ and $b$, and $q$ be the pattern represented by this tree. Then $p$ and $q$ are equipopular.
\label{leftswitch}
\end{lemma}

We allow the case where $a$ or $b$ has an empty left subtree. Figure \ref{leftswitchfig} illustrates a left subtree switch.

\begin{figure}[ht!]
\begin{tikzpicture}[scale=1,
	inf/.style={circle, draw=black, fill=black, inner sep = 0pt, minimum size = 2mm},
	big/.style={circle, draw=black, fill=black, inner sep = 0pt, minimum size = 3mm}]
	
%\node at (-5, 1.5) {5647231};
%	\node[cross out] {Cross out};
	\node (7) at (0, 3) [inf] {};
	\node (6) at (-1, 2) [big] {};
	\node (5) at (-1.5, 1) [inf] {};
	\node (4) at (-.5, 1) [inf] {};
	\node (3) at (1, 2) [big] {};
	\node (2) at (.5, 1) [inf] {};
	\node (1) at (1, 0) [inf] {};
	
	\node (7a) at (4, 3) [inf] {};
	\node (6a) at (3, 2) [big] {};
	\node (5a) at (2.5, 1) [inf] {};
	\node (4a) at (3, 0) [inf] {};
	\node (3a) at (3.5, 1) [inf] {};
	\node (2a) at (5, 2) [big] {};
	\node (1a) at (4.5, 1) [inf] {};

	\draw     (5) -- (6);
	\draw			(6) -- (7);
	\draw			(7) -- (3);
	\draw			(3) -- (2);
	\draw			(2) -- (1);
	\draw			(6) -- (4);
	
	\draw     (7a) -- (6a);
	\draw			(6a) -- (5a);
	\draw			(5a) -- (4a);
	\draw			(6a) -- (3a);
	\draw			(7a) -- (2a);
	\draw			(2a) -- (1a);
\end{tikzpicture}
\caption{On the left, $T(5647213)$, and on the right, $T(5463712)$. The right subtree is obtained from the left by switching the left subtrees of the two enlarged nodes. Lemma \ref{leftswitch} states that $4657213$ and $5463712$ are equipopular.}
\label{leftswitchfig}
\end{figure}



\begin{proof}

Let $B_n$ be the set of all $n$-node binary plane trees $T(\sigma)$, $k$ of whose nodes are colored red such that those $k$ nodes represent a $p$ pattern in $\sigma$. The order of $B_n$ is just the popularity of $p$, i.e. $|B_n|=A_n(p)$. Similarly, let $C_n$ be the set of all $n$-node binary trees $T(\sigma)$, $k$ of whose nodes are colored red, such that those $k$ nodes represent a $q$ pattern in $\sigma$. So $|C_n|=A_n(q)$. We will prove the lemma by constructing a bijection $\varphi$ from $B_n$ to $C_n$. 

Let $i$ be the index of $a$ in the in-order reading of $T(p)$ and let $j$ be the index of $b$. Then given some element $Q$ of $B_n$, let $Q_a$ be the $i$th red node in the in-order reading of $Q$ and $Q_b$ be the $j$th red node. Without loss of generality, let $i<j$. Then $\varphi(Q)$ is the tree obtained by switching the left subtrees of $Q_a$ and $Q_b$, without changing whether any node is colored red. We must show that this is well defined and that it is a bijection between $B_n$ and $C_n$. 

To show $\varphi$ is well defined, we must show that $Q_a$ is not in the left subtree of $Q_b$ and vice versa. Since $i<j$, $a$ is before $b$ in the in-order reading of $T(p)$, and $Q_a$ is before $Q_b$ in $Q$. Thus $Q_b$ is not in the left subtree of $Q_a$. Since $a$ comes before $b$ in $T(p)$ but is not in the left subtree of $b$, because of the way binary plane trees are labeled to recover a $132$-avoiding permutation we can conclude that the label of $a$ is greater than the label of $b$. So the $i$th element of $p$ is greater than the $j$th element of $p$. Thus, since the red nodes in $Q$ form a $p$ pattern, the label of the $i$th red node in $Q$, or $Q_a$, must be greater than the label of the $j$th red node, $Q_b$. If $Q_a$ were in the left subtree of $Q_b$, its label would be less than $Q_b$, so $Q_a$ must not be in the left subtree of $Q_b$. Thus function $\varphi$ is well defined on elements of $B_n$.

Now we will show that for $Q\in B_n$, we always have $\varphi(Q)\in C_n$, that is, the red nodes in $\varphi(Q)$ form a $q$ pattern. 

When we switch from $T(p)$ to $T(q)$, the only nodes that move are the nodes in the left subtree of $a$, which we will call $\alpha$, and the nodes in the left subtree of $b$, which we will call $\beta$. In $T(q)$, the sets of nodes $\alpha$ and $\beta$ simply switch position, and nothing else changes its relative order.

So, let $Q\in B_n$. The red nodes in $Q$ represent a $p$ pattern, so all the red nodes corresponding to the $\alpha$ nodes in $T(p)$ must be in the left subtree of $Q_a$, since they must be before $Q_a$ and have label less than $Q_a$. No red node in the left subtree of $Q_a$ can correspond to an element of the pattern $p$ that is not in $\alpha$ since $\alpha$ consists of all the pattern elements less than $a$ and to the left of $a$. So the red nodes in the left subtree of $Q_a$ are exactly those representing $\alpha$. Similarly, the red nodes in the left subtree of $Q_b$ are exactly those representing $\beta$. When we switch the left subtrees of $Q_a$ and $Q_b$, the only effect on the red nodes is to switch the positions of the nodes representing $\alpha$ and $\beta$. Thus, we've produced a $q$ pattern. 

%The nodes $\alpha$ represent every element in the $p$ pattern which is less than the element at index $i$ and before index $i$. Similarly, $\beta$ represents the elements in the $p$ pattern which are less than the element at $j$ and before index $j$. For $Q\in B_n$, the red nodes representing $\alpha$ must all be in the left subtree of $Q_a$, since $Q_a$ represents the element at index $i$ in the pattern $p$ and all of $\alpha$ must be to the left of and less than that element, so all the red nodes must be to the left of $Q_a$ and have label less than $Q_a$, meaning they musst be in the left subtree of $Q_a$. Similarly, all the red nodes in $Q$ representing $\beta$ must be in the left subtree of $Q_b$. So, switching the left subtrees of $Q_a$ and $Q_b$ switches the red nodes representing $\alpha$ with the red nodes representing $\beta$, and nothing else changes relative order. Thus, the new tree contains red nodes in exactly the pattern $q$. So $\varphi(Q)\in C_n$ for all $Q\in B_n$. 

%Now, to show that $\varphi$ is a bijection, we'll show that for any $U\in C_n$, there is exactly one $Q\in B_n$ such that $U=\varphi(Q)$. This will show $\varphi$ has an inverse and thus that it is a bijection. Recall that $i$ and $j$ are the indices of the nodes $a$ and $b$ in the in-order reading of $T(p)$. Let $i'$ be the index of $a$ in the in-order reading of $T(q)$. Then $i'=i-|\alpha|+|\beta|$, since $i'$ is the index when we take out all of the elements of $\alpha$ that appear before $i$ and replace them with all the elements of $\beta$. The index of $b$ in $T(q)$ is the same as the index of $b$ in $T(p)$, $j$, because the only things that are moved around all occur before $b$ in the in-order reading, and there are the same number of them before and after the switch, so $b$ still has index $j$. 
%
Now, to show that $\varphi$ is a bijection, we will show that its inverse is a very similar function $\varphi'$. Recall that $i$ and $j$ are the indices of the nodes $a$ and $b$ in the in-order reading of $T(p)$. Let $i'$ be the index of $a$ in the in-order reading of $T(q)$. Then $i'=i-|\alpha|+|\beta|$, since $i'$ is the index when we take out all of the elements of $\alpha$ that appear before $i$ and replace them with all the elements of $\beta$. The index of $b$ in $T(q)$ is the same as the index of $b$ in $T(p)$, $j$, because the only things that are moved around all occur before $b$ in the in-order reading, and there are the same number of them before and after the switch, so $b$ still has index $j$. 

Then, we can see that to invert $\varphi$, which switches the left subtrees of the $i$th and $j$th red nodes, we must simply switch those left subtrees back. But the index $i$ has changed to $i'$ since the subtrees we switched may not have been the same size. So the inverse function $\varphi':C_n\to B_n$ is defined as follows. Let $U\in C_n$, and let $U_{i'}$ be the $i'$th red node in the in-order reading of $U$, and $U_j$ the $j$th red node. Then $\varphi'(U)$ is the tree obtained by switching the left subtrees of $U_{i'}$ and $U_j$. 

We can see that $\varphi'$ is the inverse of $\varphi$ because it simply switches the subtrees back to their original positions. 

%
%Then let $U_a$ be the $i'$th red vertex of $U$ and $U_b$ be the $j$th red vertex of $U$. Switch the left subtrees of $U_a$ and $U_b$ to form $Q$. $Q\in B_n$ by the reverse of the argument above: all the red nodes in $U$ representing $\beta$ must have been in the left subtree of $U_a$ and all the red nodes representing $\alpha$ must have been in the left subtree of $U_b$, so switching the left subtrees makes only $\alpha$ and $\beta$ switch places.  After the switch, $U_a$'s index has increased by $|\alpha|-|\beta|$ because $\alpha$ elements have replaced the $\beta$ elements that were before it. So the new index of $U_a$ is $i'+|\alpha|-|\beta|=i$. The index of $U_b$ stays the same because all the switching goes on the the left of $U_b$. So we have that after the switch, $\alpha$ is the left subtree of the $i$th red node and $\beta$ is the left subtree of the $j$th red node, and nothing else has changed places, so $Q$'s red nodes are in a $p$ pattern and $Q\in B_n$. It's easy to see that $\varphi(Q)=U$ because we just switch the two left subtrees back. 
%
%$Q$ is the unique element of $B_n$ such that $\varphi(Q)=U$. Suppose, to the contrary, that $\varphi(V)=\varphi(Q)=U$. Then $V$ and $Q$ are two elements of $B_n$ such that, when you switch the left subtrees of their $i$th and $j$th red vertices, they are the same tree, $U$. So, switching the subtrees back as described above must yeild the same tree, and $V=Q$.

Thus $\varphi$ is a bijection from $B_n$ to $C_n$, so $|B_n|=|C_n|$ and $A_n(p)=A_n(q)$. Since this bijection can be defined for arbitrary $n$, $A_n(p)=A_n(q)$ for all $n$ and so $p$ and $q$ are equally popular. 

\end{proof}

Thus, every tree that can be obtained by repeatdly switching left subtrees of $T(p)$ represents a pattern equipopular to $p$. It would be convienient if every tree with the same spine structure could be transformed, via left-subtree switches, into any other tree with that spine structure; however, this is not the case. For example, Figure \ref{noswitches} shows two trees which cannot be transformed into each other by any sequence of left subtree switches. 

\begin{figure}
\begin{tikzpicture}[scale=1,
	inf/.style={circle, draw=black, fill=black, inner sep = 0pt, minimum size = 2mm}]
	\node (6a) at (2,4) [inf] {};
	\node (5a) at (1,3) [inf] {};
	\node (4a) at (0,2) [inf] {};
	\node (3a) at (1,1) [inf] {};
	\node (2a) at (2,0) [inf] {};
	\node (1a) at (2,2) [inf] {};


	\draw (6a) -- (5a) -- (4a) -- (3a) -- (2a);
	\draw (5a) -- (1a);
	
	\node (6b) at (6,4) [inf] {};
	\node (5b) at (5,3) [inf] {};
	\node (4b) at (4,2) [inf] {};
	\node (3b) at (5,1) [inf] {};
	\node (2b) at (6,2) [inf] {};
	\node (1b) at (7,1) [inf] {};


	\draw (6b) -- (5b) -- (2b) -- (1b);
	\draw (5b) -- (4b) -- (3b);
\end{tikzpicture}
\caption{Though the two trees have the same spine structure $\{3,2,1\}$, neither can be transformed to the other by left-subtree switches.}
\label{noswitches}
\end{figure}

However, we can show that every tree can be transformed to a ``left-justified'' tree with the same spine structure via left subtree switches. 

\begin{definition} A \emph{left-justified} binary plane tree is one in which every node that is a right child of its parent does not have a left child. \end{definition}

Thus the only nodes in a left-justified tree which are left children must have as parents either nodes which are also left children, or else the root. So in a left-justified tree, all the down-left edges, between a parent and its left child, form a path down the left side of the tree. We call this path the \emph{trunk} of the tree. The right subtree of each node along the trunk forms a spine. For each spine, we call the node in that spine that is on the trunk the \emph{top} node of that spine. Similarly, the spine whose top is at the root is the \emph{topmost} spine, and the \emph{lowest} spine in a left-justified tree is the one whose top node occurs lowest on the trunk.

\begin{lemma} For each binary plane tree $T(p)$, we can construct a left-justified tree $T^*(p)$ via only left-subtree switches.\label{leftjustify} \end{lemma}

\begin{proof}
If $T(p)$ is already left-justified, we are done. Otherwise, let $S$ be the set of nodes in $T(p)$ which are right children and have a left child. We will describe an operation on $T(p)$ which will reduce the size of $S$, and so repeated application of this operation will reduce the size of $S$ to zero, meaning that the resulting tree will be left-justified. 

Start at the root of $T(p)$, and move to the left child of the current node until we reach a node $x$ which has no left child. Let $y$ be some element of $S$. We know that $y$ is not in the left subtree of $x$ because $x$ has no left child. Also, $x$ is not in the left subtree of $y$ because the only ancestors of $x$ are themselves left children, and $y$ is in $S$ so it must be a right child. So we may use Lemma \ref{leftswitch} and switch the left subtrees of $x$ and $y$. Since $x$ has no left child, after the switch $y$ has no left child, so $y$ is no longer in $S$. Every other node that was in $S$ is still in $S$ because we haven't moved any of their left children. No new nodes are added to $S$ because the only node which gained a left child was $x$, but $x$ is not a right child of its parent so it cannot be an element of $S$.

Repeat this process until $S$ is empty. The resulting tree is left-justified.
\end{proof}

Switching left subtrees preserves popularity of the patterns represented by the trees, and it also preserves the spine structure of the trees. So this shows us that that any pattern $p$ is equipopular to some pattern $q$ such that $T(p)$ and $T(q)$ have the same spine structure, but $T(q)$ is left-justified. However, this is still not enough to prove our theorem: two left-justified trees may have the same spine structure, but the spines may appear in a different order. We need a way to permute the order of the spines along the trunk in a left-justified tree while preserving the popularity of the pattern that the tree represents. 

\begin{lemma}
If $T(p)$ and $T(q)$ are left-justified trees with the same spine structure, and the top spines of $T(p)$ and $T(q)$ have the same length $\ell\ge2$, then $p$ and $q$ are equipopular.
\label{sort}
\end{lemma}

\begin{proof}
We will prove this lemma by showing that every left-justified tree $T(p)$ whose top spine has length greater than $2$ can be transformed via a series of left subtree switches to a left-justified tree with all spines except the top spine appearing in sorted order by length along the trunk. 

We present an algorithm for sorting all of the spines except the top spine along the trunk. Begin by letting $a$ be the root node of $T(p)$ and $b$ be the right child of $a$. We will use $b$ as a sort of holding cell: at the beginning, $b$ cannot have a left child because $T(p)$ is left-justified, so any left subtree switch performed with $b$ as one of the elements being switched just moves a left subtree to $b$. 

The algorithm is performed by repeating the following process until the spines are in sorted order from shortest length to longest, with the longer spines further from the root, except the spine starting from the root.
\begin{enumerate}
\item Switch the left subtree of $a$ with the left subtree of $b$. 
\item Determine the spine with the shortest length which is in the left subtree of $b$. Let $x$ be the top node of this spine. 
\item Switch the left subtree of $x$'s parent with the left subtree of $a$. 
\item Let $y$ be the top node of the lowest spine in the left subtree of $a$.
\item Switch the left subtree of $b$ with the left subtree of $y$. 
\item Redefine $a$ to be the node currently labeled $x$.
\end{enumerate}

We claim that after $r$ repetitions of these steps, the $r$ shortest spines of $T(p)$ occur immediately after the topmost spine, in sorted order, and that $a$ refers to the top of the last spine of these $r$ sorted spines. We proceed by induction.

After $0$ repetitions, our claim is vacuously true. Suppose that the claim is true for $r=k$, so we have repeated the steps $k$ times and the smallest $k$ spines besides the top spine are in sorted order along the trunk. The inductive hypothesis tells us that $a$ is the top node of the lowest of these $k$ spines. So the entire left subtree of $a$ consists of the unsorted spines. We carry out the loop for the $(k+1)$st time. In step $1$, the left subtree of $a$ is moved to $b$, which does not have a subtree. Thus we've moved all the unsorted spines into the left subtree of $b$. In step $2$, we determine $x$, the top node of the shortest spine in this subtree. But the shortest spine of all the unsorted spines is the one which needs to go next. In step $3$, we switch the left subtree of $x$'s parent with the left subtree of $a$. Since we had already moved $a$'s left subtree away, it does not have a left subtree, so this is equivalent to moving the left subtree of $x$'s parent to the left subtree of $a$, and thus the spine whose top is $x$ is now next in the sorted order, as desired. Steps $4$ and $5$ move the left subtree of $b$ back to the end of the trunk, left-justifying the tree again. Finally, in step $6$ we redefine $a$ to be one node lower on the trunk. Thus after the loop we have sorted $k+1$ spines, since we added the spine whose top is $x$ to the sorted order, and $a$ is the top of the lowest of those $k+1$ sorted spines. Our induction is complete.

Therefore, repeating the loop a number of times equal to the number of spines will ensure that all the spines are sorted. 

To prove the lemma, sort $T(p)$ and $T(q)$ according to the above process, to obtain the trees $T(p')$ and $T(q')$. Since $T(p)$ and $T(q)$ both have the same spine structure and the same length of the topmost spine, then $T(p')$ and $T(q')$ are identical, so the patterns $p'$ and $q'$ they represent are the same. Since we performed only left subtree switches, $p$ and $p'$ are equipopular and $q$ and $q'$ are equipopular by the Left-Subtree-Switching Lemma. But $p'$ and $q'$ are the same so $p$ and $q$ are equipopular. 

%First we claim that at the beginning of each repetition, $b$ has no left subtree. This is certainly true before the first repetition. $b$ gains a left subtree in step (1). However, in step (5), $b$ switches left subtrees with $y$, which has no left child by construction in step (4). Thus after step (5) $b$ has no left subtree again as desired.
%
%Now we claim that at the beginning of each repetition the current tree is left-justified. This is certainly true before the first repetition as we must start with a left-justified tree. During each repetition, the only nodes that can gain a left child are $b$, $a$, and $y$, and $x$'s parent. For each of these, we must show either that at the beginning of each repetition it does not have a left child or that it is a left child itself, otherwise the tree would not be left-justified. We've already shown that at the beginning of each repetition $b$ does not have a left child. $a$ does have a left child, but $a$ is always equal to a left child or the node, because it is always reassigned to $x$ at each step, and $x$ is its left child. By construction $y$ is a left child as well. This leave's $x$'s parent. In step (1), $a$ switches left subtrees with $b$, which has no left child, so after step (1) $a$ does not have a left child. So when it switches with $x$'s parent in step (3), $x$'s parent does not gain a left child.  Thus in every repetition, no nodes are created which are right children and have left children, thus after each repetition the tree is left-justified.
%
%In each repetition, $a$ marks the position along the trunk above which all the spines are in sorted order (except the one beginning at the root). The only spines below $a$ along the trunk are longer than all the spines above $a$ except the one beginning at the root. After each repetition, the shortest spine is selected from the spines below $a$, moved to the position just below $a$, and $a$ is moved down, reflecting that the new element is in sorted order. This is a selection sort. 
%
%After each repetition $a$ moves down $1$ position along the trunk, until $a$ is the lowest node on the trunk. Then all the spines on the trunk are in sorted order except for the top one, as desired.
\end{proof}

We are ready to prove our main theorem, restated here for convenience. 

\begin{theorem}
For $132$-avoiding patterns $p$ and $q$, if the spine structures of $T(p)$ and $T(q)$ are the same, then $p$ and $q$ are equipopular.
\end{theorem}

\begin{proof}[Proof of Main Theorem]

We are given $p$ and $q$ such that $T(p)$ and $T(q)$ have the same spine structure. Using Lemma \ref{leftjustify}, we transfrom $T(p)$ the left-justified tree $T(p_1)$. Since we used only left subtree switches, by Lemma \ref{leftswitch} we know $p$ and $p_1$ are equipopular. Because left subtree switches preserve spine structure, $T(p)$ and $T(p_1)$ have the same spine structure. Similarly, we construct $T(q_1)$, so that $q$ and $q_1$ are equipopular and $T(q)$ and $T(q_1)$ have the same spine structure. 

$T(p_1)$ and $T(q_1)$ almost fit the conditions of Lemma \ref{sort}: they are both left-justified and both have the same spine structure. However, we need to ensure that they both have the same length of topmost spine, and that length must be at least $2$. The idea is to build a sort of scaffolding on top of each tree, use it to sort the rest of the spines, and then remove it at the end.

Let $p_2=(p_1\oplus 1)\ominus 1$, and consider the tree $T(p_2)$. This is a tree with the root node representing the second to last element in the in-order reading. The left subtree of the root is $T(p_1)$ and the right subtree is a single node with no children. The spine structure of $T(p_2)$ is the same as that of $T(p_1)$ with an additional spine of length $2$ added at the top of the trunk. Similarly, let $q_2=(q_1\oplus 1)\ominus 1$. Then the spine structure of $T(q_2)$ is the the same as that of $T(q_1)$ with an additional spine of length $2$ on the top.  Since $T(p_1)$ and $T(q_1)$ have the same spine structure, $T(p_2)$ and $T(q_2)$ have the same spine structure. So we invoke Lemma \ref{sort} on $T(p_2)$ and $T(q_2)$: both trees are left-justified, they have the same spine structure, and their topmost spines each have length $2$. Thus $p_2$ and $q_2$ are equipopular.

Since $p_2=(p_1\oplus 1)\ominus 1$ and $q_2=(q_1\oplus 1)\ominus 1$, by Theorem  \ref{scaffold}, $p_1$ and $q_1$ are equipopular, and thus $p$ and $q$ are equipopular as desired. 

%Since the spine structures of $T(r)$ and $T(s)$ However, $T((r\oplus 1)\ominus 1)$ and $T((s\oplus 1)\ominus 1)$ fit the conditions of Lemma \ref{sort}: the root of each tree has a right child. So, we can sort each of these trees by the proccess outlined in Lemma \ref{sort}. Let $T(u)$ be the tree that is obtained by sorting $T((r\oplus 1)\ominus 1)$. Since $T((s\oplus 1)\ominus 1)$ has the same spine structure as $T((r\oplus 1)\ominus 1)$, and the length of the spine starting at the root is the same for both trees, after sorting $T((s\oplus 1)\ominus 1)$ must also be equivalent to $T(u)$. Since sorts are performed using only left subtree switches, by Lemma \ref{leftswitch} the pattern represented by $T((r\oplus 1)\ominus 1)$ is equipopular to the pattern represented by $T(u)$, as is the pattern represented by $T((s\oplus 1)\ominus 1)$. So $(r\oplus 1)\ominus 1$ is equipopular to $(s\oplus 1)\ominus 1$. By Theorem \ref{scaffold}, $r$ and $s$ must be equipopular. But $r$ is equipopular to $p$ and $s$ is equipopular to $q$, so $p$ and $q$ are equipopular as desired.   

\end{proof}

We have computed the popularity for patterns of length $k\le 7$ and a few $n$, and thus proved the following corollary.

\begin{corollary}
If $p$ and $q$ are equipopular length-$k$ patterns, with $k\le 7$, then $T(p)$ and $T(q)$ have the same spine structure. 
\end{corollary}

\begin{proof}
A Python program computing the popularity of patterns $p$ of length $k\le7$ confirms that, for all $p$ and $q$ with different spine structures, there is a sufficiently large $n$ such that $A_n(p)\neq A_n(q)$. If $n_k$ is the least integer such that $A_{n_k}(p)\neq A_{n_k}(q)$ for any two length-$k$ patterns $p$ and $q$ with different spine structures, we have $n_4=5$, $n_5=6$, $n_6=8$, and $n_7=9$.
\end{proof}

\section{Conclusion and Future Work}
\label{conclusion}

We have shown that if the trees $T(p)$ and $T(q)$ have the same spine structure, then $p$ and $q$ are equipopular. The converse remains open. The results of this paper allow us to divide length-$k$ patterns into a relatively small number of equivalence classes based on the spine structure of the tree they map to. However, the possibility remains that some of those equivalence classes may be equivalent to each other.  

We have experimentally determined the popularity of all patterns of length $k\le7$ for relatively small $n$. We've computed enough values for $n$ to determine that all of the popularity classes predicted by the main theorem are distinct. In other words, for patterns of length up to $7$ the main theorem of this paper completely classifies $132$-avoiding permutations into equipopularity classes. Based this evidence, we conjecture that the equivalence classes proved in this paper are the smallest possible in general.

\begin{conjecture}
If $p$ and $q$ are equipopular, then $T(p)$ and $T(q)$ have the same spine structure. 
\label{smallest}
\end{conjecture}

In other words, if $p$ and $q$ map to partitions of different shape, then they are not equipopular and thus the equivalence classes corresponding to partitions of different shapes are different. 

\begin{corollary}
If Conjecture \ref{smallest} is true, then the number of equivalence classes for length-$k$ patterns is the number of partitions of $k$.
\end{corollary}

\begin{proof}
The conjecture states that each spine structure corresponds to exactly one equipopularity class. But a spine structure of a tree for a length-$k$ pattern is just a partition of $k$. Since every possible partition of $k$ can be a spine structure of a tree $T(p)$, the number of equivalence classes is the number of partitions of $k$.
\end{proof}

We also observe that, in our experiments, the relative order of the popularity of equipopularity classes corresponds to a partial ordering of the spine structures of the trees, called the \emph{refinement order}. Since a spine structure can be viewed as a partition, we state this order in terms of partitions. 

A partition $\lambda_a=\{a_1,a_2,\ldots ,a_r\}$ is less than the partition $\lambda_b=\{b_1,b_2,\ldots ,b_s\}$ in refinement order if $\lambda_b$ can be obtained from $\lambda_a$ by combining parts of $\lambda_a$, that is, if each $b_i$ is a sum of one or more $a_j$'s such that each $a_j$ is used exactly once.

\begin{example}
The partition $\{2,1,1\}$ of $4$ is less than $\{2,2\}$ in refinement order, because the two $1$'s can be combined into a $2$. $\{2,1,1\}$ is also less than $\{3,1\}$ in refinement order, by combining a $1$ and a $2$ to obtain the $3$. The partitions $\{2,2\}$ and $\{3,1\}$ are incomparable in this partial order. 
\end{example}

We conjecture that the order of the popularity of the equivalence classes follows the refinement order of the spine structures of their trees.

\begin{conjecture}
Given patterns $p$ and $q$, $A_n(p)\le A_n(q)$ for all $n$ if and only if the spine structure of $T(p)$ is less than or equal to the spine structure of $T(q)$ in refinement order.
\label{order}
\end{conjecture}

%\begin{definition}[Refinement Order]
%%The lexicographic order is an ordering of partitions of $k$. Given two partitions $\lambda_a=\{a_1,a_2,\ldots a_r\}$ and $\lambda_b=\{b_1,b_2,\ldots b_r\}$, with the $a_i$ and $b_i$ sorted in descending order, then let $j=1$. 
%%\begin{itemize}
%%\item if $a_j>b_j$, then $\lambda_a>\lambda_b$
%%\item if $a_j<b_j$, then $\lambda_a<\lambda_b$
%%\item if $a_j=b_j$, then increase $j$ by one and repeat the comparison.
%%\end{itemize}
%%If $a_j=b_j$ for all $j$ than $\lambda_a=\lambda_b$. 
%The partition $\lambda_a=\{a_1,a_2,\ldots ,a_r\}$ is less than the partition $\lambda_b=\{b_1,b_2,\ldots ,b_s\}$ in refinement order if each $b_i$ 
%\end{definition}
%
%\begin{example}
%The partitions of $4$, in lexicographic order from least to greatest, are $\{1,1,1,1\}$, $\{2,1,1\}$, $\{2,2\}$, $\{3,1\}$, $\{4\}$.
%\end{example}
%
%We conjecture that the order of the popularity of the equivalence classes is the same as the lexicographic order of the spine structures of their trees.
%
%\begin{conj}
%Given patterns $p$ and $q$, $A_n(p)\le A_n(q)$ for all $n$ if and only if the spine structure of $T(p)$ is less than or equal to the spine structure of $T(q)$ in lexicographic order.
%\label{order}
%\end{conj}
%
%We note that Conjecture \ref{order}, if true, implies Conjecture \ref{smallest}. 

This conjecture is supported by our calculations of the popularity of patterns with length up to $7$. It makes intuitive sense as well. B\'{o}na \cite{Bona1} proved previously that the increasing pattern of length $k$ is the least popular and the decreasing pattern is the most popular, for all $k$. The structure of $132$-avoiding permutations suggests that the closer a pattern is to being decreasing, the more popular it should be, and vice versa. The spines in the tree $T(p)$ represent decreasing subsequences of the pattern $p$, so in imprecise terms, longer spines give rise to a pattern that is ``closer'' to being completely decreasing, which suggests that the pattern should be more popular. 

The original question of Cooper was more broad: what can be said about the popularity of patterns in $S_n(p)$ for other $p$ than $132$? First, note that the other non-monotone length-$3$ patterns, $231$, $312$, and $213$ are the reverse, complement, and reverse-complement of $132$ respectively. So our result for $S_n(132)$ can be transformed into a symmetric result for any of the other patterns by taking the reverse or complement of the above results. Homberger \cite{Hom} has a result on the popularity of length-$3$ patterns in $S_n(123)$, which symmetrically applies to $S_n(321)$. Results on the popularity of longer patterns in $S_n(132)$, or popularity in $S_n(p)$ for patterns $p$ of length greater than $3$ would be interesting. 

\section{Acknowledgments}
This research was performed at the University of Minnesota Duluth under the supervision of Joe Gallian and supported by the National Science Foundation (grant number DMS-1062709) and the National Security Agency (grant number  H98230-11-1-0224). Many thanks to Eric Riedl, David Rolnick, and Adam Hesterberg for discussing the problem with me and reading the paper. Thanks also to all of the visitors and program participants in the 2012 Duluth REU.

%\bibliography{project-bib}{}
%\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{Bona1} Miklos B\'{o}na. \newblock The Absence of a Pattern and the Occurrences of Another. \newblock {\em Discrete Mathematics \& Theoretical Computer Science}, 14(2), 2010.

\bibitem{Bona2} Miklos B\'{o}na. \newblock Surprising symmetries in Objects Counted by Catalan Numbers. \newblock {\em Electronic Journal of Combinatorics}, 19(1), 2012.

\bibitem{Cooper} Joshua Cooper. \newblock Combinatorial Problems I Like. \newblock  \url{http://www.math.sc.edu/~cooper/combprob.html}, 2012

\bibitem{Hom} Cheyne Homberger. \newblock  Expected Patterns in Permutation Classes. \newblock \arxiv{1206.0320v2} 12 Jul 2012. 

\bibitem{bsv} Miklos B\'{o}na, Bruce Sagan, Vincent Vatter. \newblock Frequency sequences with no internal zeros. \newblock {\em Adv. Appl. Math}, 28 (2002) 395-420. 

\end{thebibliography}

\end{document}


%In the tree $T(p)$, we know that all the elements in the left subtree of $a$ have lower label than $a$ and come before $a$. Any other node in $T(p)$ which comes before $a$ must have a higher label than $a$. So the nodes in the left subtree of $a$ represent the contiguous subsequence of elements before index $i$ in $p$ which are less than the element at index $i$. Call this subsequence, including index $i$, $\alpha$. Similarly define the subsequence of $p$ using the node $b$ to be the elements to the left of and including index $j$ which are less than or equal to the element at index $j$, and call this $\beta$. Let $\gamma_1$ be the subsequence of $p$ before $\alpha$, $\gamma_2$ be the subsequence between $\alpha$ and $\beta$, and $\gamma_3$ be the subsequence after $\beta$. 

%When we switch the left subtrees of $a$ and $b$ to obtain $q$, many subsequences of $p$ do not change their pattern but only move around. Given two elements $r$ and $s$ of a $p$ pattern, they are either in a $12$ pattern or a $21$ pattern. If $r$ and $s$ were both in some $\gamma_i$, then the subtree switch does not affect their relative order and they stay in the same pattern, $12$ or $21$. If both $r$ and $s$ are in $\alpha$ or both $r$ and $s$ are in $\gamma$, after the switch to $q$ they have the same relative order since nothing is moved around in the subtrees. If $r$ is in $\alpha$ and $s$ is in $\beta$, then $r>s$.