\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P28}{20(1)}{2013}

%\usepackage{mathrsfs}
%\usepackage{bbm}
%\usepackage{enumerate}
%\usepackage{array}

%\setlength{\topmargin}{-0.5in}
%\setlength{\oddsidemargin}{.1in}
%\setlength{\evensidemargin}{.1in}
%\setlength{\textheight}{8.5in}
%\setlength{\textwidth}{6.25in}




\usepackage{latexsym}
\usepackage{amsthm,amsmath,amssymb}

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

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

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



\newcommand{\id}{\mathsf{id}}  



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% greek %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\epsilon{\varepsilon}
\def\eps{\varepsilon}
\def\e{\varepsilon}
\def\g{\gamma}
\def\k{\kappa}
\def\m{\mu}
\def\n{\nu}
\def\o{\omega}
\def\s{\sigma}
\def\t{\tau}
\def\z{\zeta}

\def\D{\Delta}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% roman %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\SCD{{\rm SCD}}
\def\Prob{{\rm Prob}}
\def\Exc{{\rm Exc}}
\def\DB{{\rm DesBot}}
\def\12-34{\text{12--34}}
\def\21-34{\text{21--34}}
\def\34-21{\text{34--21}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% mathbb %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\PP{\mathbb{P}}
\def\EE{\mathbb{E}}
\def\bbE{\mathbb{E}}
\def\bbN{\mathbb{N}}
\def\bbP{\mathbb{P}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  cal   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\cE{\mathcal{E}}
\def\cI{\mathcal{I}}
\def\cJ{\mathcal{J}}
\def\cO{\mathcal{O}}
\def\cR{\mathcal{R}}
\def\cS{\mathcal{S}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  bold  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\bi{\mathbf{i}}
\def\bj{\mathbf{j}}
\def\bq{\mathbf{q}}
\def\by{\boldsymbol{y}}
\def\bP{\boldsymbol{P}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  misc  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\l{\ell}

\def\tEj0r{\tilde{E}_{j_0}^{(r)}}  




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%             Authors/Abstract               %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\title{\bf Generalized pattern frequency\\ in large permutations}

\author{Joshua Cooper \thanks{The first author was partially supported by NSF grant DMS-1001370.}\\
\small Department of Mathematics\\[-0.8ex]
\small University of South Carolina\\[-0.8ex] 
\small Columbia, SC, U.S.A.\\
\small\tt cooper@math.sc.edu\\
\and
Erik Lundberg \\
\small Department of Mathematics \\[-0.8ex]
\small Purdue University\\[-0.8ex]
\small West Lafayette, IN, U.S.A.\\
\small\tt elundber@math.purdue.edu
\and
Brendan Nagle \thanks{The third author was partially supported by NSF grant DMS-1001781}    \\
\small Department of Mathematics and Statistics \\[-0.8ex]
\small University of South Florida\\[-0.8ex]
\small Tampa, FL, U.S.A.\\
\small\tt bnagle@usf.edu
}


\date{\dateline{Sep 7, 2012}{Jan 29, 2013}{Feb 5, 2013}\\
\small Mathematics Subject Classifications: 05A05, 05A16}


\begin{document}

\maketitle

\begin{abstract}
In the study of permutations, 
generalized patterns extend classical patterns by adding the requirement that certain adjacent integers in a pattern must be adjacent in the permutation.

For any generalized pattern $\pi_0^*$ of length $k$ with $1 \leq b \leq k$ blocks, 
we prove that for all $\mu > 0$, 
there exists $0 < c = c(k, \mu) < 1$ so that  
whenever $n \geq n_0(k, \mu, c)$, 
all but $c^n n!$ many $\pi \in S_n$ 
admit $(1 \pm \mu) \tfrac{1}{k!} \tbinom{n}{b}$ occurrences of $\pi_0^*$.  
Up to the choice of $c$, 
this result is best possible for all 
$\pi_0^*$ with 
$k \geq 2$.  



We also give a lower bound on avoidance of the generalized pattern 
$12$-$34$, which answers a question of S.~Elizalde \cite{El} (2006).  

\bigskip\noindent \textbf{Keywords:} generalized patterns; pattern avoidance; Azuma's inequality; Chernoff's inequality;
Sharkovsky's Theorem
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%           Section 1: Introduction          %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
Pattern and generalized pattern avoidance in permutations is a well-studied area (see, e.g.,[1--5, 7, 8, 10, 11]).  
Fix $1 \leq k \leq n$ and $\pi_0 \in S_k$ and let $\pi \in S_n$.  
An occurrence of a {\it pattern} $\pi_0$ in $\pi$ is a sequence of integers $1\leq \l_1 < \dots < \l_k \leq n$ so that, 
for all $1 \leq i \neq j \leq k$, 
\begin{equation}
\label{eqn:patterprop}
\pi (\l_{i}) < \pi (\l_{j}) \quad \iff \quad \pi_0(i) < \pi_0(j).  
\end{equation}
In order to define generalized patterns, take a classical pattern $\pi_0 = (a_1, \dots, a_k) = (\pi_0(1), \dots, \pi_0(k))$, and fix 
$\pi_0^* = (a_1,\eps_1, a_2, \eps_2, \dots,\eps_{k-1}, a_k)$ where, for each $1\leq i \leq k-1$, 
$\eps_i$ is either a dash `$-$' or the empty string.  
Then, $\pi \in S_n$ admits
$\pi_0^*$ as a {\it generalized pattern} 
if it contains an occurrence $1 \leq \l_1 < \dots < \l_k \leq n$ of the classical pattern $\pi_0$ satisfying that,  
\begin{equation}
\label{eqn:genpatternprop}
\text{whenever $\eps_i \neq -$, then $\l_{i+1} = \l_i + 1$.}
\end{equation}  
More explicitly, 
suppose, for some positive integer sequence $\bq = (q_1, \dots, q_b)$, for which
$q_1 + \dots + q_b = k$, that
\begin{equation}
\label{eqn:genform}
\begin{aligned}
\pi_0^* = 
\pi_0^{\bq} &= \big(a_1, \dots, a_{q_1}, -, a_{q_1 + 1}, \dots, a_{q_1 + q_2}, -, \dots, 
-, a_{k - q_b + 1}, \dots, a_k\big) \\
&= (A_{1}, -, A_{2}, -, \dots, -, A_{b}).  
\end{aligned}
\end{equation}
%We shall refer to the subsequences $A_1, \dots, A_b$ as {\it blocks}, and to $\bq = (q_1, \dots, q_b)$ as the {\it block structure} of $\pi_0^* = \pi_0^{\bq}$.  
Then, 
for some integers $1\leq \hat{\l}_1 < \dots < \hat{\l}_b \leq n$, 
%the generalized pattern 
%$(\l_1, \dots, \l_k)$ has the form 
\begin{equation}
\label{eqn:genform'}
\begin{aligned}
(\l_1, \dots, \l_k) &= 
\left(\hat{\l}_1, \dots, \hat{\l}_1 + q_1 - 1, \  \ \hat{\l}_2, \dots, \hat{\l}_2 + q_2 - 1, \  \ \dots, \  \ \hat{\l}_b, \dots, \hat{\l}_b + q_b - 1\right) \\
&= (L_1, \dots, L_b).  
\end{aligned}
\end{equation}
We shall refer to the subsequences $A_1, \dots, A_b$ and $L_1, \dots, L_b$ as {\it blocks}.  

As an illustrative example, we note that the 
permutation
$(3,5,2,4,1) = 
35241$ contains the classical pattern $132$ (realized uniquely by the $3$, $5$, and $4$ occuring in that order).
However, $35241$ does not contain the generalized pattern $1$-$32$, since the $5$ and $4$ are not adjacent.

Let $f_{\pi_0^*}(\pi)$ denote the frequency of the generalized pattern $\pi_0^*$ in $\pi$, 
and set $F_{\pi_0}(\pi) = f_{\pi_0^*}(\pi)$ in the case that $\bq = (1, \dots, 1)$ (i.e., classical patterns).
In this notation, 
the celebrated result of Marcus and Tardos~\cite{MT} (cf.~Klazar~\cite{K}) asserts $F_{\pi_0} (\pi) \geq 1$
for all but $C^n$ permutations $\pi \in S_n$, where $C = C(\pi_0) > 1$ and $n$ is sufficiently large.  The first author~\cite{Cooper} proved that 
$F_{\pi_0}$ is concentrated about its mean:  
$F_{\pi_0}(\pi) = (1 \pm o(1)) \tfrac{1}{k!} \tbinom{n}{k}$ for all but $o(n!)$ permutations $\pi \in S_n$.  
Our main result shows, more generally, that 
$f_{\pi_0^*}$ is also concentrated about its mean, 
and we provide a sharp estimate for the error $o(n!)$ of concentration.
\begin{theorem}
\label{thm:gen}
For every $k \geq 1$ 
and for all $\mu > 0$,    
there exists $0 < c < 1$ so that, for all sufficiently large integers $n$, the following holds.  
For every $\pi_0 \in S_k$ and for every sequence $\pi_0^*$ with $b$ blocks as in~(\ref{eqn:genform}), 
all but $c^n n!$ many $\pi \in S_n$ 
satisfy 
$f_{\pi_0^*}(\pi) = (1 \pm \mu) \tfrac{1}{k!} \tbinom{n}{b}$.  
\end{theorem}


\begin{remark}
\rm 
In Section~2, 
we offer two proofs of Theorem~\ref{thm:gen}.  
The first, based on martingales, is fairly short.
The second gives more detail, using a `quasi-random' property (see Lemma~\ref{lem:gen}) typical of random permutations. 
Lemma~\ref{lem:gen} extends some results from \cite{Cooper} and may be of independent interest.
%(The drawback to the second proof is that we must prove Lemma~\ref{lem:gen}, which we do in Section~4.)  
\end{remark}

Up to the choice of $0 < c < 1$, Theorem~\ref{thm:gen} is best possible for all $\pi_0^*$ with $k \geq 2$.  
In particular, we prove the following result.  

\begin{prop}
\label{prop:bestposs}  
Fix $k \geq 2$, $b\geq 1$, and
$\pi_0 = (a_1, \dots, a_k) \in S_k$.
Let $\pi_0^*$ 
be any sequence, as in~(\ref{eqn:genform}), with $b$ blocks.  
Then, there exists $0 < \g_0 < 1$ so that, for all $0 < \gamma < \g_0$, 
there exist infinitely many integers $n$ for which at least $\g ^n n!$ permutations $\pi \in S_n$ satisfy 
$f_{\pi_0^*}(\pi) < \g n^b$.   
\end{prop} 
\noindent We 
prove Proposition~\ref{prop:bestposs} in Section~3.  


Proposition~\ref{prop:bestposs} 
can often be strengthened.  
Indeed, S.~Elizalde~\cite{El} proved the following strong and quite general result (in~\cite{El}, see Proposition~4.3).  

\begin{theorem}[Elizalde~\cite{El}]
\label{thm:avoidance}  
Let $\pi_0^*$ be a sequence, as in~(\ref{eqn:genform}), having a block $A_i$ of length at least 3.  Then, there exists $0 < c < 1$ so that for all $n \geq k$, at least $c^n n!$ permutations $\pi \in S_n$ satisfy $f_{\pi_0^*}(\pi) = 0$.  
\end{theorem}  

Elizalde~\cite{El} also considered 
to what extent Theorem~\ref{thm:avoidance} can be extended to sequences $\pi_0^*$ whose every block has length at most two.  
He showed that, in general, 
Theorem~\ref{thm:avoidance} can't be extended to every such $\pi_0^*$.  
To describe these results, let $A_n(\pi_0^*)$ denote the set of permutations $\pi \in S_n$ for which $f_{\pi_0^*}(\pi) = 0$, and let $\alpha_n(\pi_0^*) = |A_n(\pi_0^*)|$.  
For $(1,-,2,3,-,4) = \text{1--23--4}$,   
Elizalde showed 
(see Corollary~6.2 in~\cite{El})
\begin{equation}
\label{eqn:1-23-4}
\lim_{n\to \infty} \left(
\frac{\a_n (\text{1--23--4})}{n!}\right)^{1/n} = 0.  
\end{equation}
He 
asked (see Section~7 of~\cite{El}):   
\begin{equation}
\label{eqn:12-34}
\text{{\it does} }
\lim_{n\to \infty} \left(
\frac{\a_n (\text{12--34})}{n!}\right)^{1/n} = 0 \text{{\it ?}}    
\end{equation}
We answer this question in the negative.  

\begin{theorem}
\label{thm:12-34}
For odd integers $n$, 
$$
\alpha_n (\text{{\rm 12--34}}) \geq \left(\frac{1}{2} - o(1)\right)^n n!.  
$$
\end{theorem}  
\noindent We prove Theorem~\ref{thm:12-34} in Section~4, and also consider some related problems.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%    Section 2 : Proof of Main Theorem       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Proofs of Theorem~\ref{thm:gen}}    
For both of the   
following proofs, fix a positive integer $k$ and fix $\mu > 0$.  


\subsection{The martingale proof}  
Let
\begin{equation}
\label{eqn:martc}  
c = \exp \left\{- \frac{\mu^2}{9 k^4 k!^2}\right\}
\end{equation}  
and let $n$ be a sufficiently large integer wherever needed.  
Fix $\pi_0^*$ with $b$ blocks as 
in~(\ref{eqn:genform}).   
We show that all but $c^n n!$ many $\pi \in S_n$ satisfy $f_{\pi_0^*}(\pi) = (1 \pm \mu) \tfrac{1}{k!} \tbinom{n}{b}$.  



To that end, 
let $\pi\in S_n$ be chosen uniformly at random.  
We use the `exposure process' to define the following sequence of random variables.  
Set 
\begin{equation}
\label{eqn:X_0}
X_0 = \EE[f_{\pi_0^*} (\pi)], \text{ where from~(\ref{eqn:genform'}), we have }  
(1 - o(1)) \frac{1}{k!} \binom{n}{b}  
\leq 
\EE[f_{\pi_0^*} (\pi)]  
\leq \frac{1}{k!} \binom{n}{b}.    
\end{equation}  
For $r \in [n] = \{1, \dots, n\}$, let 
$\pi_{[r]}$ denote
the restriction $\pi : [r] \to [n]$.  
Set 
$$
X_r = \EE \left[ f_{\pi_0^*}(\pi) \Big| \pi_{[r]} \right], 
$$
so that $X_n = f_{\pi_0^*}(\pi)$ is the variable we wish to estimate.  
Then, $X_0, X_1, \dots, X_n$ is the Doob martingale for the function $f_{\pi_0^*}$, to which we will apply
Azuma's inequality.  


For that purpose, observe that for each $0 \leq r \leq n-1$, 
\begin{equation}  
\label{eqn:differences}  
|X_{r+1} - X_r| \leq k \binom{n}{b-1}.  
\end{equation}
To see this, note that 
the element $r+1$ belongs to between 
zero and 
$k\tbinom{n}{b-1}$ occurrences $(\l_1, \dots, \l_k)$ of $\pi_0^*$ in $\pi$.  Indeed, 
if 
$\l_i = r+1$ belongs to block $L_{i'}$ (see~(\ref{eqn:genform'})), then all of $L_{i'}$ is determined by $r+1 = \l_i$ and $\bq = \bq (\pi_0^*)$.  Thus, it remains
to determine $L_1, \dots, L_{i' - 1}, L_{i'+1}, \dots, L_b$, or equivalently, $\hat{\l}_1, \dots, \hat{\l}_{i'-1}, \hat{\l}_{i'+1}, \dots, \hat{\l}_b$, of which 
there are at most $\tbinom{n}{b-1}$.  

Applying Azuma's inequality with $t = (\mu/2) X_0$
and using~(\ref{eqn:X_0})
and~(\ref{eqn:differences}), we have 
\begin{multline*}  
\bbP \big[|X_n - X_0| \geq t\big] \leq 2 \exp \left\{ - \frac{t^2}{2\sum_{r=0}^{n-1} (X_{r+1} - X_r)^2} \right\}  
\leq 
\exp \left\{ - \frac{\mu^2 \frac{1}{k!^2}\binom{n}{b}^2}{8n k^2 \binom{n}{b-1}^2} (1 - o(1)) \right\}   \\
= 
\exp \left\{ - \frac{\mu^2 n}{8 k!^2 k^2 b^2}  (1 - o(1)) \right\}   
\leq 
\exp \left\{ - \frac{\mu^2 n}{8 k!^2 k^4}  (1 - o(1)) \right\}   
\leq 
\exp \left\{ - \frac{\mu^2 n}{9 k!^2 k^4}\right\}   
\stackrel{\text{(\ref{eqn:martc})}}{=}
c^n.      
\end{multline*}  
Thus, with probability $1 - c^n$, 
$$
f_{\pi_0^*}(\pi) = 
\left(1 \pm \frac{\mu}{2} \right)  
\EE[f_{\pi_0^*} (\pi)] 
\stackrel{\text{(\ref{eqn:X_0})}}{=}  
\left(1 \pm \frac{\mu}{2} \right)  
(1 \pm o(1)) 
\frac{1}{k!} \binom{n}{b}    
= 
(1 \pm \mu) 
\frac{1}{k!} \binom{n}{b},     
$$
as desired.  


\subsection{The quasi-random proof}  
To present Lemma~\ref{lem:gen}, we need a few 
concepts.
%\footnote{We   
%write $[a, b] = \{a, a+1, \dots, b\}$ and 
%$(X)_m$ 
%for the family of $m$-permutations of $X$.}.             
For integers 
$n > t \geq j \geq 1$, 
define 
$I_j = [(j-1) \lfloor n/t \rfloor + 1, 
j \lfloor n/t \rfloor]$  
and $R = [n] \setminus \bigcup_{j=1}^{t} I_j$.   
We call $[n] = I_1 \cup I_2 \cup \dots \cup I_t \cup R$ 
the {\it $t$-partition} $\bP_t$ of $[n$].  
Now, fix $\pi \in S_n$, and consider partitions
$\bP_s = I_1 \cup \dots \cup I_s \cup R_s$ and $\bP_t = E_1 \cup \dots \cup E_t \cup R_t$ of $[n]$, where $n > t \geq s \geq q \geq 1$.  
For a set $X$,    
we will write $(X)_m$ 
for the family of $m$-permutations of $X$, 
and we write $(|X|)_m$ for $|(X)_m|$, when $|X|$ is finite.
For 
$\bi = (i_1, \dots, i_q) \in ([s])_q$ and $j \in [t]$, let 
\begin{equation}
\label{eqn:Ebijpi}
E_{\bi j} (\pi) = \Big\{ \hat{\l} \in E_j:  \, 
\hat{\l} + q - 1 \in E_j
\text{ and 
$\pi(\hat{\l} + m - 1) \in I_{i_m}$  
for all $m \in \{1, \dots, q \}$}
\Big\}.  
\end{equation}
%(We use $\hat{\l}$ notation above to draw a parallel to
%(\ref{eqn:genform'}).)
For $\z > 0$, 
and $(\bi, j) \in ([s])_q \times [t]$,    
we say $\pi \in S_n$ is {\it $(\bi, j, \z, q)$-typical
(w.r.t.~$(\bP_s, \bP_t)$)}  
if 
\begin{equation}  
\label{def:eqn:zqtyp}  
|E_{\bi j}(\pi)| \geq (1 - \z) \frac{1}{(s)_q} |E_j|
= 
(1 - \z) \frac{1}{(s)_q} \left\lfloor \frac{n}{t} \right\rfloor  
\end{equation}  
and say $\pi \in S_n$ is {\it $(\z, q)$-typical (w.r.t.~$(\bP_s, \bP_t)$)} if it is 
$(\bi, j, \z, q)$-typical %w.r.t.~$(\bP_s, \bP_t)$ 
for all $(\bi, j) \in ([s])_q \times [t]$.  
%The following lemma then says that $(\z, q)$-typicality is `typical' across $S_n$.  

\begin{lemma}
\label{lem:gen}  
For all $\z > 0$ and integers $q \geq 1$, there exists
an integer 
$s_0$ so that for all integers $s \geq s_0$, there exists 
an integer $t_0$ so that for all integers $t \geq t_0$, there exists $c_0 > 0$ so that for all sufficiently large integers
$n$, all but $\exp \{ - c_0 n\} n!$ permutations $\pi \in S_n$ are $(\z, q)$-typical w.r.t.~$(\bP_s, \bP_t)$.  
\end{lemma}

\noindent Lemma~\ref{lem:gen} follows by a standard (albeit tedious) 
probablistic analysis, which we give in Section~5. 



To show that Lemma~\ref{lem:gen} implies Theorem~\ref{thm:gen}, 
define auxiliary constants 
$\d, \z > 0$ so that 
\begin{equation}
\label{eqn:delzet}  
\d = \frac{\mu}{k!}  \qquad \text{and} \qquad (1 - 2\z)^{k+2} > 1 - \d.  
\end{equation}  
For $q \in [k]$, let $s_0(q)$
be the constant guaranteed by Lemma~\ref{lem:gen}.  
Fix an 
integer $s$ so that 
\begin{equation}
\label{eqn:gen-s}  
s \geq \max\left\{s_0(1), \dots, s_0(k)\right\} 
\qquad \text{and}
\qquad 
\binom{s}{k} \geq \frac{s^k}{k!} (1 - 2\z).  
\end{equation}
For $q \in [k]$, let 
$t_0(q)$ be the constant guaranteed by Lemma~\ref{lem:gen}.  Fix an integer
$t$ with 
\begin{equation}
\label{eqn:gen-t}  
t\geq \max\big\{t_0(1), \dots, t_0(k)\big\} \qquad \text{and so that for all $b \in [k]$,} \qquad \binom{t}{b} \geq \frac{t^b}{b!} (1 - 2\z).  
\end{equation}
For $q \in \{1, \dots, k\}$, 
let $c_0(q) > 0$ be the constant guaranteed by Lemma~\ref{lem:gen}.  
Define 
\begin{equation}
\label{eqn:gen-c}  
c_0 = \min \big\{c_0(1), \dots, c_0(k) \big\} \qquad \text{and} \qquad c = \exp\left\{- c_0 / 4 \right\}.    
\end{equation}
In all that follows, let $n$ be a sufficiently large integer.




Fix a permutation
$\pi_0 \in S_k$, 
and let $\pi_0^* = \pi_0^{\bq} = (A_1, -, \dots, -, A_b)$ 
be given as in~(\ref{eqn:genform}) 
where $\bq = (q_1, \dots, q_b)$.  
%We prove that all but $c^n n!$ permutations $\pi \in S_n$ satisfy $f_{\pi_0^{\bq}}(\pi) = (1 \pm \mu) \tfrac{1}{k!}\tbinom{n}{b}$.
Apply Lemma~\ref{lem:gen} (cf.~(\ref{eqn:gen-s})--(\ref{eqn:gen-c})) to conclude that all 
but 
$$
\Big( \exp \big\{ -c_0(q_1) n\big\} + \dots + \exp \big\{- c_0(q_b) n \big\}  \Big) n! \leq 
k \exp \{ - c_0 n \} n! \leq \exp \left\{ - \frac{c_0}{2} n\right\} n!
$$
permutations $\pi \in S_n$ are 
$(\z, q_x)$-typical w.r.t.~$(\bP_s, \bP_t)$ for all $x \in [b]$.  
For such a $\pi \in S_n$, we show   
\begin{equation}
\label{eqn:genlowerbound}  
f_{\pi_0^{\bq}}(\pi) \geq (1 - \d) \frac{1}{k!} \binom{n}{b} 
\stackrel{\text{(\ref{eqn:delzet})}}{>}  
 (1 - \mu) \frac{1}{k!} \binom{n}{b}.  
\end{equation}  





Indeed, fix indices $1 \leq i_1 < \dots < i_k \leq s$ and $1\leq j_1 < \dots < j_b \leq t$.    
For $x \in [b]$, recall the block 
$$
A_x 
= 
\big(a_{q_1 + \dots + q_{x-1} + 1}, \dots, a_{q_1 + \dots + q_x}\big)
= 
\big(\pi_0(q_1 + \dots + q_{x-1} + 1), \dots, \pi_0(q_1 + \dots + q_x)
\big)
$$
of $\pi_0^{\bq}$ (cf.~(\ref{eqn:genform})).  
Consider the injection
defined by, for each $x \in [b]$, 
\begin{align}
\label{eqn:pi*0}
j_x \longmapsto
\bi_x 
\stackrel{\text{def}}{=}  
\big(i_a\big)_{a \in A_{x}} 
&= 
\left(
i_{a_{q_1 + \dots + q_{x-1} + 1}}, \dots, 
i_{a_{q_1 + \dots + q_x}}
\right) \\ 
&= 
\left(
i_{\pi_0(q_1 + \dots + q_{x-1} + 1)}, \dots, 
i_{\pi_0(q_1 + \dots + q_x)}    
\right).
\end{align}
For each $x \in [b]$, arbitrarily select $\hat{\ell}_x \in E_{\bi_x j_x}(\pi)$
(cf.~(\ref{eqn:Ebijpi})).  
We claim that 
%$1 \leq \hat{\l}_1 < \dots < \hat{\l}_b \leq n$ corresponds to an occurrence in $\pi$ of the generalized pattern $\pi_0^{\bq}$, in the 
%sense of~(\ref{eqn:genform'}).    
the sequence
\begin{equation}
\label{eqn:L1}  
(L_1, L_2, \dots, L_b), \qquad \text{where for each $x \in [b]$,} \qquad 
L_{x} = 
\big(
\hat{\l}_x, \hat{\l}_x + 1, \dots, \hat{\l}_x + q_x - 1
\big), 
\end{equation}
is 
exactly an occurrence in $\pi$ of the generalized pattern $\pi_0^{\bq}$.  
The sequence $(L_1, \dots, L_b)$ 
clearly satisfies~(\ref{eqn:genpatternprop}), since each $L_m$ is consecutive, and since 
$(L_1, L_2, \dots, L_b)$ precisely mimics the block structure of $\pi_0^{\bq} = (A_1, -, A_2, -, \dots, -, A_b)$  
(cf.~(\ref{eqn:genform})).    
It remains to check, therefore, that $(L_1, \dots, L_b)$ is an occurrence of the classical pattern $\pi_0$ in $\pi$, i.e., 
that $(L_1, \dots, L_b)$ satisfies~(\ref{eqn:patterprop}).  



Indeed, 
rewrite the sequence $(L_1, \dots, L_b)$ as
\begin{multline} 
\label{eqn:L2}  
(\l_1, \dots, \l_k) = 
\big(\l_1, \dots, \l_{q_1}, \l_{q_1 + 1}, \dots, \l_{q_1 + q_2}, \dots \dots, 
\l_{k - q_b + 1}, \dots, \l_k\big)  \\
\text{so that for $x\in [b]$,} \qquad 
L_x = 
\big(\l_{q_1 + \dots + q_{x-1} + 1}, \dots, \l_{q_1 + \dots + q_x}\big).    
\end{multline}  
Comparing~(\ref{eqn:L1}) and~(\ref{eqn:L2}), we see that 
a term of the sequence $(L_1, \dots, L_b)$
is determined by a choice of indices $1\leq x \leq b$ and $1\leq w \leq q_x$, and written simultaneously 
as 
\begin{equation}
\label{eqn:L3} 
\hat{\l}_x + w - 1 = \l_{q_1 + \dots + q_{x-1} + w}.    
\end{equation}  
(Such a term necessarily belongs to the block $L_x$.)  
Observe 
from~(\ref{eqn:Ebijpi}) 
and~(\ref{eqn:pi*0}) that 
\begin{equation}
\label{eqn:L4}  
\pi(\hat{\l}_x + w - 1) 
%= 
%\pi(\l_{q_1 + \dots + q_{x-1} + w})     
\in I_{i(x,w)}, \quad \text{where} \quad i(x,w) =  
i_{\pi_0(q_1 + \dots + q_{x-1} + w)}.        
\end{equation}  
Now, fix two terms (cf.~(\ref{eqn:L3})) of the sequence $(L_1, \dots, L_b)$:  
$$
\hat{\l}_x + w - 1 = \l_{q_1 + \dots + q_{x-1} + w}    
\qquad \text{and} \qquad 
\hat{\l}_y + z - 1 = \l_{q_1 + \dots + q_{y-1} + z},     
$$
where 
$1\leq x, y \leq b$, $1\leq w \leq q_{x}$ and $1\leq z \leq q_y$.  
From~(\ref{eqn:L4}), we conclude 
\begin{align*}  
&\pi\big(\l_{q_1 + \dots + q_{x-1} + w}\big) <     
\pi\big(\l_{q_1 + \dots + q_{y-1} + z}\big) 
\iff 
\max I_{i(x,w)} < \min I_{i(y,z)} \\ 
&\iff i(x,w) < i(y,z) \stackrel{\text{(\ref{eqn:L4})}}{\iff} 
i_{\pi_0(q_1 + \dots + q_{x-1} + w)} <        
i_{\pi_0(q_1 + \dots + q_{y-1} + z)} \\
&\iff 
\pi_0(q_1 + \dots + q_{x-1} + w) < 
\pi_0(q_1 + \dots + q_{y-1} + z), 
\end{align*}
as required 
by~(\ref{eqn:patterprop}).  
(For the last step, recall the ordering $1 \leq i_1 < \dots < i_k \leq s$ of the fixed indices.)   



Now, the discussion above implies 
that 
\begin{equation}
\label{eqn:discussionabove2}
f_{\pi_0^{\bq}}(\pi) \geq 
\sum \sum 
\left\{  
\prod_{x=1}^b \big|E_{\bi_x j_x}(\pi)\big|: \, 
1 \leq i_1 < \dots < i_k \leq s, \, 
1 \leq j_1 < \dots < j_b \leq t
\right\}.   
\end{equation}  
Since $\pi \in S_n$ is 
$(\z, q)$-typical 
w.r.t.~$(\bP_s, \bP_t)$ 
for every $q \in \{q_1, \dots, q_b\}$, 
we have, for each $x \in [b]$, 
$$
\big|E_{\bi_x j_x}(\pi) \big| \geq (1 - \z) \frac{1}{(s)_{q_x}} \left \lfloor \frac{n}{t} \right \rfloor 
\geq (1 - 2\z) \frac{n}{t(s)_{q_x}}
\geq 
(1 - 2\z) \frac{n}{ts^{q_x}}.  
$$
Returning to~(\ref{eqn:discussionabove2}), 
\begin{align*}
\frac{f_{\pi_0^{\bq}} (\pi)}{\binom{s}{k}\binom{t}{b}} \geq 
(1 - 2\z)^b \left(\frac{n}{t}\right)^b \prod_{x = 1}^b \frac{1}{s^{q_x}}  
&= 
(1 - 2\z)^b \left(\frac{n}{t}\right)^b \frac{1}{s^{q_1 + \dots + q_b}} \\
&= 
(1 - 2\z)^b 
\left(\frac{n}{t}\right)^b \frac{1}{s^k}    
\geq (1 - 2\z)^k 
\left(\frac{n}{t}\right)^b \frac{1}{s^k},       
\end{align*}
and  
so~(\ref{eqn:genlowerbound}) follows from   
$$
f_{\pi_0^{\bq}}(\pi) \geq 
\binom{s}{k}
\binom{t}{b}  
(1 - 2\z)^k \left(\frac{n}{t}\right)^b \frac{1}{s^k}  
\stackrel{\text{(\ref{eqn:gen-s}), (\ref{eqn:gen-t})}}{\geq}
(1 - 2\z)^{k+2}  
\frac{1}{k!} \left(\frac{n^b}{b!}\right)  
\stackrel{\text{(\ref{eqn:delzet})}}{\geq}    
(1 - \d)\frac{1}{k!} \binom{n}{b}.   
$$


The corresponding upper bound 
$f_{\pi_0^{\bq}} (\pi) \leq (1 + \mu) \tfrac{1}{k!} \tbinom{n}{b}$ 
follows, in fact, from the lower bound.  
Indeed, first conclude~(\ref{eqn:genlowerbound}) for every permutation $p \in S_k$ and $p^* = p^{\bq}$.  
Thus, 
all but 
$$
k! 
\exp \left\{ - \frac{c_0}{2} n \right\} n! < 
\exp \left\{- \frac{c_0}{4} n \right\} n!  
\stackrel{\text{(\ref{eqn:gen-c})}}{=}    
c_1^n n!
$$
permutations $\pi \in S_n$ satisfy, for every $p \in S_k$, $f_{p^{\bq}}(\pi) \geq (1 - \d) \tfrac{1}{k!} \tbinom{n}{b}$.  
Fix such a $\pi \in S_n$.  Observe that every 
$1 \leq \l_1 < \dots < \l_k \leq n$ of the form 
in~(\ref{eqn:L1}) and~(\ref{eqn:L2})
defines a generalized pattern $p^{\bq}$ of some $p \in S_k$.  
(Indeed, if $\pi (\{\l_1, \dots, \l_k\}) = \{\lambda_1, \dots, \lambda_k\}$, define $p(i) = j$ if and only if $\pi(\l_i) = \lambda_j$.)  
Thus, 
\begin{multline*}  
\binom{n}{b} \geq \sum_{p\in S_k} f_{p^{\bq}}(\pi) = f_{\pi_0^{\bq}} (\pi) + \sum_{\pi_0 \neq p \in S_k} f_{p^{\bq}}(\pi)  
\geq 
f_{\pi_0^{\bq}}(\pi) + 
(k! - 1) (1 - \d) \frac{1}{k!} \binom{n}{b}  \\ 
%= 
%f_{\pi_0^{\bq}}(\pi) + 
%(1 - \d) \left(1 - \frac{1}{k!}\right) \binom{n}{b} 
\implies \qquad f_{\pi_0^{\bq}}(\pi) 
\leq 
\left(\frac{1}{k!} + \d - \frac{\d}{k!} \right) \binom{n}{b} \leq (1 + \d k!) \frac{1}{k!} \binom{n}{b} 
\stackrel{\text{
(\ref{eqn:delzet})}}{=}    
(1 + \mu) \frac{1}{k!} \binom{n}{b}.   
\end{multline*}  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%    Section 3 : Proof of Prop               %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Proof of Proposition~\ref{prop:bestposs}}   
Fix $k \geq 2$, $b \geq 1$, and 
$\pi_0 = (a_1, \dots, a_k) \in S_k$.   
Fix any sequence $\pi_0^*$, as in~(\ref{eqn:genform}), 
with $b$ blocks.  
If $\pi_0^*$ has a block of length at least 3, 
then 
let $0 < c = c(\pi_0^*)  < 1$ be the constant guaranteed by Theorem~\ref{thm:avoidance}, 
and set $\gamma_0 = c/2$.  
Otherwise, set $\gamma_0 = 1/2$.  
Fix $0 < \g < \g_0$, and write $g = \lfloor 1/\gamma \rfloor$, where we note that $\gamma < 1/2$ implies $g \geq 2$.  
For a sufficiently large integer $n$ which is divisible by $g$, 
we guarantee at least $\gamma ^n n!$ permutations $\pi \in S_n$ with $f_{\pi_0^*}(\pi) < \gamma n^b$.  



Our proof is based on cases, 
depending on the structure of the sequence $\pi_0^*$.  
Clearly, we get the following case entirely for free 
on account of 
Theorem~\ref{thm:avoidance}.

\medskip



\noindent {\bf Case 0} ($\pi_0^*$ has a block of length at least 3)$\boldsymbol{.}$  
Theorem~\ref{thm:avoidance} guarantees at least $c^n n! > \g^n n!$ 
permutations $\pi \in S_n$ with $f_{\pi_0^*}(\pi) = 0 < \g n^b$. 

\medskip

To handle all other cases, we require the following considerations.  
For $0 \leq s \leq g -1$, write 
$I_s = [s(n/g) + 1, (s+1) (n/g) ]$
and 
$R_s = \{m \in [n]: m \equiv s \; ({\rm mod}\  g)\}$.  
Then $[n] = I_0 \cup \dots \cup I_{g-1}$ and $[n] = R_0 \cup \dots \cup R_{g-1}$ are partitions of $[n]$
into parts of common size $n/g$.  
Consider the following four classes of permutations:
\begin{eqnarray*}  
S_{n,1}  & = &  
\left\{ \pi \in S_n: \pi (I_s) = I_s, \ \forall \, 0 \leq s \leq g-1
\right\}, \\  
S_{n,2}  & = &  
\left\{ \pi \in S_n: \pi (I_s) = I_{g-1 -s}, \ \forall \, 0 \leq s \leq g-1
\right\}, \\
S_{n,3}  & = &  
\left\{ \pi \in S_n: \pi (R_s) = I_{g-s}, \ \forall \, 0 \leq s \leq g-1
\right\}   \qquad \text{(take $I_g = I_0$)},   
\\
S_{n,4}  & = &  
\left\{ \pi \in S_n: \pi (R_s) = I_{s-1}, \ \forall \, 0 \leq s \leq g-1
\right\}  \qquad \text{(take $I_{-1} = I_{g-1}$)}.  
\end{eqnarray*}  
Clearly, $|S_{n,1}| = |S_{n,2}| = |S_{n,3}| = |S_{n,4}| = ((n/g)!)^g$, 
where 
by Stirling's formula, 
$$ 
\left( \left(\frac{n}{g}\right)! \right)^g 
> 
\frac{1}{2} \left(\sqrt{ 2\pi (n/g)} \left(\frac{n}{eg} \right)^{(n/g)} \right)^g
> 
\frac{\sqrt{\g}}{2} 
(2 \pi \g n)^{\tfrac{g-1}{2}}  
\times 
\g^n 
\sqrt{2\pi n} \left(\frac{n}{e}\right)^n  
> 
\g ^n n!.  
$$
We mention, in advance, that in the following four cases below, Case $i$ will be handled by the family $S_{n,i}$, for $1 \leq i \leq 4$.
We also mention that 
Cases 1 and 2 are not always disjoint from Case~0, nor are they always disjoint from each other.  
(It seemed easiest to preserve generality in the cases.)  



We now consider when $\pi_0^*$ has $b \geq 2$ blocks.  
In particular, suppose $a_i = \pi_0(i)$ and $a_j = \pi_0(j)$, $1 \leq i < j \leq k$, belong to blocks 
$A_{i'}$ and $A_{j'}$, respectively, where $A_{i'} \neq A_{j'}$.

\medskip


\noindent {\bf Case 1} ($b \geq 2$, $a_i > a_j$)$\boldsymbol{.}$  
Fix $\pi \in S_{n,1}$, 
and consider an occurence $1 \leq \l_1 < \dots < \l_k \leq n$ of the generalized pattern $\pi_0^*$ in $\pi$.  
Consider the terms $\l_i < \l_j$.  
From~(\ref{eqn:patterprop}), 
since $\pi_0(i) = a_i > a_j = \pi_0(j)$, we have $\pi(\l_i) > \pi(\l_j)$.  
We therefore claim that, 
for some $1\leq s \leq g$, we have $\l_i, \l_j \in I_s$.  Indeed, if $\l_i \in I_{s_i}$ and $\l_j \in I_{s_j}$ for some $s_i < s_j$, then 
$\pi (\l_i) < \pi (\l_j)$ on account of $\pi \in S_{n,1}$, a contradiction.  
We also recall  
from~(\ref{eqn:genform}) 
and~(\ref{eqn:genform'}), 
that 
$\l_i$ belongs to block $L_{i'}$
and 
$\l_j$ belongs to block $L_{j'}$  
(since $a_i$ belongs to block $A_{i'}$ and 
$a_j$ belongs to block $A_{j'}$).  
Finally, 
recall
from~(\ref{eqn:genform'}) that $L_{i'}$ begins with $\hat{\l}_{i'}$ and $L_{j'}$ begins with $\hat{\l}_{j'}$.  Then, since 
$\l_i, \l_j \in I_s$, we have 
that $\hat{\l}_{j'} \in I_s$ and 
$\hat{\l}_{i'} \in I_{s - 1} \cup I_s$.  
(If $\hat{\l}_{i'} \in I_{s-1}$, it occurs very near the right boundary.)  
Clearly, there are at most $|I_s| = n/g$ choices for $\hat{\l}_{j'}$.
It is easy to check that there are fewer than $n/g$ choices for $\hat{\l}_{i'}$.  
Clearly, there are 
at most $n^{b-2}$ choices for any remaining $\hat{\l}_1, \dots, \hat{\l}_b$ 
in~(\ref{eqn:genform'}).  
Thus, 
$f_{\pi_0^*}(\pi) <  
n^{b-2} 
\sum_{s =1}^g 
(n/g)^2 
\leq 
\g n^b$.

\medskip


\noindent {\bf Case 2} ($b \geq 2$, $a_i < a_j$)$\boldsymbol{.}$    
Fix $\pi \in S_{n,2}$.  
All details of Case~1 are repeated identically save the following:  Now, $\pi (\l_i) < \pi (\l_j)$, which 
similarly implies that 
$\l_i, \l_j \in I_s$ for some $1\leq s \leq g$.  Indeed, 
$\l_i \in I_{s_i}$ and $\l_j \in I_{s_j}$ for some $s_i < s_j$ would imply 
$\pi (\l_i) > \pi (\l_j)$, on account of $\pi \in S_{n,2}$.

\medskip


The only cases in the proof of Proposition~\ref{prop:bestposs} 
not covered by Cases~1 and~2 
involve generalized patterns $\pi_0^*$ with $b=1$ block.  
(These are relatively rare, since there are only $k!$ such, while there are $2^{k-1} k!$ generalized patterns of $[k]$.)  
If $k \geq 3$ and $b = 1$, then $\pi_0^*$ has (is) a block of length at least 3, which is included in 
Case~0.  
If $k = 2$ and $b = 1$, then 
$\pi_0^* = 12$ or $\pi_0^* = 21$, where these cases are entirely symmetric.

\medskip

\noindent {\bf Case 3} ($\pi_0^* = 12$)$\boldsymbol{.}$  Fix $\pi \in S_{n,3}$, and consider an occurence $1 \leq \l < \l+1 \leq n$
of the generalized pattern $12$ in $\pi$.   
From~(\ref{eqn:patterprop}), we have that $\pi (\l) < \pi (\l+1)$.  As such, 
$\pi \in S_{n,3}$ implies that 
$\l \equiv 0$ (mod $g$).   Consequently, we have only $n/g \leq \g n$ choices for $\l$.

\medskip


\noindent {\bf Case 4} ($\pi_0^* = 21$)$\boldsymbol{.}$   Fix $\pi \in S_{n,4}$.  An occurence
$1\leq \l < \l+1 \leq n$ of $21$ in $\pi$ results in $\pi (\l) > \pi (\l+1)$.  Since $\pi \in S_{n,4}$, it must be that $\l \equiv 0$ (mod $g$), 
resulting in only $n/g \leq \g n$ choices for $\l$.

\section{Proof of 
Theorem~\ref{thm:12-34}}  
Consider the following concept, which has a clear resemblance to patterns.  
For $\pi \in S_n$, call a pair $1 < i < j < n$ a {\it stretching pair} if $\pi(i) < i < j < \pi (j)$.  
We shall use stretching pairs to prove Theorem~\ref{thm:12-34}, although 
stretching pairs 
are interesting in their own right, as we discuss in Section~\ref{sec:SharksecEJC}.  



%Indeed, a celebrated theorem of Sharvoksky~\cite{Shark}, from dynamical systems, asserts
%that the occurrence of a stretching pair within a periodic orbit of a continuous interval map implies what is called `turbulence'
%(see~\cite{,} for details).  As such, we will conclude this section with a corollary of Theorem~\ref{thm:gen} for stretching pairs 
%which strengthens a statement known about them in that literature.

\subsection{Stretching pairs and Theorem~\ref{thm:12-34}}    
We establish a few initial considerations.  
First, let $C_{n+1} \subset S_{n+1}$ denote the set of $(n+1)$-cycles of $S_{n+1}$, and write each $\pi \in C_{n+1}$ in cyclic notation:  
$\pi = (n+1 \ a_1 \ \dots \ a_n)$, i.e., $\pi (a_i) = a_{i+1}$ for $0 \leq i \leq n$ and $a_0 = a_{n+1} = n+1$.  
Consider the 
bijection $\phi: C_{n+1} \to S_n$ given by, for each 
$\pi = (n+1 \ a_1 \ \dots \ a_n) \in C_{n+1}$, 
\begin{equation}
\label{eqn:bijphi}
p = \phi(\pi) = (a_1, \dots, a_n), \text{ that is, } p(i) = a_i \text{ for each $1\leq i \leq n$}.   
\end{equation}  
We prove that 
\begin{multline}
\label{eqn:spand21-34}  
\text{{\it $\pi \in C_{n+1}$ admits a stretching pair $1\leq \pi (i) < i < j < \pi (j) \neq n+1$}} \\
\text{{\it if and only if $p = \phi (\pi)$ admits} 21--34 {\it or} 34--21 {\it as a generalized pattern.}}    
\end{multline}  
\noindent Before we prove~(\ref{eqn:spand21-34}), we note that 21--34 is not the same as 12--34, which Theorem~\ref{thm:12-34} considers.  However, 
Elizalde proved (see Proposition~5.3 from~\cite{El}) that 
\begin{equation}
\label{eqn:eli3}
\alpha_n (\text{12--34}) = \alpha_n (\text{21--34}),   
\end{equation}  
and so we shall be able to 
use~(\ref{eqn:spand21-34}).    






\begin{proof}[Proof of~(\ref{eqn:spand21-34})]  
Suppose first that $p = f(\pi) = (a_1, \dots, a_n) \in S_n$ admits $\21-34$ or $\34-21$ as a generalized pattern.  
If 
$a_k, a_{k+1}, a_{\l}, a_{\l+1}$ is a copy of $\21-34$, 
where $1 < k+1 < \l < n$, 
then 
$a_{k+1} < a_k < a_{\l} < a_{\l+1}$, and so   
$\pi (i) = a_{k+1} < a_k = i < j = a_{\l} < a_{\l+1} = \pi (j) \leq n$
is a stretching pair of $\pi$.  
If $a_k, a_{k+1}, a_{\l}, a_{\l+1}$ is a copy of $\34-21$, 
then $a_{\l +1} < a_{\l} < a_k < a_{k+1}$, and so   
$\pi(i) = a_{\l+1} < a_{\l} = i < j = a_k < a_{k+1} = \pi (j) \leq n$   
is a stretching pair of $\pi$.  
Assume now that $\pi = (n+1 \ a_1 \ \dots \ a_n) \in C_{n+1}$ admits a stretching pair $1 \leq \pi (i) < i < j < \pi (j) \leq n$.  
If
$\pi = (n+1 \ a_1 \ \dots \ i \ \pi (i) \ \dots \ j \ \pi(j) \ \dots \ a_n)$, 
then for some $1 < k + 1 < \l < n$, $p = f(\pi)$ has $i = a_k$, $\pi (i) = a_{k+1}$, $j = a_{\l}$ and $\pi(j) = a_{\l+1}$, where 
$a_{k+1} < a_k < a_{\l} < a_{\l +1}$ gives 
a copy of $\21-34$.  
If
$\pi = (n+1 \ a_1 \ \dots \ j \ \pi (j) \ \dots \ i \ \pi(i) \ \dots \ a_n)$, 
then for some $1 < k + 1 < \l < n$, $p = f(\pi)$ has $j = a_k$, $\pi (j) = a_{k+1}$, $i = a_{\l}$ and $\pi(i) = a_{\l+1}$, where 
$a_{\l+1} < a_{\l} < a_k < a_{k+1}$ gives   
a copy of $\34-21$.  
\end{proof}  




Now, 
define $S_{n+1}'$ to be the family of $\pi \in S_{n+1}$ satisfying $(n+1)/2 < \pi (i) \leq n+1$ if, and only if, $1 \leq i \leq (n+1)/2$.  
Clearly, 
$S_{n+1}'$ admits no stretching pairs.  
Set $C_{n+1}' = C_{n+1} \cap S_{n+1}'$, and observe   
that $C_{n+1}' \neq \emptyset$ if, and only if, $n$ is odd.   
As such, if $n$ is both odd and sufficiently large, Stirling's formula implies 
$$
\left|C_{n+1}'\right| = \frac{2}{n+1} \left( \left( \frac{n+1}{2} \right)! \right)^2 
\geq 
\left(\frac{1}{2} - o(1) \right)^n 
n!.  
$$
It then follows from~(\ref{eqn:spand21-34}) that 
$\phi (C_{n+1}')$
avoids $\21-34$ and $\34-21$, and so 
\begin{align*}
\a_n (\12-34) 
\stackrel{\text{(\ref{eqn:eli3})}}{=}  
\a_n(\21-34) 
&\geq 
| A_n (\21-34) \cap A_n (\34-21)| \\
&\geq \left| \phi(C_{n+1}') \right| = |C_{n+1}'| \geq \left(\frac{1}{2} - o(1) \right)^n  n!,    
\end{align*}
which proves Theorem~\ref{thm:12-34}.  



\subsection{A corollary of Theorem~\ref{thm:gen} for stretching pairs}  
\label{sec:SharksecEJC}  
Stretching pairs are motivated by considerations in dynamical systems.
Namely, the occurrence of a stretching pair within a periodic orbit of a continuous interval map implies what is called `turbulence'
(see~\cite{BC,Lund} for details).   
These considerations are closely related to the celebrated theorem of Sharkovsky~\cite{Shark}.
From this point of view, the second author~\cite{Lund} considered which $n$-cycles $\pi \in C_n$ admit stretching pairs, and proved that all but $o(n-1)!$ of them do.  
Theorem~\ref{thm:gen} allows us to sharpen this result in the following way.

\begin{cor}
\label{cor:sp}  
For all $\d > 0$, there exists $0 < c < 1$ so that for all sufficiently large integers $n$, all but 
$c^n (n-1)!$ cyclic permutations $\pi \in C_n$ admit $\tfrac{1}{12}\tbinom{n}{2} (1 \pm \d)$ stretching pairs.  
\end{cor}  

\begin{proof}[Proof of Corollary~\ref{cor:sp}]  
Let $\d > 0$ be given.  Set $k = 4$ and $\mu = \d / 2$, and let 
$0 < c_1 < 1$ be the constant guaranteed by Theorem~\ref{thm:gen}.  Define $c$ to be any constant
satisfying 
$c_1 < c < 1$, 
and let $n$ be sufficiently large.  
For an $n$-cycle $\pi \in C_n$, write $\sigma (\pi)$ for the number of stretching pairs of $\pi$, and write 
$\sigma'(\pi)$ for the number of stretching pairs $1 \leq \pi (i) < i < j < \pi (j) \neq n$.  Note that 
$\sigma' (\pi) \leq \sigma (\pi) \leq \sigma' (\pi) + n$, 
since if 
$1 \leq \pi (i) < i < j < \pi (j) = n$, then $j = \pi^{-1}(n)$ is fixed and there are at most $j-1 \leq n$ choices for $i$.    
Note, moreover,  
that it follows from~(\ref{eqn:spand21-34}) that, for $p = \phi (\pi) \in S_{n-1}$,   
$\sigma ' (\pi) = f_{\text{21--34}}(p) + f_{\text{34--21}}(p)$.  
Theorem~\ref{thm:gen} ensures that all but $2c_1^{n-1}(n-1)! < c^n (n-1)!$ permutations $p \in S_{n-1}$ satisfy 
$$
f_{\text{21-34}}(p) 
= 
(1 \pm \mu) \frac{1}{4!} \binom{n-1}{2} \quad \text{and} \quad 
f_{\text{34-21}}(p)  
= 
(1 \pm \mu) \frac{1}{4!} \binom{n-1}{2}.  
$$
For each such permutation $p \in S_{n-1}$,   
the corresponding $n$-cycle 
$\pi = \phi^{-1}(p) \in C_n$ satisfies 
\begin{align}
\sigma(\pi) &= 
(1 \pm \mu) \frac{1}{4!} \binom{n-1}{2} +   
(1 \pm \mu) \frac{1}{4!} \binom{n-1}{2}  \pm n \\
&=   
(1 \pm \mu \pm o(1)) \frac{1}{12} \binom{n}{2} = (1 \pm \d) \frac{1}{12}\binom{n}{2},   
\end{align}
which proves Corollary~\ref{cor:sp}.  
\end{proof}  






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%     Section 5 : Proof of Quasi Lemma       %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%                                            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Proof of Lemma~\ref{lem:gen}}  
\label{sec:lem:gen}  
Fix $\z > 0$ and integer $q \geq 1$.  
Define auxiliary constant 
\begin{equation}
\label{eqn:z0q}
\z_0 = \z/4.  
\end{equation}  
Define $s_0 = s_0(q, \z_0)$ to be the least integer $s$ for which 
\begin{equation}
\label{eqn:s0q}
(s)_q \geq (1 - 2\z_0) s^q.   
%s^q \leq (s)_q \frac{1}{1 - 2\z_0}.  
\end{equation}  
Let $s \geq s_0$ be given.  
Define 
\begin{equation}
\label{eqn:t0q}
t_0 = 
\left\lceil 
4q 8^q s^{2q}\z_0^{-2}    
%\frac{8q 4^q s^{q+1}}{\z_0^2}    
\right\rceil.   
\end{equation}  
Let integer $t \geq t_0$ be given.  Define 
\begin{equation}
\label{eqn:c0q}
c_0 = \frac{\z_0^2}{3qt2^{q+3}s^q}.  
\end{equation}  
Let $n$ be a sufficiently large integer, and   
fix $(\bi_0, j_0) \in ([s])_q \times [t]$.  
We prove 
\begin{equation}
\label{eqn:new13}
\text{all but $\exp \{ - 2 c_0 n\} n!$ permutations $\pi \in S_n$ are $(\bi_0, j_0, \z, q)$-typical w.r.t.~$(\bP_s, \bP_t)$.}  
\end{equation}
Applying~(\ref{eqn:new13}) to all $(\bi, j) \in ([s])_q \times [t]$ and noting 
$s^q t \exp \{-2 c_0 n\} < \exp\{-c_0 n\}$
yields Lemma~\ref{lem:gen}.  




We now outline our approach for proving~(\ref{eqn:new13})  
(and reduce the $\hat{\l}$ notation in~(\ref{eqn:Ebijpi}) to $\l$).    
Define equivalence relation $\sim$ on $E_{j_0}$:  
$\ell \sim \ell'  \iff  q \, | \, (\ell - \ell')$.   
Thus, for an integer $0 \leq r < q$, we may write 
\begin{equation}
\label{eqn:Ejr}
E_{j_0} ^{(r)} = \left\{ \ell \in E_{j_0}: \ell \sim (j_0-1) \left\lfloor \frac{n}{t} \right\rfloor + 1 + r \right\} 
\qquad \text{so that}  \qquad 
E_j = E_j^{(0)} \cup \dots \cup E_j^{(q-1)} 
\end{equation}
is a partition.  
A key observation for later in the proof (cf.~Claim~\ref{cl:gen}) 
will be that 
%whenever $\l, \l' \in E_j^{(r)}$ are distinct, then the sequences
%$(\l, \l+1, \dots, \l + q - 1)$ and $(\l', \l' + 1, \dots, \l' + q - 1)$ are disjoint, that is, 
\begin{equation}
\label{eqn:keyobs}
[\l, \l + 1 - q] \cap [\l', \l' + q - 1] = \emptyset \quad \text{whenever $\l \neq \l' \in E_j^{(r)}$.}  
\end{equation}  
For some final notation, we shall write, for a permutation $\pi \in S_n$, 
\begin{equation}
\label{eqn:Ejrpi}
E_{\bi_0 j_0}^{(r)} (\pi) = 
E_{\bi_0 j_0} (\pi) \cap E_{j_0}^{(r)} \qquad \text{so that} \qquad 
E_{\bi_0 j_0}(\pi) = 
E_{\bi_0 j_0}^{(0)}(\pi) 
\cup 
\dots \cup
E_{\bi_0 j_0}^{(q-1)}(\pi) 
\end{equation}
is a partition.  
We shall prove that, 
for a fixed $0 \leq r < q$, 
\begin{equation}
\label{eqn:new13'}  
\text{{\it all but $\exp \{ - 3 c_0 n\} n!$ permutations $\pi \in S_n$ satisfy that }} 
\left|E_{\bi_0j_0}^{(r)}(\pi) \right|
\geq 
(1 - \z) \frac{1}{q(s)_q} \left|E_{j_0}\right|.   
\end{equation}
Note that~(\ref{eqn:new13'})  
implies~(\ref{eqn:new13})  
since 
then 
all but 
$q \exp\{ - 3 c_0 n \} n! < \exp \{-2 c_0 n\} n!$ many $\pi \in S_n$ satisfy 
$$
\left| E_{\bi_0j_0}(\pi) \right| 
\stackrel{\text{(\ref{eqn:Ejrpi})}}{=}  
\sum_{r=0}^{q-1} 
\left|E_{\bi_0j_0}^{(r)}(\pi) \right|
\geq
(1 - \z) \frac{1}{(s)_q}
\left|E_{j_0} \right|.   
$$


To prove~(\ref{eqn:new13'}), 
let $\pi \in S_n$ be chosen uniformly at random.  Then, 
$Y = Y^{(r)}_{\bi_0j_0} = |E_{\bi_0j_0}^{(r)}(\pi)|$ is a random variable
whose mean we evaluate.  To that end, 
recall 
from~(\ref{eqn:Ebijpi}) 
that for an element $\l \in E_{j_0}$
to be an element of $E_{\bi_0 j_0}(\pi)$, we require that $\l \leq j_0 \lfloor n/t \rfloor - q + 1$, 
where we will 
write $n_t = \lfloor n/t \rfloor$ and $n_s = \lfloor n/s \rfloor$.  
As such, 
delete the last $q-1$ elements from $E_{j_0}$, and write 
\begin{multline}
\label{eqn:tildeEj}
\tilde{E}_{j_0} 
\stackrel{\text{def}}{=}  
\big[ (j_0 - 1) n_t + 1,   \ 
j_0 n_t - q + 1 \big], \quad  
\tilde{E}_{j_0}^{(r)} = E_{j_0}^{(r)} \cap \tilde{E}_{j_0}, \\
\text{and} \quad n_{t,q} \stackrel{\text{def}}{=} \left|\tilde{E}_{j_0}^{(r)}\right| = 
\left\lfloor \frac{n_t - q + 1}{q} \right\rfloor
= 
\left\lfloor \frac{n_t + 1}{q} \right\rfloor
- 1.  
\end{multline}  
Now, 
for $\l \in \tilde{E}_{j_0}^{(r)}$, define
indicator random variable $Y_{\l}$ by (cf.~$\bi_0 = (i_1, \dots, i_q)$)  
$$
Y_{\l} = 
\left\{
\begin{array}{cc}
1 & \text{if $\pi(\l + m - 1) \in I_{i_m}$ $\forall$ $m \in [q]$,}   \\
0 & \text{otherwise,} 
\end{array}
\right.
\qquad \implies \qquad 
Y = \sum \left\{ Y_{\l}: \l \in \tEj0r \right\}  
$$
\begin{equation}
\label{eqn:EYl}  
\text{so that} \quad 
\bbE [Y_{\l}] = \frac{(n-q)! \prod_{m=1}^q |I_{i_m}|}{n!}  = 
\frac{n_s^q}{(n)_q} 
 \implies 
\bbE[Y] = 
\frac{|\tEj0r| \prod_{m=1}^q |I_{i_m}|}{(n)_q}  = 
\frac{n_s^q n_{t,q}}{(n)_q}.  
\end{equation}  
Following the method of Bernstein for the Chernoff inequality (cf.~\cite{JLR}), 
for $u = \log (1 - \z_0) = \log_e(1 - \z_0)$, the Markov inequality implies 
\begin{multline}  
\label{eqn:BernstlowupY} 
\bbP [Y \leq \bbE[Y] (1 - \z_0)] = 
\bbP \left[e^{uY} \geq \exp\left\{u \bbE[Y] (1 - \z_0)\right\} \right]  \\
\leq 
\exp\left\{- u \bbE [Y] (1 - \z_0) \right\}  \bbE \left[e^{uY} \right]    
\stackrel{\text{(\ref{eqn:EYl})}}{=}    
\exp\left\{ - u 
\frac{n_s^qn_{t,q}}{(n)_q} (1 - \z_0) \right\} \bbE\left[e^{uY}\right].  
\end{multline}  
While we do not have mutual independence among the $Y_{\l}$'s, we will prove the following.  
\begin{claim}
\label{cl:gen}
\begin{multline*}  
\bbE \left[e^{uY}\right] = 
\bbE \left[ \prod_{\l \in \tEj0r} e^{uY_{\l}} \right]  
\leq 
\left(1 + q\frac{(4s)^q}{t} \right)^{n_{t,q}} 
\prod_{\l \in \tEj0r} 
\bbE\left[e^{uY_{\l}}\right]  \\
\stackrel{\text{\rm (\ref{eqn:EYl})}}{=}    
\left(
\left(1 + q\frac{(4s)^q}{t}\right)
\left(
1 + 
\frac{n_s^q}{(n)_q}
\left(e^u - 1\right) 
\right)
\right)^{n_{t,q}}
\leq 
\exp\left\{ n_{t,q} \left(q\frac{(4s)^q}{t}  + \frac{n_s^q}{(n)_q} \left(e^u - 1\right)
\right)
\right\}.  
\end{multline*}  
\end{claim}  
\noindent  We shall defer the proof of Claim~\ref{cl:gen} in order first to finish the proof of~(\ref{eqn:new13'}).    

Applying Claim~\ref{cl:gen} 
to~(\ref{eqn:BernstlowupY}), together with the Taylor series bound $-u (1 - \z_0)  +  e^u - 1  \leq - \z_0^2 / 2,$  %(which follows from the Taylor series of $\log (1 - \z_0)$), 
\begin{align*}  
\bbP [Y \leq \bbE[Y] (1 - \z_0)] \leq 
\exp\left\{
n_{t,q} \left(
q\frac{(4s)^q}{t} + 
\frac{n_s^q}{(n)_q}
\Big( - u (1 - \z_0) + e^u - 1 \Big) 
\right)  
\right\}  \\
\leq 
\exp
\left\{ 
n_{t,q} \left( 
q\frac{(4s)^q}{t}  
- \frac{\z_0^2 n_s^q}{2 (n)_q}\right)\right\} 
\leq 
\exp
\left\{ 
n_{t,q} \left( 
q\frac{(4s)^q}{t}  
- \frac{\z_0^2}{2}
\left(\frac{n_s}{n}\right)^q 
\right)\right\} \\
\leq 
\exp
\left\{ 
n_{t,q} \left( 
q\frac{(4s)^q}{t}  
- \frac{\z_0^2}{2^{q+1} s^q}
\right)\right\}
\qquad 
\text{(since $n_s = \lfloor n/s \rfloor \geq n/(2s)$)} \\  
\stackrel{\text{
(\ref{eqn:t0q})}}{\leq}  
\exp
\left\{ 
n_{t,q} \left( 
- \frac{\z_0^2}{2^{q+2} s^q}
\right)\right\}
\leq 
\exp
\left\{ 
- \left( 
\frac{\z_0^2}{qt 2^{q+3} s^q}\right) n
\right\}
\stackrel{\text{(\ref{eqn:c0q})}}{=}  
\exp \left\{ - 3 c_0 n \right\}.  
\end{align*}
(The last inequality above follows from $n_{t,q} = \lfloor (n_t + 1) / q \rfloor - 1 \geq n/(2tq)$.)
In other words, with probability $1 - \exp \{ - 3 c_0 n\}$, the randomly chosen permutation $\pi \in S_n$ satisfies 

\begin{align*}
Y &= \left|E_{\bi_0j_0}^{(r)}(\pi) \right|
 \geq 
\bbE [Y] (1 - \z_0) 
\stackrel{\text{(\ref{eqn:EYl})}}{=}    
\frac{n_s^q n_{t,q}}{(n)_q} (1 - \z_0)  
\stackrel{\text{
(\ref{eqn:tildeEj})}}{=}  
(1 - \z_0) (1 - o(1)) \frac{1}{qs^q} \left\lfloor \frac{n}{t} \right\rfloor  \\
& \stackrel{\text{(\ref{eqn:s0q})}}{\geq}  
(1 - 2\z_0)^2 
\frac{1}{q(s)_q} \left\lfloor \frac{n}{t} \right\rfloor 
\geq 
(1 - 4 \z_0)  
\frac{1}{q(s)_q} \left\lfloor \frac{n}{t} \right\rfloor 
\stackrel{\text{(\ref{eqn:z0q})}}{=} 
(1 - \z) 
\frac{1}{q(s)_q} \left\lfloor \frac{n}{t} \right\rfloor.   
\end{align*}

%This 
%proves~(\ref{eqn:new13'}), and hence, Lemma~\ref{lem:gen}.      









\subsection{Proof of Claim~\ref{cl:gen}}  
Write $\tEj0r$ as $\l_1 < \dots < \l_{n_{t,q}}$ 
(cf.~(\ref{eqn:tildeEj})) so that  
\begin{equation}
\label{eqn:new10}
\bbE\left[\prod_{\l \in \tEj0r} e^{u Y_\l} \right] 
= 
\sum_{(y_1, \dots, y_{n_{t,q}}) \in \{0, 1\}^{n_{t,q}}}
\bbP
\left[
\bigwedge_{i=1}^{n_{t,q}} Y_{\l_i} = y_i \right]
\prod_{i =1}^{n_{t,q}} e^{u y_i}.
\end{equation}
Fix $(y_1, \dots, y_{n_{t,q}}) \in \{0, 1\}^{n_{t,q}}$ so that 
$$
\bbP
\left[
\bigwedge_{i=1}^{n_{t,q}} Y_{\l_i} = y_i \right]
= 
\bbP
\left[
Y_{\l_{n_{t,q}}} = y_{n_{t,q}} \Big| 
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right] 
\cdot 
\bbP
\left[
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right].
$$
We claim that 
\begin{equation}
\label{eqn:wedgeclaimr}  
\bbP
\left[
Y_{\l_{n_{t,q}}} = y_{n_{t,q}} \Big| 
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right] 
= 
\bbP
\left[Y_{\l_{n_{t,q}}} = y_{n_{t,q}} \right] 
\left(1 \pm 
q\frac{(4s)^q}{t} 
\right).    
\end{equation} 
If so, iteratively 
applying~(\ref{eqn:wedgeclaimr})   
to~(\ref{eqn:new10}) 
yields Claim~\ref{cl:gen}.   











To see~(\ref{eqn:wedgeclaimr}),    
recall 
the observation in~(\ref{eqn:keyobs}).  Thus, 
%that the intervals 
%$[\l_1, \l_1 + q - 1], \dots, [\l_{n_{t_q}}, \l_{n_{t_q}} + q - 1]$  
%are pairwise disjoint.  
\begin{align*}
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1 \Big| 
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right] 
&\leq 
\frac{(n - qn_{t,q})! \prod_{m=1}^q |I_{i_m}|}{(n - q(n_{t,q} -1))!}  
= 
\frac{n_s^q}{(n - q n_{t,q} + q)_q}
\text{,  and}\\
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \Big| 
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right] 
&\geq 
\frac{(n - qn_{t,q})! 
\prod_{m=1}^q (|I_{i_m}| - q(n_{t,q} - 1))}{(n - q (n_{t,q} - 1))!} \\
&= 
\frac{(n_s - qn_{t,q} + q)^q}{(n - qn_{t,q} + q)_q}.  
\end{align*}
For the upper bound, we
use~(\ref{eqn:EYl})   
(and $q n_{t,q} \leq n_t$
(cf.~(\ref{eqn:tildeEj}))  
to infer 
\begin{multline*}  
\frac{n_s^q}{(n - q n_{t,q} + q)_q}
= 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\cdot \frac{(n)_q}{(n - qn_{t,q} + q)_q}
\leq 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(
\frac{n}{n - n_t}\right)^q    \\
\leq 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(1 - \frac{1}{t}\right)^{-q}  
\leq 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(1 + \frac{2}{t}\right)^{q}  
\leq 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(1 + q \frac{4^{q}}{t}\right).  
\end{multline*}  
For the lower bound, we similarly infer 
\begin{align*}
\frac{(n_s - qn_{t,q} + q)^q}{(n - qn_{t,q} + q)_q}
&\geq 
\frac{(n_s - qn_{t,q})^q}{(n)_q}
= 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(
\frac{n_s - q n_{t,q}}{n_s}\right)^q \\  
&\geq 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(\frac{n_s - n_t}{n_s}\right)^q 
\geq 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(1 - 2\frac{s}{t}\right)^q \\
&\geq 
\bbP  
\left[
Y_{\l_{n_{t,q}}} = 1  \right]  
\left(1 - q \frac{(4s)^q}{t}\right).  
\end{align*}  
This proves~(\ref{eqn:wedgeclaimr}) when $y_{n,t} = 1$.  Otherwise, 
(using 
$\bbP
[Y_{\l_{n_{t,q}}} = 1]  
\leq 1/2 \leq 
\bbP
[
Y_{\l_{n_{t,q}}} = 0]$)     
we have
\begin{align*}
\bbP
\left[
Y_{\l_{n_{t,q}}} = 0  \Big| 
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right] 
&= 
1 - 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 1  \Big| 
\bigwedge_{j=1}^{n_{t,q}-1} Y_{\l_j} = y_j \right] \\
&= 
\bbP
\left[
Y_{\l_{n_{t,q}}} = 0  \right]  
\left(1 \pm q \frac{(4s)^q}{t} \right), 
\end{align*}
where
we used   
$\bbP
[Y_{\l_{n_{t,q}}} = 1]  
\leq 1/2 \leq 
\bbP
[
Y_{\l_{n_{t,q}}} = 0]$.    


\subsection*{Acknowledgements}
We would like to thank the Referee for their careful reading of our work, and for helpful suggestions leading to an improved
exposition.





%\bibliographystyle{amsplain}

\begin{thebibliography}{11}


\bibitem{AF}  Alon, N., Friedgut, E., {\it On the number of permutations
avoiding a given pattern}, J.~Combin.~Theory, Ser.~A {\bf 89}
(2000), no.~1, 133--140.  

\bibitem{BS}  Babson, E., Steingr\'{\i}msson, E., {\it Generalized permutation
patterns and a classificiation of the Mahonian statistics}, 
S\'em.~Lothar.~Combin.~{\bf 44}, Art.~B44b (2000).  


\bibitem{BC}
Block, L., Coppel, W., \emph{Dynamics in One Dimension}, Lecture Notes in Mathematics, Vol 1513, Springer-Verlag, Berlin, 1992.


\bibitem{Bona1}  B\'ona, M., {\it Exact enumeration of 1342-avoiding
permutations: A close link with labeled trees and planar maps}, 
J.~Combin.~Theory Ser.~A {\bf 80} (1997), 257--272.  

\bibitem{Bona2}  B\'ona, M., {\it The solution of a conjecture of 
Stanley and Wilf for all layered patterns}, J.~Combin.~Theory Ser.~A
{\bf 85} (1999), no.~1, 96--104.  

\bibitem{Cl}  Claesson, A., {\it Generalized pattern avoidance}, European J.~Combin.~{\bf 22}
(2001), 961--973. 

\bibitem{Cooper}  Cooper, J., {\it Quasirandom permutations}, J.~Combin.~Theory.~Ser.~A {\bf 106} (2004), 123--142.  

\bibitem{El}  Elizalde, S., {\it Asymptotic enumeration of permutations
avoiding generalized patterns}, Adv.~in Appl.~Math.~{\bf 36} (2006), 
2851--2869.    

\bibitem{ElN}  Elizalde, S., Noy, M., {\it Consecutive patterns in 
permutations}, 
Adv.~in Appl.~Math.~{\bf 30} (2003), 110--125.  

\bibitem{JLR}
Janson, S., \L uczak, T., Ruci\'nski, A., 
{\it Random Graphs}, Wiley, New York
(2000).  

\bibitem{K}
Klazar, M., {\it The F\"uredi-Hajnal conjecture implies the Stanley-Wilf
conjecture}, Formal Power Series and Algebraic Combinatorics
(D.~Krob, A.A.~Mikhalev, and A.V.~Mikhalev, eds.), Springer, Berlin, 
2000, 250--255.  


\bibitem{Lund}
Lundberg, E., 
{\it Almost all orbit types imply period-3}, Topol.~and its Appl., {\bf 154}, (2007), 2741--2744.   


\bibitem{MT}
Marcus, A., Tardos, G., {\it Excluded permutation matrices and the
Stanely-Wilf conjecture}, J.~Combin.~Theory Ser.~A {\bf 107}
(2004), no.~1, 153--160.  


\bibitem{Shark}
Sharkovsky, A.N., \emph{Coexistence of cycles of a continuous map of a line into itself}, Ukrain.
Mat. Zh. 16 (1964), 61-71 (Russian); English translation, Internat. J. Bifur. Chaos Appl.
Sci. Engrg. 5 (1995), 1263--1273.



\end{thebibliography}

\end{document}

















