\documentclass[12pt]{article} % preamble \usepackage{e-jc} \specs{P43}{19(3)}{2012} \sloppy \usepackage{amsthm,amssymb,amsmath} \usepackage{enumerate} \usepackage{graphicx} \usepackage{float} \usepackage{subfig} \usepackage{tikz} % theorem stuff \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{fact}[theorem]{Fact} \newtheorem{example}[theorem]{Example} % commands \newcommand{\C}{\mathcal{C}} \newcommand{\Avns}{\Av_n^*(123)} \newcommand{\Avn}{\Av_n(123)} \newcommand{\Avnn}{\Av_n (132)} \newcommand{\bt}[2]{ \begin{#1} {#2} \end{#1}} \newcommand{\Z}{\mathbb{Z}_+} \newcommand{\ds}{\displaystyle} \newcommand{\D}{\mathcal{D}} \newcommand{\ra}{\rightarrow} \newcommand{\R}{\mathcal{R}} \newcommand{\B}{\mathcal{B}} \DeclareMathOperator{\Av}{Av} \DeclareMathOperator{\num}{f} \DeclareMathOperator{\Sp}{Span} \title{\bf Expected Patterns in Permutation Classes} \author{Cheyne Homberger \\ \small Department of Mathematics \\[-0.8ex] \small University of Florida \\[-0.8ex] \small Gainesville, FL \\ \small\tt cheyne42@ufl.edu } \date{\dateline{Jul 7, 2012}{Sep 17, 2012}{Oct 4, 2012}\\ \small Mathematics Subject Classifications: 05A05, 05A15} %===================================================================% \begin{document} % title and abstract \maketitle \begin{abstract} Each length $k$ pattern occurs equally often in the set $S_n$ of all permutations of length $n$, but the same is not true in general for a proper subset of $S_n$. Mikl\'os B\'ona recently proved that if we consider the set of $n$-permutations avoiding the pattern 132, all other non-monotone patterns of length 3 are equally common. In this paper we focus on the set $\operatorname{Av}_n (123)$ of $n$-permutations avoiding $123$, and give exact formulae for the occurrences of each length 3 pattern. While this set does not have the same symmetries as $\operatorname{Av}_n (132)$, we find several similarities between the two and prove that the number of 231 patterns is the same in each. \end{abstract} %===================================================================% \section{Background} Let $p = p_1 p_2 \ldots p_n$ be a permutation in the symmetric group $S_n$ written in one-line notation. Given a permutation $q \in S_k$, say that $p$ contains $q$ as a pattern if there exist indices $ 1 \leq i_1 \leq i_2 \leq \ldots \leq i_k \leq n$ such that the entries $p_{i_1} p_{i_2} \ldots p_{i_k}$ are in the same relative order as the entries of $q$ (that is, $q_j < q_k$ if and only if $p_{i_j} < p_{i_k}$). If $p$ does not contain $q$ as a pattern, we say that $p$ \emph{avoids} $q$. The set of all permutations equipped with this ordering can be viewed as a partially ordered set which is graded with respect to permutation length. With this in mind, we define a \emph{permutation class} to be a downset (or ideal) of this poset. That is, a class is a collection of permutations $\C$ for which, if $p \in \C$ and $q$ is contained in $p$, then $q \in \C$. Given a pattern $q$, the set $\Av (q)$ of all permutations avoiding $q$ forms a permutation class, and much study has been devoted to understanding and enumerating classes of this form. An early result in the area from Knuth \cite{knuth3}, is that the number of $n$-permutations avoiding the pattern $231$ is equal to the Catalan number $c_n = \frac{1}{n+1} \binom{2n}{n}$, and these are exactly the stack sortable permutations. A more comprehensive introduction to permutation patterns can be found in \cite{bonabook}. A question of Joshua Cooper and a recent result of Mikl\'os B\'ona have opened up a new line of research: in the set of all permutations of length $n$ in a given permutation class, what can be said about the average number of occurrences of each pattern? or equivalently: what is the total number of occurrences of each pattern in this set? It is simple to show that in the set of all permutations, all patterns of a given length are equally common. The situation becomes much more complex as we restrict our attention to proper subclasses. %===================================================================% \section{Preliminaries} \begin{definition} Let $p,q$ be permutations. Denote by $\num_{q}(p)$ the number of occurrences of $q$ in $p$ as a pattern. \end{definition} For example, $\num_{213}(462513) = 2$ since the first, third, and fourth entries as well as the third, fifth, and sixth entries form $213$ patterns. Also, for any permutation $p$, $\num_{21}(p)$ counts the number of inversions of $p$. Note that every permutation statistic can be expressed through combinations of counts of permutation patterns, as described in \cite{claesson11}. We shall be concerned primarily with the total number of patterns in a set of permutations. For simplicity, we use similar notation. \begin{definition} For an integer $n$ and a permutation class $\mathcal{C}$, let $\mathcal{C}_n$ denote the set of permutations of length $n$ in $\mathcal{C}$. For a pattern $q$, define $\num_{q}(\mathcal{C}_n)= \sum_{p \in \mathcal{C}_n} \num_q(p)$. We will omit the $\mathcal{C}_n$ when the set in question is unambiguous. \end{definition} \begin{example} \label{linearity} Let $q \in S_k$. Then it follows by linearity of expectation that $$\num_q(S_n) = \frac{n!}{k!} \binom{n}{k}.$$ \end{example} The Catalan numbers will appear frequently in our enumeration, and so it will be useful to establish some standard notation and a few simple identities. \begin{definition} Let $c_n = \frac{1}{n+1} \binom{2n}{n}$ denote the $n$th Catalan number. Also, let $$ C(x) = \sum_{n\geq 0} c_n x^n = \frac{1 - \sqrt{1-4x}}{2x}.$$ \end{definition} \begin{fact} The following identities follow directly from the recurrence $C(x) = xC(x)^2 +1$. $$ C(x)^2 = \frac{C(x)}{1-xC(x)} = \frac{1}{(1-xC(x))^2} \text{ \ and \ } \frac{C(x)-1}{C(x)} = xC(x).$$ \end{fact} In \cite{bona10} and \cite{bona12}, Mikl\'os B\'ona studied the class $\Av (132)$ and found some surprising symmetries. He also gave exact formula and generating functions for the expectation of all length three patterns. In this paper we give a similar classification of the class $\Av (123)$, with some equally surprising connections to $\Av (132)$. Because both $132$ and $123$ are involutions and $231^{-1} = 312$, we have the following identity. Further identities, however, require considerably more effort. \begin{fact} In both $\Avnn$ and $\Avn$, $\num_{231} = \num_{312}$. \end{fact} For a fixed integer $k$, in each of the sets $\Avnn$ and $\Avn$ inversion provides a bijection from the set of permutations containing exactly $k$ $231$ patterns to the set containing exactly $k$ $312$ patterns. This proves not only that the total number of each pattern is the same, but that these numbers are equidistributed in each set. B\'ona showed that equidistribution is not required for the total number of patterns to be equal. \begin{theorem}[B\'ona] \label{bonasthm} In $\Avnn $, the total numbers of $231$, $213$, and $312$ patterns are equal, and their numbers, with respect to $n$, are given by the generating function $$ \frac{x^2C(x)^3}{(1-2xC(x))(1-4x)^{3/2}}.$$ Furthermore, $321$ is the most common pattern and $123$ is the least common. \end{theorem} The first few values of $\num_q(\Avn)$ and $\num_q(\Avnn)$ for $q$ of length $3$ are shown in the table below $$ \begin{array}{c|c|c|c|c|c|c} \multicolumn{7}{c}{\Avn } \\ \text{length} & \num_{123} & \num_{132} & \num_{213} & \num_{231} & \num_{312} & \num_{321} \\ \hline 3 & 0 & 1 & 1 & 1 & 1 & 1 \\ 4 & 0 & 9 & 9 & 11 & 11 & 16 \\ 5 & 0 & 57 & 57 & 81 & 81 & 144 \\ 6 & 0 & 312 & 312 & 500 & 500 & 1016 \\ 7 & 0 & 1578 & 1578 & 2794 & 2794 & 6271 \end{array} $$ \vspace{1pc} $$ \begin{array}{c|c|c|c|c|c|c} \multicolumn{7}{c}{\Avnn } \\ \text{length} & \num_{123} & \num_{132} & \num_{213} & \num_{231} & \num_{312} & \num_{321} \\ \hline 3 & 1 & 0 & 1 & 1 & 1 & 1 \\ 4 & 10 & 0 & 11 & 11 & 11 & 13 \\ 5 & 68 & 0 & 81 & 81 & 81 & 109 \\ 6 & 392 & 0 & 500 & 500 & 500 & 748 \\ 7 & 2063 & 0 & 2794 & 2794 & 2794 & 4570 \end{array} $$ \vspace{1pc} Note that $\num_{231}$ and $\num_{312}$ are not equidistributed as statistics in $\Avnn$. Theorem \ref{bonasthm} was proved with a bijection from patterns to patterns, not necessarily respecting the underlying permutation. Turning our attention to the class $\Av(123)$, we will similarly classify the expectation of all length $3$ patterns and provide both generating functions and exact formula. In addition, we show some interesting and surprising connections to patterns in $\Av(132)$. In particular, we will show that there are an equal number of $231$ patterns in $\Avn$ and $\Avnn$, as suggested by the numerical evidence. %===================================================================% \section{The class $\Av(123)$} \subsection{Patterns of length $2$} The simplest place to start is with patterns of length $2$. The number of $12$ patterns corresponds to the total number of non-inversions, and these numbers have already been studied, most notably in \cite{cheng7}. Clearly, the total number of $12$ patterns plus the number of $21$ patterns gives the total number of pairs of entries in all permutations in the set which, for $\Avn$, is given by $\binom{n}{2} c_n$. \begin{theorem}[Cheng, Eu, Fu] \label{inv} Let $\C_n = \Avn$. Then $$ \sum_{n \geq 0} f_{12}(\C_n) x^n = \frac{x^2 C(x)^2}{1-4x}.$$ Furthermore, we have that $$ \num_{12}(\C_n) = 4^{n-1} - \binom{2n-1}{n}.$$ \end{theorem} \begin{corollary} The number of $21$ patterns in the set of all $n$-permutations avoiding $123$ is given by $$ \num_{21}(\Avn) = \binom{n}{2} c_n + \binom{2n-1}{n} - 4^{n-1}.$$ \end{corollary} %===================================================================% \subsection{Patterns of length $3$} We turn our attention now to patterns of length $3$, and provide a similar classification. To start, using the fact that $123$ is an involution and is fixed under reverse complementation provides some immediate identities, as these provide bijections from $\Avn$ to itself. \begin{fact} In $\Avn$, $\num_{132} = \num_{213}$ and $\num_{231} = \num_{312}$. \end{fact} Numerical data and intuition suggest that $\num_{132} < \num_{231} < \num_{321}$. We begin by establishing some basic relationships between these numbers which will eventually combine to give us exact formulae. First, note that the total number of all length $k$ patterns is exactly $\binom{n}{k} c_n$. For $k = 3$ this gives the following fact. \begin{fact} \label{relation1} In the set $\Avn$ we have that $$ \num_{132} + \num_{213} + \num_{231} + \num_{312} + \num_{321} = \binom{n}{3} c_n.$$ Note that since $\num_{132} = \num_{213}$ and $\num_{312} = \num_{231}$, we can rewrite this as $$ 2 \num_{132} + 2 \num_{231} + \num_{321} = \binom{n}{3}c_n.$$ \end{fact} Our next uses Theorem \ref{inv} to provide another linear relationship between these three numbers. \begin{proposition} \label{relation2} In the set $\Avn$, we have % $$(n-2)\num_{12} - (\num_{132} + \num_{213}) = % \num_{132}+\num_{213}+\num_{231}+\num_{312} .$$ % This can be rewritten as $$ 4 \num_{132} + 2 \num_{231} = (n-2)\num_{12}.$$ \end{proposition} \begin{proof} Rewrite the equation as $$(n-2)\num_{12} - (\num_{132} + \num_{213}) = \num_{132}+\num_{213}+\num_{231}+\num_{312} .$$ We claim that both sides count the total number of length $3$ patterns which contain at least one $12$ pattern. Indeed, the right hand side counts all length $3$ patterns other than $321$. The left hand side first takes a $12$ pattern and adds another entry to it. However, this double counts each triple which has two $12$ patterns, and these are exactly the patterns $132$ and $213$. Subtracting these off yields the desired identity. \end{proof} Note that we now have two linear relationships between the three unknown quantities, and so some new information would completely solve the system. We summarize this in the following lemma. \begin{lemma}\label{linsys} Let $\C = \Avn$, and let $a_n = \num_{132}(\C) = \num_{213}(\C)$, $b_n = \num_{231}(\C) = \num_{312}(\C)$, and $d_n = \num_{321}(\C)$. Then we have $$ \begin{array}{ll} 2a_n + 2b_n + d_n & = \binom{n}{3} c_n \\ 4a_n + 2b_n & = 4^{n-1} - \binom{2n-1}{n}. \end{array} $$ \end{lemma} We note that Proposition \ref{relation2} has a complementary analogue, obtained by counting inversions instead of non-inversions. However, this leads to a relation which is linearly dependent on the first two. It takes a new approach to yield new information, which requires a few new definitions. \begin{definition} A permutation $p = p_1p_2 \ldots p_n$ is \emph{decomposable} (sometimes referred to as skew-decomposable) if there exists $k \in [n]$ such that for all $i \leq k$ and all $j > k$, we have that $p_i > p_j$. An \emph{indecomposable} permutation is one for which no such $k$ exists. \end{definition} \begin{definition} Denote the set of all indecomposable $123$-avoiding permutations by $\Av^* (123)$, and $\Av^* (123) \cap S_n$ by $\Avns$. \end{definition} In general, for simplicity of notation, indecomposability will be denoted with a star. Our first step, naturally, is to find the size of the set $\Avns$. \begin{proposition} For all $n \geq 1$, $$|\Avns| = \frac{1}{n} \binom{2n-2}{n-1} = c_{n-1}.$$ \end{proposition} \begin{proof} We know that $|\Avn| = c_n$, so $$ \sum_{n \geq 0} |\Avn| x^n = \frac{1 - \sqrt{1 - 4x}}{2x} = C(x).$$ Let $C^*(x) = \sum_{n\geq 1} |\Avns| x^n$. Every permutation in $\Avn$ can be expressed as a skew sum of indecomposable $123$-avoiding permutations, so it follows that $$ C(x) = 1 + C^*(x) + (C^*(x))^2 + (C^*(x))^3 + \ldots = \frac{1}{1-C^*(x)}.$$ Solving this algebraically gives that $C^*(x) = \frac{C(x)-1}{C(x)} = xC(x)$, which finishes the proof. \end{proof} % \begin{definition} % For a permutation $p \in S_n$, let $i(p)$ denote the number of % inversions (or $21$) patterns in $p$, and let $v(p) = \binom{n}{2} % - i(p)$ denote the number of $12$ patterns. % \end{definition} Lemma \ref{linsys} now has an immediate indecomposable analogue, and for all integers $n$ and each pattern $q$ the numbers $\num_q \left(\Avn\right)$ and $\num_q \left( \Avns \right)$ can be related easily. However, this alone does not allow us to solve for an exact formula. Our new information will come from exactly counting the number of $213$ patterns in the set $\Avns$ by building a bijection to Dyck paths. We start by defining these paths, which are counted by the Catalan numbers. \begin{definition} A \emph{Dyck path} of length $2n$ (or of semilength $n$) is defined as a sequence of steps from the set $\{(1,1),(-1,1)\}$ which begins at $(0,0)$, ends at $(2n,0)$, and never steps below the line $x=0$. % An \emph{elevated Dyck path} is one which never steps below the % line $x=1$, except for the first and last step. \end{definition} \begin{lemma} \label{biglemma} The generating function $A^*(x)$ for the number of $213$ patterns in $\Avns$ is given by $$ A^*(x) = \sum_{n\geq 0} \num_{213}(\Avns) = \frac{x^3C(x)}{(1-4x)^{3/2}} = \frac{x^2}{2(1-4x)^{3/2}} - \frac{x^2}{2(1-4x)}.$$ \end{lemma} \begin{proof} The proof consists of three parts: First, we examine the structure of permutations in $\Avns$, and find a simple way of counting the number of $213$ patterns. Second, we build a bijection onto Dyck paths which maps $213$ patterns to a path statistic. Finally, we find the weighted sum of all Dyck paths with respect to this statistic. % The idea of the proof is as follows: We build a bijection from the % set of permutations $\Avns$ to the set $\D$ of elevated Dyck % paths of semilength $n$, find a statistic on these paths which % corresponds to $213$ patterns, and then find the weighted sum of % all dyck paths with respect to this statistic. Fix $n$, and let $p$ be a permutation in $\Avns$. Note that since $p$ avoids $123$, it can be viewed as a union of two descending sequences, so every entry in $p$ is a left-to-right minima or a right-to-left maxima, and by indecomposability no entry is both. Graph $p$ on an $n \times n$ lattice by plotting $(i,p(i))$ for each $i \in [n]$, and color each left-to-right minima red and each right-to-left maxima blue. Denote the sequence of red entries (ordered from left to right) by $\R=(r_1,r_2,\ldots r_j)$, and the sequence of blue entries by $\B=(b_1,b_2,\ldots b_k)$. Denote by $\Sp b_i$ the number of red entries below and to the left of $b_i$. Note that $\Sp b_i \geq 1$ for all $b_i$ by indecomposability. Now, we count the number of $213$ patterns in $p$. It follows that for any such pattern $q$, the $2$ entry and $1$ entry must be red, and the $3$ entry blue. It is also clear that each blue entry is contained in $\binom{\Sp b_i}{2}$ $213$ patterns. Therefore we have that $$ \num_{213} (p) = \sum_{i=1}^{k} \binom{\Sp b_i}{2}.$$ Now we are ready to build our bijection $\phi: \Avns \ra \D_{n-1}$, where $\D_{n-1}$ denotes the set of Dyck paths of semilength $n-1$. From each blue vertex, extend a vertical line to the $x$-axis and a horizontal line to the $y$-axis, and color each point of intersection of these lines green. Define a path $P'$ from $(1,n)$ to $(n,1)$ by the following rules: \begin{enumerate}[1)] \item Begin by walking east from $(1,n)$ \item At a blue vertex, turn south and continue walking \item At a green vertex, turn east and continue walking \item End at $(n,1)$ \end{enumerate} Rotate the path $P'$ by $\pi/4$ radians counter-clockwise to obtain a Dyck path $P$. This path is a slight modification of the path given by Krattenthaler's bijection \cite{krat01}, taking advantage of the indecomposability of the permutation to yield a more geometric description. This geometric interpretation of the bijection gives some additional insight into the number of $213$ patterns. % \begin{figure} % \centering \label{permtopath} % \mbox{ % \subfloat{\includegraphics[width=1.5in]{pictures/permtopath}} % \quad % \subfloat{\includegraphics[width=2in]{pictures/path}} % } % \caption{$\phi(4762513) = UDUDUUDDUUDD$} % \end{figure} % \begin{figure}[ht] % \centering % \includegraphics[width=2.5in]{pictures/permtopath} % \caption{$\phi(4762513) = UDUDUUDDUUDD$} % \end{figure} \begin{figure}[ht] \centering \label{permtopath} \subfloat{ \fbox{ \begin{tikzpicture} [scale=.6, auto=center, every node/.style={circle, fill=black, inner sep=2pt, minimum size=2pt}] \foreach \x/\y in {1/4,2/7,3/6,4/2,5/5,6/1,7/3}{ \node (p-\x) at (\x,\y) {}; } \end{tikzpicture} } } \subfloat{ \fbox{ \begin{tikzpicture} [scale=.6, auto=center] \foreach \x/\y in {1/4,4/2,6/1}{ \node[circle,fill=black,inner sep=2pt, minimum size=2pt] (r\x) at (\x,\y) {}; } \foreach \num/\x/\y in {1/2/7,2/3/6,3/5/5,4/7/3}{ \node[circle,fill=black,inner sep=2pt, minimum size=2pt] (b\num) at (\x,\y) {};} \foreach \num/\x/\y in {1/1/7,2/2/6,3/3/5,4/5/3,5/7/1}{ \node[circle,fill=black, inner sep=0pt, minimum size=0pt] (g\num) at (\x,\y) {};} \foreach \to/\from in {g1/b1,b1/g2,g2/b2,b2/g3, g3/b3,b3/g4,g4/b4,b4/g5}{ \draw (\to) -- (\from);} \end{tikzpicture} } } \\ \subfloat{ \fbox{ \begin{tikzpicture} [scale=.5, auto=center] \draw (0,0) -- (1,1); \draw (1,1) -- (2,0); \draw (2,0) -- (3,1); \draw (3,1) -- (4,0); \draw (4,0) -- (6,2); \draw (6,2) -- (8,0); \draw (8,0) -- (10,2); \draw (10,2) -- (12,0); \end{tikzpicture} } } \caption{$\phi(4762513) = UDUDUUDDUUDD$} \end{figure} Note that each blue entry in $p$ produces a peak in $P$. Furthermore, $b_i$ corresponds to a peak of height $\Sp b_i$ above the $x$-axis in $P$. Therefore, if we let $h_{n,k}$ denote the total number of peaks of height $k$ in all Dyck paths of semilength $n$, we have that $$ \num_{213}(\Avns) =\sum_{k = 1}^{n-1} \binom{k}{2} h_{n-1,k}.$$ Finally, we can compute $H(x,u) = \sum_{n,k \geq 0} h_{n,k} x^n u^k$ as follows. First, note that since each Dyck path begins with an upstep it has a unique first point at which the path returns to the $x$-axis, so we can decompose each path $P$ of length $n$ into the concatenation of two shorter paths $Q$ and $R$. This gives that $P = uQdR$, where $u$ denotes an upstep and $d$ a downstep, and each peak of height $k-1$ in $Q$ and height $k$ in $R$ leads to a peak of height $k$ in $P$. With this in mind, we have the following generating function relation: $$ H(x,u) = ux(H(x,u)+1)C(x) + xH(x,u)C(x) .$$ Here the first term counts the peaks from the $uQd$ part, including the case when $Q$ is empty. The second term counts the contribution from the $R$ part. Rearranging leads to $$ H(x,u) = \frac{uxC(x)}{1-uxC(x)-xC(x)}.$$ Now, to count $213$ patterns, we need to count each peak with weight $\binom{k}{2}$. By taking derivatives twice with respect to $u$, setting $u=1$, dividing by two and scaling by $x$, we find that $$ \begin{aligned} \sum_{n,k \geq 0} \binom{k}{2} h_{n-1,k}x^n & = x \frac{\left. \partial_u ^2 H(x,u)\right|_{u=1}}{2} = \frac{x^3C(x)}{(1-4x)^{3/2}} \\ & = x^3 + 7x^4 + 38x^5 + 187x^6 + 874x^7 + \ldots \ . \end{aligned} $$ The sequence $0,0,1,7,38,187\ldots$ is entry A000531 in the OEIS. Finally, the correspondence between peaks and $213$ patterns completes the proof. \end{proof} Now, it is relatively simple to move from the set of indecomposable $123$-avoiding permutations to the larger set of all $123$-avoiding permutations. \begin{theorem} \label{213pats} Let $a_n$ be the number of $213$ patterns in $\Av_n 123$. Then $$ \sum_{n\geq 0} a_n x^n = \frac{x^3C(x)^3}{(1-4x)^{3/2}} = \frac{x-1}{2(1-4x)} - \frac{3x-1}{2(1-4x)^{3/2}} .$$ \end{theorem} \begin{proof} Let $A(x)$ be the generating function for the numbers $a_n$, and let $A^*(x)$ denote the generating function for the number of $213$ patterns in \emph{indecomposable} $123$-avoiding permutations. Now, any permutation $p$ in $\Av(123)$ can be written uniquely as a skew sum of a nonempty indecomposable $123$-avoiding permutation $q$ and another, possibly empty, $123$-avoiding permutation $r$. Now, it is clear that any $213$ pattern in $p$ must be contained entirely in either $q$ or $r$. This leads to the following relation: $$ A(x) = A^*(x)C(x) + xC(x)A(x).$$ Solving for $A$ gives $$ A(x) = \frac{A^*(x) C(x)}{1-xC(x)} = C^2(x) A^*(x).$$ Lemma \ref{biglemma} now implies $$ A(x) = \frac{x^3 C(x)^3}{(1-4x)^{3/2}}.$$ % Exact formula for the numbers $a_n$ is obtained from the % generating function by expanding by partial fractions. \end{proof} Theorem \ref{213pats} combined with Lemma \ref{linsys} allows us to obtain both generating functions and exact formulae for the occurrence of all length $3$ patterns in $\Avn$. We start with $231$ patterns, which reveal a surprising connection to the class $\Av(132)$. \begin{corollary} \label{231pats} Let $b_n$ denote the number of $231$ (or $312$) patterns in all $123$-avoiding $n$-permutations. Then $$\sum_{n \geq 0} b_n x^n= \frac{3x-1}{(1-4x)^{2}} - \frac{4x^2 - 5x + 1}{(1-4x)^{5/2}}.$$ \end{corollary} \begin{proof} Let $B(x)$ be the generating function for the numbers $b_n$, let $A(x)$ be the generating function for the number of $213$ patterns, and let $j_n$ be the number of $12$ patterns with corresponding generating function $J(x)$. We know from Lemma \ref{linsys} that $$ 4A(x) + 2B(x) = \sum_{n \geq 0} (n-2) j_n x^n = (J(x)/x^2)' x^3 .$$ Solving this for $B(x)$ using elementary algebra and a bit of calculus yields $$ \begin{aligned} B(x) &= \frac{x^2C(x)^3}{(1 - 2xC(x))(1-4x)^{3/2}} \\ & = \frac{3x-1}{(1-4x)^{3/2}} - \frac{4x^2 - 5x + 1}{(1-4x)^{5/2}} \end{aligned}.$$ \end{proof} The connection between the classes $\Av(123)$ and $\Av(132)$ is now immediate. \begin{corollary} \label{bridge} Theorem \ref{231pats} together with Theorem \ref{bonasthm} imply immediately that the total number of $231$ patterns in $\Av_n (123)$ is equal to the total number of $231$ patterns in $\Av_n (132)$. \end{corollary} We can similarly apply Lemma \ref{linsys} to $321$ patterns. \begin{corollary} Let $d_n = f_{321}(\Avn)$. Then we have that $$ \sum_{n\geq 0} d_n x^n = \frac{ 8x^3 - 20x^2 + 8x - 1}{(1-4x)^{2}} - \frac{36x^3 - 34x^2 + 10x - 1}{(1-4x)^{5/2}}. $$ \end{corollary} Before analyzing these generating functions, we note also that Lemma \ref{linsys} and its indecomposable analogue produce several other interesting identities. We summarize some of them here for completeness. \begin{corollary} The following identities hold. $$ \num_{21}(\Avn) = 2\num_{213}(\Avns) $$ $$ \num_{213}(\Avn) + \num_{231}(\Avn) = \num_{231} (\Av _{n-1}^*(123))$$ $$ C(x) \left(\sum_{n\geq 0} \num_{213}(\Avn) x^n \right) = x C'(x) \left(\sum_{n \geq 0} \num_{12}(\Avn)x^n \right) $$ $$ \sum_{n\geq 0} \num_{213} (\Av_n^* (132) x^n) = \sum_{n \geq 0} \big(\num_{132}(\Avns) + \num_{231}(\Avns)\big)x^n. $$ \end{corollary} Note that each of these identities are equivalent. That is, combined with Lemma \ref{linsys}, a combinatorial proof of any of them would imply all of the others (including Lemma \ref{biglemma}). Now we can do some analysis of the main sequences. Using some standard generating function analysis \cite{flajolet}, we find that the asymptotic growth of the number of length $3$ patterns are as follows: \vspace{1pc} $$ \num_{213} (\Avn) \sim \sqrt{\frac{n}{\pi}} 4^n$$ $$ \num_{231} (\Avn) \sim \frac{n}{2} 4^n $$ $$ \num_{321} (\Avn) \sim \frac{8}{3} \sqrt{\frac{n^3}{\pi}} 4^n. $$ We see that the three sequences each differ by a factor of approximately $\sqrt{n}$. Surprisingly, this is the same factor that the sequences $\num_{123}, \num_{231}, \num_{321}$ differ by in the class $\Av (132)$, as seen in \cite{bona10}. Each of these generating functions are simple enough that exact formulas can be obtained with relatively little hassle. One could argue that the asymptotic values are more interesting and provide more insight than the complicated formulas, but we present them here for completeness. \begin{corollary} Let $a_n = \num_{132}(\Avn)$, $b_n = \num_{213}(\Avn)$, and $d_n = \num_{321}(\Avn)$. Then we have that $$ a_n = \frac{n+2}{4} \binom{2n}{n} - 3 \cdot 2^{2n-3} $$ $$ b_n = (2n-1) \binom{2n-3}{n-2} - (2n+1)\binom{2n-1}{n-1} + (n+4) \cdot 2^{2n-3}$$ $$ \begin{aligned} d_n = \frac{1}{6} \binom{2n+5}{n+1} \binom{n+4}{2} &- \frac{5}{3} \binom{2n+3}{n} \binom{n+3}{2} + \frac{17}{3} \binom{2n+1}{n-1} \binom{n+2}{2} \\ &- 6\binom{2n-1}{n-2} \binom{n+1}{2} - (n+1) \cdot 4^{n-1}. \end{aligned} $$ \end{corollary} %===================================================================% \subsection{Larger Patterns} Some of these same techniques are applicable to larger patterns. For example, we can easily modify Lemma \ref{linsys} to patterns of all sizes. This leads to increasingly complicated expressions, but this simple idea can be used to prove the following proposition. \begin{proposition} Let $k \in \mathbb{Z}^+$, and $q$ be any permutation in $S_k$ other than the decreasing permutation. Then for $n$ large enough, we have that $$\num_{k \ldots 3 2 1}(\Avn) > \num_{q}(\Avn).$$ \end{proposition} \begin{proof} Let $T$ be the set of permutation in $S_k$ which are not the decreasing permutation. As in Proposition \ref{relation2} and Fact \ref{relation1}, we can express the number $\binom{n-2}{k-2}\num_{12}(\Avn)$ as a positive linear combination of all of $\num_{q} (\Avn)$ where $q \in T$, and we can express $\binom{n}{k} c_n$ as the sum of all $\num_r (\Avn)$ where $r \in S_n$. It follows that there is a positive integer $m$ and positive integers $e_i$ such that $$ \binom{n}{k} c_n - m\binom{n-2}{k-2} \num_{12} (\Avn) = \num_{k \ldots 321} - \sum_{q \in T} e_i \num_q (\Avn).$$ Asymptotic analysis shows that the left hand side is eventually positive, and so the first term on the right side eventually outgrows the second term, which completes the proof. \end{proof} %===================================================================% \section{Further Directions} The numbers $\num_q (\Av_n (p))$ for permutations $p,q$ exhibit numerous symmetries and produce many new questions. All of the generating functions presented here and in \cite{bona10} are \emph{almost} rational, in the sense that they lie in the ring $\mathbb{Q}(x,\sqrt{1-4x})$. This allows for easy asymptotic analysis, and leaves open the possibility of bijections to other Catalan-related objects. Building on what was mentioned in \cite{bona12}, we have instances of the same sequence of numbers which correspond to sums of statistics with different distributions in objects counted by the Catalan numbers. Do these sequences and statistics have analogues in other such objects? Thus far, to the author's knowledge, the expectation of patterns has only been studied for the classes $\Av (123)$ and $\Av (132)$ (and their symmetries). Applying these ideas to more general classes could yield similarly interesting identities. Note that the increasing and decreasing permutations do not always provide the opposite extreme cases: it is simple to show that $\num_{123}(\Av_n (2413)) = \num_{321}(\Av_n(2413))$. This leads to the natural question: in the set of $n$-permutations avoiding a specific pattern (or a set of patterns), can we easily determine what pattern is most common? And how large can the difference be between the most and least common? Finally, are there other occurrences of the same sequence of patterns arising in different classes? Or within the same class, as in $\Av (132)$? Taking this to the extreme, is there a proper, non-trivial permutation class for which each pattern of a given length is equally as common, as in the class of all permutations? Various computer searches have yet to produce any similarly unexpected coincidences. %In particular, searches on patterns of length less than $8$ in permutations avoiding length $4$ patterns have uncovered no nontrivial symmetries. In particular, searches on patterns of length 3 in permutations avoiding length 4 patterns have uncovered no nontrivial symmetries. % \nocite{*} % \bibliographystyle{plain} % \bibliography{expat} %===================================================================% \begin{thebibliography}{1} \bibitem{bonabook} Mikl{\'o}s B{\'o}na. \newblock {\em Combinatorics of permutations}. \newblock Discrete Mathematics and its Applications (Boca Raton). Chapman \& Hall/CRC, Boca Raton, FL, 2004. \newblock With a foreword by Richard Stanley. \bibitem{bona10} Mikl{\'o}s B{\'o}na. \newblock The absence of a pattern and the occurrences of another. \newblock {\em Discrete Math. Theor. Comput. Sci.}, 12(2):89--102, 2010. \bibitem{bona12} Mikl{\'o}s B{\'o}na. \newblock Surprising symmetries in objects counted by {C}atalan numbers. \newblock {\em Electron. J. Combin.}, 19(1):Paper 62, 12, 2012. \bibitem{claesson11} Petter Br{\"a}nd{\'e}n and Anders Claesson. \newblock Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. \newblock {\em Electron. J. Combin.}, 18(2):Paper 5, 14, 2011. \bibitem{cheng7} Szu-En Cheng, Sen-Peng Eu, and Tung-Shan Fu. \newblock Area of {C}atalan paths on a checkerboard. \newblock {\em European J. Combin.}, 28(4):1331--1344, 2007. \bibitem{claesson8} Anders Claesson and Sergey Kitaev. \newblock Classification of bijections between 321- and 132-avoiding permutations. \newblock In {\em 20th {A}nnual {I}nternational {C}onference on {F}ormal {P}ower {S}eries and {A}lgebraic {C}ombinatorics ({FPSAC} 2008)}, Discrete Math. Theor. Comput. Sci. Proc., AJ, pages 495--506. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008. \bibitem{flajolet} Philippe Flajolet and Robert Sedgewick. \newblock {\em Analytic combinatorics}. \newblock Cambridge University Press, Cambridge, 2009. \bibitem{knuth3} Donald~E. Knuth. \newblock {\em The art of computer programming. {V}olume 3}. \newblock Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. \newblock Sorting and searching, Addison-Wesley Series in Computer Science and Information Processing. \bibitem{krat01} C.~Krattenthaler. \newblock Permutations with restricted patterns and {D}yck paths. \newblock {\em Adv. in Appl. Math.}, 27(2-3):510--530, 2001. \newblock Special issue in honor of Dominique Foata's 65th birthday (Philadelphia, PA, 2000). \end{thebibliography} \end{document}