\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{multirow}
\usepackage{mathrsfs}
\usepackage{cases}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
Pattern Popularity in Multiply Restricted \\
\vskip .11in
Permutations 
}
\vskip 1cm
\large
Alina F. Y. Zhao\\
School of Mathematical Sciences and Institute of Mathematics \\
Nanjing Normal University\\
Nanjing 210023\\
PR China\\
\href{mailto:alinazhao@njnu.edu.cn}{\tt alinazhao@njnu.edu.cn}\\
\end{center}

\vskip .2 in

\def \C{{\mathcal{C}}}
\def \sg {{\sigma}}
\def \maj {{\mathrm{maj}}}
\def \asc {{\mathrm{asc}}}

\vskip .2 in

\begin{abstract}
We derive explicit formulae or generating functions for the
popularity of all the length-$3$ patterns in multiply restricted
permutations, and provide combinatorial interpretations for some
non-trivial equipopular patterns as well.
\end{abstract}

\section{Introduction}

Let $\sg=\sg_1\sg_2\cdots \sg_n$ be a permutation in the symmetric
group $S_n$. We say that $\sg$ {\it contains a pattern}
$q=q_1q_2\cdots q_k\in S_k$ if there exist $1\leq i_1<i_2< \cdots
< i_k \leq n$ such that the entries $\sg_{i_1}\sg_{i_2}\cdots
\sg_{i_k}$ have the same relative order as the entries of $q$,
i.e., $q_j < q_l$ if and only if $\sg_{i_j} < \sg_{i_l}$ whenever
$1\leq j,l\leq k$. We say that $\sg$ avoids $q$ if $\sg$ does not
contain $q$ as a pattern. A permutation may contain multiple
copies of a pattern. For example, permutation $43512$ contains two
copies of pattern $321$, namely $431$ and $432$, but avoids
pattern $123$.

For a pattern $q$, let $S_n(q)$ denote the set of all permutations
in $S_n$ that avoid the pattern $q$, and for $R\subseteq S_k$, let
$S_n(R)= \bigcap_{q\in R}S_n(q)$ be the set of permutations in
$S_n$ that avoid every pattern contained in $R$. For two
permutations $\sg$ and $q$, we set $f_q(\sg)$ to be the number of
copies of $q$ in $\sg$ as a pattern. The {\it popularity} of
pattern $q$ in $S_n(R)$ is defined as
\[f_q(S_n(R))=\sum_{\sg\in S_n(R)}f_q(\sg).\]
We say that $p$ and $q$ are equipopular if $f_p(S_n(R))=
f_q(S_n(R))$ for all $n$.

The \emph{complement} of $\sg$ is given by
$\sg^c=(n+1-\sg_1)(n+1-\sg_2)\cdots (n+1-\sg_n)$, its
\emph{reverse} is defined as $\sg^r=\sg_n\cdots \sg_2\sg_1$ and
the \emph{inverse} $\sg^{-1}$ is the regular group-theoretic
inverse permutation. For any set of permutations $R$, let $R^c$ be
the set obtained by complementing each element of $R$, and the
sets $R^r$ and $R^{-1}$ are defined analogously. It is well known
that
\begin{lemma}\label{oper}
Let $R\subseteq S_k$ be any set of permutations in $S_k$, and $\sg
\in S_n$, we have
\[ \sg\in S_n(R)\Leftrightarrow \sg^c\in S_n(R^c)\Leftrightarrow \sg^r\in S_n(R^r)\Leftrightarrow \sg^{-1}\in S_n(R^{-1}).\]
\end{lemma}


Cooper \cite{Coo} first raised the problem of determining the
total number $f_q(S_n(r))$, and B\'{o}na \cite{Bona2010} derived
the generating function of the sequence $(f_q(S_n(132)))_{n\geq
1}$ for monotone pattern, i.e., $q=12\cdots k$ or $q=k(k-1)\cdots
2 1$. Further, B\'{o}na \cite{Bona} studied the generating
functions for other length-$3$ patterns in $S_n(132)$, and showed
both algebraically and bijectively that
\[
f_{231}(S_n(132)) = f_{312}(S_n(132))=f_{213}(S_n(132)).
\]

According to the correspondence between $132$-avoiding
permutations and binary plane trees, Rudolph \cite{Rud} showed
that patterns of equal length are equipopular if their associated
binary plane trees have identical spine structure. For the
converse direction, Chua and Sankar \cite{Chua} gave a complete
classification of $132$-avoiding permutations into equipopularity
classes. Moreover, Homberger \cite{Hom} presented exact formulae
for the occurrences of each length-$3$ pattern in $S_n(123)$. From
Lemma~\ref{oper} and the existing results on $S_n(123)$ and
$S_n(132)$, we can obtain the popularity of each length-$3$
pattern for the singly restricted permutations $S_n(r)$ with
$r=213,231,312,321$. Therefore, it is well-studied for the
popularity of length-$3$ patterns in singly restricted
permutations, whereas it remains open for multiply restricted
permutations.


\begin{table*}[t!]
\setlength{\unitlength}{1mm}
\begin{center}
\begin{tabular}{|p{15mm}|c|c|p{52mm}|}
\hline
 \multirow{3}{*}{} & {\tiny $f_{213}(n)=(n-3)2^{n-2}+1 $}
&\multirow{2}{*}{}
&{\tiny $\sum f_{231}(n)x^n=\sum f_{312}(n)x^n=\frac{x^3(1+2x)}{(1-x-x^2)^3}$}\\
\cline{2-2}\cline{4-4}{\tiny $S_n(123,132)$} &
{\tiny$f_{231}(n)=f_{312}(n)=(n^2-5n+8)2^{n-3}-1$} & {\tiny
$S_n(123,132,213)$}
&{\tiny $\sum f_{321}(n)x^n= \frac{x^3(1+6x+12x^2+8x^3)}{(1-x-x^2)^4}$}\\
\cline{2-4} & {\tiny $f_{321}(n)=(n^3/3-2n^2+14n/3-5)2^{n-2}+1$} &
&{\tiny $f_{213}(n)=f_{312}(n)={n\choose 3}$} \\
\cline{1-2}\cline{4-4}
 \multirow{2}{*}{} & {\tiny
$f_{123}(n)=(n-4)2^{n-1}+n+2$} &\multirow{1}{*}{}{\tiny
$S_n(123,132,231)$ } & {\tiny $f_{321}(n)=(n-2){n\choose 3}$}
\\
\cline{2-4}\cline{4-4}{\tiny $S_n(132,213)$} &{\tiny
$f_{231}(n)=f_{312}(n)=(\frac{n^2}{4}-\frac{7n}{4}+4)2^{n}-n-4$} &
&{\tiny $f_{123}(n)=f_{312}(n)={n+1\choose 4}$}
 \\
\cline{2-2}\cline{4-4}& {\tiny
$f_{321}(n)=(\frac{1}{12}n^3-\frac{3}{4}n^2+\frac{38}{12}n-6)2^{n}+n+6$}
&\multirow{1}{*}{}{\tiny $S_n(132,213,231)$} &{\tiny
$f_{321}(n)=\frac{1}{12}n(n-2)(n-1)^2$}
\\
\hline {\tiny $S_n(132,231)$}& {\tiny
$f_{123}(n)=f_{213}(n)=f_{312}(n)=f_{321}(n)=\frac{2^n}{8}{n\choose
3}$}
& &{\tiny $f_{213}(n)=f_{231}(n)={n\choose 3}$}\\
\cline{1-2}\cline{4-4}

{\tiny $S_n(132,312)$}& {\tiny
$f_{123}(n)=f_{213}(n)=f_{231}(n)=f_{321}(n)=\frac{2^n}{8}{n\choose
3}$}
& \multirow{1}{*}{}{\tiny $S_n(123,132,312)$} &{\tiny $f_{321}(n)=(n-2){n\choose 3}$}\\
\hline

\multirow{2}{*}{}
& {\tiny $f_{213}(n)=f_{231}(n)=f_{312}(n)={n+2\choose 5}$}&&{\tiny $f_{132}(n)=f_{213}(n)={n+1\choose 4}$}\\
\cline{2-2}\cline{4-4}{\tiny $S_n(132,321)$}&  {\tiny
$f_{123}(n)=\frac{7n^5}{120}-\frac{n^4}{3}+\frac{17n^3}{24}-\frac{2n^2}{3}+\frac{7}{30}$}
&\multirow{1}{*}{}{\tiny $S_n(123,231,312)$}&{\tiny $f_{321}(n)=\frac{1}{12}n(n-2)(n-1)^2$} \\
\hline
\end{tabular}
\end{center}
\caption{Pattern popularity in doubly and triply restricted
permutations.}\label{tab:sum}
\end{table*}


In this paper, we focus on counting the number of occurrences of
length-$3$ patterns in multiply restricted permutations $S_n(R)$
for $R\subset S_3$, especially for double and triple restrictions.
We obtain exact formulae or generating functions for popularity of
each length-$3$ pattern, and the detailed results are summarized
in Table~\ref{tab:sum}. Moreover, we present combinatorial proofs
for non-trivial equalities between the number of occurrences of
different patterns. It is routine to consider the restricted
permutations of higher multiplicity since there are only finite
permutations, as shown in \cite[Proposition\ 17]{Sim}. Therefore,
this work gives a complete study on the popularity of length-$3$
patterns in the multiply restricted permutations. For the
distributions of other statistics in multiply restricted
permutations, see \cite{Do,Eli,Man01,Man04,MaRo}.

\section{Doubly restricted permutations}

This section deals with the enumeration of the popularity for
length-$3$ patterns in the doubly restricted permutations, i.e.,
permutations avoiding two different patterns in $S_3$. For doubly
restricted permutations, we have the following proposition from
\cite{Sim}.
\begin{proposition}{\rm (\cite[Lemma\ 5]{Sim})}
For every symmetric group $S_n$,
\begin{enumerate}
\item $|S_n(123,132)|= |S_n(123,213)|=|S_n(231,321)|=
|S_n(312,321)|= 2^{n-1}$; \item
$|S_n(132,213)|=|S_n(231,312)|=2^{n-1}$; \item
$|S_n(132,231)|=|S_n(213,312)|=2^{n-1}$; \item
$|S_n(132,312)|=|S_n(213,231)|=2^{n-1}$; \item
$|S_n(132,321)|=|S_n(123,231)|=|S_n(123,312)|=|S_n(213,321)|={n\choose
2}+1$; \item $|S_n(123,321)|=0$ for $n\geq 5$.
\end{enumerate}
\end{proposition}

Thus it is sufficient to consider the pattern popularity for the
first set from class~1 to class~5, and the pattern popularity for
the other sets can be derived by taking complement, reverse or
inverse.

A \emph{composition} of $n$ is an expression of $n$ as an ordered
sum of positive integers, and we say that $c$ has $k$ parts or $c$
is a $k$-composition if there are exactly $k$ summands appeared in
 composition $c$. Let $\mathcal{C}_n$ and $\mathcal{C}_{n,k}$
denote the set of all compositions of $n$ and the set of
$k$-compositions of $n$, respectively. It is known that
$|\mathcal{C}_0|=1$, and for $n\geq 1$, $1\leq k \leq n$,
$|\mathcal{C}_n|=2^{n-1}$ and $|\mathcal{C}_{n,k}|= {n-1\choose
k-1}$. For more details on compositions, see \cite{Sta}. It is
helpful to introduce a lemma as follows:
\begin{lemma}\label{com1}
For $n\geq 1$, we have
\begin{eqnarray*}
a(n)&:=&\sum_{ c_1+c_2+\cdots+c_k=n}c_k=2^n-1,\\
b(n)&:=&\sum_{c_1+c_2+\cdots+c_k=n}c_k(c_k-1)=2^{n+1}-2n-2,\\
c(n)&:=&\sum_{c_1+c_2+\cdots+c_k=n}k=(n+1)2^{n-2},\\
d(n)&:=&\sum_{ c_1+c_2+\cdots+c_k=n}k(k-1)=(n^2+n-2)2^{n-3},
\end{eqnarray*}
where the sums are taken over all compositions of $n$.
\end{lemma}
\begin{proof}
 For $c_k=m$ , we can regard $c_1+c_2+\cdots+c_{k-1}$ as a
composition of $n-m$. Since the number of compositions of $n-m$ is
$2^{n-m-1}$ for $1\leq m\leq n-1$ and the number of compositions
of $n$ with $k$ parts is ${n-1\choose k-1}$, we have

\[a(n)=n+\sum_{m=1}^{n-1}m2^{n-m-1} ,~~
b(n)=n(n-1)+\sum_{m=1}^{n-1}m(m-1)2^{n-m-1},\] and
\[c(n)=\sum_{k=1}^{n}k{n-1\choose
k-1} ,~~d(n)=\sum_{k=1}^{n}k(k-1){n-1\choose k-1}.\] Let
$g(x)=\sum_{i=0}^{n-1}x^{i}=\frac{1-x^n}{1-x}$ and
$h(x)=x\sum_{i=1}^{n}{n-1\choose i-1}x^{i-1}=x(1+x)^{n-1}$. We
have
\begin{align*}
g'(x)&=\sum_{i=1}^{n-1}ix^{i-1}=\frac{(n-1)x^n-nx^{n-1}+1}{(1-x)^2}, \\
g''(x)&=\sum_{i=1}^{n-1}i(i-1)x^{i-2}=\frac{(3n-n^2-2)x^n+(2n^2-4n)x^{n-1}+(n-n^2)x^{n-2}+2}{(1-x)^3},\\
h'(x) &=\sum_{i=1}^n i{n-1\choose i-1} x^{i-1}=(nx+1)(1+x)^{n-2},  \\
h''(x)&=\sum_{i=1}^n i(i-1){n-1\choose
i-1}x^{i-2}=\left[n^2x+n(2-x)-2\right](1+x)^{n-3}.
\end{align*}
It follows that
\[a(n)=2^{n-2}g'(1/2)+n,~~b(n)=2^{n-3}g''(1/2)+n(n-1),\] and
\[c(n)=h'(1),~~d(n)=h''(1).\]
Lemma~\ref{com1} holds by simple computations.\end{proof}




\subsection{Pattern popularity in $(123,132)$-avoiding permutations}

In this subsection, we calculate the popularity of all length-$3$
patterns in $S_n(123,132)$. For a permutation
$\sg=\sg_1\sg_2\cdots \sg_n$, $\sg_i$ is said to be a
\emph{left-to-right maximum} (resp., \emph{right-to-left maximum})
if $\sg_i>\sg_j$ for all $j<i$ (resp., $j>i$). We first recall a
correspondence between $S_n(123,132)$ and $\mathcal{C}_n$ as
implicitly shown in \cite{Man01}.
\begin{lemma}{\rm(\cite[Theorem\ 3]{Man01})}\label{ta}
There is a bijection $\varphi_1$ between $S_n(123,132)$ and
$\mathcal{C}_n$.
\end{lemma}
\begin{proof} Given $\sg\in S_n(123,132)$, let
$\sg_{i_1},\sg_{i_2},\ldots,\sg_{i_k}$ be the $k$ right-to-left
maxima with $i_1<i_2<\cdots<i_k$. Then
$c=i_1+(i_2-i_1)+\cdots+(i_{k-1}-i_{k-2})+(i_{k}-i_{k-1})$ is a
composition of $n$ since $i_k=n$. On the converse, let
$m_i=n-(c_1+\cdots+c_{i-1})$ for any given composition
$n=c_1+c_2+\cdots+c_k\in \C_n$. Set
$\tau_i=m_i-1,m_i-2,\ldots,m_i-c_i+1,m_i$ for $1\leq i \leq k$. It
is easy to check that $\sg=\tau_1 \,\tau_2\,\cdots\,\tau_k \in
S_n(123,132)$.
\end{proof}For example, $\sg=8\,9\,7\,5\,4\,3\,6\,1\,2$
corresponds to the composition $9=2+1+4+2$.

Given a pattern $q$, for simplicity, let
$f_{q}(n):=\sum_{\sigma\in S_n(123,132)}f_q(\sigma)$ be the number
of occurrences of pattern $q$ in $S_n(123,132)$, and we will use
this notation in subsequent sections when the set in question is
unambiguous. A {\it factor} of $\sg$ is a subsequence consisting
of contiguous letters in $\sg$. From Lemma~\ref{ta}, we have
\begin{proposition}\label{pa}
For $n\geq3$,
\begin{eqnarray}
f_{213}(n)&=&\sum_{c_1+c_2+\cdots+c_k=n}\sum_{i=1}^k{c_i-1\choose 2},\label{pa1}\\
f_{231}(n)&=&\sum_{ c_1+c_2+\cdots+c_k=n}\sum_{i=1}^{k-1}\sum_{j=
i+1}^kc_j(c_i-1) .\label{pa2}
\end{eqnarray}
\end{proposition}
\begin{proof}
For each permutation $\sg\in S_n(123,132)$ with
$\varphi_1(\sg)=c_1+ c_2+ \cdots+c_k$, we can rewrite $\sg$ as
$\sg=\tau_1 \,\tau_2\,\cdots\,\tau_k$ from Lemma~\ref{ta}. We say
that $\tau_i>\tau_j$ if all the elements in $\tau_i$ are larger
than that in $\tau_j$. We see that the pattern $213$ can only
occur in every factor $\tau_i$ since the elements except the last
one are decreasing in $\tau_i$ and $\tau_i>\tau_{j}$ for $j>i$.
Thus, there are ${c_i-1 \choose 2}$ choices to select two elements
in $\tau_i$ to play the role of $``21"$, and the last element of
$\tau_i$ plays the role of $``3"$. If $c_i\leq 2$, then there is
no copy of the pattern $213$ in $\tau_i$, this coincides with the
value ${c_i-1\choose 2}=0$ for $c_i=1$ or $2$. Summing up all the
number of $213$-patterns in factors $\tau_1,\tau_2,\ldots,\tau_k$
yields formula~\eqref{pa1}.

For pattern $231$, we have $c_i-1$ choices in factor $\tau_i$ to
select one element to play the role of $``2"$ and one choice
(always the last element of $\tau_i$) for $``3"$. After this, we
have $c_{i+1}+\cdots+c_k$ choices to select one element in
$\tau_{i+1},\ldots,\tau_k$ for the role of $``1"$ since all the
elements after $\tau_i$ are smaller than those in $\tau_i$.
Summing up all the number of $231$-patterns according to the
position of $``3"$ gives formula~\eqref{pa2}.
\end{proof}

\begin{theorem}\label{ta1}
For $n\geq 3$, in the set $S_n(123,132)$, we have
\begin{eqnarray}
f_{213}(n)&=&(n-3)2^{n-2}+1, \label{fta1} \\
f_{231}(n)&=&f_{312}(n)=(n^2-5n+8)2^{n-3}-1,\label{fta2}   \\
f_{321}(n)&=&(n^3/3-2n^2+14n/3-5)2^{n-2}+1.\label{fta4}
\end{eqnarray}
\end{theorem}

\begin{proof} From $S_3(123,132)= \{213,231,312,321\}$, we have
\[
f_{213}(3)=f_{231}(3)=1.
\]
To prove formula~\eqref{fta1}, Proposition~\ref{pa} gives that,
for $n\geq3$,
\[
f_{213}(n+1)=\sum_{ c_k=1\atop c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^k
{c_i-1\choose2}+\sum_{ c_k\geq2 \atop
c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^k {c_i-1\choose2}.
\]
If $c_k=1$, then $k\geq2$, and we have
\[
\sum_{ c_k=1 \atop c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^k
{c_i-1\choose2}=\sum_{ c_1+c_2+\cdots+c_{k-1}=n}\sum_{i=1}^{k-1}
{c_i-1\choose 2}=f_{213}(n).
\]
If $c_k\geq 2$, then we set $c_k=1+r_k$ with $r_k\geq 1$. From
Lemma~\ref{com1}, we find that
\begin{align*}
\sum_{c_k\geq2 \atop c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^k {c_i-1\choose2}&=\sum_{\atop c_1+\cdots+c_{k-1}+r_k=n}\left[\sum_{i=1}^{k-1}{c_i-1\choose 2}+{r_k-1\choose 2}+(r_k-1)\right]\\
&=f_{213}(n)+\sum_{ c_1+\cdots+c_{k-1}+r_k=n}(r_k-1)
\\ &=f_{213}(n)+a(n)-2^{n-1}.
\end{align*}
Combining the above two cases, we have
\[f_{213}(n+1)=2f_{213}(n)+2^{n-1}-1,\]
which proves formula~\eqref{fta1} by solving the recurrence with
initial value $f_{213}(3)=1$.

For formula~\eqref{fta2}, we first have $f_{231}(n)=f_{312}(n)$
from $231^{-1}=312$ and $\sg \in S_n(123,132)\Leftrightarrow
\sg^{-1}\in S_n(123,132)$. Using the same method as in the proof
of formula~\eqref{fta1}, we can show
\begin{align*}
\sum_{c_k=1 \atop c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^{k-1}\sum_{j=
i+1}^k c_j(c_i-1)= f_{231}(n)-c(n)+n2^{n-1},
\end{align*}
and
\begin{align*}
\sum_{c_k\geq2 \atop
c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^{k-1}\sum_{j= i+1}^k
c_j(c_i-1)=f_{231}(n)-a(n)-c(n)+(n+1)2^{n-1}.
\end{align*}
It follows that, from Lemma~\ref{com1},
\[
f_{231}(n+1)=2f_{231}(n)+(n-2)2^{n-1}+1.
\]
Formula~\eqref{fta2} is proved by solving this recurrence using
$f_{231}(3)=1$.

Since the total number of all length-$3$ patterns in a permutation
$\sg \in S_n$ is ${n\choose 3}$, we have
\[
f_{213}(n)+2f_{231}(n)+f_{321}(n)={n\choose 3}2^{n-1},
\]
and formula~\eqref{fta4} holds.\end{proof}

The first few values of $f_q(S_n(123,132))$ for $q$ of length $3$
are shown below. Moreover, we observe that they appear in the
On-Line Encyclopedia of Integer Sequences \cite{Slo} as follows:
$(f_{213}(n))_{n\geq 3}$ form sequence \seqnum{A000337},
$(f_{231}(n))_{n\geq 3}$ form sequence \seqnum{A055580}.

\bigskip

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|}
\hline   $n$ &$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$
&$f_{321}$
       & $n$ &$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$\\
\hline   $3$ &$0$      &$0$      &$1$       &$1$      &$1$&$1$ &$6$ &$0$      &$0$       &$49$     &$111$    &$111$     &$369$\\
\hline   $4$ &$0$      &$0$       &$5$       &$7$      &$7$       &$13$ &$7$ &$0$      &$0$       &$129$     &$351$    &$351$     &$1409$\\
\hline   $5$ &$0$      &$0$       &$17$      &$31$     &$31$      &$81$ &$8$ &$0$      &$0$       &$321$     &$1023$    &$1023$     &$4801$\\
\hline
\end{tabular}\label{2a}
\end{center}

\bigskip

\subsection{Pattern popularity in $(132,213)$-avoiding permutations}
We first recall a correspondence between $S_n(132,213)$ and
$\mathcal{C}_n$ as follows:
\begin{lemma}{\rm (\cite[Theorem\ 8]{Man01})}\label{tb}
There is a bijection $\varphi_2$ between $S_n(132,213)$ and
$\mathcal{C}_n$.
\end{lemma}
\begin{proof} Given $\sg\in S_n(132,213)$, let $\sg_{i_1},\sg_{i_2},\ldots, \sg_{i_k}$ be the
$k$ right-to-left maxima with $i_1<i_2<\cdots<i_k$. It follows
that $c=i_1+(i_2-i_1)+\cdots+(i_{k-1}-i_{k-2})+(i_{k}-i_{k-1})$ is
a composition of $n$ since $i_k=n$. On the converse, given a
composition $n=c_1+c_2+\cdots+c_k\in \C_n$, let
$m_i=n-(c_1+\cdots+c_{i-1})$ and
$\tau_i=m_i-c_i+1,m_i-c_i+2,\ldots,m_i-1,m_i$ for $1\leq i \leq
k$. Set $\sg=\tau_1\,\tau_2\,\cdots\,\tau_k$, and it is easy to
check that $\sg \in S_n(132,213)$.
\end{proof}
For example, for the composition $9=3+3+1+2$, we get
$\sg=7\,8\,9\,4\,5\,6\,3\,1\,2$. From this lemma, we have
\begin{proposition}\label{pb}
For $n\geq3$,
\begin{align}
f_{123}(n)&=\sum_{ c_1+c_2+\cdots+c_k=n} \sum_{i=1}^k{c_i\choose 3},\label{pb1}\\
f_{231}(n)&=\sum_{ \atop c_1+c_2+\cdots+c_k=n}\sum_{i=1}^{k-1}
\sum_{j=i+1}^kc_j {c_i\choose 2}\label{pb2}.
\end{align}
\end{proposition}
\begin{proof} For a permutation $\sg\in S_n(132,213)$ with
$\varphi_2(\sg)=c_1+c_2+\cdots+c_k$, we rewrite $\sg$ as
$\sg=\tau_1\,\tau_2\,\cdots\,\tau_k$. The pattern $123$ can only
occur in every factor $\tau_i$ as $\tau_i>\tau_{j}$ for $j>i$ and
the elements in $\tau_i$ are increasing. Thus, we have ${c_i
\choose 3}$ choices to select three elements in $\tau_i$ to play
the role of $``123"$, and formula~\eqref{pb1} follows by summing
up all $123$-patterns in factors $\tau_1,\tau_2,\ldots,\tau_k$.

For the pattern $231$, we have ${c_i \choose 2}$ choices in factor
$\tau_i$ to select two elements to play the role of $``23"$. After
this, we have $c_{i+1}+\cdots+c_k$ choices to select one element
in $\tau_{i+1},\ldots,\tau_k$ for the role of $``1"$ since
$\tau_j<\tau_i$ for all $j>i$. Summing up all the number of
$231$-patterns according to the position of $``23"$ gives formula
\eqref{pb2}. \end{proof}


\begin{theorem}\label{tb1}
For $n\geq 3$, in the set $S_n(132,213)$, we have
\begin{align}
f_{123}(n)&=(n-4)2^{n-1}+n+2,\label{ftb1}\\
f_{231}(n)&=f_{312}(n)=(n^2-7n+16)2^{n-2}-n-4,\label{ftb2}\\
f_{321}(n)&=(n^3/3-3n^2+38n/3-24)2^{n-2}+n+6.\label{ftb3}
\end{align}
\end{theorem}

\begin{proof} From Proposition~\ref{pb}, it follows that
\[
f_{123}(n+1)=\sum_{ c_k=1 \atop
c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^k {c_i\choose 3}+\sum_{ c_k\geq2
\atop c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^k {c_i\choose 3}.
\]
An argument similar to the proof of Theorem \ref{ta1} shows that
\[f_{123}(n+1)=2f_{123}(n)+2^n-n-1.\]
Solving this recurrence with initial value $f_{123}(3)=1$ leads to
formula~\eqref{ftb1}.

 From Lemma~\ref{oper}, we see that $\sg \in
S_n(132,213)\Leftrightarrow \sg^{-1}\in S_n(132,213)$, which
implies $f_{231}(n)=f_{312}(n)$ as $231^{-1}=312$.

To calculate $f_{231}(n)$, by Proposition~\ref{pb}, we arrive at
\[f_{231}(n+1)=\sum_{c_k=1 \atop
c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^{k-1} \sum_{j=i+1}^kc_j
{c_i\choose 2}+\sum_{c_k\geq 2 \atop
c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^{k-1} \sum_{j=i+1}^kc_j
{c_i\choose 2}.
\]
If $c_k=1$, then $k\geq 2$, and we have
\begin{align*}
\sum_{c_k=1 \atop c_1+c_2+\cdots+c_k=n+1}\sum_{i=1}^{k-1}
\sum_{j=i+1}^kc_j{c_i\choose 2} =f_{231}(n)+\alpha(n),
\end{align*}
where
\begin{eqnarray*}
\alpha(n)&=&\sum \limits_{c_1+\cdots+
c_k=n}\sum_{i=1}^{k}{c_i\choose 2}=\sum_{
c_1+\cdots+c_{k}=n}\sum_{i=1}^{k}\left[{c_i-1\choose
2}+c_i-1\right]\\
&=&f_{213}(S_n(123,132))+\sum_{ c_1+\cdots+c_{k}=n}(n-k)\\
&=&f_{213}(S_n(123,132))-c(n)+n2^{n-1}.
\end{eqnarray*}
Here we have used the deduced expression~\eqref{pa1}.\\
If $c_k\geq 2$, then we can derive that
\begin{align*}
\sum_{c_k\geq 2 \atop c_1+\cdots+c_k=n+1}
\sum_{i=1}^{k-1}\sum_{j=i+1}^kc_j{c_i\choose 2}
=f_{231}(n)+\beta(n),
\end{align*}
where
\begin{align*}
\beta(n)&=\sum\limits_{c_1+\cdots+c_k=n}
\sum_{i=1}^{k-1}{c_i\choose 2}\\
&=\sum_{ c_1+\cdots+c_k=n} \sum_{i=1}^{k}{c_i\choose 2}-\sum_{
c_1+\cdots+c_k=n} \frac{c_k (c_{k}-1)}{2}=\alpha(n)-b(n)/2.
\end{align*}
From Lemma~\ref{com1}, we get
\[
f_{231}(n+1)=2f_{231}(n)+(2n-6)2^{n-1}+n+3.
\]
Formula~\eqref{ftb2} holds by solving this recurrence with initial
condition $f_{213}(3)=1$.

Finally, formula~\eqref{ftb3} follows from
$f_{123}(n)+2f_{231}(n)+f_{321}(n)={n\choose 3}2^{n-1}$.
\end{proof}

The first few values of $f_q(S_n(132,213))$ for $q$ of length $3$
are shown below. They appear in \cite{Slo} as follows:
$(f_{123}(n))_{n\geq 3}$ form sequence \seqnum{A045618},
$(f_{231}(n))_{n\geq 3}$ form sequence \seqnum{A055581} and
$(f_{321}(n))_{n\geq 3}$ form sequence \seqnum{A055586}.

\bigskip

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|}
\hline $n$ &$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$ &$n$ &$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$\\
\hline   $3$ &$1$      &$0$      &$0$       &$1$      &$1$&$1$ &$6$ &$72$      &$0$       &$0$     &$150$    &$150$     &$268$\\
\hline   $4$ &$6$      &$0$       &$0$       &$8$      &$8$       &$10$ &$7$ &$201$      &$0$       &$0$     &$501$    &$501$     &$1037$\\
\hline   $5$ &$23$      &$0$       &$0$      &$39$     &$39$      &$59$ &$8$ &$522$      &$0$       &$0$     &$1524$    &$1524$     &$3598$\\
\hline
\end{tabular}\label{2b}
\end{center}



\subsection{Pattern popularity in $(132,231)$-avoiding permutations}

For each $\sg \in S_n(132,231)$, we observe that $n$ must lie in
the beginning or the end of $\sg$, and $n-1$ must lie in the
beginning or the end of $\sg \backslash \{n\}$,..., and so on.
Here $\sg \backslash \{n\}$ denotes the sequence obtained from
$\sg$ by deleting the element $n$. In view of such special
structure, we can derive the pattern popularity in
$(132,231)$-avoiding permutations directly.
\begin{theorem}\label{tc1}
For $n\geq 3$, in the set $S_n(132,231)$, we have
\begin{align}\label{ftc1}
f_{123}(n)=f_{213}(n)=f_{312}(n)=f_{321}(n)={n\choose 3}2^{n-3}.
\end{align}
\end{theorem}

\begin{proof}  Suppose that $q$ is a
length-$3$ pattern in $\{123, 213,312,321\}$, and $abc$ is a copy
of the pattern $q$. Set
\[[n] \backslash \{a,b,c\}:=\{r_1>r_2>\cdots>r_{n-4}>r_{n-3}\}.\]
We will construct a permutation in the set $S_n(132,231)$ which
contains $abc$ as a copy of the pattern $q$. Start with the
subsequence $\sg^0:=abc$, and for $i$ from $1$ to $n-3$, $\sg^i$
is obtained by inserting $r_i$ into $\sg^{i-1}$ such that
\begin{itemize}
\item If there are at least two elements in $\sg^{i-1}$ that are
smaller than $r_i$, then choose the two elements $A$ and $B$ such
that $A$ is the leftmost one and $B$ is the rightmost one. We put
$r_i$ immediately to the left of $A$ or immediately to the right
of $B$; \item If there is only one element $A$ in $\sg^{i-1}$ such
that $A<r_i$, then we put $r_i$ immediately to the left or to the
right of $A$; \item If all the elements in $\sg^{i-1}$ are larger
than $r_i$, then choose $A$ the smallest one, and put $r_i$
immediately to the left or to the right of $A$.
\end{itemize}

Finally, we set $\sg:=\sg^{n-3}$ and $\sg\in S_n(132,231)$ from
the above construction. It can be seen that, the number of
permutations having a copy $abc$ is $2^{n-3}$ since each $r_i$ has
$2$ choices in the inserting procedure. Moreover, there are
${n\choose 3}$ choices to select three elements $a, b, c$ as an
appearance of the pattern $q$ in $\{123, 213,312,321\}$. Hence we
deduce $ f_{q}(n)={n\choose 3}2^{n-3}$.\end{proof}

Here we give an illustration for constructing a permutation in
$S_8(132,231)$ which contains $abc=256$ as a copy of the pattern
$123$. Set $\sg^0:=2\,5\,6$, we may have $\sg^1=8\,2\,5\,6$,
$\sg^2=8\,7\,2\,5\,6$, $\sg^3=8\,7\,2\,4\,5\,6$,
$\sg^4=8\,7\,3\,2\,4\,5\,6$, $\sg:=\sg^5=8\,7\,3\,2\,1\,4\,5\,6$.

We can also give a combinatorial proof for Theorem~\ref{tc1}.
Since $\sg \in S_n(132,231)\Leftrightarrow \sg^{r}\in
S_n(132,231)$, it is easy to show $f_{123}(n)=f_{321}(n)$ and
$f_{213}(n)=f_{312}(n)$ from $123^{r}=321$ and $213^{r}=312$. It
remains to give a bijection for $f_{213}(n)=f_{123}(n)$, and our
 construction is motivated from B\'{o}na \cite{Bona}.

We first introduce some notation about trees. A {\it binary plane
tree} is a rooted unlabelled tree in which each vertex has at most
two children, and each child is a left child or a right child of
its parent. For each $\sg\in S_n(132)$, we can construct a binary
plane tree $T(\sg)$ as follows: the root of $T(\sg)$ corresponds
to the entry $n$ of $\sg$, the left subtree of the root
corresponds to the string of entries of $\sg$ on the left of $n$,
and the right subtree of the root corresponds to the string of
entries of $\sg$ on the right of $n$. Both subtrees are
constructed recursively by the same rule. For more details, see
\cite{Bona2011,Bona,Rud}.

A {\it left descendant} (resp., {\it right descendant}) of a
vertex $x$ in a binary plane tree is a vertex in the left (resp.,
right) subtree of $x$. Similarly, an {\it ascendant} of a vertex
$x$ in a binary plane tree is a vertex whose subtree contains $x$.
Given a tree $T$ and a vertex $v \in T$, let $T_v$ be the subtree
of $T$ rooted at $v$. Let $R$ be an occurrence of the pattern
$123$ in $\sg \in S_n(132)$, and let $R_1,R_2,R_3$ be the three
vertices of $T(\sg)$ that correspond to $R$, going left to right.
Then, $R_1$ is a left descendant of $R_2$, and $R_2$ is a left
descendant of $R_3$.

According to the correspondence between $132$-avoiding
permutations and binary plane trees, we see that for $\sg \in
S_n(132,231)$, $T(\sg)$ is a binary plane tree on $n$ vertices
such that each vertex has at most one child from the forbiddance
of the pattern $231$. For simplicity, let $\mathcal{T}_n$ be the
set of such binary plane trees on $n$ vertices. Let $Q$ be an
occurrence of the pattern $213$ in $\sg \in S_n(132,231)$, and let
$Q_2,Q_1,Q_3$ be the three vertices of $T(\sg)$ that correspond to
$Q$, going left to right. From the characterization of trees in
$\mathcal{T}_n$, $Q_2$ is a left descendant of $Q_3$, and $Q_1$ is
a right descendant of $Q_2$.

{\it Combinatorial proof for $f_{213}(n)=f_{123}(n)$.~~} Let
$\mathcal{A}_n$ be the set of binary plane trees in
$\mathcal{T}_n$ where three vertices forming a $213$-pattern are
colored black. Let $\mathcal{B}_n$ be the set of all binary plane
trees in $\mathcal{T}_n$ where three vertices forming a
123-pattern are colored black. We define a map $\rho:
\mathcal{A}_n \rightarrow \mathcal{B}_n$ as follows.

Given a tree $T\in \mathcal{A}_n$ with $Q_2,Q_1,Q_3$ being the
three black vertices as a $213$-pattern, we define $\rho(T)$ be the
tree obtained from $T$ by changing the right subtree of $Q_2$ to
be its left subtree. See Figure~\ref{fig1} for an illustration.
\begin{figure}[h,t]
\setlength{\unitlength}{0.6mm}%
\begin{center}
\begin{picture}(100,55)
\put(0,24){\circle*{3.5}}\put(6,18){\circle*{2}}
\put(12,12){\circle*{3.5}}\put(18,0){\circle*{2}}
\put(6,30){\circle*{2}} \put(12,36){\circle*{3.5}}
\put(6,42){\circle*{2}} \put(0,54){\circle*{2}}
\qbezier[1000](0,24)(3,21)(6,18) \qbezier[1000](6,18)(9,15)(12,12)
\qbezier[1000](12,12)(15,6)(18,0) \qbezier[1000](0,24)(3,27)(6,30)
\qbezier[1000](6,30)(9,33)(12,36)
\qbezier[1000](12,36)(9,39)(6,42) \qbezier[1000](0,54)(3,48)(6,42)
%%
\put(17,12){\makebox(0,0){\tiny $Q_1$}}
\put(-5,24){\makebox(0,0){\tiny $Q_2$}}
\put(17,36){\makebox(0,0){\tiny $Q_3$}}

\put(50,24){\makebox(0,0){$\rightleftharpoons$}}
%
%\put(70,0){\circle*{2}}\put(76,12){\circle*{3.5}}
\put(94,0){\circle*{2}}\put(88,12){\circle*{3.5}}
\put(82,18){\circle*{2}} \put(88,24){\circle*{3.5}}
\put(94,30){\circle*{2}} \put(100,36){\circle*{3.5}}
\put(94,42){\circle*{2}} \put(88,54){\circle*{2}}
\qbezier[1000](94,0)(91,6)(88,12)
\qbezier[1000](88,12)(85,15)(82,18)\qbezier[1000](82,18)(85,21)(88,24)
\qbezier[1000](88,24)(91,27)(94,30)
\qbezier[1000](94,30)(97,33)(100,36)
\qbezier[1000](100,36)(97,39)(94,42)
\qbezier[1000](94,42)(91,48)(88,54)
\put(93,12){\makebox(0,0){\tiny $Q_1$}}
\put(93,24){\makebox(0,0){\tiny $Q_2$}}
\put(105,36){\makebox(0,0){\tiny $Q_3$}}
\put(3,-2){\dashbox{0.5}(18,23)} \put(4,4){\tiny right subtree of
$Q_2$}


\put(79,-2){\dashbox{0.5}(18,23)} \put(80,4){\tiny left subtree of
$Q_2$}
\end{picture}
\end{center}
\caption {The bijection $\rho$.} \label{fig1}
\end{figure}


In the tree $\rho(T)$, the relative positions of $Q_2$ and $Q_3$
keep the same, and $Q_1$ is a left descendant of $Q_2$. Therefore,
 points $Q_1Q_2Q_3$ form a $123$-pattern in
$\rho(T)$, and $\rho(T)\in \mathcal{B}_n$. On the converse, it is
routine to verify that changing left subtree of $Q_2$ to be
its right subtree is the desired reverse map. Therefore, $\rho$ is
a bijection between $\mathcal{A}_n$ and $\mathcal{B}_n$.


The initial values for $f_q(S_n(132,231))$ are
\[ 1, 8, 40, 160, 560, 1792, \ldots,\] and this is essentially the sequence \seqnum{A001789} in \cite{Slo}.




\subsection{Pattern popularity in $(132,312)$-avoiding permutations}

We first present a lemma as follows:
\begin{lemma}
There is a bijection $\varphi_4$ between $S_n(132,312)$
and $\mathcal{C}_n$.
\end{lemma}
\begin{proof} For $\sg\in S_n(132,312)$, let $\sg_{i_1},\sg_{i_2},\ldots,
\sg_{i_k}$ be the $k$ left-to-right maxima with
$i_1<i_2<\cdots<i_k$. Then
$c=(i_2-i_1)+(i_3-i_2)+\cdots+(i_{k}-i_{k-1})+(n+1-i_{k})$ is a
composition of $n$ since $i_1=1$. On the converse, let
$n=c_k+c_{k-1}+\cdots+c_2+c_1\in \C_n$. For $1\leq i \leq k$, if
$c_i=1$ then set $\tau_i=n-i+1$; otherwise, set
$m_i=c_1+\cdots+c_{i-1}-i+2$ and
$\tau_i=n-i+1,m_i+c_i-2,\ldots,m_i+1,m_i$. It is easy to get
$\sg=\tau_k\,\tau_{k-1}\,\cdots\,\tau_2\,\tau_1\in S_n(132,312)$.
\end{proof} For example, if $9=3+1+2+3$, then
$\sg=6\,5\,4\,7\,8\,3\,9\,2\,1$.
\begin{proposition}\label{pd}
For $n\geq3$,
\begin{align}\label{pd1}
f_{123}(n)=\sum_{c_1+c_2+\cdots+c_k=n}
\sum_{i=1}^{k-2}c_i{k-i\choose2}.
\end{align}
\end{proposition}

\begin{proof} Let $\sg=\tau_k\,\cdots\,\tau_2\,\tau_1$ be a permutation in
$S_n(132,312)$ whose composition is given by
$n=c_k+c_{k-1}+\cdots+c_2+c_1$. It is evident that, for $i+1\leq j
\leq k$, the first element in $\tau_i$ is larger than all the
elements in $\tau_{j}$, whereas the other elements in $\tau_i$ are
smaller than that in $\tau_{j}$. Furthermore, the left-to-right
maxima form an increasing subsequence and the other elements form
a decreasing subsequence. Thus we have $c_i$ choices to select one
element in $\tau_{i}$ to play the role of $``1"$, and then
${i-1\choose 2}$ choices to select two left-to-right maxima after
$\tau_i$ to paly the role of $``23"$. Summing up all the number of
$123$-patterns in factors $\tau_k,\ldots,\tau_2,\tau_1$ yields
that \[f_{123}(n)=\sum_{c_k+\cdots+c_2+c_1=n}
\sum_{i=3}^{k}c_i{i-1\choose2}.\] By setting $i:=k-i+1$ and using
the symmetry of the summands in compositions, it is equivalent to
formula~\eqref{pd1}.\end{proof}


\begin{theorem}\label{td1}
For $n\geq 3$, in the set $S_n(132,312)$, we have
\begin{align}\label{fd1}
f_{123}(n)&=f_{321}(n)={n\choose 3}2^{n-3},\\\label{fd2}
f_{213}(n)&=f_{231}(n)={n\choose 3}2^{n-3}.
\end{align}
\end{theorem}

\begin{proof}  From Lemma~\ref{oper}, we know that
$\sg \in S_n(132,312)\Leftrightarrow \sg^{c}\in S_n(132,312)$.
Hence it is obvious that $f_{123}(n)=f_{321}(n)$ and
$f_{213}(n)=f_{231}(n)$ as $123^{c}=321$ and $213^{c}=231$.

To calculate $f_{123}(n)$, by using Proposition~\ref{pd} and the
similar argument in the proof of Theorem~\ref{ta1}, we  have
\[ f_{123}(n+1)=2f_{123}(n)+(n^2-n)2^{n-3}.
\]
Formula~\eqref{fd1} holds by  solving the recurrence with initial value $f_{123}(3)=1$, and
formula~\eqref{fd2} is a direct computation of $2f_{123}(n)+2f_{213}(n)={n\choose
3}2^{n-1}$.\end{proof}

We will give a combinatorial interpretation for
$f_{231}(n)=f_{123}(n)$. For each $\sg \in S_n(132,312)$, we construct a binary plane tree $T(\sg)$
on $n$ vertices such that each vertex with a right descendant
of some vertex does not have a left descendant from the
forbiddance of the pattern $312$. Let $\mathscr{T}_n$ denote the
set of such trees on $n$ vertices. Let $Q$ be an occurrence of the
pattern $231$ in $\sg \in S_n(132,312)$, and let $Q_2,Q_3,Q_1$ be
the three vertices of $T(\sg)$ that correspond to $Q$, going left
to right. Then, $Q_2$ is a left descendant of $Q_3$, and there
exists a lowest ascendant $x$ of $Q_3$ or $x=Q_3$ so that $Q_1$ is
a right descendant of $x$.

{\it Combinatorial proof for $f_{231}(n)=f_{123}(n)$.~~} Let
$\mathscr{A}_n$ be the set of binary plane trees in
$\mathscr{T}_n$ in which three vertices forming a $231$-pattern
are colored black. Let $\mathscr{B}_n$ be the set of all binary
plane trees in $\mathscr{T}_n$ in which three vertices forming a
123-pattern are colored black. We define a map $\varrho:
\mathscr{A}_n \rightarrow \mathscr{B}_n$ as follows.

Given a tree $T\in \mathscr{A}_n$ with $Q_2,Q_3,Q_1$ being the
three black vertices forming a $231$-pattern, let $y$ be the
parent of $x$ if it exists. We can see that $x$ is the left child
of $y$ from $T\in \mathscr{A}_n$. Let $T^u:=T-T_x$ be the tree
obtained from $T$ by deleting the subtree $T_x$, and
$T^d:=T_x-T_{Q_1}$ be the tree obtained from $T_x$ by deleting
$T_{Q_1}$. Now we define $\varrho(T)$ to be the tree obtained from
$T$ by first adjoining $T_{Q_1}$ to the vertex $y$ as its left
subtree, then adjoining
 $T^d$ to $Q_1$ as its left subtree and
keeping all three black vertices the same if $y$ exits; otherwise,
we adjoin $T^d$ to $Q_1$ as its left
subtree directly. An illustration is given in Figure~\ref{fig2}.

\begin{figure}[h,t]
\setlength{\unitlength}{0.7mm}%
\begin{center}
\begin{picture}(100,55)
\put(0,0){\circle*{2}}\put(12,0){\circle*{2}}
\put(6,12){\circle*{3.5}}\put(9,18){\circle*{2}}
\put(12,24){\circle*{3.5}} \put(15,30){\circle*{2}}
\put(18,36){\circle*{2}} \put(21,30){\circle*{2}}
\put(24,24){\circle*{3.5}} \put(30,12){\circle*{2}}
\put(21,42){\circle*{2}}
\put(24,48){\circle*{2}}\put(27,42){\circle*{2}}
\qbezier[1000](0,0)(3,6)(6,12)\qbezier[1000](12,0)(9,6)(6,12)
\qbezier[1000](6,12)(7.5,15)(9,18)
\qbezier[1000](9,18)(10.5,21)(12,24)
\qbezier[1000](12,24)(13.5,27)(15,30)
\qbezier[1000](15,30)(16.5,33)(18,36)
\qbezier[1000](18,36)(19.5,33)(21,30)
\qbezier[1000](21,30)(22.5,27)(24,24)
\qbezier[1000](24,24)(27,18)(30,12)
\qbezier[1000](18,36)(19.5,39)(21,42)
\qbezier[1000](21,42)(22.5,45)(24,48)
\qbezier[1000](24,48)(25.5,45)(27,42)
\put(2,12){\makebox(0,0){\tiny $Q_2$}}
\put(8,24){\makebox(0,0){\tiny $Q_3$}}
\put(29,24){\makebox(0,0){\tiny $Q_1$}}
\put(16,35){\makebox(0,0){\tiny $x$}}
\put(23,42){\makebox(0,0){\tiny $y$}}
\put(45,18){\makebox(0,0){$\Rightarrow$}}

\put(60,0){\circle*{2}}\put(72,0){\circle*{2}}
\put(66,12){\circle*{3.5}}\put(69,18){\circle*{2}}
\put(72,24){\circle*{3.5}} \put(75,30){\circle*{2}}
\put(78,36){\circle*{2}}\put(81,42){\circle*{3.5}}
\put(81,30){\circle*{2}} \put(87,30){\circle*{2}}
\put(84,48){\circle*{2}}\put(87,54){\circle*{2}}
\put(90,48){\circle*{2}}

\qbezier[1000](60,0)(63,6)(66,12)\qbezier[1000](72,0)(69,6)(66,12)
\qbezier[1000](66,12)(67.5,15)(69,18)
\qbezier[1000](69,18)(70.5,21)(72,24)
\qbezier[1000](72,24)(73.5,27)(75,30)
\qbezier[1000](75,30)(76.5,33)(78,36)
\qbezier[1000](78,36)(79.5,33)(81,30)

\qbezier[1000](78,36)(79.5,39)(81,42)
\qbezier[1000](81,42)(84,36)(87,30)
\qbezier[1000](81,42)(82.5,45)(84,48)
\qbezier[1000](84,48)(85.5,51)(87,54)
\qbezier[1000](87,54)(88.5,51)(90,48)

\put(62,12){\makebox(0,0){\tiny $Q_2$}}
\put(68,24){\makebox(0,0){\tiny $Q_3$}}
\put(77,42){\makebox(0,0){\tiny $Q_1$}}
\put(76,35){\makebox(0,0){\tiny $x$}}
\put(86.5,48){\makebox(0,0){\tiny $y$}}

\put(19,39){\dashbox{0.5}(10,13)} \put(35,50){\footnotesize
$T_u$}\put(26,48){$\nearrow$}

\put(82,45){\dashbox{0.5}(10,13)} \put(97,50){\footnotesize $T_u$}
\put(90,50){$\rightarrow$}

\put(-2,-2){\dashbox{0.5}(24,40)} \put(27,4){\footnotesize $T_d$}
\put(20,10){$\searrow$}

\put(58,-2){\dashbox{0.5}(24,40)} \put(90,4){\footnotesize $T_d$}
\put(80,4){$\rightarrow$}

\end{picture}
\end{center}
\caption {The bijection $\varrho$.} \label{fig2}
\end{figure}

In the tree $\varrho(T)$, the relative positions of $Q_2$ and
$Q_3$ are unchanged, and $Q_3$ is a left descendant of $Q_1$, thus
the three black points $Q_2Q_3Q_1$ form a $123$-pattern in
$\varrho(T)$, and $\varrho(T)\in \mathscr{B}_n$. It is easy to
describe the inverse map and we omit here.



\subsection{Pattern popularity in $(132,321)$-avoiding permutations}

We first introduce a lemma as follows:
\begin{lemma}{\rm \cite[Proposition\ 13]{Sim}}\label{2le}
There is a bijection $\varphi_5$ between
$S_n(132,321)\backslash \{\text{id}\}$ and the set of $2$-element
subsets of $[n]$.
\end{lemma}
\begin{proof} For a permutation $\sg \in S_n(132,321)\backslash
\{\text{id}\}$, suppose $\sg_k=m$ ($k<m$) and define
$\varphi_5(\sg)=\{k,m\}$. On the converse, given two elements
$1\leq k<m \leq n$, set $\tau_1=m-k+1,m-k+2,\ldots,m-1,m$,
$\tau_2=1,2,\ldots,m-k$ and $\tau_3=m+1,m+2,\ldots,n-1,n$. We have
 $\sg=\varphi_5^{-1}(k,m)=\tau_1\,\tau_2\,\tau_3$.
\end{proof}
For example, if $k=4,m=6$, then $\sg=3\,4\,5\,6\,1\,2\,7\,8$.
\begin{proposition}\label{pe}
For $n\geq3$,
\begin{align}
f_{213}(n)&=\sum_{1\leq k<m \leq n}k(m-k)(n-m)\label{pe1},\\
f_{312}(n)&=\sum_{1\leq k<m \leq n}k{m-k\choose
2}.~~~~~~\label{pe2}
\end{align}
\end{proposition}
\begin{proof} Given a permutation $\sg=\tau_1\,\tau_2\,\tau_3$ in
$S_n(132,321)$ with $\varphi_5(\sg)=\{k,m\}$, we see that the
elements in each $\tau_i$ ($1\leq i \leq 3$) are increasing, and
$\tau_2<\tau_1<\tau_3$. Hence we have $k$ choices to select one
element in $\tau_{1}$ to play the role of $``2"$, $m-k$ choices to
select one element in $\tau_{2}$ to play the role of $``1"$, and
$n-m$ choices to select one element in $\tau_{3}$ to play the role
of $``3"$. Summing up all possible $k$ and $m$ gives
formula~\eqref{pe1}.

For the pattern $312$, we have $k$ choices to select one element
in factor $\tau_1$ to play the role of $``3"$, and then have
${m-k\choose 2}$ choices to select two elements in factor $\tau_2$
to play the role of $``12"$. Summing up all $k$ and $m$ proves
formula~\eqref{pe2}. \end{proof}

We now derive the exact formulae
for the popularity of patterns in $S_n(132,321)$ as follows.
\begin{theorem}\label{te1}
For $n\geq 3$, in the set $S_n(132,321)$, we have
\begin{align}\label{tf51}
f_{213}(n)&=f_{231}(n)=f_{312}(n)={n+2\choose 5},\\
f_{123}(n)&=n(7n^4-40n^3+85n^2-80n+28)/120.
\end{align}
\end{theorem}
\begin{proof}
It is simple to prove $f_{312}(n)=f_{231}(n)$ from Lemma~\ref{oper} and $312^{-1}=231$. By
Proposition~\ref{pe}, we have
\begin{align*}
f_{312}(n)&=\sum_{1\leq k<m \leq n}k{m-k\choose 2}\\
&=\sum_{k=1}^{n-1}k\sum_{m=k+1}^n{m-k\choose 2}=\sum_{k=1}^{n-1}k{n-k+1\choose 3}\\
&=\sum_{k=1}^{n-1}\left[(n^3-n)k+(1-3n^2)k^2+2nk^3-k^4\right],
\end{align*}
and
\begin{align*}
f_{213}(n)&=\sum_{1\leq k<m \leq n}k(m-k)(n-m)=\sum_{k=1}^{n-1}\sum_{m=k+1}^nk(m-k)(n-m)\\
&=\sum_{k=1}^{n-1}\sum_{m'=1}^{n-k}km'(n-m'-k)=\sum_{k=1}^{n-1}k(n-k)\sum_{m'=1}^{n-k}m'-\sum_{k=1}^{n-1}k\sum_{m'=1}^{n-k}m'^2\\
&=\sum_{k=1}^{n-1}\left[
\left(\frac{n^3}{6}-\frac{n}{6}\right)k+\left(\frac{1}{6}-\frac{n^2}{2}\right)k^2+
\frac{n}{2}k^3-\frac{1}{6}k^4\right].
\end{align*}
We get formula~\eqref{tf51} by substituting the closed forms of $\sum_{k=1}^n k^p$ $(p=1,2,3,4)$ into the above
expressions, and this theorem holds from
$2f_{231}(n)+f_{213}(n)+f_{123}(n)={n\choose 3}\left[{n\choose
2}+1\right]$.\end{proof}

Notice that $f_{213}(n)=f_{231}(n)$ can be proved by B\'{o}na's
bijection \cite{Bona} on the set of binary plane trees on $n$
vertices such that the vertex which is a right descendant of some
node has no right descendant.

The first few values of $f_q(S_n(132,321))$ for $q$ of length $3$
are shown below, and $(f_{213}(n))_{n\geq 3}$ form sequence
\seqnum{A000389} in \cite{Slo}.

\bigskip

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|}
\hline  $n$&$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$
&$f_{321}$
&$n$&$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$\\
\hline   $3$ &$1$      &$0$      &$1$     &$1$&$1$  &$0$      &$6$ &$152$      &$0$       &$56$   &$56$ &$56$   &$0$ \\
\hline   $4$ &$10$      &$0$       &$6$   &$6$ &$6$     &$0$   &$7$ &$392$      &$0$       &$126$  &$126$ &$126$   &$0$   \\
\hline   $5$ &$47$      &$0$       &$21$   &$21$  &$21$     &$0$    &$8$ &$868$      &$0$       &$252$  &$252$ &$252$   &$0$ \\
\hline
\end{tabular}\label{2e}
\end{center}

\section{Triply restricted permutations}

This section studies the pattern popularity in the
permutations which avoid simultaneously any three patterns of
length $3$. We begin with the following proposition from \cite{Sim}.
\begin{proposition}{\rm(\cite[Lemma\ 6]{Sim})}
The numbers of triply restricted permutations in $S_n$ satisfy the
following equalities: {\small
\begin{enumerate}
\item $|S_n(123,132,213)|=|S_n(231,312,321)|=F_{n+1}$; \item
$|S_n(123,132,231)|=|S_n(123,213,312)|=|S_n(132,231,321)|=|S_n(213,312,321)|=n$;
\item
$|S_n(132,213,231)|=|S_n(132,213,312)|=|S_n(132,231,312)|=|S_n(213,231,312)|=n$;
 \item
$|S_n(123,132,312)|=|S_n(123,213,231)|=|S_n(132,312,321)|=|S_n(213,231,321)|=n$;
 \item $|S_n(123,231,312)|=|S_n(132,213,321)|=n$; \item
$|S_n(R)|=0$ for all $R\supset \{123,321\}$ if $n\geq 5$, where
$F_{n}$ is the Fibonacci number given by $F_0=0,F_1=1$ and
$F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 2$.
\end{enumerate}}
\end{proposition}

An argument similar to the one used for doubly restricted
permutations shows that we only need to consider the pattern
popularity for the first set of class~1 to class~5.


\subsection{Pattern popularity in $(123,132,213)$-avoiding permutations}

It is well-known that Fibonacci number $F_{n+1}$ counts the number
of $0$-$1$ sequences of length $n-1$ in which there are no
consecutive ones, see \cite{Com}. We call such a sequence a
\emph{Fibonacci binary word} for convenience. Let $B_n$ denote the
set of all Fibonacci binary words of length $n$. Simion and
Schmidt \cite{Sim} showed that
\begin{lemma}{\rm (\cite[Proposition\ $15^*$]{Sim})}
There is a bijection $\psi_1$ between $S_n(123,132,213)$
and $B_{n-1}$.
\end{lemma}
\begin{proof} For $w=w_1w_2\cdots w_{n-1} \in B_{n-1}$, we construct the permutation $\sg$ as follows. For $1\leq i \leq n-1$, let $X_i=[n]-\{\sg_1,\ldots,\sg_{i-1}\}$, and set
\begin{subnumcases}
{\sg_i=}
\text{largest element in}~ X_i, &if $w_i=0$, \nonumber\\
\text{second largest element in}~ X_i, &if $w_i=1$.\nonumber
\end{subnumcases}
Finally, $\sg_n$ is the unique element in $X_n$. \end{proof} For
example, if $w=01001010$, then
$\psi_1(w)=9\,7\,8\,6\,4\,5\,2\,3\,1$.

Given a word $w=w_1w_2\cdots w_{n} \in B_{n}$, the index $i$
($1\leq i<n$) is an \emph{ascent} of $w$ if $w_i<w_{i+1}$. Let
$\asc(w)=\{ i\,| w_i<w_{i+1} \}$ be the set of ascents of $w$, and
let $\maj(w)=\sum_{i \in \asc(w)}i$.
\begin{proposition}\label{paa}
For $n\geq 3$,
\begin{align}\label{paa1}
f_{312}(n)=\sum_{w \in B_{n-1}}\maj(w).
\end{align}
\end{proposition}

\begin{proof} Suppose $\sg \in S_n(123,132,213)$ and $\psi_1(\sg)=w_1w_2\cdots
w_{n-1}$. If $k$ is an ascent of $w$, then $w_kw_{k+1}=01$ and
$\sg_k>\sg_{k+1}$. From bijection $\psi_1$, we see that for
all $i\in [n-1]$, there is at most one $j>i$ such that
$\sg_j>\sg_i$. This implies that $\sg_i>\sg_{k+1}$ for all $i<k$.
Since $\sg_{k}$ is the largest element in $X_{k}$, we have
$\sg_i>\sg_{j}$ for all $i<k+1$ and $j>k+1$. On the other hand,
since $\sg_{k+1}$ is the second largest element in $X_{k+1}$,
there exists a unique $l>k+1$ such that $\sg_{l}>\sg_{k+1}$. Thus,
we find that $\sg_i \sg_{k+1} \sg_{l}$ forms a $312$-pattern for
all $i\leq k$, that is the ascent $k$ will produce $k$'s copies of
$312$-pattern in which $\sg_{k+1}$ plays the role of $``1"$.
Summing up all the ascents, we derive that the number of copies of
$312$-pattern in $\sg$ is $\maj(\psi_1(\sg))$.
\end{proof}

Recall that the generating function of the Fibonacci number $F_n$
is given by
\begin{align*}
\sum_{n\geq 0}F_nx^n=\frac{x}{1-x-x^2}.
\end{align*}Hence we can deduce that
\begin{align}
&\sum_{n\geq 3}F_{n+1}x^n=x\sum_{n\geq
2}F_{n+2}x^{n}=\frac{1}{x}\left(\frac{x}{1-x-x^2}-x-x^2-2x^3\right)
=\frac{x^3(3+2x)}{1-x-x^2}\label{fb1},\\
& \sum_{n\geq
2}nF_{n+2}x^n=x\left(\frac{x^2(3+2x)}{1-x-x^2}\right)'
=\frac{x^2(6+3x-4x^2-2x^3)}{(1-x-x^2)^2}\label{fb2},\\
&\sum_{n\geq 3}{n\choose
3}F_{n+1}x^n=\frac{x^3}{6}\left(\sum_{n\geq
3}F_{n+1}x^n\right)^{'''}=\frac{x^3(3+8x+6x^2+4x^3)}{(1-x-x^2)^4}.\label{fb3}
\end{align}

\begin{theorem}\label{Tta1}
For $n\geq 3$, in the set $S_n(123,132,213)$, we have
\begin{align}
\sum_{n\geq 3}f_{231}(n)x^n&=\sum_{n\geq 3}f_{312}(n)x^n=\frac{x^3(1+2x)}{(1-x-x^2)^3},\label{fTta1}\\
\sum_{n\geq 3}f_{321}(n)x^n&= \frac{x^3(1+6x+12x^2+8x^3)}
{(1-x-x^2)^4}.\label{Tca2}
\end{align}
\end{theorem}

\begin{proof} From Lemma~\ref{oper}, we have $f_{231}(n)=f_{312}(n)$
as $\sg \in S_n(123,132,213)\Leftrightarrow \sg^{-1}\in
S_n(123,132,213)$ and $231^{-1}=312$. By Proposition~\ref{paa}, we
can write
\[
\sum_{n\geq 3}f_{312}(n)x^n=\sum_{n\geq 3}x^n\sum_{w \in
B_{n-1}}\maj(w) =x\sum_{n\geq 3}\sum_{w \in
B_{n-1}}\maj(w)x^{n-1}=xu(x),
\]
where $u(x)=\sum\limits_{n\geq 2}\sum\limits_{w \in
B_n}\maj(w)x^n$. To calculate  $u(x)$, we set \[ M_n(q)=\sum\limits_{w \in B_n} q^{\maj(w)}
\text{ and } M(x,q)=\sum\limits_{n\geq 2}M_n(q)x^n.\] It is easy to get
\[u(x)=\frac{\partial M(x,q)}{\partial q}\mid_{q=1}.\] Given a word
$w=w_1w_2\cdots w_n \in B_n$, if $w_n=0$, then
$\maj(w)=\maj(w_1w_2\cdots w_{n-1})$; otherwise, $w_{n-1}w_n=01$
and $\maj(w)=\maj(w_1w_2\cdots w_{n-2})+n-1$. Hence, we have
\begin{align*}
M_n(q)=M_{n-1}(q)+q^{n-1}M_{n-2}(q) \text{ for }n\geq 4,
\end{align*}
with $M_2(q)=2+q$ and $M_3(q)=2+q+2q^2$. Multiplying the recursion
by $x^n$ and summing over $n\geq 4$ yields that
\[ M(x,q)-(2+q)x^2-(2+q+2q^2)x^3=x\left[M(x,q)-(2+q)x^2\right]+qx^2M(xq,q).\]
Therefore \[(1-x)M(x,q)=qx^2M(xq,q)+(2+q)x^2+2q^2x^3.\]
Differentiate both sides with respect to $q$, we get
\begin{align*}\label{ftaf}
(1-x)\frac{\partial M(x,q)}{\partial
q}=x^2\left[M(xq,q)+q\frac{\partial M(xq,q)}{\partial q}
\right]+x^2+4qx^3.
\end{align*}
Setting $q=1$ gives
\[
(1-x)u(x)=x^2\left[M(x,1)+\frac{\partial M(xq,q)}{\partial
q}\mid_{q=1}\right] +x^2+4x^3.
\]
Notice that
\[
M(x,1)=\sum_{n\geq 2}|B_{n}|x^n=\sum_{n\geq 2}F_{n+2}x^n,
\]
and
\begin{align*} \frac{\partial M(xq,q)}{\partial
q}\mid_{q=1}&=\left(\sum_{n\geq 2}\sum_{w \in B_n}
(n+\maj(w))q^{n+\maj(w)-1}x^n
\right)|_{q=1}\\
&=\sum_{n\geq 2}x^n\sum_{w \in B_n}(n+\maj(w))\\
&=\sum_{n\geq 2}nF_{n+2}x^n+u(x).
\end{align*}
Invoking formulae~\eqref{fb1} and \eqref{fb2}, this implies that
\[(1-x)u(x)=x^2\left[\frac{x^2(3+2x)}{1-x-x^2}+\frac{x^2(6+3x-4x^2-2x^3)}{(1-x-x^2)^2}+u(x)\right]
+x^2+4x^3.\] Therefore, $u(x)={x^2(1+2x)}/{(1-x-x^2)^3}.$
Multiplying $u(x)$ by $x$, we arrive at formula~\eqref{fTta1}.

As for formula~\eqref{Tca2}, we notice that
\begin{align}\label{Tta2f}
\sum_{n\geq 3}f_{321}(n)x^n=\sum_{n\geq 3}{n\choose 3}F_{n+1}x^n-
2\sum_{n\geq 3}f_{312}(n)x^n
\end{align}
from the observation $2f_{312}(n)+f_{321}(n)={n\choose 3}F_{n+1}$.
Thus formula~\eqref{Tca2} is obtained by substituting equation
\eqref{fb3} and the generating function of $f_{312}(n)$ into
formula~\eqref{Tta2f}.
\end{proof}

The first few values of $f_q(S_n(123,132,213))$ for $q$ of length
$3$ are shown below, and $(f_{231}(n))_{n\geq 3}$ form sequence
\seqnum{A152881} in \cite{Slo}.

\bigskip

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|}
\hline  $n$&$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$
&$f_{321}$
& $n$&$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$\\
\hline   $3$ &$0$      &$0$      &$0$       &$1$      &$1$      &$1$ & $6$ &$0$      &$0$       &$0$     &$40$    &$40$     &$180$\\
\hline   $4$ &$0$      &$0$       &$0$       &$5$      &$5$       &$10$ &$7$ &$0$      &$0$       &$0$     &$95$    &$95$     &$545$\\
\hline   $5$ &$0$      &$0$       &$0$      &$15$     &$15$      &$50$ &$8$ &$0$      &$0$       &$0$     &$213$    &$213$     &$1478$\\
\hline
\end{tabular}\label{3a}
\end{center}

\bigskip

\subsection{Pattern popularity in other triply restricted permutations}
This subsection deals with the popularity of length-$3$ patterns
in the other four classes of triply restricted permutations. We
begin with a helpful lemma from \cite{Sim} as follows:
\begin{lemma}{\rm (\cite[Proposition\ $16^*$]{Sim})}We have
\begin{align}\label{Ta-2}
\sg\in S_n(123,132,231)&\Leftrightarrow
\sg=n,n-1,\ldots,k+1,k-1,k-2,\ldots,2,1,k \text{ for some } k.\\
\label{Ta-3}
 \sg\in S_n(132,213,231)&\Leftrightarrow
 \sg=n,n-1,\ldots,k+1,1,2,3,\ldots,k-1,k \text{~for some~} k.\\ \label{Ta-4}
 \sg\in S_n(123,132,312)&\Leftrightarrow \sg=n-1,n-2,\ldots,k+1,n,k,k-1,\ldots,1 \text{ for some }
 k.\\\label{Ta-5}
 \sg\in S_n(123,231,312)&\Leftrightarrow
 \sg=k-1,k-2,\ldots,3,2,1,n,n-1\ldots,k \text{~for some~} k.
\end{align}
\end{lemma}

Appealing to the above structural characterizations, we can derive
the pattern popularity in those classes as follows.
\begin{theorem}
For $n\geq 3$, in the set $S_n(123,132,231)$, we have
\begin{align}
f_{213}(n)&=f_{312}(n)={n\choose 3},\\
f_{321}(n)&=(n-2){n\choose 3}.
\end{align}
\end{theorem}

\begin{proof}
According to the structural formula~\eqref{Ta-2}, the identity
$f_{213}(n)=f_{312}(n)$ can be proved by a direct bijection.

Let $q=abc$ ($b<a<c$) be a copy of $213$-pattern in $\sg \in
S_n(123,132,231)$. We have $\sg(n)=c$ since $b<c$ and $\sg\in
S_n(123,132,231)$ has only one ascent at position $n-1$.
Therefore, $q$ is a $213$-pattern in the sole permutation
\[\sg=n,n-1,\ldots,c+1,c-1,\ldots,\underline{a},\ldots,\underline{b},\ldots,2,1,\underline{c}.\]
For the sake of clarity, we underline the occurrence of the
assumed pattern.

For $q'=cba$ ($312$-pattern), we find similarly that
$q'$ is a $312$-pattern in
\[\sg'=n,n-1,\ldots,\underline{c},\ldots,a+1,a-1,\ldots,\underline{b},\ldots,2,1,\underline{a}.\]
For example, if $n=7$ and $q=326$, then
$\sg=7\,5\,4\,\underline{3}\,\underline{2}\,1\,\underline{6}$, $q'=623$ and
$\sg'=7\,\underline{6}\,5\,4\,\underline{2}\,1\,\underline{3}$.

Hence, for every copy of $213$-pattern $(q,\sg)$, there is a
unique copy of $312$-pattern $(q',\sg')$, and the converse is also
true. This implies that $f_{213}(n)=f_{312}(n)$.

To calculate $f_{312}(n)$, we suppose
$\sg=n,n-1,\ldots,k+1,k-1,k-2, \ldots,2,1,k$ for some $k$. We
construct a $312$-pattern as follows: Choose one element from the
first $n-k$ elements to play the role of $``3"$, then choose one
element from the next $k-1$ elements to play the role of $``1"$,
and the last element plays the role of $``2"$. Thus, summing up
 $k$ gives
\[
f_{312}(n)=\sum_{k=1}^n
(n-k)(k-1)=-n^2+(n+1)\sum_{k=1}^nk-\sum_{k=1}^nk^2=\frac{n(n-1)(n-2)}{6}={n\choose
3}.
\]
The proof is completed by the relation
$f_{213}(n)+f_{312}(n)+f_{321}(n)=n{n\choose 3}.$\end{proof}



The first few values of $f_q(S_n(123,132,231))$ for $q$ of length
$3$ are shown below, and $(f_{213}(n))_{n\geq 3}$ form sequence
\seqnum{A000292}, $(f_{321}(n))_{n\geq 3}$ form sequence
\seqnum{A002417} in \cite{Slo}.

\bigskip

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|}
\hline  $n$&$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$ &$n$&$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$\\
\hline   $3$ &$0$      &$0$      &$1$&$0$             &$1$      &$1$ &$6$ &$0$      &$0$       &$20$&$0$         &$20$     &$80$\\
\hline   $4$ &$0$      &$0$      &$4$ &$0$             &$4$       &$8$&$7$ &$0$      &$0$       &$35$   &$0$         &$35$     &$175$\\
\hline   $5$ &$0$      &$0$      &$10$ &$0$           &$10$      &$30$ &$8$ &$0$      &$0$       &$56$   &$0$         &$56$     &$336$\\
\hline
\end{tabular}\label{3b}
\end{center}

\bigskip

\begin{theorem}
For $n\geq 3$, in the set $S_n(132,213,231)$, we have
\begin{align}
f_{123}(n)&=f_{312}(n)={n+1\choose 4},\\
f_{321}(n)&=\frac{n(n-2)(n-1)^2}{12}.
\end{align}
\end{theorem}
\begin{proof}
Based on structural formula~\eqref{Ta-3}, we could also prove
$f_{123}(n)=f_{312}(n)$ directly. Let $abc$ be a $123$-pattern in
\[
\sg=n,n-1,\ldots,k+1,1,\ldots, \underline{a},a+1,\ldots,
\underline{b},b+1,\ldots,c-1,\underline{c},c+1,\ldots,k-1,k.
\]
Set
\[
\sg'=n,n-1,\ldots,\underline{n-k+c},\ldots,c,1,2,\ldots,
\underline{a},a+1,\ldots,\underline{b},b+1,\ldots,c-1.
\]
It is easy to check that $(n-k+c)\,a\,b$ is a $312$-pattern of
$\sg'$. For example, if $\sg=9\,8\,7\,1\,\underline{2}\,
\underline{3}\,4\, \underline{5}\,6$, then
$\sg'=9\,\underline{8}\,7\,6\,5\,1\, \underline{2}\,
\underline{3}\,4$.

To calculate $f_{123}(n)$, we suppose
$\sg=n,n-1,\ldots,k+1,1,2,\ldots,k-1,k$ for some $k$. A
$123$-pattern can be obtained by picking three elements from the
last $k$ elements to play the role of $``123"$. Thus, summing up
all possible $k$ gives
\[
f_{123}(n)=\sum_{k=1}^n {k \choose 3}={n+1\choose 4}.
\]
We complete the proof from
$f_{123}(n)+f_{312}(n)+f_{321}(n)=n{n\choose 3}$.\end{proof}

The first few values of $f_q(S_n(132,213,231))$ for $q$ of length
$3$ are shown below, and $(f_{123}(n))_{n\geq 3}$ form sequence
\seqnum{A000332}, $(f_{321}(n))_{n\geq 3}$ form sequence
\seqnum{A002415} in \cite{Slo}.

\bigskip

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|}
\hline $n$ &$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$ &$n$ &$f_{123}$&$f_{132}$&$f_{213}$ &$f_{231}$&$f_{312}$  &$f_{321}$\\
\hline   $3$ &$1$      &$0$      &$0$       &$0$      &$1$      &$1$ &$6$ &$35$      &$0$       &$0$     &$0$    &$35$     &$50$\\
\hline   $4$ &$5$      &$0$       &$0$       &$0$      &$5$       &$6$  & $7$ &$70$      &$0$       &$0$     &$0$    &$70$     &$105$\\
\hline   $5$ &$15$      &$0$       &$0$      &$0$     &$15$      &$20$ & $8$ &$126$      &$0$       &$0$     &$0$    &$126$     &$196$\\
\hline
\end{tabular}\label{3c}
\end{center}



\begin{theorem}
For $n\geq 3$, in the set $S_n(123,132,312)$, we have
\begin{align}
f_{213}(n)&=f_{231}(n)={n\choose 3},\\
f_{321}(n)&=(n-2){n\choose 3}.
\end{align}
\end{theorem}
\begin{proof}

In view of the structural formula~\eqref{Ta-4}, the equality
$f_{213}(n)=f_{231}(n)$ can be proved by a direct correspondence.
Let $abn$ be a copy of $213$-pattern in
\[\sg=n-1,\ldots,\underline{a},a+1,\ldots,\underline{b},b+1,\ldots,k+1,\underline{n},
k,k-1, \ldots,2,1.\] Set
\[\sg'=n-1,\ldots,\underline{n-a+b},\ldots,n-a+k+1,\underline{n},n-a+k,n-a+k-1,\ldots,
\underline{n-a},\ldots,2,1.\] Then $n-a+b,n,n-a$ is a
$231$-pattern of $\sg'$. For example, if
$\sg=8\,\underline{7}\,6\,\underline{5}\,4\,\underline{9}\,3\,2\,1$,
then
$\sg'=\sg=8\,\underline{7}\,6\,\underline{9}\,5\,4\,3\,\underline{2}\,1$.

To calculate $f_{213}(n)$, we suppose that
$\sg=n-1,n-2,\ldots,k+1,n,k,k-1,\ldots,2,1$ for some $k$. A
$213$-pattern can be obtained by choosing two elements from the
first $n-k-1$ elements to play the role of $``21"$, and let $n$
play the role of $``3"$. Thus, summing up all possible $k$, we
have\[ f_{213}(n)=\sum_{k=0}^{n-1} {n-k-1 \choose 2}={n\choose 3}.
\]
The proof is completed by using the relation
$f_{213}(n)+f_{231}(n)+f_{321}(n)=n{n\choose 3}$.\end{proof}


\begin{theorem}
For $n\geq 3$, in the set $S_n(123,231,312)$, we have
\begin{align}
f_{132}(n)&=f_{213}(n)={n+1\choose 4},\label{Tte1}\\
f_{321}(n)&=\frac{n(n-2)(n-1)^2}{12}.
\end{align}
\end{theorem}
\begin{proof} From Lemma~\ref{oper}, we see that
\[
\sg \in S_n(123,231,312)\Leftrightarrow \sg^{r}\in
S_n(321,132,213)\Leftrightarrow (\sg^{r})^c\in S_n(123,231,312).
\]
As a consequence, we have $f_{213}(n)=f_{132}(n)$ from
$(213^{r})^c=312^c=132$.

For $f_{213}(n)$, we will employ the structure in
formula~\eqref{Ta-5}. Suppose
$\sg=k-1,k-2,\ldots,3,2,1,n,n-1\ldots,k$ for some $k$. A
$213$-pattern can be obtained as follows: Choose two elements from
the first $k-1$ elements to play the role of $``21"$, and choose
one element from the last $n-k+1$ elements to play the role of
$``3"$. Thus, summing up all possible $k$, we have
\begin{align*}
f_{213}(n)&=\sum_{k=1}^n {k-1 \choose
2}(n-k+1)=\sum_{k=0}^{n-1}{k\choose 2}(n-k)={n+1\choose 4}.
\end{align*}
The formula for $f_{321}(n)$ is obtained by the relation
$2f_{213}(n)+f_{321}(n)=n{n\choose 3}$.  \end{proof}

\section{Acknowledgments}

The author thanks the anonymous referee and the editor for their
helpful comments. This work was supported by the National Natural
Science Foundation of China (No.\ 11401316), the Natural Science
Foundation of Jiangsu Province (No.\ BK20131393) and Program of
Natural Science Research of Jiangsu Higher Education Institutions
of China (No.\ 13KJB110019).

\begin{thebibliography}{99}
\bibitem{Bona2011}
M. B\'{o}na, {\it A Walk Through Combinatorics}, 3rd edition,
World Scientific, 2011.

\bibitem{Bona2010}
M. B\'{o}na, The absence of a pattern and the occurrences of
another, {\it Discrete Math. Theor. Comput. Sci}. {\bf 12} (2010),
89--102.

\bibitem{Bona}
M. B\'{o}na, Surprising symmetries in objects counted by Catalan
numbers, {\it Electron. J. Combin}. {\bf 19} (2012), P62.

\bibitem{Chua}
L. Chua and K. R. Sankary, Equipopularity classes of
$132$-avoiding permutations, {\it Electron. J. Combin}. {\bf 21}
(2014), P1.59.

\bibitem{Com}
L. Comtet, {\it Advanced Combinatorics}, Reidel, 1974.

\bibitem{Coo}
J. Cooper, {\it Combinatorial Problems I like}, available at \\ 
\url{http://www.math.sc.edu/~cooper/combprob.html}.

\bibitem{Do}
T. Dokosa, T. Dwyer, B. P. Johnson, B. E. Sagan, and K. Selsor,
Permutation patterns and statistics, {\it Discrete Math}. {\bf
312} (2012), 2760--2775.

\bibitem{Eli}
S. Elizalde, Multiple pattern avoidance with respect to fixed
points and excedances, {\it Electron. J. Combin}. {\bf 11} (2004),
R51.

\bibitem{Hom}
C. Homberger, Expected patterns in permutation classes, {\it
Electron. J. Combin}. {\bf 19} (2012), P43.


\bibitem{Man01}
T. Mansour, Permutations avoiding a pattern from $S_k$ and at
least two patterns from $S_3$, {\it Ars Combin}. {\bf 62} (2001),
227--239.


\bibitem{Man04}
T. Mansour, Permutations containing a pattern exactly once and
avoiding at least two patterns of three letters, {\it Ars Combin}.
{\bf 72} (2004), 213--222.


\bibitem{MaRo}
T. Mansour and A. Robertson, Refined restricted permutations
avoiding subsets of patterns of length three, {\it Ann. Combin}.
{\bf 6} (2003), 407--418.



\bibitem{Rud}
K. Rudolph, Pattern popularity in $132$-avoiding permutations,
{\it Electron. J. Combin}. {\bf 20} (2013), P8.


\bibitem{Sim}
R. Simion and F. W. Schmidt, Restricted permutations, {\it
European J. Combin}. {\bf 6} (1985), 383--406.


\bibitem{Slo}
N. J. A. Sloane, {\it On-Line Encyclopedia of Integer Sequences},
\url{http://oeis.org}.

\bibitem{Sta}
R. P. Stanley, {\it Enumerative Combinatorics}, Vol.~1, Cambridge
University Press, 1997.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary
05A05; Secondary 05A15;   05A19.

\noindent \emph{Keywords: } permutation, pattern, composition,
binary plane tree, Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000292},
\seqnum{A000332}, \seqnum{A000337}, \seqnum{A000389},
\seqnum{A001789}, \seqnum{A002415}, \seqnum{A002417},
\seqnum{A045618}, \seqnum{A055580}, \seqnum{A055581},
\seqnum{A055586}, and \seqnum{A152881}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in} \noindent 
Received April 8 2014;
revised versions received August 30 2014; September 19 2014; September
22 2014.
Published in {\it Journal of Integer Sequences}, November 2 2014.

\bigskip
\hrule
\bigskip

\noindent Return to \htmladdnormallink{Journal of Integer
Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}