\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}

